03第3章 词法分析1

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第,3,章 词法分析,2024年10月2日,1,内容提要,1,、词法分析的功能,2,、词法分析结果表示,3,、正则文法及状态图,4,、词法分析程序的设计与实现,2024年10月2日,2,3.1,词法分析的功能,（,1,）分析和识别单词及属性，包括识别语言的关键字、标识符、常数、运算符等；,（,2,）跳过各种分隔符，如空格，回车，制表符等；,（,3,）删除注释；,（,4,）进行词法检查，报告所发现的错误；,（,5,）建立符号表。,main( )/*ADD*/,int x=10,y=20,sum;,sum=x+y;,main,、,(,、,),、,、,int,、,x,、,=,、,10,、,、,y,、,=,、,20,、,、,sum,、,;,、,sum,、,=,、,x,、,+,、,y,、,;,、,词法分析,2024年10月2日,3,实现方案：基本上有两种,1.,词法分析单独作为一遍,2.,词法分析程序作为语法分析的子程序,S.P.(,字符串,),词法分析,S.P.(,单词串,),语法分析,第一遍,第二遍,单词串,优点,:,结构清晰、各遍功能单一,缺点：效率低,S.P.(,字符串,),词法分,析程序,语法分,析程序,取单词,单词,2024年10月2日,4,3.2,词法分析结果表示,词法分析的输出常采用二元组。,单词类别用一个整数类码或单词记号表示。,单词记号比整数码含义明确。例如，保留字,for,，可直接用字符串,for,作为单词记号来表示,整数类码，含义不直观。,单词类别如何分类、分成几类、怎样编码，主要取决于技术处理上的方便。标识符一般归为一类，常数则按类型（整数、实数等）分类。保留字即可将全体定为一类，也可一字一类。分界符可单独作为一类，也可采用一符一类的分法。,单词类别,单词值,2024年10月2日,5,3.3,正则文法及状态图,程序设计语言的单词符号可用正则文法来描述。,正则文法所描述的语言可用有穷自动机来识别。,自动机的非形式表示，即状态图。,为识别单词而专门设计的有向图，是设计词法分析程序的一种好途径。,2024年10月2日,6,状态图,状态图是一张有穷的有向图。结点代表状态，用圆圈表示，状态间用有向弧连接，弧上有标记符号，表示在弧线射出端的状态下，读入弧上标记的符号可转换到弧指向的状态。,状态图只有有穷个状态，其中只有一个开始状态，至少有一个结束状态，结束状态常用双圈表示。,2024年10月2日,7,由正则文法构造状态图,（,1,）对于右线性文法,步骤,1,增加结点,Z,为终态；,步骤,2,将每个非终结符号设置为一个对应的状态；将开始符号作为初态。,步骤,3,对于,Aa,，引一条从,A,到,Z,的弧，弧上标记为,a,；而对于,AaB,，引一条从,A,到,B,的弧，弧上标记为,a,。,SlA,A|lA|dA,l|d,A,Z,S,l,S,A,l,l|d,2024年10月2日,8,（,2,）对于左线性文法,步骤,1,增加结点,S,为初态；,步骤,2,将每个非终结符号设置为一个对应的状态；文法中的开始符号对应的结点为终结状态,步骤,3,对于,Aa,，引一条从,S,到,A,的弧，弧上标记为,a,；而对于,ABa,，引一条从,B,到,A,的弧，弧上标记为,a,。,Al|Al|Ad,l|d,A,S,l,SlA,A|lA|dA,2024年10月2日,9,例,3.1,，设有正则文法,GZ,：,ZU0|V1,UZ1|1,VZ0|0,画出该文法对应的状态图。,解：,1,、根据正则文法是左线性还是右线性以及非终结符的数量，确定状态图的结点数量以及开始状态和结束状态。,2,、根据产生式画状态图。,思考：该文法确定的语言是什么？,S,U,V,Z,0,0,0,1,1,1,2024年10月2日,10,3.3.2,状态图的用法,利用状态图可分析和识别字符串，其方法如下：,1.,设初始状态,S,为当前状态。从输入串的最左字符开始重复步骤,2,，直到到达输入串的右端为止。,2.,扫描输入串的下一个字符，在当前状态所射出的弧中，找出标记有该字符的弧，并沿此弧前进，过渡到下一个状态。,如果找不到标记有该字符的弧，则说明输入串不合法，分析过程失败结束；,如果扫描输入串的最后一个字符，并从当前状态出发沿着标记有该字符的弧到达终结状态，则表示输入串合法，识别过程成功结束；,如果扫描输入串的最后一个符号后到达的状态不是状态图的终结状态，则表示输入串不合法，识别过程失败结束。,2024年10月2日,11,3.3.2,状态图的用法,例,3.2,，对句子,0110,进行分析。,步骤,状态,扫描的字符,余留部分,1,S,0,110,2,V,1,10,3,Z,1,0,4,U,0,5,Z,Z,U,0,Z,1,V,1,0,3.5,（,a,）输入串,0110,分析过程,图,3.5,（,b,）输入串,0110,的语法树,S,U,V,Z,0,0,0,1,1,1,正则文法,GZ,：,（,1,）,ZU0|V1,（,2,）,UZ1|1,（,3,）,VZ0|0,2024年10月2日,12,利用状态图（由左线性文法构造）识别句子的方法是一种自底向上的分析方法。,开始时，处于开始状态，此时句柄是随后扫描的字符，即输入串的的第一个符号，所要归约的符号就是从开始状态经过标记有句柄符号的弧到达的下一个状态的名字。,以后每一步（除第一步外）的句柄是当前状态的名字和随后扫描的字符，而句柄所要归约的符号就是下一个状态的名字。,问题：右线性文法构造的状态图？,2024年10月2日,13,状态图的应用,问题：,一个人带着狼、山羊和白菜在一条河的左岸，有一条船，大小正好能装下这个人和其它,3,件东西中的一件。人和他的随行物都要过到河的右岸。人每次只能将一件东西摆渡过河。但若人将狼和羊留在同一岸而无人照顾的话，狼将把羊吃掉，类似的，羊也可能会吃掉白菜。请问是否有可能摆渡过河，并使得羊和白菜都不会被吃掉？,2024年10月2日,14,分析：人和物件在左右岸的组合构成问题的所有状态。状态表示：,左岸组合,，,右岸组合,，令,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,有用状态，画出状态图。,问题：如何编程求出所有状态？,问题等价于求集合的幂集,2024年10月2日,15,由状态图可知有两种渡河方案,2024年10月2日,16,2024年10月2日,词法规则 正则文法 状态图 分析程序,3.4,词法分析程序的设计与实现,（,1,）,根据词法规则写出正则文法；,（,2,）,将正则文法转换成状态图；,（,3,）,将状态图转换成流程图。,17,2024年10月2日,标识符,:,由字母打头的字母数字组合,关键字：标识符的子集,无符号整数：任意数字组合,运算符：,+,、*、,、,=,分界符：,、,;,例：假设某语言的单词符号的子集有：,构造此语言子集的词法分析程序。,18,2024年10月2日,（,1,）根据词法规则写出正则文法,|,|, + | * | |, | ;|=, =,0|1|2|3|4|5|6|7|8|9,a|b|c|,|z|A|B|C|,|Z,19,标识符,:,由字母打头的字母数字组合,关键字：标识符的子集,无符号整数：任意数字组合,运算符：,+,、*、,、,=,分界符：,、,;,2024年10月2日,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, + | * | |, | ;|=, =,2024年10月2日,（,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, + | * | |, | ;|=, =,2024年10月2日,合并, 将初始状态合并为一个唯一的初态；, 化简调整状态冲突并对冲突状态重新编号；, 如有必要，增加出错状态。,22,2024年10月2日,（,3,）,将状态图转换成流程图,写出词法分析程序,23,含有分支或回路的状态示意,(a),含分支的状态,i,；,(b),含回路的状态,i,2024年10月2日,24,2024年10月2日,不含回路的分支状态可对应一个,switch( ),语句或一组,if-else,语句。例如，上图,(a),的状态,i,所对应的,switch,语句如下：,s=getchar ( );,switch (s), case a:,case b:,case z:,; /*,实现状态,j,功能的语句*,/,case 0:,case 1:,case 9:,; /*,实现状态,k,功能的语句*,/,25,s=getchar ( );,while (isalpha(s)|isdigit(s ),s = getchar ();,; /*,实现状态,j,功能的语句*,/,终态一般对应一个,return( ),语句；,return,意味着从词法分析器返回到调用段，一般指返回到语法分析器。,2024年10月2日,