編譯原理之LR分析概述

LR分析的提出

LR（k）分析方法是1995年Knuth提出的，括號中的k表示向右檢視輸入串符號的個數。這種方法比起自頂向下的LL（k）分析方法和自頂向上的優先分析方法對文法的限制要少得多，也就是說，對於大多數用無二義性上下文無關文法描述的語言都可以用相應的LR分析器進行識別，而且這種方法還具有分析速度快，能準確、及時地指出出錯位置的特點。它的主要缺點是對於一個實用語言文法的分析器的構造工作量相當大，k愈大，構造愈複雜，實現比較困難。因此，目前許多實用的編譯程式，當採用LR分析器時都是藉助於美國Bell實驗室推出的yacc來實現的。yacc能接受一個用BNF描述的滿足LR類中LALR（1）的上下無關文法並對其自動構造出LALR（1）分析器。

LR分析概述

一個LR分析器由3個部分組成：

（1）總控程式，也稱驅動程式。對所有的LR分析器，總控程式都是相同的。

（2）分析表或分析函式。不同文法分析表將不同，同一個文法採用的LR分析器不同時，分析表也不同，分析表又可分為動作（ACTION）表和狀態轉換（GOTO）表兩個部分，它們都可以用二維陣列表示。

（3）分析棧，包括文法符號棧和相應的狀態棧。它們均是先進後出棧。

分析器的動作由棧頂狀態和當前輸入符號來決定（LR（0）分析器不需要向前檢視輸入符號）。

LR分析器工作過程示意圖：

LR分析器工作過程

ACTION［Si，a］規定了棧頂狀態為Si時遇到輸入符號a應該執行的動作。動作有四種可能：

（1）移進

當Si=GOTO［Si，a］成立，則把Si移入到狀態棧，把a移入到檔案符號棧。其中i，j表示狀態號。

（2）規約

當棧頂形成控制代碼為阝時，則用阝歸約為相應的非終結符A，即當文法中有A–>阝的產生式，而阝的長度為r，則從狀態棧和文法符號棧中自頂向下去掉r個符號，即棧指標SP減去r。並把A移入文法符號棧內，再把滿足Sj=GOTO［Si，A］的狀態轉移進狀態棧，其中Si修改指標後的棧頂狀態。

（3）接受acc

當規約到文法符號棧中只剩文法的開始符號S，並且輸入符號串已結束，即當前輸入符是#，則為分析成功。

（4）報錯

當遇到狀態棧頂為某一狀態下出現不該遇到的文法符號時則報錯，說明輸入串不是該文法能接受的句子。

LR分析器的關鍵部分是分析表的構造，後面將針對每種不同的LR分析器詳細介紹其構造思想及方法。