编译原理总结2词法1.ppt

1,词法分析,2,（1）分析和识别单词及属性， 包括识别语言的关键字、标识符、常数、运算符等； （2）跳过各种分隔符，如空格，回车，制表符等； （3）删除注释； （4）进行词法检查，报告所发现的错误； （5）建立符号表。,3.1 词法分析程序概述,词法分析的任务,3,词法分析的基本思路 将单词符号的语法用有效的工具描述； 基于该描述建立单词的识别机制； 设计和实现词法分析程序。,3.1 词法分析程序概述,4,词法分析程序的工作方式 相对独立方式（单遍）：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。 完全独立方式（多遍）：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。,3.1 词法分析程序概述,5,3.1 词法分析程序概述,词法分析程序的输出形式,单词类别可以用整数编码 表示:一类一种或一字一种,6,词法分析程序的设计与实现,3.1 词法分析程序概述,（1）根据词法规则写出正规文法； （2）将正规文法转换成状态图； （3）将状态图转换成流程图； （4）写出词法分析程序。,7,3.1 词法分析程序概述,正规文法及其状态图,状态图：为识别单词而专门设计的有向图， 是设计词法分析程序的一种好途径。,结点代表状态，用圆圈表示，为非终结符； 有向弧表示状态转移； 弧上的标记表示在射出弧的结点状态下可能出现的输入字符，为终结符。,一张状态图包含有穷个状态，只能有一个初态，至少要有一个终态（用双圈表示）。,8,由正规文法构造状态图,3.1 词法分析程序概述,（1）对于右线性文法 步骤1 增加结点Z为终态； 步骤2 将每个非终结符号设置为一个对应的状态； 步骤3 对于Aa，引一条从A到Z的弧，弧上标记为a； 而对于AaB，引一条从A到B的弧，弧上标记为a。,SlA A|lA|dA,9,由正规文法构造状态图,（2）对于左线性文法 步骤1 增加结点S为初态； 步骤2 将每个非终结符号设置为一个对应的状态； 步骤3 对于Aa，引一条从S到A的弧，弧上标记为a； 而对于ABa，引一条从B到A的弧，弧上标记为a。,3.1 词法分析程序概述,Al|Al|Ad,SlA A|lA|dA,10,3.2 正规文法与正规式,正规式和正规集的定义,(1) 和都是上的正规式，它们所表示的正规集分别为和。 (2) 对任一个a，a是上的一个正规式，它所表示的正规集为a。 (3) 如果R和S是上的正规式，它们所表示的正规集分别为L(R) 和L(S)，则： RS是上的正规式，它所表示的正规集为L(R)L(S)； RS是上的正规式，它所表示的正规集为L(R)L(S)； R*是上的正规式，它所表示的正规集为(L(R)*； (R)也是上的正规式，它所表示的正规集为L(R)。 (4) 仅由有限次使用规则(1)(3)得到的表示式是上的正规式，它 所表示的集合是上的正规集。,11,正规式中的运算符： | 或（选择） 连接 * 或 重复 （） 括号,运算符的优先级： 先 * , 后 , 最后 | 在正规式中可以省略。,正规式相等这两个正规式表示的语言相等,3.2 正规文法与正规式,12,正规式：单词的词型公式 正规集：符合词型公式的单词的集合，是符号集 运算符：从高到低的优先次序：* | 正规式的定义是一种递归定义 正规式等价 正规式R和S，如果L(R)=L(S),则RS,【例】 L(b(ab)*)=L(ba)*b)， b(ab)*=(ba)*b L(a|b)*)=L(a)*(b)*)*), (a|b)*=(a)*(b)*)*,3.2 正规文法与正规式,正规式和正规集的说明,13,一个正规语言可以由正规文法定义，也可以由正规式定义。 对任意一个正规文法，存在一个定义同一个正规语言的正规式；反之，对每个正规式，存在一个生成同一语言的正规文法。,3.2 正规文法与正规式,正规文法和正规式的等价性,14,(1)令S是文法G的开始符号，首先形成Sr (2)对形成的形如Axy的正规产生式，重写为：AxB，By (3)对形成的形如Ax*y的正规产生式，重写为：AxA，Ay (4)对形成的形如Axy*的正规产生式，重写为： Ax，AAy (5)对形如Ax|y的正规产生式，重写为：Ax，Ay (6)不断利用上述规则做变换，直到每个产生式都符合正规文法 的要求。,正规式转换成正规文法,将上的正规式 r 转换成文法G(VN,VT,S,P)方法如下：,3.2 正规文法与正规式,正规文法和正规式的等价性,15,步骤1 构造 Sr 步骤2 不断利用下表的规则做变换,直到每个产生式 最多含有一个终结符为止。,3.2 正规文法与正规式,16,将一个正规文法转换为正规式的规则： (1)AxB，By 正规式为： A=xy (2)AxA|y， 正规式为： A=x*y (3)Ax，Ay 正规式为： A=x|y,不断收缩产生式规则，直到剩下一个开始符号定 义的正规式，并且该产生式的右部不含非终结符。,(顺序规则) (循环规则) (分支规则),AxA，Ay,3.2 正