编译原理练习答案蒋宗礼第三章

《编译原理练习答案蒋宗礼第三章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一部分重点知识回顾第二章词法分析词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析器的功能是输入源程序，输出单词符号，且输出的单词符号常常表示成如下的二元式：（单词种别，单词自身的值）我们可以把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时，就调用这个子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号，把它交给语法分析器。1状态转换图使用状态转换图是设计词法分析程序（扫描器）的一种好途径。转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之

2、间用有向弧连结，有向弧上的标记代表着可能出现的输入字符。一张转换图只包含有限个状态，其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。例如，识别标识符的状态转换图如图2.1所示，其中0为初态，2为终态。终态结上打着星号“*”，意味着多读进了一个不属于标识符部分的字符，应把它退还给输入串。用手工设计词法分析器的方法是：先使用状态转换图描述出所有的单词符号，然后用程序实现状态转换图。最简单的办法是让每个状态对应一小段程序。2正规表达式与有限自动机有限自动机理论是描述词法规则的基本理论。一条词法规则表示为一个正规表达式（简称正规式），而一个正规表达式又可化为一个确

3、定的有限自动机，这个有限自动机就可以用来识别该词法规则定义的所有单词符号。把程序设计语言的所有词法规则都构造出相应的有限自动机，就得到了一个词法分析器。词法分析器自动生成的过程是：根据某种程序设计语言的词法规则，写出相应的正规式，再根据这些正规式，写出某种语言（比如LEX)的源程序，由LEX编译程序翻译后便得到了一个词法分析器，它可以用来识别该程序语言的全部单词。所以，要实现词法分析器的自动生成，关键是要有某种语言（比如LEX）的编译程序。一旦有了这个编译程序，就可以通过它得到其他各种程序语言的词法分析器。正规式与正规集对于字母表∑，我们感兴趣的是它的一些特殊字集，即正规

4、集。下面是正规式和正规集的递归定义：(1)ε和φ都是∑上的正规式，它们所表示的正规集分别为｛ε｝和φ；(2)任何a∈∑，则称a是∑上的一个正规式，它所表示的正规集为｛a};(3）假定U和V都是∑上的正规式，它们所表示的正规集分别为L(U)和L(V)，则（U

5、V）、（U·V）和（U)*也都是正规式，它们所表示的正规集分别为L（U)∪L（V)、L(U)L(V)（连接积）和(L(U))*（闭包）。仅通过有限次使用上述三步骤定义的表达式才是∑上的正规式，仅由这些正规式所表示的字集才是∑上的正规集。令U、V和W均为正规式，则下述关系成立：（1）U

6、V=V

7、U（交换律）(2）U

8、(V

9、

10、W)=(U

11、V)W或U(VW)=(UV)W（结合律）(3）U(V

12、W)=UV

13、UW或（V

14、W）U=VU

15、WU（分配律）(4）εU=Uε=U若两个正规式所表示的正规集相同，则认为二者等价。******例如：b(ab)=(ba)b,(a

16、b)=(ab）。******注意：ab、(a

17、b)、(ab)、a

18、b相互都不等价，它们表示的含义如图所示.确定有限自动机(DFA)一个确定的有限自动机（DFA）M是一个五元式：M=（Q,∑,f，s0,Z），其中：（1)Q是一个有限集，它的每个元素称为一个状态；（2)∑是一个有穷字母表，它的每个元素称为一个输入字符；（3)f是一个从Q×∑至Q的

19、（单值）部分映射。f(q,a)=p意味着当现行状态为q,输入字符为a时，将转换到下一状态p。我们把p称为q的一个后继状态；（4）s0∈S，是唯一的初态；（5）Z⊂Q，是一个终态集（可空）。一个确定的有限自动机可以用一个矩阵表示。该矩阵的行表示状态，列表示输入字符，矩阵元素表示f(q,a)的值。这个矩阵称为状态转换矩阵。一个确定的有限自动机也可以表示成一张（确定的）状态转换图。状态转换图的构造方法是：若确定的有限自动机M含有m个状态和n个输入字符，则这个图含有m个状态结点，每个结点顶多有n条有向弧射出和别的结点相连接，每条弧用∑中的一个互不相同的输入字符作标记，整个图含有唯一

20、的一个初态结和若干个（可以是0个）终态结点。*对于∑中的任何字α，若存在一条从初态到某一终态结的道路，且这条路上所有弧的标记符连接成的字等于α，则称α可为确定的有限自动机M所识别（读出或接受）。若M的初态结同时又是终态结点，则空字ε可为M所识别（或接受）。确定的有限自动机M所能识别字的全体记为L（M）。注意：确定的有限自动机其确定性表现在映射f:Q×∑→Q是一个单值函数。也就是说，对任何状态q∈Q和输入符号a∈∑,f(q,a)唯一地确定了下一个状态。非确定有限自动机（NFA）如果允许f是一个多值函数，就得到非确定