LR 分析法

LR文法(Knuth, 1963) 是最大的、可以构造出相应移入-归约语法分析器的文法类

  • L: 对输入进行从左到右的扫描

  • R: 反向构造出一个最右推导序列

  • LR(k)分析:需要向前查看k个输入符号的LR分析

    k = 0 和 k = 1 这两种情况具有实践意义,当省略(k)时,表示k =1

LR 分析法的基本原理

自底向上分析的关键问题是什么?

如何正确地识别句柄

句柄是逐步形成的,用“状态”表示句柄识别的进展程度

例:S→bBB

LR分析器基于这样一些状态来 构造自动机进行句柄的识别

LR 分析器(自动机)的总体结构

LR 分析表的结构

文法

① S→BB
② B→aB
③ B→b

sn:将符号a、状态n 压入栈
rn:用第n个产生式进行归约

LR 分析器的工作过程

初始化

一般情况下

①如果ACTION [sm, ai]= sx,那么格局变为:

②如果ACTION[sm , ai]= rx 表示用第x个产生式A→Xm-(k-1)…Xm进行归约,那么格局变为:

​ 如果GOTO[sm-k , A]=y,那么格局变为:

③如果ACTION[sm , ai]=acc,那么分析成功
④如果ACTION[sm , ai]=err ,那么出现语法错误

LR 分析算法

  • 输入:串w和LR语法分析表,该表描述了文法G的ACTION函数和GOTO函数。
  • 输出:如果w在 L(G)中,则输出w的自底向上语法分析过程中的归约步骤;否则给出一个错误指示。
  • 方法:初始时,语法分析器栈中的内容为初始状态s0,输入缓冲区中的内容为w$。然后,语法分析器执行下面的程序:
令a为w$的第一个符号;
while(1) { /* 永远重复*/ 
    令s是栈顶的状态;
    if ( ACTION [s,a] = st ) {
        将t压入栈中;
        令a为下一个输入符号;
    } else if (ACTION [s,a] =归约A → β ) {
        从栈中弹出│ β │个符号;
        将GOTO [t,A]压入栈中;
        输出产生式 A → β ;
    } else if (ACTION [s,a] =接受) break; /* 语法分析完成*/
    else调用错误恢复例程;
}

如何构造给定文法的LR分析表?

  • LR(0)分析
  • SLR分析
  • LR(1)分析
  • LALR分析

原文链接:

最后修改日期:2020年6月1日

留言

撰写回覆或留言