词法分析课件

词法分析

词法分析(LexicalAnalysis)词法的表示词法分析器的设计与实现3.1词法分析（扫描）器的功能功能：输入源程序，输出(单词)符号(token)。即：把构成源程序的字符串转换成单词符号的序列单词符号的形式按照最小的语义单位设计通常表示为二元组： （单词符号种别，属性值）关键——找出符号的分割符例如：axx=70.35+12+exp(2.7)1)单词符号的表示常用单词符号种别——分类（P42）各关键字（保留字、基本字），各种运算符，各种分界符——各用一个种别码标识其它标识符——用一个种别码标识常数——用一个种别码标识属性（值）——单词符号的值常数的值，标识符的名字等保留字、运算符、分界符的属性值可以省略单词符号编码举例单词符号种别编码内部值助记符DIM1$DIMIF2$IFDO3$DOSTOP4$STOPEND5$END标识符6内部符号串$IDN整数7标准二进制$INT=8$ASG+9$PLUS*10$STAR**11$POWER，12$COMMA（13$SLP）14$SRP例3-1:单词符号序列

while(pointer!=N){S=S++;pointer++;}

while (WHILE,_)( (SLP,_)pointer (IDN,符号表项指针)!= (NE,_)N (IDN,符号表项指针)) (SRP,_){ (LP,_)S (IDN,符号表项指针) = (EQ,_)S (IDN,符号表项指针)++ (INC,_); (SEMI,_)pointer(IDN,符号表项指针)++ (INC,_); (SEMI,_)} (RP,_)2）相关问题词法分析器可以作为一个独立的子程序，也可以作为一遍独立的扫描来安排。输入缓冲区工作区(token)单词开始指针扫描指针正拼单词双缓冲区并行、捻接每次移动向前指针都需要做两次测试2）相关问题？如何设计和实现扫描器大小问题128Byte*2|1024Byte*2|4096Byte*2forward:=forward+1;if

forward在缓冲区第一部分末尾

then重装缓冲区第二部分elseifforward在缓冲区第二部分末尾

thenbegin

重装缓冲区第一部分;

将forward移到缓冲区第一部分开始

endforward:=forward+1;ifforward！=eofthenif

forward在第一部分末尾

then

重装第二部分

elseifforward在第二部分末尾

thenbegin

重装第一部分;

将forward

移到第一部分开始

endelse终止词法分析/*eof

在表示输入结束*/3.2符号的描述——正规(表达)式例：标识符的文法描述约定：用d表示数字：0,1,2,…,9;

用l表示字母：A,B,…,Z,a,b,…,zG=({d,l},{S,T},P,S)S→lS→SdS→Sl左线性文法S→l|lTT→lT|lT→dT|d右线性文法表示集合：{l}{l,d}*

1)正规式：正规语言的另一种描述方法例3-2：标识符的另一种表示l(l|d)*|表示"或"*表示Kleene闭包符号的并列表示符号连接关系正规式r表示正规集,相应的正规集记为L(r)正规(表达)式(RegularExpression——RE)设∑是一个字母表，⑴Φ是∑上的RE，L(Φ)=Φ；⑵ε是∑上的RE，L(ε)={ε}；⑶对于

a∈∑，a是RE，L(a)={a}；⑷如果r和s是RE，L(r)=R,L(s)=S，则：

r与s的“和”(r|s)是RE，L(r|s)=R∪S；

r与s的“乘积”(rs)是RE，L(rs)=RS；

r的克林闭包(r*)是RE，L(r*)=R*。⑸只有满足⑴、⑵、⑶、⑷的才是RE。运算的优先级运算优先级和结合性:*高于“连接”和|，“连接”高于|| 具有交换律、结合律“连接” 具有结合律、和对|的分配律()指定优先关系意义清楚时，括号可以省略例：L(a(a|b)*(ε|((.|_)(a|b)(a|b)*))){a}{a,b}*({ε}∪{.,_}{a,b}{a,b}*)2)正规文法与正规式正规文法与正规式等价对任何正规文法，存在定义同一语言的正规式对任何正规式，存在生成同一语言的正规文法例3-3标识符定义的转换引入SS→l(l|d)*引入A消除闭包S→lAA→(l|d)A|ε执行连接对|的分配律

S→lA A→lA|dA|ε

例3-4正规式到正规文法的转换a(a|b)*(ε|((.|_)(a|b)(a|b)*)) =a(a|b)* |a(a|b)*.(a(a|b)*|b(a|b)*) |a(a|b)*_(a(a|b)*|b(a|b)*) =aA|aCA→aA|bA|εC→aC|bC|.B|_BB→aA|bAS→aA|aCA→aA|bA|εC→aC|bC|.B|_BB→aA|bA正规式到正规文法的转换按如下方法构造正规定义式，并逐步将其转换成正则文法引入开始符号S，从如下正规定义式开始S→r对r中的形如r1|r2|…|rn的子串用产生式组 A→r1|r2|…|rn表示正规式到正规文法的转换对r中的形如r1*的子串用产生式组A→ε|r1A表示对r中的形如r1+的子式子，用产生式组A→r1|r1A表示执行连接对|的分配律对连接运算，要作特殊处理：按出现顺序定义正规式到正规文法的转换用到了正规定义式的概念例3-5：一个简单词法的正规定义式词法规则 单词种别 属性<标识符>→<字母>(<字母>|<数字>)*

IDN 符号表项入口<无符号整数>→<数字>(<数字>)*

NUM 数值<赋值符>→:= ASG 无<加号>→+ + 无

<减号>→- MINUS 无<星号>→* STAR 无变换为正规文法<标识符>→letter<标识符尾><标识符尾>→ε|letter<标识符尾>|digit<标识符尾><整数>→digit<整数尾><整数尾>→ε|digit<整数尾> <赋值号>→:=<加号>→+<等号>→=…(其它：实数、算术运算符、关系运算符、分号、括号等）正规文法到正规定义式的转换代入：对于A→xB,B→y，构造A→xy递归：对于A→xA|y，构造A→x*y多候选式：对于A→x，A→y，构造A→x|yS→0AA→1BB→2B|2C C→3C|3S→01BS→012*2CS→012*23*3S→012+3+

一个语言的文法描述不是唯一的（等价文法）3.3符号的识别──状态转换图1状态转换图（有穷自动机FAM=(Q，∑，δ，q0，F)）

用来描述词法分析器识别记号的分析过程结点：状态用○表示；终态用◎表示有向弧──箭头弧标记──输入字符标识符的状态图<标识符>→letter(letter|digit)*

123letterletter,digit其它开始终态初态例3-5的状态图词法规则 单词种别 属性<标识符>→letter(letter|digit)*

IDN 符号表项入口<无符号整数>→digit(digit)*

NUM 数值<赋值符>→:= ASG 无<加号>→+ + 无

<减号>→- MINUS 无<星号>→* STAR 无例3-5的状态图letter,digitletter（IDN，入口）digitdigit

(其它)

(其它)（NUM，值）（ASG，_）=：+（ADD，_）s+（INC，_）其它IDN→letter(letter|digit)*NUM→digit(digit)*ASG→:=INC→++ADD→+利用状态转换图识别单词符号1.从初态出发2.读入一字符3.按当前字符转入下一状态4.重复2,3直到无法继续转移在遇到读入的字符是Token的分割符时，若当前状态是终止状态，说明读入的字符组成一单词；否则，说明输入不符合词法规则。2、从正规文法出发，构造状态图1.以每个非终结符为状态结点，开始符号对应初态S2.增设一个终态TABaAa3.对于规则A→aB，画从状态A到B的弧，标为a4.对于规则A→a，画从状态A到终态T的弧，标为a*.对于规则A→rB,B→

sB，画从状态A到状态N的弧，标为r和状态N到N的标记为s的弧AsrB例3-6 Ｃ语言无符号整数的识别

1、正规定义式描述八进制数:(OCT，值)oct→0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十进制数:(DEC，值)dec→(1|...|9)(0|...|9)*|0十六进制数:(HEX，值)hex→0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f|A|…|F)*Asr2、识别不同进制数的状态图342100-70-7

(其它)56101-90-9

(其它)十进制整数八进制整数oct→0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*dec→(1|...|9)(0|...|9)*|02、识别不同进制数的状态图910810

(其它)十六进制整数7x0-9,a-f0-9,a-f状态图合并1、从开始状态出发；2、选择输入符号，构成目标状态集3、从新状态集出发，重复1、2hex→0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f|A|…|F)*（HEX，值）（OCT，值）3、Ｃ语言无符号整数识别的状态图9810其它2,6,7x0-9,a-f0-9,a-f30-70-7其它51-90-9其它（DEC，值）其它4106另一种做法开始12061-93x0-9,a-f40-9,a-f其它0-9其它50-70-7其它（DEC，值）（HEX，值）（OCT，值）其它3.4词法分析程序的设计与实现状态转移图——教材P43状态转移图的实现——教材P44-46另一种实现：子程序scan()输入：字符流输出：Symbol(Code):单词种别Attr(value):属性（全局变量）数据结构与子例程数据结构ch当前输入字符token输入缓冲区(字符数组)symbol单词种别（子程序的返回值）attr属性（全局变量）子程序Lookup(token):将token存入符号表，返回入口指针isKeyword(token):判别token是关键字？返回关键字种别或-1getchar():从输入缓冲区中读入一个字符放入chisdigit()isalpha()例3-3的状态图的实现算法1.getchar()2.WHILEch是空格 //跳过空格2.1DOgetchar();3.CASEchOF4.isdigit(ch):4.1ch→token;getchar();4.2WHILEisdigit(ch)DO{ch→token;getchar();}4.3输入指针回退一个字符；4.4将token中的字符串变成数值→attr4.5返回NUM5.isalpha(ch):5.1ch→token;getchar();5.2WHILEisalpha(ch)ORisdigit(ch)DO{ch→token;getchar()};5.3 输入指针回退一个字符;5.4key=isKeyword(token);5.5IFkey≥0THEN返回key5.6Lookup(token)→attr;5.7返回IDN6':':getchar();6.1IFch等于'='THEN返回ASG6.2出错处理7'+':返回ADD8'-':返回SUB9'*':返回MUL10'/':返回DIV11'=':返回EQ12'>':返回GT13'<':返回LT14'(':返回LP15')':返回RP16';':返回SEMI17其它:出错处理18E