【编译原理】LR分析算法

LR分析法需要构造一张LR分析表，用于当面临输入字符时，考虑选择移进or规约，接受or出错。

LR分析算法 （移进归约算法）

• 算法运行高效
• 有现成的工具可用
• 也是目前应该广泛的一类语法分析器的自动生成器中采用的算法 （YACC, bison, CUP, C#yacc等）

自顶向上分析的基本思想

案例：

0: S -> E
1: E -> E + T
2:    | T
3: T -> T * F
4:    | F
5: F -> n

2 + 3 * 4

最右推导的逆过程！

2 + 3 * 4
F + 3 * 4
T + 3 * 4
E + 3 * 4
E + F * 4
E + T * 4
E + T * F
E + T
E
S

引入点记号：为了方便标记语法分析器已经读入了多少输入，我们可以引入一个点记号

E + 3 ● * 4
已经读入的：E + 3
剩余的输入： * 4

2 + 3 * 4            2 ● + 3 * 4
F + 3 * 4            F ● + 3 * 4
T + 3 * 4            T ● + 3 * 4
E + 3 * 4            E + 3 ● * 4
E + F * 4            E + F ● * 4
E + T * 4            E + T * 4 ●
E + T * F            E + T * F ●
E + T                E + T ●
E                    E ●
S                    S ●

另外的写法：

2 + 3 * 4
 ● + 3 * 4
 ● + 3 * 4
 ● + 3 * 4
 ● + 3 * 4
   ● 3 * 4
 ● * 4
 ● * 4
 ● * 4
   ● 4
 ●
 ●
 ●
 ●
 ●

生成一个逆序的最右公式推导

两个步骤：

• 移进 一个记号到栈顶上，或者

• 归约 栈顶上的n个符号（某产生式的右部）到左部的非终结符

  • 对产生式 A -> β1 … βn

    • 如果βn … β1在栈顶上，则弹出 βn… β1
    • 压入A

核心问题：如何确定移进和归约的时机。

示例：

0: S'-> S$
1: S -> x x T
2: T -> y

1                ● x x y $
1 x 2            ● x y $
1 x 2 x 3        ● y $
1 x 2 x 3 y 4    ● $
1 x 2 x 3 T 5    ● $
1 S 6            ● $
6                ● $
6 $              ●
S'               ●