MENU

【编译原理】LR分析算法

June 2, 2020 • Read: 174 • 编程之路,编译原理

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'               ●
- - - 结束 - - -
  • 文章标题:【编译原理】LR分析算法
  • 文章链接:https://blog.canye365.cn/archives/334.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 11, 2021