LALR解析器生成器实现问题
我目前正在尝试实现一个 LALR 解析器生成器，如“编译器原理技术和工具”（也称为“龙书”）中所述。
很多已经起作用了。解析器生成器当前能够生成完整的跳转图。
Example Grammar:
S' --> S
S --> C C
C --> c C
C --> d
Nonterminals: S', S, C
Terminals: c, d
Start: S'
goto-graph：
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 . , $ |<-----+
+---------------+
我在实现生成动作表的算法时遇到了麻烦！ 我的算法计算以下输出：
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 吗？
如果有什么描述不够清楚，请询问，我会尽力解释得更好！ 感谢您的帮助！
I'm currently trying to implement a LALR parser generator as described in "compilers principles techniques and tools" (also called "dragon book").
A lot already works. The parser generator is currently able to generate the full goto-graph.
Example Grammar:
S' --> S
S --> C C
C --> c C
C --> d
Nonterminals: S', S, C
Terminals: c, d
Start: S'
The goto-graph:
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 . , $ |<-----+
+---------------+
I have trubbles with implementing the algorithm to generate the actions-table!
My algorithm computes the following output:
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... shift to state x
rx... reduce to state x
The r? means that I don't know how to get the state (the ?) to which the parser should reduce. Does anyone know an algorithm to get ? using the goto-graph above?
If anything is describe no clearly enough, please ask and I will try to explain it better!
Thanks for your help!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
移位条目归因于下一个状态，但归约条目表示生产。
当您转移时，您将状态引用推入堆栈并继续到下一个状态。
当您减少时，这是针对特定生产的。产生式负责将 n 个状态转移到堆栈上，其中 n 是该产生式中的符号数量。例如，一个用于S'，两个用于S，以及两个或一个用于C（即用于C的第一或第二替代方案）。
当 n 个条目从堆栈中弹出后，您将返回到开始处理该产生式的状态。对于该状态和产生式产生的非终结符，您可以查找 goto 表以找到下一个状态，然后将其推送。
因此，reduce 条目标识了一个产生式。事实上，知道生成的非终结符以及要弹出的符号数量可能就足够了。
因此，您的表应显示
rx 表示减少生产 x。
A shift entry is attributed by the next state, but a reduce entry indicates a production.
When you shift, you push a state reference onto your stack and proceed to the next state.
When you reduce, this is for a specific production. The production was responsible for shifting n states onto your stack, where n is the number of symbols in that production. E.g. one for S', two for S, and two or one for C (i.e. for the first or second alternative for C).
After n entries are popped off the stack, you return to the state where you started processing that production. For that state and the nonterminal resulting from the production, you lookup the goto table to find the next state, which is then pushed.
So the reduce entries identify a production. In fact it may be sufficient to know the resulting nonterminal, and the number of symbols to pop.
Your table thus should read
where rx indicates reduce by production x.
您需要弹出堆栈并从那里找到下一个状态。
You need to pop the stack and and find the next state from there.
rx 的意思是：使用数字 x 的产生式来减少！
那么一切就都清楚了！
简单地弹出产品的主体并将头部移回顶部！
The rx means: reduce using the production with the number x!
Then everything gets clear!
Simple pop the body of the production and shift the head back onto the top!