软件设计师培训03

软件工程师培训

软件设计师培训——第三讲王宇 东北大学网络中心

软件工程师培训

2011年3月7日

提纲程序语言基础知识 程序语言基础知识相关试题

王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识了解程序语言的种类、特点和适用范围，掌握 汇编、编译、解释系统的基本原理，以及程序 语言的数据结构和控制结构。 各种程序设计语言的主要特点和适用情况。 计算机只能理解和执行机器语言。程序语言要 在计算机上运行，必须有一个程序，使机器能 够理解用程序语言书写的用户程序，这就是所 谓的语言处理程序。它可以分为两大类：解释 程序和翻译程序。王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识(续)常用程序语言介绍Fortran是第一个被广泛用于科学计算的高级语言。 Algol是另一个早期研制出来的高级语言。它有严格 的文法规则，用巴科斯范式BNF来描述语言的文法。 Algol是一个分程序结构的语言。 Cobal是一种面向事务处理的高级语言。 Pascal语言提供的为数不多而又相当紧凑的机制使 得这个语言具有相当强的表达能力，是第一个完整 的结构化程序设计语言。王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识(续)C是一种通用程序设计语言。 面向对象的C++ 逻辑型语言Prolog 函数型语言LISP

解释程序和翻译程序解释：同时输入程序和数据执行 翻译：把程序设计语言降低到机器水平汇编程序：源程序为汇编程序 编译程序：源程序为高级语言

翻译方式程序执行效率高，解释方式简单移植性好 JAVA语言，先编译后解释王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识(续)编译程序的功能是把某高级语言的源程序翻译成与之 等价的低级语言(汇编语言或机器语言)的目标程序。其 过程很复杂，可分成6个阶段：词法分析阶段。该阶段的任务是从左到右逐个字符的读入源 程序，识别出一个个的单词符号。词法分析所依据的是语言 的词法规则，即描述单词结构的规则。词法规则可用3型文法 (正规文法)或正规式来描述，有限自动机能识别正规文法 所定义的语言和正规式所表示的集合。 语法分析阶段。该阶段任务是在词法分析的基础上将单词符 号序列分解成各类语法单元。语法分析所依据的是语言的语 法规则，即描述程序结构的规则。语法分析有自顶向下分析 (递归子程序分析法LL1)和自底向上分析(LR和算符优先分 析)两大类。王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识(续)语义分析阶段。审查源程序有无语义错误，为代码

生成阶段收集类型信息。 中间代码生成阶段。所谓“中间代码”是一种简单、 含义明确的记号系统。 代码优化阶段。对前阶段产生的中间代码进行变换 或进行改造，目的是使生成的目标代码更为高级， 即省时间和省空间。 目标代码生成阶段。是把中间代码变换成特定机器 上的绝对指令代码或可重定位的指令代码或汇编指 令代码。这是编译的最后阶段，它的工作与硬件系 统的结构和指令的含义有关。王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识(续)词法分析和语法分析本质上都是对源程序的 结构进行分析。而语义分析和中间代码生成 所依据的是语言的语义规则，一般采用语法 指导翻译和中间代码生成。 自底向上分析法采用一个后进先出栈的数据 结构，是移进-规约过程(找出句柄)。 自顶向下分析法必须改写文法，采用预测分 析法，要消除左递归和提取公共左因子。王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识(续)文法和语言形式描述文法G是一个四元组，可表示为G(VT, VN, S, P)。VT是一个非空有限集，每个元素称为终结符。 VN是一个非空有限集，每个元素称为非终结符。 P是一个非终结符，称为开始符号；它至少要在一条产生式中作为左部出现。 S是一个产生式集合(有限)。王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识(续)文法根据对产生式施加不同的限制，分成4种类型，即0型、1型、2型和3型。

文法类型 0型(PSG) 1型(CSG) 2型(CFG) 3型

文法名称 短语结构文法 上下文有关文法 上下文无关文法 右线性文法(正规文法)

语言名称 递归可枚举语言 上下文有关语言 上下文无关语言 有限状态文法

对应的自动机 图灵机(Turing) 线性界限自动机 非确定下推自动机 有限状态自动机

王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识(续)通过对产生式施加不同的限制，Chomsky将文法分为四 种类型： 0型文法：对任一产生式α→β,都有α∈(VN∪VT) +,β∈(V ∪V )* N T 1型文法：对任一产生式α→β,都有|β|≥|α|, 仅仅 S→ε除外 2型文法：对任一产生式α→β,都有α∈VN,β∈ (VN∪VT)* 3型文法：任一产生式α→β的形式都为A→aB或 A→a(右线性)A→Ba或A→a(左线性),其中A∈VN, B∈VN,a∈VT王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识(续)数据类型是一组数据对象及创建和操纵它们的 操作集合所组成的类。数据是程序操作的对象，具有名称、类型、存储类、 作用域和生存期等属性

,使用时要为它分配内存空 间。 数据名称是用户指定的标识符：类型说明数据占用 内存的大小和存放形式，存储类说明数据在内存中 的位置和生存期；作用域说明数据可以使用的范围； 生存期说明数据占用内存的时间。王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识(续)分类按数据的作用域大小，可分为全局量和局部量 按生存期可分为自动生存期、静态生存期和动态生成期 按程序运行时数据的值是否能改变可分为常量和变量 数据按其构造方式又可分为基本类型和派生类型

数据按类型可分为4种：Void、标量(Scalar)、函数 和聚合(Aggregate)标量又可分为算术、枚举和指针 聚合类型可分为数组、结构体和共用体

王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识相关试题下图为一确定有限自动机的状态转换图，与该自动机等价的正 规表达式是__(12)__,图中的__(13)__是可以合并的状 态。C, B (12)A.(a|b)*bb(a*b*)* B.(a|b)*bba*|b* C.(a*b*)bb(a|b)* D.(a*|b*)*bb(a*|b*) (13)A.0和1 B.2和3 C.1和2 D.0和3

王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识相关试题(续)简化该有限自动机DFA,为以下划分： ({0},{1},{2,3})

王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识相关试题(续)编译的优化工作对于下面程序段构造的控制流程图有__(15)__ 个基本块。DA:=0 j:=100 i:=1 loop1: B:=j+1 C:=B+I A:=A+C if i=100 goto loop2 i:=i+1 Goto loop1 loop2: write A halt (15)A.1 B.2 C.3 D. 4王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识相关试题(续)基本块划分选择语句入口程序的第一个语句 能由条件转移语句或无条件转移语句转移到的语句 紧跟在条件转移语句后边的语句

构造所属的基本块入口到另一个入口之间 入口到一个转移语句之间 入口到停转移halt之间

检查无法到达的语句未纳入基本块中的语句，是不会被执行到的语句王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识相关试题(续)A:=0 入口 j:=100 i:=1 loop1: B:=j+1 入口 C:=B+I A:=A+C if i=100 goto loop2 i:=i+1 入口 Goto loop1 loop2: write A 入口 halt王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识相关试题(续)

答案：D S -> xSx -> x(xSx)x -> x2Sx2 ……

王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识相关试题(续)已知文法G[S]:S→A0|Bl,A→S1|1, B→S0|0;该文法属于乔姆斯基定义的 __(12)__文法，它不能产生串__(13)__。 D, A (12) A. 0型 B. 1型 C. 2型 D. 3型 (13) A. 0011 B. 1010 C.

1001 D. 0101

王宇 东北大学网络中心 wangy@

软件工程师培训

2011年3月7日

程序语言基础知识相关试题(续)

王宇 东北大学网络中心 wangy@

本文来源：https://www.bwwdw.com/article/t5be.html