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' ●
- - - 结束 - - -