LALR解析器生成器实现问题

我目前正在尝试按照“编译器原理技巧和工具”（也称为“龙书”）中所述实现LALR解析器生成器。LALR解析器生成器实现问题

很多已经工作。解析器生成器当前能够生成完整的goto-graph。

Example Grammar: 
        S' --> S 
        S --> C C 
        C --> c C 
        C --> d 

Nonterminals: S', S, C 
Terminals: c, d 
Start: S'

的后藤图：

I[0]---------------+  I[1]-------------+ 
| S' --> . S , $ |--S-->| S' --> S . , $ | 
| S --> . C C , $ |  +----------------+ 
| C --> . c C , c | 
| C --> . c C , d |  I[2]--------------+ 
| C --> . d , c |  | S --> C . C , $ |  I[3]--------------+ 
| C --> . d , d |--C-->| C --> . c C , $ |--C-->| S --> C C . , $ | 
+------------------+  | C --> . d , $ |  +-----------------+ 
    | |     +-----------------+ 
    | |   +--c--+ |  | 
    | |   |  | c  | 
    | |   |  v v  | 
    | |  I[4]--------------+ | 
    | c  | C --> c . C , c | | 
    | |  | C --> c . C , d | | 
    | |  | C --> c . C , $ | d 
    | |  | C --> . c C , c | | 
    | +---->| C --> . c C , d | | 
    |  | C --> . c C , $ | | 
    d  | C --> . d , c |--+ | 
    | +-----| C --> . d , d | | | 
    | |  | C --> . d , $ | | | 
    | |  +-----------------+ | | 
    | C       | | 
    | |  I[6]--------------+ | | 
    | |  | C --> c C . , c | d | 
    | +---->| C --> c C . , d | | | 
    |  | C --> c C . , $ | | | 
    |  +-----------------+ | | 
    |        | | 
    |  I[5]------------+ | | 
    |  | C --> d . , c |<---+ | 
    +------->| C --> d . , d |  | 
      | C --> d . , $ |<-----+ 
      +---------------+

我有实现算法生成的动作表trubbles！我的算法计算以下的输出：

state | action  
     | c | d | $ 
------------------------ 
    0 | s4 | s5 | 
------------------------ 
    1 |  |  | acc 
------------------------ 
    2 | s4 | s5 | 
------------------------ 
    3 |  |  | r? 
------------------------ 
    4 | s4 | s5 | 
------------------------ 
    5 | r? | r? | r? 
------------------------ 
    6 | r? | r? | r?

SX ...转移到状态X
RX ...减少状态X

将R？意味着我不知道如何获得解析器应该减少的状态（？）。有谁知道算法得到？使用上面的goto-graph？

如果有任何描述不够清楚，请问，我会尽力解释它！感谢您的帮助！

来源

2010-08-02 raisyn

换档条目归因于下一个状态，但减少条目表示生产。

当你转移时，你将一个状态参考推入你的堆栈并进入下一个状态。

当您减少时，这是针对特定的生产。生产负责将n个状态转移到您的堆栈上，其中n是该生产中的符号数。例如。一个用于S'，两个用于S，并且两个或一个用于C（即，用于C的第一或第二替代）。

当n个条目从堆栈中弹出后，您将返回到开始处理该生产的状态。对于该状态和由生产产生的非终结符，您可以查找goto表以找到下一个状态，然后将其推送。

因此，减少条目标识生产。事实上，知道产生的非终结符号以及要弹出的符号数量就足够了。因此

你的表应该读

state | action  | goto 
     | c | d | $ | C | S 
------------------------------------ 
    0 | s4 | s5 |  | 2 | 1 
------------------------------------ 
    1 |  |  | acc |  | 
------------------------------------ 
    2 | s4 | s5 |  | 3 | 
------------------------------------ 
    3 |  |  | r0 |  | 
------------------------------------ 
    4 | s4 | s5 |  |  | 6 
------------------------------------ 
    5 | r3 | r3 | r3 |  | 
------------------------------------ 
    6 | r2 | r2 | r2 |  |

其中，Rx表示通过产生X减少。

来源

2010-08-02 20:48:16 Gunther

非常感谢！ – raisyn 2010-08-10 15:47:03

您需要弹出堆栈并从中找到下一个状态。

来源

2010-08-02 19:40:11

所以我不需要知道rx？只是我必须减少？这本书说，第一个r值？ = r1;接下来的三个= r4;最后三位= r2;任何想法这是什么意思，如果你是对的？ – raisyn 2010-08-02 19:50:43

rx表示：使用数字x减少生产量！
然后一切都变得清晰！简单地弹出生产的主体，并将头部移回顶部！

来源

2010-08-02 20:42:04 raisyn

LALR解析器生成器实现问题

回答

相关问题