编译原理练习答案蒋宗礼第三篇.pdfVIP

第一部分 重点知识回顾 第二章 词法分析 词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号， 把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析器的功能是输入源 程序，输出单词符号，且输出的单词符号常常表示成如下的二元式： （单词种别，单词自身的值） 我们可以把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时，就调 用这个子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号，把它交给语法 分析器。 1 状态转换图 使用状态转换图是设计词法分析程序（扫描器）的一种好途径。转换图是一张有限方向 图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用有向弧连结，有向弧上的标 记代表着可能出现的输入字符。一张转换图只包含有限个状态，其中有一个被认为是初态， 而且实际上至少要有一个终态（用双圈表示）。例如，识别标识符的状态转换图如图 2. 1 所 示， 其中 0 为初态，2 为终态。终态结上打着星号“*”，意味着多读进了一个不属于标识符部分 的字符，应把它退还给输入串。 用手工设计词法分析器的方法是：先使用状态转换图描述出所有的单词符号，然后用程 序实现状态转换图。最简单的办法是让每个状态对应一小段程序。 2 正规表达式与有限自动机 有限自动机理论是描述词法规则的基本理论。一条词法规则表示为一个正规表达式（简 称正规式），而一个正规表达式又可化为一个确定的有限自动机，这个有限自动机就可以用 来识别该词法规则定义的所有单词符号。把程序设计语言的所有词法规则都构造出相应的有 限自动机，就得到了一个词法分析器。 词法分析器自动生成的过程是：根据某种程序设计语言的词法规则，写出相应的正规式， 再根据这些正规式，写出某种语言（比如 LEX) 的源程序，由LEX 编译程序翻译后便得到 了一个词法分析器，它可以用来识别该程序语言的全部单词。所以，要实现词法分析器的自 动生成，关键是要有某种语言（比如 LEX ）的编译程序。一旦有了这个编译程序，就可以 通过它得到其他各种程序语言的词法分析器。  正规式与正规集 对于字母表∑，我们感兴趣的是它的一些特殊字集，即正规集。下面是正规式和正规集 的递归定义： (1)ε 和φ 都是∑上的正规式，它们所表示的正规集分别为｛ε ｝和φ ； (2)任何 a ∈∑，则称a 是∑上的一个正规式，它所表示的正规集为｛a}; (3 ）假定U 和 V 都是∑上的正规式，它们所表示的正规集分别为 L (U)和 L (V) ， 则（U|V ）、（U ·V ）和（U)*也都是正规式，它们所表示的正规集分别为 L （U) ∪L （V) 、 L (U) L (V) （连接积）和(L (U))* （闭包）。 仅通过有限次使用上述三步骤定义的表达式才是∑上的正规式，仅由这些正规式所表示 的字集才是∑上的正规集。 令 U 、V 和 W 均为正规式，则下述关系成立： （1）U|V=V|U （交换律） (2 ）U|(V|W)=(U|V)W 或 U(VW)=(UV)W （结合律） (3 ）U(V|W)=UV|UW 或 （V|W ）U=VU|WU （分配律） (4 ）ε U=Uε =U 若两个正规式所表示的正规集相同，则认为二者等价。 * * * * * * 例如：b(ab) =(ba) b, (a|b) =(a b ） 。 * * * * * * 注意： a b 、(a|b) 、(ab) 、a |b 相互都不等价，它们表示的含义如图所示  .确定有限自动机(DFA) 一个确定的有限自动机（DFA ）M 是一个五元式：M= （Q, ∑ ,f，s ,Z），其中： 0 （1) Q 是一个有限集，它的每个元素称为一个状态； （2) ∑是一个有穷字母表，它的每个元素称为一个输入字符； （3) f 是一个从 Q ×∑至Q 的（单值）部分映射。f(q,a)=p 意味