我們之前意見(jiàn)寫好了自動(dòng)機(jī)，接下來(lái)用自動(dòng)機(jī)來(lái)構(gòu)建語(yǔ)法分析表。
語(yǔ)法分析表由兩部分組成，一個(gè)語(yǔ)法分析動(dòng)作函數(shù)ACTION和一個(gè)轉(zhuǎn)換函數(shù)GOTO
- ACTION函數(shù)有兩個(gè)參數(shù)：一個(gè)是狀態(tài)i，另一個(gè)是終結(jié)符號(hào)a（或是輸入標(biāo)記符號(hào)$），ACTION[i,a]有四種形式:
- 移入j，j是一個(gè)狀態(tài)
- 歸約A->β
- 接受
- 報(bào)錯(cuò)
2.我們把定義在項(xiàng)集上的GOTO函數(shù)拓展為定義在狀態(tài)集上的函數(shù)：如果GOTO[Ii,A] = Ii，那么GOTO也把狀態(tài)i和一個(gè)非終結(jié)符號(hào)A映射到狀態(tài)j。
構(gòu)建表示，我們約定：
- si表示移入并將狀態(tài)i壓棧
- rj表示按照編號(hào)j的產(chǎn)生式歸約
- acc表示接受
- 空白表示報(bào)錯(cuò)
示例文法：
E ——> E + T | T
T ——> T * F | F
F ——> ( E ) | id
構(gòu)建自動(dòng)機(jī)：
構(gòu)建語(yǔ)法分析表：
構(gòu)建算法：
假設(shè)已構(gòu)造出LR(0)項(xiàng)目集規(guī)范族為：C={I0,I1, … , In}，其中Ik為項(xiàng)目集的名字，k為狀態(tài)名，令包含S′→·S項(xiàng)目的集合Ik的下標(biāo)k為分析器的初始狀態(tài)。那么分析表的ACTION表和GOTO表構(gòu)造步驟為：
① 若項(xiàng)目A→α·aβ屬于Ik且轉(zhuǎn)換函數(shù)GO(Ik,a)= Ij，當(dāng)a為終結(jié)符時(shí)則置ACTION[k,a]為Sj?！?br>
② 若項(xiàng)目A→α· 屬于Ik，則對(duì)任何終結(jié)符a 和’#'號(hào)置ACTION[k,a]和ACTION[k,#]為”rj”，j為在文法G′中某產(chǎn)生式A→α的序號(hào)。
?、?若GO(Ik,A)＝Ij，則置GOTO[k,A]為”j”，其中A為非終結(jié)符。
?、?若項(xiàng)目S′→S·屬于Ik，則置ACTION[k,#]為”acc”，表示接受。
?、?凡不能用上述方法填入的分析表的元素，均應(yīng)填上”報(bào)錯(cuò)標(biāo)志”。為了表的清晰我們僅用空白表示錯(cuò)誤標(biāo)志。
