第3章-1-詞法器設(shè)計(jì)概述

第3章詞法分析詞法分析(LexicalAnalysis)詞法的表示詞法分析器的設(shè)計(jì)與實(shí)現(xiàn)主要內(nèi)容詞法分析器(LexicalAnalyzer,Scanner)的功能正規(guī)表達(dá)式有限狀態(tài)自動機(jī)FA——狀態(tài)圖詞法分析器的設(shè)計(jì)與實(shí)現(xiàn)3.1詞法分析（掃描）器的功能功能：輸入源程序，輸出(單詞)符號(token)。即：把構(gòu)成源程序的字符串轉(zhuǎn)換成單詞符號的序列單詞符號的形式按照最小的語義單位設(shè)計(jì)通常表示為二元組： （單詞符號種別，屬性值）關(guān)鍵——找出符號的分割符例如：axx=70.35+12+exp(2.7)1)單詞符號的表示常用單詞符號類別——分類（P79）各關(guān)鍵字（保留字、基本字），各種運(yùn)算符，各種分界符——各用一個(gè)類別碼標(biāo)識其它標(biāo)識符——用一個(gè)類別碼標(biāo)識常數(shù)——用一個(gè)類別碼標(biāo)識屬性（值）——單詞符號的值常數(shù)的值，標(biāo)識符的名字等保留字、運(yùn)算符、分界符的屬性值可以省略單詞符號編碼舉例單詞符號種別編碼內(nèi)部值助記符BEGIN1$BEGINEND2$ENDIF3$IFTHEN4$THENELSE5$ELSE標(biāo)識符6內(nèi)部符號串$IDN整數(shù)7標(biāo)準(zhǔn)二進(jìn)制$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,符號表項(xiàng)指針)!= (NE,_)N (IDN,符號表項(xiàng)指針)) (SRP,_){ (LP,_)S (IDN,符號表項(xiàng)指針) = (EQ,_)S (IDN,符號表項(xiàng)指針)++ (INC,_); (SEMI,_)pointer(IDN,符號表項(xiàng)指針)++ (INC,_); (SEMI,_)} (RP,_)2）相關(guān)問題詞法分析器可以作為一個(gè)獨(dú)立的子程序，也可以作為一遍獨(dú)立的掃描來安排。輸入緩沖區(qū)工作區(qū)(token)單詞開始指針掃描指針正拼單詞雙緩沖區(qū)并行、捻接識別標(biāo)識符的若干約定和策略一般來說，單詞的長度是有限制的在允許長度下，應(yīng)按最長匹配原則進(jìn)行識別有時(shí)需要超前掃描來進(jìn)行單詞識別。例如，F(xiàn)ORTRAN語言中的算術(shù)條件句IF(e)=L1,L2,L3和語句函數(shù)定義句IF(x)=f(x)中的IF的識別；以及<和<=、<>等。在進(jìn)行超前掃描時(shí)，還應(yīng)注意“回退”字符，即將多吃掉的字符退還回輸入緩沖區(qū)。書中P46程序3-1給出了使用堆棧實(shí)現(xiàn)多字符回退的算法。如何描述單詞的結(jié)構(gòu)、如何識別單詞1、正規(guī)文法（正規(guī)式）表示單詞的構(gòu)詞規(guī)則2、有限自動機(jī)實(shí)現(xiàn)詞法分析器，識別單詞

3.4符號的描述——正規(guī)(表達(dá))式例：標(biāo)識符的文法描述約定：用d表示數(shù)字：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)正規(guī)式：正規(guī)語言的另一種描述方法例3-2：標(biāo)識符的另一種表示l(l|d)*|表示"或"*表示Kleene閉包?符號的并列表示符號連接關(guān)系正規(guī)式r表示正規(guī)集,相應(yīng)的正規(guī)集記為L(r)正規(guī)(表達(dá))式(RegularExpression——RE)設(shè)∑是一個(gè)字母表，⑴Φ是∑上的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。運(yùn)算的優(yōu)先級運(yùn)算優(yōu)先級和結(jié)合性:*高于“連接”和|，?“連接”高于|| 具有交換律、結(jié)合律?“連接” 具有結(jié)合律、和對|的分配律()指定優(yōu)先關(guān)系意義清楚時(shí)，括號可以省略例:(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*正規(guī)式的基本等價(jià)關(guān)系(“公理”)若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)才是Σ上的正規(guī)集正規(guī)式與正規(guī)集2)正規(guī)文法與正規(guī)式正規(guī)文法與正規(guī)式等價(jià)對任何正規(guī)文法，存在定義同一語言的正規(guī)式對任何正規(guī)式，存在生成同一語言的正規(guī)文法例3-3標(biāo)識符定義的轉(zhuǎn)換引入SS→l(l|d)*引入A消除閉包S→lAA→(l|d)A|ε執(zhí)行連接對|的分配律

S→lA A→lA|dA|ε

例：一個(gè)簡單詞法的正規(guī)定義式詞法規(guī)則 單詞種別 屬性<標(biāo)識符>→<字母>(<字母>|<數(shù)字>)*

IDN 符號表項(xiàng)入口<無符號整數(shù)>→<數(shù)字>(<數(shù)字>)*

NUM 數(shù)值<賦值符>→:= ASG 無<加號>→+ + 無

<減號>→- MINUS 無<星號>→* STAR 無變換為正規(guī)文法<標(biāo)識符>→letter<標(biāo)識符尾><標(biāo)識符尾>→ε|letter<標(biāo)識符尾>|digit<標(biāo)識符尾><整數(shù)>→digit<整數(shù)尾><整數(shù)尾>→ε|digit<整數(shù)尾> <賦值號>→:=<加號>→+<等號>→=…(其它：實(shí)數(shù)、算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、分號、括號等）3.4.2由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式方法:將G視為定義所含非終結(jié)符為變量的聯(lián)立方程組,通過解方程組求得相應(yīng)的正規(guī)式.例SaS|bA|b AaS設(shè)S,A所產(chǎn)生的正規(guī)集為LS,LA則有

LS={a}LSLALA={a}LS

由定義可知,L(G)=LS,視S,A為LS,LA的正規(guī)式,相應(yīng)的關(guān)系為

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都是正規(guī)式。3.4.2由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式論斷3.1方程X=rX+t有形如X=r*t(不唯一)證:X=rX+t對應(yīng)：XrXXtLx={t,rt,rrt,rrrt,…}

S=aS+baS+b=(a+ba)S+b由論斷3.1可知,S=(a+ba)*b=(a|ba)*b.另外,對(3)連續(xù)使用兩次論斷3.1,有S=a*(baS+b)=a*baS+a*b=(a*ba)*a*b可得一副產(chǎn)品:(a|ba)*b=(a*ba)*a*b例SaAAbA|aB|bBaA

相應(yīng)的方程組為

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由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式例SbS|aAAaA|bBBaA|bC|b

CbS|aA對應(yīng)的方程組為：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由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式3.4.2由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式對于左線性文法,在解聯(lián)立方程時(shí)最終會得到形如X=Xr+t的方程,類似于論斷3.1,可知其有解X=tr*3.4.2由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式例:標(biāo)示符文法

標(biāo)識符<標(biāo)識符>字母|<標(biāo)識符>數(shù)字|字母對應(yīng)的方程為：

標(biāo)識符=<標(biāo)識符>字母+<標(biāo)識符>數(shù)字+字母標(biāo)識符=<標(biāo)識符>(字母+數(shù)字)+字母標(biāo)識符=字母(字母+數(shù)字)*標(biāo)識符=字母(字母|數(shù)字)*3.4.2由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式例SSa|AbAAb|BaBAb|Ca|a

CSa|Ab對應(yīng)的方程組為：

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

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