第3章-1-词法器设计概述

第3章词法分析词法分析(LexicalAnalysis)词法的表示词法分析器的设计与实现主要内容词法分析器(LexicalAnalyzer,Scanner)的功能正规表达式有限状态自动机FA——状态图词法分析器的设计与实现3.1词法分析（扫描）器的功能功能：输入源程序，输出(单词)符号(token)。即：把构成源程序的字符串转换成单词符号的序列单词符号的形式按照最小的语义单位设计通常表示为二元组： （单词符号种别，属性值）关键——找出符号的分割符例如：axx=70.35+12+exp(2.7)1)单词符号的表示常用单词符号类别——分类（P79）各关键字（保留字、基本字），各种运算符，各种分界符——各用一个类别码标识其它标识符——用一个类别码标识常数——用一个类别码标识属性（值）——单词符号的值常数的值，标识符的名字等保留字、运算符、分界符的属性值可以省略单词符号编码举例单词符号种别编码内部值助记符BEGIN1$BEGINEND2$ENDIF3$IFTHEN4$THENELSE5$ELSE标识符6内部符号串$IDN整数7标准二进制$INT=8$ASG+9$PLUS*10$STAR>11$GT<12$LT（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)单词开始指针扫描指针正拼单词双缓冲区并行、捻接识别标识符的若干约定和策略一般来说，单词的长度是有限制的在允许长度下，应按最长匹配原则进行识别有时需要超前扫描来进行单词识别。例如，FORTRAN语言中的算术条件句IF(e)=L1,L2,L3和语句函数定义句IF(x)=f(x)中的IF的识别；以及<和<=、<>等。在进行超前扫描时，还应注意“回退”字符，即将多吃掉的字符退还回输入缓冲区。书中P46程序3-1给出了使用堆栈实现多字符回退的算法。如何描述单词的结构、如何识别单词1、正规文法（正规式）表示单词的构词规则2、有限自动机实现词法分析器，识别单词

3.4符号的描述——正规(表达)式例：标识符的文法描述约定：用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。运算的优先级运算优先级和结合性:*高于“连接”和|，•“连接”高于|| 具有交换律、结合律•“连接” 具有结合律、和对|的分配律()指定优先关系意义清楚时，括号可以省略例:(a|b)*及(a*b*)*b(ab)*及(ba)*bA1.r|s=s|r A2.r|r=r A3.r|=r A4.(r|s)|t=r|(s|t)A5.(rs)t=r(st)A6.r(s|t)=rs|rtA7.(s|t)r=sr|st A8.r=r=A9.r=r=r A10.r*=(|r)*=|rr*正规式的基本等价关系(“公理”)若两个正规式所表示的正规集相同，则认为二者等价才是Σ上的正规集正规式与正规集2)正规文法与正规式正规文法与正规式等价对任何正规文法，存在定义同一语言的正规式对任何正规式，存在生成同一语言的正规文法例3-3标识符定义的转换引入SS→l(l|d)*引入A消除闭包S→lAA→(l|d)A|ε执行连接对|的分配律

S→lA A→lA|dA|ε

例：一个简单词法的正规定义式词法规则 单词种别 属性<标识符>→<字母>(<字母>|<数字>)*

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

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

<减号>→- MINUS 无<星号>→* STAR 无变换为正规文法<标识符>→letter<标识符尾><标识符尾>→ε|letter<标识符尾>|digit<标识符尾><整数>→digit<整数尾><整数尾>→ε|digit<整数尾> <赋值号>→:=<加号>→+<等号>→=…(其它：实数、算术运算符、关系运算符、分号、括号等）3.4.2由正规文法构造相应的正规式方法:将G视为定义所含非终结符为变量的联立方程组,通过解方程组求得相应的正规式.例SaS|bA|b AaS设S,A所产生的正规集为LS,LA则有

LS={a}LS{b}LA{b}LA={a}LS

由定义可知,L(G)=LS,视S,A为LS,LA的正规式,相应的关系为

S=aS|bA|bA=aS记‘|’为‘+’,

有S=aS+bA+b(1)A=aS(2)

将(2)代入(1),

得S=aS+baS+b=(a+ba)S+b(3)

得到形如 X=rX+t的方程,r,t都是正规式。3.4.2由正规文法构造相应的正规式论断3.1方程X=rX+t有形如X=r*t(不唯一)证:X=rX+t对应：XrXXtLx={t,rt,rrt,rrrt,…}

S=aS+baS+b=(a+ba)S+b由论断3.1可知,S=(a+ba)*b=(a|ba)*b.另外,对(3)连续使用两次论断3.1,有S=a*(baS+b)=a*baS+a*b=(a*ba)*a*b可得一副产品:(a|ba)*b=(a*ba)*a*b例SaAAbA|aB|bBaA

相应的方程组为

S=aA(1) A=bA+aB+b(2)B=aA(3) (3)代入(2): A=(b+aa)A+b得 A=(b+aa)*b

代入(1): S=a(b+aa)*b=a(b|aa)*b3.4.2由正规文法构造相应的正规式例SbS|aAAaA|bBBaA|bC|b

CbS|aA对应的方程组为：S=bS+aA(1)A=aA+bB(2)B=aA+bC+b(3)

C=bS+aA(4)

由(1),(4)得，C=S，代入(3)中B=S+b，代入(2)中，A=S+bb，代入(1)中S=(a+b)S+abbS=(a+b)abb*=(a|b)abb*3.4.2由正规文法构造相应的正规式3.4.2由正规文法构造相应的正规式对于左线性文法,在解联立方程时最终会得到形如X=Xr+t的方程,类似于论断3.1,可知其有解X=tr*3.4.2由正规文法构造相应的正规式例:标示符文法

标识符<标识符>字母|<标识符>数字|字母对应的方程为：

标识符=<标识符>字母+<标识符>数字+字母标识符=<标识符>(字母+数字)+字母标识符=字母(字母+数字)*标识符=字母(字母|数字)*3.4.2由正规文法构造相应的正规式例SSa|AbAAb|BaBAb|Ca|a

CSa|Ab对应的方程组为：

S=Sa+AbA=Ab+BaB=Ab+Ca+a

C=Sa+Ab由(1),(4)得，C=S，代入(3)中B=S+a