从 Lemon Parser Generator 生成 LR parse table

Question

我正在尝试使用柠檬解析器生成器生成解析器 table，但是当我运行 lemon grammar.y 时生成的 .out 文件仅包含以下状态自动机。

有没有办法同时获得非终端的 goto table，而不仅仅是自动机的状态？或者这只能通过读取生成的代码来完成？是否有任何其他工具可以生成操作和转到 tables？

PS:

简单语法的 .out 文件（由 lemon 生成）如下所示：

State 0:
          start ::= * e
          e ::= * e PLUS t
          e ::= * t
          t ::= * t MUL f
          t ::= * f
          f ::= * LPAR e RPAR
          f ::= * ID

                          LPAR shift        1      
                            ID shift        4      
                         start accept
                             e shift        11     
                             t shift        6      
                             f shift        5      

State 1:
          e ::= * e PLUS t
          e ::= * t
          t ::= * t MUL f
          t ::= * f
          f ::= * LPAR e RPAR
          f ::= LPAR * e RPAR
          f ::= * ID

                          LPAR shift        1      
                            ID shift        4      
                             e shift        10     
                             t shift        6      
                             f shift        5      

State 2:
          e ::= e PLUS * t
          t ::= * t MUL f
          t ::= * f
          f ::= * LPAR e RPAR
          f ::= * ID

                          LPAR shift        1      
                            ID shift        4      
                             t shift        9      
                             f shift        5      

State 3:
          t ::= t MUL * f
          f ::= * LPAR e RPAR
          f ::= * ID

                          LPAR shift        1      
                            ID shift        4      
                             f shift        8      

State 4:
      (6) f ::= ID *

                             $ reduce       6      f ::= ID
                          PLUS reduce       6      f ::= ID
                           MUL reduce       6      f ::= ID
                          RPAR reduce       6      f ::= ID

State 5:
      (4) t ::= f *

                             $ reduce       4      t ::= f
                          PLUS reduce       4      t ::= f
                           MUL reduce       4      t ::= f
                          RPAR reduce       4      t ::= f

State 6:
      (2) e ::= t *
          t ::= t * MUL f

                             $ reduce       2      e ::= t
                          PLUS reduce       2      e ::= t
                           MUL shift        3      
                          RPAR reduce       2      e ::= t

State 7:
      (5) f ::= LPAR e RPAR *

                             $ reduce       5      f ::= LPAR e RPAR
                          PLUS reduce       5      f ::= LPAR e RPAR
                           MUL reduce       5      f ::= LPAR e RPAR
                          RPAR reduce       5      f ::= LPAR e RPAR

State 8:
      (3) t ::= t MUL f *

                             $ reduce       3      t ::= t MUL f
                          PLUS reduce       3      t ::= t MUL f
                           MUL reduce       3      t ::= t MUL f
                          RPAR reduce       3      t ::= t MUL f

State 9:
      (1) e ::= e PLUS t *
          t ::= t * MUL f

                             $ reduce       1      e ::= e PLUS t
                          PLUS reduce       1      e ::= e PLUS t
                           MUL shift        3      
                          RPAR reduce       1      e ::= e PLUS t

State 10:
          e ::= e * PLUS t
          f ::= LPAR e * RPAR

                          PLUS shift        2      
                          RPAR shift        7      

State 11:
      (0) start ::= e *
          e ::= e * PLUS t

                             $ reduce       0      start ::= e
                          PLUS shift        2      

----------------------------------------------------
Symbols:
    0: $:
    1: PLUS
    2: MUL
    3: LPAR
    4: RPAR
    5: ID
    6: error:
    7: start: LPAR ID
    8: e: LPAR ID
    9: t: LPAR ID
   10: f: LPAR ID

Answer 1

Lemon 在单个块中输出操作 table 和转到 table。 goto 函数看起来像 shift 动作，除了 lookahead 是非终结符而不是终结符。

因此，如果我们采用状态 0：

 LPAR shift        1      
   ID shift        4      
start accept
    e shift        11     
    t shift        6      
    f shift        5

前两行分别是读取LPAR和ID的动作。其余行是 goto 函数，当 reduce 操作通过弹出堆栈来显示此状态时使用该函数。（与传统的 LR 机器不同，在 Lemon 中，accept 动作在 goto table 中，而不是在输入结束伪终端的动作 table 中。）

虽然大多数 LR 解析器的描述都区分了动作 table 和 goto table，但 "shift" 动作和 "goto" 之间的区别很小减少行动的一部分。这两个都将当前状态号和一个符号推送到解析器堆栈上。不同之处在于，reduce 操作（例如 reduce 6，这意味着 "reduce using production 6"——它与状态 6 无关）首先将指定产生式的右侧弹出堆栈，然后在执行 shift/goto 之前将当前状态设置为堆栈顶部新显示的状态。（另一个区别是在shift动作之后，需要读取一个新的lookahead token，而reduce动作不消耗输入。）

从 Lemon Parser Generator 生成 LR parse table

Generate the LR parse table from the Lemon Parser Generator

parsing

lr

lemon