詞法分析課件

詞法分析

詞法分析(LexicalAnalysis)詞法的表示詞法分析器的設(shè)計與實現(xiàn)3.1詞法分析（掃描）器的功能功能：輸入源程序，輸出(單詞)符號(token)。即：把構(gòu)成源程序的字符串轉(zhuǎn)換成單詞符號的序列單詞符號的形式按照最小的語義單位設(shè)計通常表示為二元組： （單詞符號種別，屬性值）關(guān)鍵——找出符號的分割符例如：axx=70.35+12+exp(2.7)1)單詞符號的表示常用單詞符號種別——分類（P42）各關(guān)鍵字（保留字、基本字），各種運算符，各種分界符——各用一個種別碼標識其它標識符——用一個種別碼標識常數(shù)——用一個種別碼標識屬性（值）——單詞符號的值常數(shù)的值，標識符的名字等保留字、運算符、分界符的屬性值可以省略單詞符號編碼舉例單詞符號種別編碼內(nèi)部值助記符DIM1$DIMIF2$IFDO3$DOSTOP4$STOPEND5$END標識符6內(nèi)部符號串$IDN整數(shù)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）相關(guān)問題詞法分析器可以作為一個獨立的子程序，也可以作為一遍獨立的掃描來安排。輸入緩沖區(qū)工作區(qū)(token)單詞開始指針掃描指針正拼單詞雙緩沖區(qū)并行、捻接每次移動向前指針都需要做兩次測試2）相關(guān)問題？如何設(shè)計和實現(xiàn)掃描器大小問題128Byte*2|1024Byte*2|4096Byte*2forward:=forward+1;if

forward在緩沖區(qū)第一部分末尾

then重裝緩沖區(qū)第二部分elseifforward在緩沖區(qū)第二部分末尾

thenbegin

重裝緩沖區(qū)第一部分;

將forward移到緩沖區(qū)第一部分開始

endforward:=forward+1;ifforward！=eofthenif

forward在第一部分末尾

then

重裝第二部分

elseifforward在第二部分末尾

thenbegin

重裝第一部分;

將forward

移到第一部分開始

endelse終止詞法分析/*eof

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

S→lA A→lA|dA|ε

例3-4正規(guī)式到正規(guī)文法的轉(zhuǎn)換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正規(guī)式到正規(guī)文法的轉(zhuǎn)換按如下方法構(gòu)造正規(guī)定義式，并逐步將其轉(zhuǎn)換成正則文法引入開始符號S，從如下正規(guī)定義式開始S→r對r中的形如r1|r2|…|rn的子串用產(chǎn)生式組 A→r1|r2|…|rn表示正規(guī)式到正規(guī)文法的轉(zhuǎn)換對r中的形如r1*的子串用產(chǎn)生式組A→ε|r1A表示對r中的形如r1+的子式子，用產(chǎn)生式組A→r1|r1A表示執(zhí)行連接對|的分配律對連接運算，要作特殊處理：按出現(xiàn)順序定義正規(guī)式到正規(guī)文法的轉(zhuǎn)換用到了正規(guī)定義式的概念例3-5：一個簡單詞法的正規(guī)定義式詞法規(guī)則 單詞種別 屬性<標識符>→<字母>(<字母>|<數(shù)字>)*

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

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

<減號>→- MINUS 無<星號>→* STAR 無變換為正規(guī)文法<標識符>→letter<標識符尾><標識符尾>→ε|letter<標識符尾>|digit<標識符尾><整數(shù)>→digit<整數(shù)尾><整數(shù)尾>→ε|digit<整數(shù)尾> <賦值號>→:=<加號>→+<等號>→=…(其它：實數(shù)、算術(shù)運算符、關(guān)系運算符、分號、括號等）正規(guī)文法到正規(guī)定義式的轉(zhuǎn)換代入：對于A→xB,B→y，構(gòu)造A→xy遞歸：對于A→xA|y，構(gòu)造A→x*y多候選式：對于A→x，A→y，構(gòu)造A→x|yS→0AA→1BB→2B|2C C→3C|3S→01BS→012*2CS→012*23*3S→012+3+

一個語言的文法描述不是唯一的（等價文法）3.3符號的識別──狀態(tài)轉(zhuǎn)換圖1狀態(tài)轉(zhuǎn)換圖（有窮自動機FAM=(Q，∑，δ，q0，F(xiàn))）

用來描述詞法分析器識別記號的分析過程結(jié)點：狀態(tài)用○表示；終態(tài)用◎表示有向弧──箭頭弧標記──輸入字符標識符的狀態(tài)圖<標識符>→letter(letter|digit)*

123letterletter,digit其它開始終態(tài)初態(tài)例3-5的狀態(tài)圖詞法規(guī)則 單詞種別 屬性<標識符>→letter(letter|digit)*

IDN 符號表項入口<無符號整數(shù)>→digit(digit)*

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

<減號>→- MINUS 無<星號>→* STAR 無例3-5的狀態(tài)圖letter,digitletter（IDN，入口）digitdigit

(其它)

(其它)（NUM，值）（ASG，_）=：+（ADD，_）s+（INC，_）其它IDN→letter(letter|digit)*NUM→digit(digit)*ASG→:=INC→++ADD→+利用狀態(tài)轉(zhuǎn)換圖識別單詞符號1.從初態(tài)出發(fā)2.讀入一字符3.按當前字符轉(zhuǎn)入下一狀態(tài)4.重復(fù)2,3直到無法繼續(xù)轉(zhuǎn)移在遇到讀入的字符是Token的分割符時，若當前狀態(tài)是終止狀態(tài)，說明讀入的字符組成一單詞；否則，說明輸入不符合詞法規(guī)則。2、從正規(guī)文法出發(fā)，構(gòu)造狀態(tài)圖1.以每個非終結(jié)符為狀態(tài)結(jié)點，開始符號對應(yīng)初態(tài)S2.增設(shè)一個終態(tài)TABaAa3.對于規(guī)則A→aB，畫從狀態(tài)A到B的弧，標為a4.對于規(guī)則A→a，畫從狀態(tài)A到終態(tài)T的弧，標為a*.對于規(guī)則A→rB,B→

sB，畫從狀態(tài)A到狀態(tài)N的弧，標為r和狀態(tài)N到N的標記為s的弧AsrB例3-6 Ｃ語言無符號整數(shù)的識別

1、正規(guī)定義式描述八進制數(shù):(OCT，值)oct→0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十進制數(shù):(DEC，值)dec→(1|...|9)(0|...|9)*|0十六進制數(shù):(HEX，值)hex→0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f|A|…|F)*Asr2、識別不同進制數(shù)的狀態(tài)圖342100-70-7

(其它)56101-90-9

(其它)十進制整數(shù)八進制整數(shù)oct→0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*dec→(1|...|9)(0|...|9)*|02、識別不同進制數(shù)的狀態(tài)圖910810

(其它)十六進制整數(shù)7x0-9,a-f0-9,a-f狀態(tài)圖合并1、從開始狀態(tài)出發(fā)；2、選擇輸入符號，構(gòu)成目標狀態(tài)集3、從新狀態(tài)集出發(fā)，重復(fù)1、2hex→0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f|A|…|F)*（HEX，值）（OCT，值）3、Ｃ語言無符號整數(shù)識別的狀態(tài)圖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詞法分析程序的設(shè)計與實現(xiàn)狀態(tài)轉(zhuǎn)移圖——教材P43狀態(tài)轉(zhuǎn)移圖的實現(xiàn)——教材P44-46另一種實現(xiàn)：子程序scan()輸入：字符流輸出：Symbol(Code):單詞種別Attr(value):屬性（全局變量）數(shù)據(jù)結(jié)構(gòu)與子例程數(shù)據(jù)結(jié)構(gòu)ch當前輸入字符token輸入緩沖區(qū)(字符數(shù)組)symbol單詞種別（子程序的返回值）attr屬性（全局變量）子程序Lookup(token):將token存入符號表，返回入口指針isKeyword(token):判別token是關(guān)鍵字？返回關(guān)鍵字種別或-1getchar():從輸入緩沖區(qū)中讀入一個字符放入chisdigit()isalpha()例3-3的狀態(tài)圖的實現(xiàn)算法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中的字符串變成數(shù)值→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