第3章 词法分析1.ppt

1、第3章 词法分析,2020年7月28日,1,内容提要,1、词法分析的功能 2、词法分析结果表示 3、正则文法及状态图 4、词法分析程序的设计与实现,2020年7月28日,2,3.1词法分析的功能,（1）分析和识别单词及属性，包括识别语言的关键字、标识符、常数、运算符等； （2）跳过各种分隔符，如空格，回车，制表符等； （3）删除注释； （4）进行词法检查，报告所发现的错误； （5）建立符号表。,main( )/*ADD*/ int x=10,y=20,sum; sum=x+y; ,2020年7月28日,3,实现方案：基本上有两种,1.词法分析单独作为一遍,2.词法分析程序作为语法分析的子程序,

2、S.P.(字符串),词法分析,S.P.(单词串),语法分析,第一遍,第二遍,单词串,优点: 结构清晰、各遍功能单一 缺点：效率低,2020年7月28日,4,3.2 词法分析结果表示,词法分析的输出常采用二元组。 单词类别用一个整数类码或单词记号表示。 单词记号比整数码含义明确。例如，保留字for，可直接用字符串for作为单词记号来表示 整数类码，含义不直观。 单词类别如何分类、分成几类、怎样编码，主要取决于技术处理上的方便。标识符一般归为一类，常数则按类型（整数、实数等）分类。保留字即可将全体定为一类，也可一字一类。分界符可单独作为一类，也可采用一符一类的分法。,2020年7月28日,5,3.

3、3 正则文法及状态图,程序设计语言的单词符号可用正则文法来描述。 正则文法所描述的语言可用有穷自动机来识别。 自动机的非形式表示，即状态图。 为识别单词而专门设计的有向图，是设计词法分析程序的一种好途径。,2020年7月28日,6,状态图 状态图是一张有穷的有向图。结点代表状态，用圆圈表示，状态间用有向弧连接，弧上有标记符号，表示在弧线射出端的状态下，读入弧上标记的符号可转换到弧指向的状态。 状态图只有有穷个状态，其中只有一个开始状态，至少有一个结束状态，结束状态常用双圈表示。,2020年7月28日,7,由正则文法构造状态图,（1）对于右线性文法 步骤1 增加结点Z为终态； 步骤2 将每个非终

4、结符号设置为一个对应的状态；将开始符号作为初态。 步骤3 对于Aa，引一条从A到Z的弧，弧上标记为a；而对于AaB，引一条从A到B的弧，弧上标记为a。,SlA A|lA|dA,2020年7月28日,8,（2）对于左线性文法 步骤1 增加结点S为初态； 步骤2 将每个非终结符号设置为一个对应的状态；文法中的开始符号对应的结点为终结状态 步骤3 对于Aa，引一条从S到A的弧，弧上标记为a；而对于ABa，引一条从B到A的弧，弧上标记为a。,Al|Al|Ad,2020年7月28日,9,例3.1，设有正则文法GZ： ZU0|V1 UZ1|1 VZ0|0 画出该文法对应的状态图。,解：1、根据正则文法是左

5、线性还是右线性以及非终结符的数量，确定状态图的结点数量以及开始状态和结束状态。 2、根据产生式画状态图。 思考：该文法确定的语言是什么？,S,U,V,Z,0,0,0,1,1,1,2020年7月28日,10,3.3.2 状态图的用法,利用状态图可分析和识别字符串，其方法如下： 1.设初始状态S为当前状态。从输入串的最左字符开始重复步骤2，直到到达输入串的右端为止。 2.扫描输入串的下一个字符，在当前状态所射出的弧中，找出标记有该字符的弧，并沿此弧前进，过渡到下一个状态。 如果找不到标记有该字符的弧，则说明输入串不合法，分析过程失败结束； 如果扫描输入串的最后一个字符，并从当前状态出发沿着标记有该

6、字符的弧到达终结状态，则表示输入串合法，识别过程成功结束； 如果扫描输入串的最后一个符号后到达的状态不是状态图的终结状态，则表示输入串不合法，识别过程失败结束。,2020年7月28日,11,3.3.2 状态图的用法,例3.2，对句子0110进行分析。,Z,U,0,Z,1,V,1,0,3.5（a）输入串0110分析过程,图3.5（b）输入串0110的语法树,正则文法GZ： （1）ZU0|V1 （2）UZ1|1 （3）VZ0|0,2020年7月28日,12,利用状态图（由左线性文法构造）识别句子的方法是一种自底向上的分析方法。 开始时，处于开始状态，此时句柄是随后扫描的字符，即输入串的的第一个符号

7、，所要归约的符号就是从开始状态经过标记有句柄符号的弧到达的下一个状态的名字。 以后每一步（除第一步外）的句柄是当前状态的名字和随后扫描的字符，而句柄所要归约的符号就是下一个状态的名字。 问题：右线性文法构造的状态图？,2020年7月28日,13,状态图的应用,问题： 一个人带着狼、山羊和白菜在一条河的左岸，有一条船，大小正好能装下这个人和其它3件东西中的一件。人和他的随行物都要过到河的右岸。人每次只能将一件东西摆渡过河。但若人将狼和羊留在同一岸而无人照顾的话，狼将把羊吃掉，类似的，羊也可能会吃掉白菜。请问是否有可能摆渡过河，并使得羊和白菜都不会被吃掉？,2020年7月28日,14,分析：人和物

8、件在左右岸的组合构成问题的所有状态。状态表示：左岸组合，右岸组合，令M = 人，W= 狼，G = 山羊，C = 白菜,则所有状态为： C(4,0): M,W,G,C, ; ,M,W,G,C ; C(4,1): W,G,C,M; M,G,C,W; M,W,C,G ; M,W,G,C; M, W,G,C; W,M,G,C; G , M,W,C; C , M,W,G; C(4,2): M,G,W,C ; M, C,W,G ; M,W,G,C ; W,G,M,C ; W,C, M,G; G,C, M,W; 去除不安全状态，剩下10有用状态，画出状态图。 问题：如何编程求出所有状态？ 问题等价于求集合的

9、幂集,2020年7月28日,15,由状态图可知有两种渡河方案,2020年7月28日,16,2020年7月28日,3.4 词法分析程序的设计与实现,（1）根据词法规则写出正则文法； （2）将正则文法转换成状态图； （3）将状态图转换成流程图。,17,2020年7月28日,标识符:由字母打头的字母数字组合 关键字：标识符的子集 无符号整数：任意数字组合 运算符： +、*、= 分界符：,、;,例：假设某语言的单词符号的子集有：,构造此语言子集的词法分析程序。,18,2020年7月28日,（1）根据词法规则写出正则文法,| | + | * | 0|1|2|3|4|5|6|7|8|9 a|b|c|z|A

10、|B|C|Z,19,标识符:由字母打头的字母数字组合 关键字：标识符的子集 无符号整数：任意数字组合 运算符： +、*、= 分界符：,、;,2020年7月28日,20,| | | + | * | 0|1|2|3|4|5|6|7|8|9 a|b|c|z|A|B|C|Z, a|b|c|z|A|B|C|Z|a|z |A|Z|0|9 0|1|2|3|4|5|6|7|8|9| 0|9 + | * | =,2020年7月28日,（2）将正则文法转换成状态图,21, a|b|c|z|A|B|C|Z| a|z |A|Z|0|9 0|1|2|3|4|5|6|7|8|9| 0|9 + | * | =,2020年7

11、月28日,合并 将初始状态合并为一个唯一的初态； 化简调整状态冲突并对冲突状态重新编号； 如有必要，增加出错状态。,22,2020年7月28日,（3）将状态图转换成流程图,写出词法分析程序,23,含有分支或回路的状态示意 (a) 含分支的状态i； (b) 含回路的状态i,2020年7月28日,24,2020年7月28日,不含回路的分支状态可对应一个switch( )语句或一组if-else语句。例如，上图(a)的状态i所对应的switch语句如下：,s=getchar ( ); switch (s) case a: case b: case z: ; /*实现状态j功能的语句*/ case 0: case 1: