第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