LR語法分析器

特點(diǎn)：
1）由表格驅(qū)動(dòng)
2）幾乎適用所有程序設(shè)計(jì)語言
3）無回溯的移入歸約技術(shù)
4）可以盡早檢測到錯(cuò)誤

項(xiàng)

什么是項(xiàng)？這里所說的項(xiàng)是一種狀態(tài)，用來在LR語法分析中對(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ǔ)。稱為LR（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 為開始符號(hào)的文法，那么 G 的增廣文法 G' 就是在 G 中加上新開始符號(hào) S‘ 和產(chǎn)生式 S'->S 而得到的文法。
這里以示例文法來講解自動(dòng)機(jī)的構(gòu)成

E ——> E + T | T
T ——> T * F | F
F ——> ( E ) | id

LR（0）自動(dòng)機(jī)

先畫出I₀，使用增廣文法，構(gòu)造E'->E，然后求E的閉包得到E -> E + T、E -> T、T -> T * F、T -> F、F -> ( E )、F -> id，以上構(gòu)成I₀集合，然后在他們前面都加上一個(gè)點(diǎn)，得到

I0
對(duì) E 進(jìn)行GOTO操作，就是把I₀中所有包含有 ?E 的項(xiàng)拿出來，變成 E?，構(gòu)建成為I₁

I1
對(duì) T 進(jìn)行GOTO操作，得到I₂

I2
對(duì)F進(jìn)行GOTO操作，得到I₃

I3
對(duì)（進(jìn)行GOTO操作，得到I₄，由于此時(shí)?后為非終結(jié)符，故可以進(jìn)行閉包操作，對(duì)F求閉包

I4
對(duì) id 進(jìn)行GOTO操作，得到I₅

I5

此時(shí)對(duì)I₀的操作全部結(jié)束，圖應(yīng)為這樣

處理I0后

對(duì)I₁中的E'->E進(jìn)行歸約操作，得到accept，注意只有開始符號(hào)才可以進(jìn)行這樣的操作。
對(duì)+進(jìn)行GOTO操作，得到I₆

I6
之后，對(duì)I₂、I₃由于已經(jīng)為歸約項(xiàng)目，所以無操作）、I₄、I₅（由于已經(jīng)為歸約項(xiàng)目，所以無操作）都進(jìn)行跟之前類似的操作，可以得到I₇、I₈

I7

I8