LR語(yǔ)法分析器
特點(diǎn)：
1）由表格驅(qū)動(dòng)
2）幾乎適用所有程序設(shè)計(jì)語(yǔ)言
3）無(wú)回溯的移入歸約技術(shù)
4）可以盡早檢測(cè)到錯(cuò)誤
項(xiàng)
什么是項(xiàng)？這里所說(shuō)的項(xiàng)是一種狀態(tài)，用來(lái)在LR語(yǔ)法分析中對(duì)集合進(jìn)行描述。
例如產(chǎn)生式 A -> XYZ 會(huì)有四個(gè)項(xiàng)
A -> ?XYZ
A -> X?YZ
A -> XY?Z
A -> XYZ?
產(chǎn)生式 A -> ε 只有一個(gè)項(xiàng) A -> ?
一個(gè)規(guī)范的LR（0）項(xiàng)族集提供了構(gòu)建確定有窮自動(dòng)機(jī)的基礎(chǔ)燕侠。稱為L(zhǎng)R（0）自動(dòng)機(jī)裙戏。
LR（0）項(xiàng)集中的項(xiàng)共分為四大類：
1）歸約項(xiàng)目：歸約結(jié)束，原點(diǎn)在最右端橘券。如：A -> a?
2）接收項(xiàng)目：左端為 S' 的歸約項(xiàng)目。如：S' -> a?
3）待約項(xiàng)目：原點(diǎn)后為非終結(jié)符的項(xiàng)目卿吐。如：A -> α?Bβ
4）移進(jìn)項(xiàng)目：原點(diǎn)后為終結(jié)符的項(xiàng)目旁舰。如：A -> α?aβ
LR（0）自動(dòng)機(jī)
構(gòu)建一個(gè)LR（0）自動(dòng)機(jī)，會(huì)涉及到一個(gè)增廣文法和兩個(gè)函數(shù)（CLOSURE和GOTO）兩個(gè)函數(shù)之前都有了解了嗡官，分別用于求閉包和移進(jìn)箭窜。增廣文法含義如下：如果 G 是一個(gè)以 S 為開(kāi)始符號(hào)的文法，那么 G 的增廣文法 G' 就是在 G 中加上新開(kāi)始符號(hào) S‘ 和產(chǎn)生式 S'->S 而得到的文法衍腥。
這里以示例文法來(lái)講解自動(dòng)機(jī)的構(gòu)成
E ——> E + T | T
T ——> T * F | F
F ——> ( E ) | id
-
先畫出I0磺樱，使用增廣文法，構(gòu)造E'->E婆咸，然后求E的閉包得到E -> E + T竹捉、E -> T、T -> T * F尚骄、T -> F块差、F -> ( E )、F -> id倔丈，以上構(gòu)成I0集合憨闰，然后在他們前面都加上一個(gè)點(diǎn)，得到
I0 -
對(duì) E 進(jìn)行GOTO操作需五，就是把I0中所有包含有 ?E 的項(xiàng)拿出來(lái)鹉动，變成 E?，構(gòu)建成為I1
I1 -
對(duì) T 進(jìn)行GOTO操作宏邮，得到I2
I2 -
對(duì)F進(jìn)行GOTO操作泽示，得到I3
I3 -
對(duì)（ 進(jìn)行GOTO操作缸血，得到I4，由于此時(shí)?后為非終結(jié)符边琉，故可以進(jìn)行閉包操作属百，對(duì)F求閉包
I4 -
對(duì) id 進(jìn)行GOTO操作记劝，得到I5
I5
此時(shí)對(duì)I0的操作全部結(jié)束变姨，圖應(yīng)為這樣
-
對(duì)I1中的E'->E進(jìn)行歸約操作，得到accept厌丑，注意只有開(kāi)始符號(hào)才可以進(jìn)行這樣的操作定欧。
-
對(duì)+進(jìn)行GOTO操作，得到I6
I6 -
之后怒竿，對(duì)I2砍鸠、I3由于已經(jīng)為歸約項(xiàng)目，所以無(wú)操作）耕驰、I4爷辱、I5（由于已經(jīng)為歸約項(xiàng)目，所以無(wú)操作）都進(jìn)行跟之前類似的操作朦肘，可以得到I7饭弓、I8
I7
I8
第二輪畫完后是這樣，為了便于區(qū)分媒抠，這里使用紅色標(biāo)記第二輪弟断，值得注意的是I4部分很容易出現(xiàn)漏畫的情況。
-
對(duì)新生成的I6趴生、I7阀趴、I8進(jìn)行處理，得到I9苍匆、I10刘急、I11
I9
I10
I11
此時(shí)自動(dòng)機(jī)的圖為這樣：
-
最后對(duì)I9、I10浸踩、I11處理得到完整的自動(dòng)機(jī)叔汁。
至此，LR（0）自動(dòng)機(jī)構(gòu)建完畢民轴。
此時(shí)我們?cè)賹?duì)歸約式分析時(shí)就可以采用這樣的方法來(lái)進(jìn)行分析
id * id =》 F * id =》 T * id =》 T * F =》 T =》 E
