词法分析课件

詞法分析

詞法分析(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其他:出錯處理18END