① 编译原理-句型、句子、短语、直接短语、句柄、素短语、最左素短语
在进行语法分析的时候，有时候会对这些词语的概念不清晰，这里我们就详细归纳总结一下。
可以看出这个里面，最需要理解的概念就是短语，其他大部分概念都是在短语基础上延伸的，从概念上可以看出：
假设有一个文法
针对文法的一个特定句型 (Sd(T)db) , 其推导过程如下:
这个句型 (Sd(T)db) 对应的 CFG 分析树如下：
那个这个句型 (Sd(T)db) 有多少个短语呢？
还记得短语的定义么， S ⇒* αβδ ， αβδ 代表句型就是这里的 (Sd(T)db) 。
因此这个句型 (Sd(T)db) :
算法非常简单，就是通过分析树的后序遍历，先将子树的叶节点从左到右排合并成字符串(即一个短语)，然后用它代表子树的根节点的值，再和与子树根节点同一层节点值合并，得到新的短语。就这样从分析树的最底层，一路合并到分析树的根节点，就能得到所有的短语了。
通过递归的方法，获取短语列表 phraseList , 直接短语列表 directPhraseList 和 素短语列表 plainPhraseList 。
运行结果:
② 【编译原理】第二章：语言和文法
上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。
约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：
产生式
可以简写为：
如上例中，
可以简写为：
给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。
如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。
推导的反过程称为 归约 。
如果 ，则称 是 的一个 句型（sentential form ）。
由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：
例
文法
表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。
并、连接、幂、克林闭包、正闭包。
如上例表示为：
中必须包含一个 非终结符 。
产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。
上下文有关文法不包含空产生式（ ）。
产生式的一般形式：
即产生式左边都是非终结符。
右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。
例：（右线性文法）
以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：
正则文法能描述程序设计语言中的多数单词。
正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。
根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。
给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。
直接短语一定是某产生式的右部，但反之不一定。
如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。
二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。
③ 编译原理中 “句子”的概念 LR（1）分析法中“L” “ R”的含义分别是
字母表上符合某种规则构成的串称作句子。
L：自左至右扫描，R：最右推倒的逆过程。
④ 编译原理
编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程，同时也是计算机专业课程中最难及最挑战学习能力的课程之一。编译原理课程内容主要是原理性质，高度抽象[1]。
中文名
编译原理[1]
外文名
Compilers: Principles, Techniques, and Tools[1]
领域
计算机专业的一门重要专业课[1]
快速
导航
编译器
编译原理课程
编译技术的发展
编译的基本流程
编译过程概述
基本概念
编译原理即是对高级程序语言进行翻译的一门科学技术, 我们都知道计算机程序由程序语言编写而成, 在早期计算机程序语言发展较为缓慢, 因为计算机存储的数据和执行的程序都是由0、1代码组合而成的, 那么在早期程序员编写计算机程序时必须十分了解计算机的底层指令代码通过将这些微程序指令组合排列从而完成一个特定功能的程序, 这就对程序员的要求非常高了。人们一直在研究如何如何高效的开发计算机程序, 使编程的门槛降低。[2]
编译器
C语言编译器是一种现代化的设备, 其需要借助计算机编译程序, C语言编译器的设计是一项专业性比较强的工作, 设计人员需要考虑计算机程序繁琐的设计流程, 还要考虑计算机用户的需求。计算机的种类在不断增加, 所以, 在对C语言编译器进行设计时, 一定要增加其适用性。C语言具有较强的处理能力, 其属于结构化语言, 而且在计算机系统维护中应用比较多, C语言具有高效率的优点, 在其不同类型的计算机中应用比较多。[3]
C语言编译器前端设计
编译过程一般是在计算机系统中实现的, 是将源代码转化为计算机通用语言的过程。编译器中包含入口点的地址、名称以及机器代码。编译器是计算机程序中应用比较多的工具, 在对编译器进行前端设计时, 一定要充分考虑影响因素, 还要对词法、语法、语义进行分析。[3]
1 词法分析[3]
词法分析是编译器前端设计的基础阶段, 在这一阶段, 编译器会根据设定的语法规则, 对源程序进行标记, 在标记的过程中, 每一处记号都代表着一类单词, 在做记号的过程中, 主要有标识符、关键字、特殊符号等类型, 编译器中包含词法分析器、输入源程序、输出识别记号符, 利用这些功能可以将字号转化为熟悉的单词。[3]
2 语法分析[3]
语法分析是指利用设定的语法规则, 对记号中的结构进行标识, 这包括句子、短语等方式, 在标识的过程中, 可以形成特殊的结构语法树。语法分析对编译器功能的发挥有着重要影响, 在设计的过程中, 一定要保证标识的准确性。[3]
3 语义分析[3]
语义分析也需要借助语法规则, 在对语法单元的静态语义进行检查时, 要保证语法规则设定的准确性。在对词法或者语法进行转化时, 一定要保证语法结构设置的合法性。在对语法、词法进行检查时, 语法结构设定不合理, 则会出现编译错误的问题。前端设计对精确性要求比较好, 设计人员能够要做好校对工作, 这会影响到编译的准确性, 如果前端设计存在失误, 则会影响C语言编译的效果。[3]
⑤ 求解编译原理的一道题:设有文法如下
首先要做这题你要知道判别文法类型
包括四个层次：
0-型文法（无限制文法或短语结构文法）包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。
1-型文法（上下文相关文法）生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号，而 α, β 和 γ 是包含非终结符号与终结符号的字串；α, β 可以是空串，但 γ 必须不能是空串；这种文法也可以包含规则 S->ε ，但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
2-型文法生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。
正规语言类包含于上下文无关语言类，上下文无关语言类包含于上下文相关语言类，上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系，也就是说：存在递归可枚举语言不属于上下文相关语言类，存在上下文相关语言不属于上下文无关语言类，存在上下文无关语言不属于正规语言类。
1）本题应该是--上下文无关文法
句子是产生式在推导时“仅仅有终结符”的任何一步
2）%mm%nn 是一个句子
由于下面一题的图我等级不够 不能贴图 发你邮箱
⑥ 编译器有哪几部分构成.编译原理
1. 词法分析
词法分析器根据词法规则识别出源程序
中的各个记号（token）,每个记号代表一类单词（lexeme）。源程序中常见的记号可以归为几大类：关键字、标识符、字面量和特殊符号。词法分析器
的输入是源程序,输出是识别的记号流。词法分析器的任务是把源文件的字符流转换成记号流。本质上它查看连续的字符然后把它们识别为“单词”。
2. 语法分析
语法分析器根据语法规则识别出记号流中的结构（短语、句子）,并构造一棵能够正确反映该结构的语法树。
3. 语义分析
语义分析器根据语义规则对语法树中的语法单元进行静态语义检查,如果类型检查和转换等,其目的在于保证语法正确的结构在语义上也是合法的。
4. 中间代码生成
中间代码生成器根据语义分析器的输出生成中间代码。中间代码可以有若干种形式,它们的共同特征是与具体机器无关。最常用的一种中间代码是三地址码,它的一种实现方式是四元式。三地址码的优点是便于阅读、便于优化。
⑦ 编译原理实现判断是不是一个文法的句子
构造LL(1)语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合（编译出错），则输出错误信息。
⑧ 编译原理题目
习题一、单项选择题
1、将编译程序分成若干个“遍”是为了 。
a．提高程序的执行效率
b．使程序的结构更加清晰
c．利用有限的机器内存并提高机器的执行效率
d．利用有限的机器内存但降低了机器的执行效率
2、构造编译程序应掌握 。
a．源程序 b．目标语言
c．编译方法 d．以上三项都是
3、变量应当 。
a．持有左值 b．持有右值
c．既持有左值又持有右值 d．既不持有左值也不持有右值
4、编译程序绝大多数时间花在 上。
a．出错处理 b．词法分析
c．目标代码生成 d．管理表格
5、 不可能是目标代码。
a．汇编指令代码 b．可重定位指令代码
c．绝对指令代码 d．中间代码
6、使用 可以定义一个程序的意义。
a．语义规则 b．词法规则
c．产生规则 d．词法规则
7、词法分析器的输入是 。
a．单词符号串 b．源程序
c．语法单位 d．目标程序
8、中间代码生成时所遵循的是- 。
a．语法规则 b．词法规则
c．语义规则 d．等价变换规则
9、编译程序是对 。
a．汇编程序的翻译 b．高级语言程序的解释执行
c．机器语言的执行 d．高级语言的翻译
10、语法分析应遵循 。
a．语义规则 b．语法规则
c．构词规则 d．等价变换规则
解答
1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。
2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。
3、对编译而言，变量既持有左值又持有右值，故选c。
4、编译程序打交道最多的就是各种表格，因此选d。
5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。
6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。因此选a。
7、b 8、c 9、d 10、c
二、多项选择题
1、编译程序各阶段的工作都涉及到 。
a．语法分析 b．表格管理 c．出错处理
d．语义分析 e．词法分析
2、编译程序工作时，通常有 阶段。
a．词法分析 b．语法分析 c．中间代码生成
d．语义检查 e．目标代码生成
解答
1．b、c 2. a、b、c、e
三、填空题
1、解释程序和编译程序的区别在于 。
2、编译过程通常可分为5个阶段，分别是 、语法分析 、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是 ，最后阶段的输出为 程序。
4、编译程序是指将 程序翻译成 程序的程序。 解答
是否生成目标程序 2、词法分析 中间代码生成 3、源程序 目标代码生成 4、源程序 目标语言
一、单项选择题
1、文法G：S→xSx|y所识别的语言是 。
a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx*
2、文法G描述的语言L(G)是指 。
a. L(G)={α|S+ ⇒α , α∈VT*} b. L(G)={α|S*⇒α, α∈VT*}
c. L(G)={α|S*⇒α,α∈(VT∪VN*)} d. L(G)={α|S+ ⇒α, α∈(VT∪VN*)}
3、有限状态自动机能识别 。
a. 上下文无关文法 b. 上下文有关文法
c.正规文法 d. 短语文法
4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立 。
a. 若f(a)>g(b)，则a>b b.若f(a)<g(b)，则a<b
c. a~b都不一定成立 d. a~b一定成立
5、如果文法G是无二义的，则它的任何句子α 。
a. 最左推导和最右推导对应的语法树必定相同
b. 最左推导和最右推导对应的语法树可能不同
c. 最左推导和最右推导必定相同
d. 可能存在两个不同的最左推导，但它们对应的语法树相同
6、由文法的开始符经0步或多步推导产生的文法符号序列是 。
a. 短语 b.句柄 c. 句型 d. 句子
7、文法G：E→E+T|T
T→T*P|P
P→(E)|I
则句型P+T+i的句柄和最左素短语为 。
a.P+T和i b. P和P+T c. i和P+T+i d.P和T
8、设文法为：S→SA|A
A→a|b
则对句子aba，下面 是规范推导。
a. SÞSAÞSAAÞAAAÞaAAÞabAÞaba
b. SÞSAÞSAAÞAAAÞAAaÞAbaÞaba
c. SÞSAÞSAAÞSAaÞSbaÞAbaÞaba
d. SÞSAÞSaÞSAaÞSbaÞAbaÞaba
9、文法G：S→b|∧(T)
T→T,S|S
则FIRSTVT(T) 。
a. {b,∧,(} b. {b,∧,)} c.{b,∧,(,，} d.{b,∧,),，}
10、产生正规语言的文法为 。
a. 0型 b. 1型 c. 2型 d. 3型
11、采用自上而下分析，必须 。
a. 消除左递归 b. 消除右递归 c. 消除回溯 d. 提取公共左因子
12、在规范归约中，用 来刻画可归约串。
a. 直接短语 b. 句柄 c. 最左素短语 d. 素短语
13、有文法G：E→E*T|T
T→T+i|i
句子1+2*8+6按该文法G归约，其值为 。
a. 23 B. 42 c. 30 d. 17
14、规范归约指 。
a. 最左推导的逆过程 b. 最右推导的逆过程
c. 规范推导 d. 最左归约的逆过程
[解答]
1、选c。
2、选a。
3、选c。
4、虽然a与b没有优先关系，但构造优先函数后，a与b就一定存在优先关系了。所以，由f(a)>g)(b)或f(a)<g(b)并不能判定原来的a与b之间是否存在优先关系：故选c。
5、如果文法G无二义性，则最左推导是先生长右边的枝叶：对于d，如果有两个不同的是了左推导，则必然有二义性。故选a。
6、选c。
7、由图2-8-1的语法树和优先关系可以看出应选b。
8、规范推导是最左推导，故选d。
9、由T→T,…和T→(… 得FIRSTVT(T))={(,，)}；
由T→S得FIRSTVT(S)⊂FIRSTVT(T)，而FIRSTVT(S)={b,∧,(}；即
FIRSTVT(T)={b,∧,(,，}； 因此选c。
10、d 11、c 12、b 13、b 14、b
二、多项选择题
1、下面哪些说法是错误的 。
a. 有向图是一个状态转换图 b. 状态转换图是一个有向图
c.有向图是一个DFA d.DFA可以用状态转换图表示
2、对无二义性文法来说，一棵语法树往往代表了 。
a. 多种推导过程 b. 多种最左推导过程 c.一种最左推导过程
d.仅一种推导过程 e.一种最左推导过程
3、如果文法G存在一个句子，满足下列条件 之一时，则称该文法是二义文法。
a. 该句子的最左推导与最右推导相同
b. 该句子有两个不同的最左推导
c. 该句子有两棵不同的最右推导
d. 该句子有两棵不同的语法树
e.该句子的语法树只有一个
4、有一文法G：S→AB
A→aAb|ε
B→cBd|ε
它不产生下面 集合。
a. {anbmcndm|n,m≥0} b. {anbncmdm|n,m>0}
c. {anbmcmdn|n,m≥0} d. {anbncmdm|n,m≥0}
e. {anbncndn|n≥0}
5、自下而上的语法分析中，应从 开始分析。
a. 句型 b. 句子 c. 以单词为单位的程序
d. 文法的开始符 e. 句柄
6、对正规文法描述的语言，以下 有能力描述它。
a.0型文法 b.1型文法 c.上下文无关文法 d.右线性文法 e.左线性文法
解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e
三、填空题
1、文法中的终结符和非终结符的交集是 。词法分析器交给语法分析器的文法符号一定是 ，它一定只出现在产生式的 部。
2、最左推导是指每次都对句型中的 非终结符进行扩展。
3、在语法分析中，最常见的两种方法一定是 分析法，另一是 分析法。
4、采用 语法分析时，必须消除文法的左递归。
5、 树代表推导过程， 树代表归约过程。
6、自下而上分析法采用 、归约、错误处理、 等四种操作。
7、Chomsky把文法分为 种类型，编译器构造中采用 和 文法，它们分别产生 和 语言，并分别用 和 自动机识别所产生的语言。
解答 1、空集 终结符 右
2、最左
3、自上而上 自下而上
4、自上而上
5、语法 分析
6、移进 接受
7、4 2 型 3型 上下文无关语言 正规语言 下推自动机 有限
四、判断题
1、文法 S→aS|bR|ε描述的语言是(a|bc)* ( )
R→cS
2、在自下而上的语法分析中，语法树与分析树一定相同。 （ ）
3、二义文法不是上下文无关文法。 （ ）
4、语法分析时必须先消除文法中的左递归。 （ ）
5、规范归约和规范推导是互逆的两个过程。 （ ）
6、一个文法所有句型的集合形成该文法所能接受的语言。 （ ）
解答 1、对 2、错 3、错 4、错 5、错 6、错
五、简答题
1、句柄 2、素短语 3、语法树 4、归约 5、推导
[解答]
1、句柄：一个句型的最左直接短语称为该句型的句柄。
2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。
3、语法树：满足下面4个条件的树称之为文法G[S]的一棵语法树。
①每一终结均有一标记，此标记为VN∪VT中的一个符号；
②树的根结点以文法G[S]的开始符S标记；
③若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；
④若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,…,XK，则A→X1,X2,…,XK，必然是G的一个产生式。
4、归约：我们称αγβ直接归约出αAβ，仅当A→γ 是一个产生式，且α、β∈(VN∪VT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。
5、推导：我们称αAβ直接推出αγβ，即αAβÞαγβ，仅当A→ γ 是一个产生式，且α、β∈(VN∪VT)*。如果α1Þα2Þ…Þαn，则我们称这个序列是从α1至α2的一个推导。若存在一个从α1αn的推导，则称α1可推导出αn。推导是归约的逆过程。
六、问答题
1、给出上下文无关文法的定义。
[解答]
一个上下文无关文法G是一个四元式（VT,VN,S, P），其中：
●VT是一个非空有限集，它的每个元素称为终结符号；
●VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=Φ；
●S是一个非终结符号，称为开始符号；
●P是一个产生式集合（有限），每个产生式的形式是P→α，其中，P∈VN，
α∈(VT∪VN)*。开始符号S至少必须在某个产生式的左部出现一次。
2、文法G[S]：
S→aSPQ|abQ
QP→PQ
bP→bb
bQ→bc
cQ→cc
（1）它是Chomsky哪一型文法？
（2）它生成的语言是什么？
[解答]
（1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法G[S]是Chomsky1型文法，即上下文有关文法。
（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到：
SÞabQÞabc
SÞaSPQÞaabQPQÞaabPQQÞaabbQQÞaabbcQÞaabbcc
SÞaSPQÞaaSPQPQÞaaabQPQPQÞaaabPQQPQÞaaabPQPQQÞaaaPPQQQÞ
aaabbPqqqÞaaabbQQQÞaaabbbcQQÞaaabbbccQÞaaabbbccc
……
于是得到文法G[S]生成的语言L={anbncn|n≥1}
3、按指定类型，给出语言的文法。
L={aibj|j＞i≥1}的上下文无关文法。
【解答】
（1）由L={aibj|j＞i≥1}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S→Sb或S→bS型的产生式，用以保证b的个数多于a的个数；也即所求上下文无关文法G[S]为：
G[S]：S→aSb|Sb|b
4、有文法G：S→aAcB|Bd
A→AaB|c
B→bScA|b
（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄；
（2）写出句子acabcbbdcc的最左推导过程。
【解答】（1）分别画出对应两句型的语法树，如图2-8-2所示
句柄:AaB Bd
图2-8-2 语法树
（2）句子acabcbbdcc的最左推导如下：
SÞaAcBÞaAaBcBÞacaBcBÞacabcBÞacabcbScAÞacabcbBdcA
ÞacabcbbdcAÞacabcbbdcc
5、对于文法G[S]：
S→（L）|aS|a L→L, S|S
（1）画出句型（S,（a））的语法树。（2）写出上述句型的所有短语、直接短语、句柄和素短语。
【解答】
（1）句型（S,（a））的语法树如图2-8-3所示
（2）由图2-8-3可知：
①短语：S、a、(a)、S,(a)、(S,(a))；
②直接短语：a、S；
③句柄：S；
④素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；
因此素短语为a。
6、考虑文法G[T]：
T→T*F|F
F→F↑P|P
P→（T）|i
证明T*P↑（T*F）是该文法的一个句型，并指出直接短语和句柄。
【解答】
首先构造T*P↑（T*F）的语法树如图2-8-4所示。
由图2-8-4可知，T*P↑（T*F）是文法G[T]的一个句型。
直接短语有两个，即P和T*F；句柄为P。
一、单项选择题
1、词法分析所依据的是 。
a. 语义规则 b. 构词规则 c. 语法规则 d. 等价变换规则
2、词法分析器的输出结果是 。
a. 单词的种别编码 b. 单词在符号表中的位置
c. 单词的种别编码和自身值 d. 单词自身值
3、正规式M1和M2等价是指 。
a. M1和M2的状态数相等 b. M1和M2的有向弧条数相等
c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向弧条数相等
4、状态转换图（见图3-6-1）接受的字集为 。
a. 以 0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合
c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合
5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此， 。
a. 词法分析器应作为独立的一遍 b. 词法分析器作为子程序较好
c. 词法分析器分解为多个过程，由语法分析器选择使用 d. 词法分析器并不作为一个独立的阶段
解答 1、b 2、c 3、c 4、d 5、b
二、多项选择题
1、在词法分析中，能识别出 。
a. 基本字 b. 四元式 c. 运算符
d. 逆波兰式 e. 常数
2、令∑={a,b}，则∑上所有以b开头，后跟若干个ab的字的全体对应的正规式为 。
a. b(ab)* b. b(ab)+ c.(ba)*b
d. (ba)+b e. b(a|b)
解答 1、a、c、e 2、a、b、d
三、填空题
1、确定有限自动机DFA是 的一个特例。
2、若二个正规式所表示的 相同，则认为二者是等价的。
3、一个字集是正规的，当且仅当它可由 所 。
解答 1、NFA 2、正规集 3、DFA（NFA）所识别
四、判断题
1、一个有限状态自动机中，有且仅有一个唯一终态。 （ ）
2、设r和s分别是正规式，则有L（r|s）=L(r)|L(s)。 （ ）
3、自动机M和M′的状态数不同，则二者必不等价。 （ ）
4、确定的自动机以及不确定的自动机都能正确地识别正规集。 （ ）
5、对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。 （ ）
6、对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M)。 （ ）
7、对任何正规表达式e，都存在一个NFA M，满足L(G)=L(e)。 （ ）
8、对任何正规表达式e，都存在一个DFA M，满足L(G)=L(e)。 （ ）
解答 1 、2、3、错 4、5、6、7、8、正确
五、基本题
1、设M＝（{x,y}, {a,b}, f,x,{y}）为一非确定的有限自动机，其中f定义如下：
f（x,a）＝{x,y} f（x,b）＝{y}
f（y,a）＝φ f（y,b）＝{x,y}
试构造相应的确定有限自动机M′。
解答：对照自动机的定义M=(S,Σ,f,S0,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出NFA M相应的状态图，如图3-6-2所示。
用子集法构造状态转换矩阵表3-6-3所示。
I Ia Ib
{x} {x,y} {y}
{y} — {x,y}
{x,y} {x,y} {x,y}
将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。
表3-6-4 状态转换矩阵
a b
0 2 1
1 — 2
2 2 2
即得到M′=（{0,1,2}, {a,b}, f,0, {1,2}），其状态转换图如图3-6-5所示。
将图3-6-5的DFA M′最小化。首先，将M′的状态分成终态组{1，2}与非终态组{0}；其次，考察{1,2}。由于{1,2}a={1,2}b={2}⊂{1,2}，所以不再将其划分了，也即整个划分只有两组{0}，{1,2}：令状态1代表{1,2}，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图3-6-6所示化简DFA M′。
2、对给定正规式b*（d|ad）（b|ab）+，构造其NFA M；
解答：首先用A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*；其次，构造该正规式的NFA M，如图3-6-7所示。
求采纳为满意回答。