资源描述：
《编译原理总结2词法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1S.PO.P语义分析及生成中间代码程序代码生成程序代码优化程序语法分析程序词法分析程序错误处理符号表管理词法分析2（1）分析和识别单词及属性，包括识别语言的关键字、标识符、常数、运算符等；（2）跳过各种分隔符，如空格，回车，制表符等；（3）删除注释；（4）进行词法检查，报告所发现的错误；（5）建立符号表。3.1词法分析程序概述词法分析的任务3词法分析的基本思路将单词符号的语法用有效的工具描述；基于该描述建立单词的识别机制；设计和实现词法分析程序。3.1词法分析程序概述4词法分析程序的工作方式相对独立方式（单遍）：把词法分析程序作为语法分析程序的一个独立子程序。语法
2、分析程序需要新符号时调用这个子程序。完全独立方式（多遍）：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。3.1词法分析程序概述5二元式：单词类别单词的属性值单词类别关键字标识符常数运算符分界符编码123453.1词法分析程序概述词法分析程序的输出形式单词类别可以用整数编码表示:一类一种或一字一种6词法规则状态图词法分析程序词法分析程序的设计与实现3.1词法分析程序概述（1）根据词法规则写出正规文法；（2）将正规文法转换成状态图；（3）将状态图转换成流程图；（4）写出词法分析程序。73.1词法分析程序概述正规文法及其状态图
3、状态图：为识别单词而专门设计的有向图，是设计词法分析程序的一种好途径。结点代表状态，用圆圈表示，为非终结符；有向弧表示状态转移；弧上的标记表示在射出弧的结点状态下可能出现的输入字符，为终结符。一张状态图包含有穷个状态，只能有一个初态，至少要有一个终态（用双圈表示）。SUVZ1110008由正规文法构造状态图3.1词法分析程序概述（1）对于右线性文法步骤1增加结点Z为终态；步骤2将每个非终结符号设置为一个对应的状态；步骤3对于A→a，引一条从A到Z的弧，弧上标记为a；而对于A→aB，引一条从A到B的弧，弧上标记为a。S→lAA→ε
4、lA
5、dAl
6、dAZεSlAZll
7、
8、d9由正规文法构造状态图（2）对于左线性文法步骤1增加结点S为初态；步骤2将每个非终结符号设置为一个对应的状态；步骤3对于A→a，引一条从S到A的弧，弧上标记为a；而对于A→Ba，引一条从B到A的弧，弧上标记为a。3.1词法分析程序概述A→l
9、Al
10、Adl
11、dASlS→lAA→ε
12、lA
13、dAl
14、dAZεSl103.2正规文法与正规式正规式和正规集的定义(1)ε和Ф都是Σ上的正规式，它们所表示的正规集分别为{ε}和Ф。(2)对任一个a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}。(3)如果R和S是Σ上的正规式，它们所表示的正规集分别为L(R)和L(S)，则：①
15、R∣S是Σ上的正规式，它所表示的正规集为L(R)∪L(S)；②R·S是Σ上的正规式，它所表示的正规集为L(R)L(S)；③R*是Σ上的正规式，它所表示的正规集为(L(R))*；④(R)也是Σ上的正规式，它所表示的正规集为L(R)。(4)仅由有限次使用规则(1)～(3)得到的表示式是Σ上的正规式，它所表示的集合是Σ上的正规集。原子 正规式11正规式中的运算符：
16、——或（选择）•——连接*或{}——重复（）——括号运算符的优先级：先*,后•,最后
17、•在正规式中可以省略。正规式相等这两个正规式表示的语言相等3.2正规文法与正规式12正规式：单词的词型公式正规集：符合词型
18、公式的单词的集合，是符号集运算符：从高到低的优先次序：*∙
19、正规式的定义是一种递归定义正规式等价正规式R和S，如果L(R)=L(S),则R＝S【例】∵L(b(ab)*)=L((ba)*b)，∴b(ab)*=(ba)*b∵L((a
20、b)*)=L(((a)*(b)*)*),∴(a
21、b)*=((a)*(b)*)*3.2正规文法与正规式正规式和正规集的说明13一个正规语言可以由正规文法定义，也可以由正规式定义。对任意一个正规文法，存在一个定义同一个正规语言的正规式；反之，对每个正规式，存在一个生成同一语言的正规文法。3.2正规文法与正规式正规文法和正规式的等价性14(1)令
22、S是文法G的开始符号，首先形成S→r(2)对形成的形如A→xy的正规产生式，重写为：A→xB，B→y(3)对形成的形如A→x*y的正规产生式，重写为：A→xA，A→y(4)对形成的形如A→xy*的正规产生式，重写为：A→x，A→Ay(5)对形如A→x
23、y的正规产生式，重写为：A→x，A→y(6)不断利用上述规则做变换，直到每个产生式都符合正规文法的要求。正规式转换成正规文法将Σ上的正规式r转换成文法G(VN,VT,S,P)方法如下：3.2正规文法与正规式正规文法和正规式的等价性15步骤1构造S→r步骤2不断利用下表的规则做变换,直到每个产生式最多含有一个终结符为
