程序语言基础知识

 

2.2.1  主 要知识点

了解程序语言的种类、特点和适用范围，掌握汇编、编译、解释系统的 基本原理，以及程序语言的数据结构和控制结构。特别是编译系统形式的基础知识，应当下功夫掌握。

2.2.1.1  程 序语言概述

低级语言又称面向机器语言，它是特定的计算机系统所固有的语言。用 机器语言编制出来的, 程序可读性很差，程序员难以修改和维护，于是人们考虑改用助记符号来表示机器 指令中操作码和操作数，这就是汇编语言。汇编语言仍然是一种和计算机的机器语言十分接近的语言，它的书写格式在很大程度上取决于特定计算机的机器指令。它 是一种低级语言，这对于人们抽象思维和交流十分不便。在这个基础上，高级语言就发展起来了。目前已有许多流行较广的高级语言，如Fortra 、Cobol 、PascalC 、和C++ 等。这类语言与人们的自然语言 比较接近，大大提高了程序设计的效率，便于人们进行交流。

计算机只能理解和执行机器语言。程序语言要在计算机上运行，必须有 一个程序，使机器能够理解用程序语言书写的用户程序，这就是所谓的语言处理程序。它可以分为两大类：解释程序和翻译程序。

2.2.1.2  程 序语言基础知识

程序语言种类繁多，在应用上各有不同的侧重面。

Fortran 是 第一个被广泛用于科学计算的高级语言。

Algol 是 另一个早期研制出来的高级语言。它有严格的文法规则，用巴科斯范式BNF 来描述语言的文法。Algol 是一个分程序结构的语言。

Cobal 是 一种面向事务处理的高级语言。

Pascal 语 言提供的为数不多而又相当紧凑的机制使得这个语言具有相当强的表达能力。

C 是一种通 用程序设计语言。C 作为一种较低级的语言，提供了指针和地址操作的功能。C 提供书写结构良好的程序所需的控制结构。C 与UNIX 操作系统紧密相关，UNIX 操作系统及其上的 许多软件都是C 编写的。

还有几种特殊而又重要的程序语言：

(1) 面向对象的 C++
C++ 是在C 语言的基础上发展起来的 与C 兼容的语言。主要增加了类功能，成为面向对象的程序设计语言。面向对象程序语言至少包含以下几 个重要概念：

①对象是人们要进行研究的任何事物，它包括状态( 用数据来描述) 和操作( 用来改变对象的状态) 两方面。面对对象语言把状态和操 作封装于对象体之中，并提供一种访问机制，使对象状态的具体表示和操作的具体实现都是隐蔽的。

②类是面向对象语言必需提供的用户定义的数据的类型，它将具有相同 状态、操作和访问机制的多个对象抽象成一个对象类。在定义了类以后，属于这种类的一个对象叫作类实例或类对象。

③继承是面向对象语言的另一个必备要素。类与类之间可以组成继承层 次，一个类的定义( 称为子类) 可以定义在另 一个已定义类( 称为父类) 的基础上。子类可 以继在父类中的属性和
操作，也可以定义自己的属性和操作。

(2) 逻辑 型语言Prolog

逻辑型语言是一类以形式逻辑为基础的语言。Prolog 是这类语言的代表。Prolog 建立在关系 理论和一阶谓词理论基础上，具有和传统的命令型程序设计完全不同的风格。Prolog 程序由一些称 为事实和规则的Horn 子句组成。具有很强的推理功能，适用于书写自动定理证明、专家系统、自然语 言理解等问题的程序。

(3) 函数型语言 LISP
函数型程序语言是一类以 γ 演算为基础的语言。LISP 是典型的函数型程序语言。函数是一种对应规则( 映 射) ，它使其定义域中每一个值和值域中唯一的值相对应。

函数型程序设计语言的优点之一是对表达式中出现的任何函数都可以用 其他函数来代替，只要这些函数调用产生相同的值。由于用函数程序设计语言书写的程序是利用自变量的值来计算函数的值的，它没有副作用。这些特点有助于程序 模块化的实现。

2.2.1.3  程 序语言的数据类型

不同程序语言所提供的数据类型不尽相同。数据是程序操作的对象，具 有名称、类型、存储类、作用域和生存期等属性，使用时要为它分配内存空间。数据名称由用户可通过标识符命名：类型说明数据占用内存的大小和存放形式，存储 类说明数据在内存中的位置和生存期；作用域说明数据可以使用的范围；生存期说明数据占用内存的时间。

数据从不同角度可分成不同的类别。按数据的作用域大小，可分为全局 量和局部量；按生存期可分为自动生存期、静态生存期和动态生成期；按程序运行时数据的值是否能改变可分为常量和变量。

数据按类型可分为4 种：Void 、标量(Scalar) 、函数和聚合(Aggregate) 。标量又可分为算术、枚举和指针；聚合类型可分为数组、结构体和共用体。
数据按其构造方式又可分为基本类 型和派生类型。

2.2.1.4  程 序语言的控制结构

程序语言中控制结构为将数据和数据上的运算组合成程序提供了基本框 架。可计算问题的程序都可用顺序、选择和循环这3 种控制结构来描述。

2.2.1.5  汇 编程序基础知识

汇编语言是为特定的计算机中计算机系统设计的面向机器的语言。汇编 语言中的语句可分成两大类：一类是与机器指令相对应的可执行汇编语句；另一类汇编语句称为汇编控制语句( 亦 称伪指令) 。用汇编语言编写的源程序，要通过汇编程序将它民机器语言程序，才能被计算机理解执行。 经过汇编程序的工作，可执行汇编语句被转化成对应的机器指令；而伪指令并不翻译成机器指令，它们的作用是控制汇编程序工作。伪指令主要用来告诉汇编程序做 一些除了翻译机器指令外必须做的工作。

汇编程序的功能是将汇编语言所编写的源程序翻译成由机器指令和其他 信息组成的目标程序。汇编程序的基本工作包括两项：一是将每一条可执行汇编语句转换成对应的机器指令；二是处理源程序中出现的伪指令。

2.2.1.6  解 释程序基础知识

解释程序是一种语言处理程序，它直接执行源程序或源程序的内部形 成。它并不产生目标程序，它是它和编译程序的主要区别。

高级语言实现语言处理4 种 方案：

第1 种，源 程序被直接解释执行。

第2 种，先 将源程序翻译成高级中间代码，然后再扫描高级中间代码，对高级中间代码进行解释执行。

第3 种，也 是一种解释程序的实现方案，与第2 种方案的解释程序不同点在于，首先将源程序转化成和机器代码十分 接近的低级中间代码，然后再解释执行这种低纸中间代码。这类系统具有良好的可移植性。

第4 种，是 普通的编译程序。在编译程序方案下，高级语言编写的源程序被最终翻译成机器语言表示的目标程序。这类系统的目标执行效率最高。

一般说来，建立在翻译基础上的系统在执行速度上都优于建立在解释执 行基础上的系统。翻译系统的缺点是其复杂性，这使得它的开发和维护费用都大。相反，解释系统比较简单，可称植性较好，适合于以交互方式执行程序，其缺点是 执行速度慢。

解释系统的结构可分成两部分。第1 部分包括通常用的词法分析程序以及语法和语义分析程序，它的作用仍是把源翻译成中间代码，中间代码的设计常采 用逆波兰表示形式。第2 部分是解释部分，用来对第1 部 分所产生的中间代码进行解释执行，完成真正的解释工作。

2.2.1.7  编 译程序基础知识

编译程序的功能是把某高级语言书写的源程序翻译成与之等价的低级语 言( 汇编语言或机器语言) 的目标程序。其过 程很复杂，可分成6 个阶段；

①词法分析阶段是编译过程的第1 个阶段。词法分析所依据的是语言的词法规则，即描述单词结构的规则。词法规则可用3 型文法( 正规文法) 或正规式来描述，有限自动机能识别正规文法所定义的语言和正规式所表示的集合。

②语法分析阶段。在词法分析的基础上将单词符合序列分解成各类语法 单位。语法分析所依据的是语言的语法规则，即描述程序结构的规则。
词法分析和语法分析本质上都是对源程序的结构进行分析。

③语义分析阶段是审查源程序有无语义错误，为代码生成阶段收集类型 信息。比如语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象。

④中间代码生成阶段。在进行了上述的语法分析和语义分析阶段工作之 后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。所谓" 中 间代码" 是一种简单、含义明确的记号系统。

语义分析和中间代码生成所依据的是语言的语义规则。一般采用语法指 导翻译规则和中间代码生成规则。

⑤代码优化阶段是对前阶段产生的中间代码进行变换或进行改造，目的 是使生成的目标代码更为高级，即省时间和省空间。

⑥目标代码生成阶段。是把中间代码变换成特定机器上的绝对指令代码 或可重定位的指令代码或汇编指令代码。这是编译的最后阶段，它的工作与硬件系统的结构和指令的含义有关。

编译过程的6 个 阶段的任务，再加上表格管理和出错处理的工作可分别由几个模块或程序完成，它们分别称作词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代 码优化程序、目标代码生成程序、表格管理程序和出错处理程序。

2.2.2  试 题分析

从历年试题统计( 见 表2-2) 来看，程序语言基础试题是每年必考的知识点，考查的重点是形式语言基础、语法和词法分析 方法、程序控制结构。复习中还应注意补充有关程序语言最新发展方面的知识。



试题1 (2000 年 试题3)

从供选择的答案中，选出应填入下面叙述中{ } 内的最确切的解答，把相应编号写在答卷的对应栏内。

假设某程序语言的文法如下：

S→a|b|(T)

T→TdS|S

其中： Vt={a,b,d,(,)},Nn={S,T} ， S 是开始符号。

考查该文法，称句型 (Sd(T)db) 是 S 的一个 A 。 其中B 是句柄；C 是素短语；D 是该句型的直接短词；E 是短语。

供选择的答案

A ：①最左 推导 ②最右推导 ③规范推导 ④推导

B ：① S  ② b  ③ (T)  ④ Sd(T)

C ：① S  ② b  ③ (T)  ④ Sd(T)

D ：① S  ② S ， (T) ， b
③ S ， (T) ， TdS ， b  ④ (Sd(T)db)

E ：① (Sd(T)db)  ② d(T)  ③ Td  ④ Sd(T)d

【解析】 

解答本题要搞清楚基本概念，下面具体分析各个问题。

先来看问题A 。 最左 ( 右 ) 推导：任何一步推导过程σ→β ( 其中 σ 、 β 是句型 ) 都是对σ中的最左 ( 最右 ) 非终结符进行替换，这种推导为最左 ( 最右 ) 推导。在 形式语言中，最右推导常被称为规范推导。

题中的句型 (Sd(T)db) 的第一步肯定是由 S→(T)→(TdS) 得出的。按照最左推导的规则 (Tds)→(TdSdS)→(SdSdS) ，最终不可能推出原来的 句型。

按照最右推导的规则 (Tds)→(Tdb)→(Td(T)db) ，最终不可能推出原先的 句型。

最后可以看出句型 (Sd(T)db) 是由一般推导推出的，步骤如下：

S→(T)→(Tds)→(Tdb)→(Td(T)db)→(Sd(T)db)

所以正确答案是④。

再来看问题 B ～ E 。来文法， S 是 文法的开始符号，αβδ是文法 G 的一个句 型。如果有 S→ α A δ ，且 A→ β ，则称 β是句型αβδ相对于非终符 A 的短语。特别 是如有 A β ，则称β是句型αβδ相对于规则 A→ β 的直接短语。一个句型的最左直接短语称为该句型的句柄。

本文法推导树如下：



所以， S 是句型相对于规则 T→S 的直接短语，也是最左直接短语 ( 句柄 ) 。 (T) 是句 型相对于规则 S→(T) 的直接短语，对于问 题 B ，选择①是正确的。

素短语是一个短语，它至少包含一个终结 符，并除自身外不包含其他的素短语。所以，问题 C 的答案③正确。

d 是句型相对于规则 S→d 的直接短语，则问题 D 的答案②正确。

由推导树可知，无论如何，无法由 S 推导出 d(T) 、 Td 或 Sd(T)d ，所以问题 E 的答案①正确。

【答案】：  A ：④  B ：①  C ：③  D ：②  E ：①

试题 2 (1999 年试题 )3

从供选择的答案中，选出应填入下面叙述 中 { } 内的最确切的解答，把相应编号写在 答卷扔对应栏内。

假设某程序语言的文法如下：

S→SaT|T

T→TbR|R

R→PdR|P

P→fSg|e

其中 Vr{a,b,d,e,f,g};Vn={S,T,R,P};S 是开始 符号，那么，此文法是 A 文法。这种文法的语 法分析通常采用优先短阵。优先短阵给出了该文法中各个终结符之间的优先关系 ( 大于、小于、等于和无关系 ) 。在上述文法中，某些终结符之间的优先关系如下：

b{B}a; f{C}g; a{D}a;d{E}d 。 

供选择的答案

A ：①五则文法   ② 算符文法   ③二义文法   ④属性文法

B ：①大于   ②小 于   ③等于   ④无关系

C ：①大于   ②小 于   ③等于   ④无关系

D ：①大于   ②小 于   ③等于   ④无关系

E ：①大于   ②小 于   ③等于   ④无关系

【解析】 

所谓算符文法，可以作如下的描述：如果 在一个文法 G 中，不含有形如 "U→…AB…" 的产生式，其中 A,B∈Vn ，则 G 为算符文法。也就是说，如果 G 是一算符文法，那么 G 的任何产生式的右部都不会出现两个非终结符号相邻的情况，而且，对算符文法而言，也不会含有两个非终对符号相邻出现的句型。这 种性质意味着，如果把终对符号看作广义运算符，而把非终结符号看作广义运算的对象，则在算符文法的任何句型中，两相邻运算符之间的运算对象至多只有一个， 而不会出现其间运算对象个数不确定的情况，这样就使得广义运算总是按照中缀形式出现，对语法分析工作非常有益。

对于给定的文法 G ，可以逐个检查 G 的各产生式，查看它们的右部是否含有相邻出现的非终结符号，以确定 G 是否为一算符文法，然后再构造相应的优先矩阵。若此矩阵中无多重定 义的元素 ( 即各运算符对之间至多只有一种优 先关系 ) ，同则可确认理一算符优先文法。

在算符文法中，一般按照如下规则判断终 结符之间的优先关系：

当且仅当 G 中有形如 "U→…ab…" 或者 "U→…aBb…" 的产生时， a=b ； 

当且仅当 G 中有形如 "U→…aA…" 的产生式，且有或者 "A=⁺ = ＞ b…" 或者 "A=⁺ = ＞ …aB" 时， a ＞ b ；

当且仅当 G 中有形如 "U→…Ab…" 的产生式，且有或者 "A=⁺ = ＞ a…" 或者 "A=⁺ = ＞ …aB" 时， a ＞ b 。


如果算符文法 G 的 任何一对终结符号之间，至多只有 3 种算符优 先关系：等于、大于或者小于成立，则称 G 为 算符优先文法。

【答案】： A ：②  B ：①  C ：③  D ：①  E ：②

试题 3 (1998 年试题 4)

从供选择的答案中，选出应填入下面叙述 中 { } 内的最确切的解答，把相应编号写在 答卷的对应栏内。

语法分析方法大体上可分成自上而下和自 下而上的两种。自下而上分析法，是从输入符号串开始逐步进行 A ，直至 A 成文法 的起始符号。自上而下分析法，则是从文法的起始符号开始反复使用产生式进行 B 直至 B 出输入 符号串。

符符优先文法是一种自下而上分析方法， 其文法的特点是文法产生式中 C 。自下而下的 分析方法，通常要求文法的产生式 D ，如 E 文法就是一种可以自上而下分析的文法。 

供选择的答案

A 、 B ：①递归   ②综合   ③回归   ④推 导   ⑤分解   ⑥归约

C ：①不含两个相邻的非终结符   ②不含两个相邻的终结符
③不含   产生式   ④不含长度为 1 的 产生式

D ：①不以非终结符开头   ②不以终结符开头
③不含左递归   ④不含右递归

E ：① LR(1)  ② LL(1)  ③ SLR(1)  ④ LALR(1)

【解析】 

语法分析的程序以词法分析程序所输出的 用内部编码表示的单词序列为输入，其任务是分析源程序的结构，差别它是否是相应程序设计语言的一个合法程序。为了完成这个任务，通常由语法分析程序尝试着 为其构造一棵完整的语法树。若尝试成功，则表明输入的符号串在结构上是一个合乎语法的程序，否则，源程序中必然存在的错误。

就产生语法树的方向而言，可大致把它们 分为自顶向下和自底向上两大类。所谓自顶向下的分析是对给定的符号串，试图自上而下地为其构造出一棵语法树，或者说从文法的开始符号出发，为其构造一个最 左推导。所谓自底向上的分析是给定的符号串，试图自下而上地为其构造出一棵语法树，或者说从给定的符号串本身出发，试图将其归约为文法的开始符号。

算符优先文法属于自下而上的分析法，它 利用各个算符间的优先关系和结合规则来进行语法分析，特别适用于分析各种表达式。算符优先文法的任何产生式的右部都还会出现两个非终结符相领的情况，且其 任何一对终对符之间至多只有 3 种算符关系 " ＜ " 、 " ＞和 "=" 之一成立。自顶向下的文法中不能有左递归，否则自顶和下的分析 过程进入死循环，不能正常进行。 E 中 IL(1) 为自顶向下的文法外，其他均为自底向上的文法。

【答案】： A ：⑥  B ：④  C ：①  D ：③  E ：②

试题 4 (1998 年试题 6)

从供选择的答案中，选出应填入下面叙述 中 { } 内的最确切的答案，把相应编号写在 答卷的对应栏内。

在高级程序设计语言中，使用参数是子程 序之间传递信息的一种手段。子程序说明中的参数称为形式参数，调用语句中的参数称为实在参数。调用时，实在参数的个数、类型和顺序要和形式参数保持一致。 

知道一种语言 ( 或编译器 ) 使用哪种参数传递方法是很重要的，因为程序的运行依赖于所用的方法。参数传递方法有传值调用 (Call by value) 、引用调用 (Call by reference) 、传名调用 (Call by name) 和宏扩展 (Macro expansion) 。 

传值调用是把实在参数的 A 传递给相应的形式参数，子程序通过这种传值形参 B ；引用调用是指把实在参数的 C 传给相应的形式参数，此时子程序对形式参数的一次引用或赋值被处理成 对形式参数的 D 访问。

C 语言中的函数，以 E 方式进行参数传递。

供选择的答案

A 、 C ：①地址 ②名 ③值 ④地址和值
⑤值和名 ⑥名和地址

B ：①可传回结果的值   ②可传回存放结果的地址
③可传回结果的值和存放结果的地址   ④不可传回任何结果 ( 值或地址 )

D ：①直接   ②间 接   ③变址   ④引用或赋值

E ：①传值调用   ② 引用调用   ③传名调用   ④宏扩展

【解析】 

传值调用是指把实在参数的值传递给相应 的形式参数，子程序不能通过这种方式传回任何结果。引用调用是指把实在参数的地址传递给相应的形式参数，此时子程序对形式参数的一次引用或赋值都是对形式 参数的间接访问。

C 语言规定，实参变量对形式参数的数据传递是 " 值传递 " ，即 单向传递，只能由实参传给形参，而不能由形参传给实参。所以说， C 语言中函数是传值调用的。

【答案】 A ：③  B ：④  C ：①  D ：②  E ：①

试题 5 (1997 年试题 1)

从供选择的答案中，选出应填入下面叙述 中   内的最确切的答案，把相应编号写在答卷 的对应栏内。

一种最早用于科学计算的程序设计语言是 A ；一种提供指针和指针操作且不存在布尔类型的、应用广泛的系统程序 设计语言是 B ；一种适合在互联网上编写程序 可供不同平台上运行的面向对象程序设计语言是 C ；一种在解决人工智能问题上使用最多的、有较强的表处理功能的函数程序设计语言是 D ；一种以谓词逻辑为基础的、核心是事实、规则和推理机制的实用逻辑程 序设计语言 E 。 

供选择的答案

A ～ E ：① Pascal  ② Ada  ③ Smalltalk  ④ Snobol  ⑤ C
⑥ Alogo 68  ⑦ Java  ⑧ Lisp  ⑨ Prologo  ⑩ Fortran

【解析】 

程序设计语言从机器语言、汇编语言到今 的高级语言，其发展越来越快，功能越来越强，同时，其可理解性也越来越接爱人类的思维方式。

Fortran 是第一种被用于进行科学计算的高级语言，它出现于 50 年代中期，其设计目的主要暖和于科学计算，它在程序设计语言的发展史上起着突出的作用。

Alogo 68 是另一种早期研制出来的高级语言，虽然没有被广泛使用，但对后来的程序设计语言的发展有着重大影响。

C 语言是目前应用最广泛的系统程序设计语言，它提供了指针与指针操作，且不存在布尔类型，对数据的访问灵活广泛， C 语言还可提供很多底层系统调用，与硬件结合紧密，易用性强。

Java 是适应 Internet 发展的需要而产生的通用网络程序设计语言，它提供了更好的网络安全性和平台无关性，并且采用了面向对象的原理，便于扩展，适合 在互联网上编写可供不同平台上运行的面向对象程序设计语言。

Prolog 语言在人工智能领域应用较广泛，是一种以谓词逻辑为基础，借助于推理规则从已有事实推出新的事实的实用的逻辑程序设计语言。 

Ada 和 smalltalk 两种语言引入了一定的封装机制，实现了信息隐藏。 Ada 的主要封装机制为程序包； Smalltalk 是一种纯面向对象程序设计语言，它侧重于动态链接，不进行任何类型检查，并且类和对象之间没有明显区别。

Snobol 于 1962 年 由贝尔实验室开发，它主要的操作为字符串操作。该语言一般不作为通用语言使用，而是作为一种研究工具，用于对文艺作品、音乐等进行分析。

Lisp 是一种在解决人工智能问题上使用最多的、有强的表处理功能的函数程序设计语言。

【答案】 A ：⑩：  B ：⑤  C ：⑦  D ：⑧  E ：⑨

试题 6 (1997) 年试题 7

从供选择的答案中，选出应填入下面叙述 中 { } 内的最确切的答案，把相应编号写在 答卷的对应栏内。

用高级语言编写程序时，子程序调用语句 中的实在参数必须与子程序说明中的形式参数在 A 上保持一致。在允许子程序递归调用的高级语言环境中，需用动态存储管理方法，它通常使用一个 B 存放子程序的调用记录，调用记录可包括 (1) 全局量存储区域的 C ； (2) 调用点所在子程序的 D ； (3) 调用点 的 E ； (4) 形式参数和实在参数的通信区域； (5) 返回值； (6) 本子程序的局部量和临时变量存储区域等。

供选择的答案

A ：①个数、类型   ② 个数、顺序
③个数、格式、顺序   ④个数、类型、顺序

B ：①线性表   ② 队列   ③堆   ④下推栈

C ～ E ：①子程序 首地址   ②调用记录首地址
③参数地址   ④ 寄存器地址
⑤返回地址   ⑥开始地址

【解析】 

除少数程序语言之外，形式参数和实在参 数之间的对应关系通常按位置来确定。子程序定义中有形式参数表，而子程序调用是用实在参数法表。进入子程序时，第一个形式参数就和第一个实在参数所表示的 数据或其他信息相关联，依奖对应。这样，子程序调用语句中的实在参数必须与子程序说明中的形式参数在个数、类型和顺序上保持一致，否则就不能在主程序和子 程序之间正确地传递信息。

对于允许子程序递归调用的程序语言，一 般采用动态存储管理方法，用下堆栈来实现。由于某一子程序可能被调用了若干次，但只有最近一次调用正处于执行状态，而其余各次调用正等待下次调用的返回。 这样，前几次该子程序调用的属于该子程序的局部变量存储区中的内容必须保存起来，以便下次调用返回时再继续使用。子程序执行需要一个用来存放有关信息的区 域，这个区域为过程的调用记录，一般包含以下几部分：

· 全局变量存储区域的开始地址；

· 调用点所在子程序的调用记录的地址；

· 调用点机器状态，如返回地址和寄存器当时值；

· 形式参数和实在参数的通信区域；

· 返回值； 

· 本子程序的局部量和临时变量存储区。

【答案】： A ：④  B ：④  C ：⑥  D ：②  E ：⑤

试题 7 (1996 年试题 5)

从供选择的答案中，选出应填入下面叙述 中   内的最确切的解答，把相应编号写在答卷 的对应栏内。

有限状态自动机可用五元组 (VT ， Q ， δ ， q0 ， Qf) 来描述，它可对应于 A 。设有一有限状态自动机 M  的定义如下：

VT={0 ， 1} Q={q0,q1,q2}

δ 定义为：

δ(q0,0)=q1,δ(q1,0)=q2

δ(q2,1)=q2,δ(q2,0)=q2

Qf={q2}

M 是一个 B 有限状 态自动机，它所对应的状态转换图为 C ，它所 能接受的语言可以用正则表达式表示为 D ，其 含义为 E 。 

供选择的答案

A ：① 0 型文法 ② 1 型文法 ③ 2 型文法 ④ 3 型 文法 

B ：①歧义的   ② 非歧义的   ③确定的   ④非确定的

 

D ：① (0|1)*  ② 00(0|1)  ③ (0|1)*00  ④ 0(0|1)*0

E ：①由 0 和 1 所组成的符号串的集合。

②以 0 为头符号和尾符号、由 0 和 1 所组成的符号串的集合。

③以两个 0 为结束的、由 0 和 1 所组成的 符号串的集合。

④以两个 0 为开始的、由 0 和 1 所组成的 符号串的集合。

【解析】 

先来看一下地分类表 2-3

 

一个有限状态自动机 M 用 5 元组 (VT ， Q ， δ ， q0 ， Qf) 来表示，其中 VT={0 ， 1} 是一个有穷字母表，它的每个元素称为一个输入字符： Q=(q0,q1,q2) 是一个有限集，它的每个元素称为一个状态；δ定义为δ (q0,0)=q1, δ (q1,0)=q2, δ (q2,1)=q2, δ (q2,0)=q2 是一个从 VT×Q 到 Q 上的 ( 单值 ) 部分映 射； q0 为初态； Qf={q2} 为终态集。

有限自动机分为确定的有限自动机和非确 定的有限自动机。确定的有限自动机的确定性表现在映射δ： VT×Q→Q 是一个单值函数，即对任何状态 qQ 和输入字符 aVT ，映射 δ (q,a) 唯一确定下一个状态。由分析可知本题给出的是一个确定的有限自动机，它的状态转换如图 2-7 所示。 
它所能接受的语言可以用正则表达式表示为 00(0|1)* ，其含义为由两个 0 开始的后跟任意个 ( 包含 0 个或多个 )0 或 1