编译原理总结2词法.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。,SlAA|lA|dA,9,由正规文法构造状态图,（2）对于左线性文法 步骤1 增加结点S为初态；步骤2 将每个非终结符号设置为一个对应的状态；步骤3 对于Aa，引一条从S到A的弧，弧上标记为a；而对于ABa，引一条从B到A的弧，弧上标记为a。,3.1 词法分析程序概述,Al|Al|Ad,SlAA|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 正规文法与正规式,正规文法转换成正规式,正规文法和正规式的等价性,17,步骤1 将每条产生式改写为正规式；步骤2 用代入法解正规式方程组，最后只剩下一个 开始符号定义的正规式，其中不含非终结符。,3.2 正规文法与正规式,
