我如何看到LR(0)项目自动机中存在冲突? [英] How do I see that there is a conflict in the LR(0) items automata?

问题描述

关于 LR(0)，我有些不了解.我想弄清楚什么时候语法不是 LR(0).据我了解，我构建了 LR(0)项目自动机.然后，我需要寻找冲突.但是我不完全理解 LR(0)项目自动机中的两个项目之间是否存在冲突.是否有可能清除有关此部分的内容?我何时知道 LR(0)项目自动机中有冲突?看看一个或两个示例会很有帮助(不是语法本身，而是两个有某种冲突的项目).

There is something I don't fully get about the LR(0). I'm trying to figure out when grammar is not LR(0). As I understand I build the LR(0) items automata. Then I need to look for conflict. But I don't think that I fully understand when there is a conflict between two items in the LR(0) items automata. Is it possible to clear things up about this part? When do I know is there a conflict in the LR(0) items automata? Would be helpful to see an example or two (not for the grammar itself, rather for two items that have a conflict off some kind).

例如:

S ::= T C
T ::= char
T ::= int
C ::= [ num ] C
C ::= ''

我得到:

为什么4和8之间有冲突?

Why is there a conflict between 4 and 8?

推荐答案

不存在"4与8之间的冲突".(这没有意义，因为解析机始终处于一种状态.)这两种状态(独立地)都存在冲突.

There is not a "conflict between 4 and 8". (That wouldn't make sense, since the parsing machine is always in exactly one state.) Each of the two states (independently) has a conflict.

LR(0)解析器无法使用前瞻性来预测动作，因此每个状态都必须具有:

LR(0) parsers cannot use lookahead to predict the action, so every state must either have:

1. 每个输入的换档转换，或
2. 对每个输入都执行相同的减少操作

这意味着，如果该州的项目集中只有一个项目，且末尾带有•(即可简化项目)，则它必须是项目集中的唯一项目.其他任何项目要么是转移，要么是不同的减少.在您的计算机中，状态4和状态8并非如此.他们两个都有项目 C :: =•，以及其他不以•结尾的项目.

That means that if there is a single item in the state's itemset with the • at the end (i.e. a reducible item), then it must be the only item in the itemset. Any other item would either be a shift or a different reduction. And that's not the case for states 4 and 8 in your machine; both of them have the item C ::= •, along with other items not ending with •.

这篇关于我如何看到LR(0)项目自动机中存在冲突?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！