有没有办法把这个语法变成LALR(1)？
我有一个包含如下规则的语法
A -> pq
B -> pr
Block -> { Astar Bstar }
Astar -> Astar A
| epsilon
Bstar -> Bstar B
| epsilon有没有办法把这个语法转换成LALR(1)？据我所知，如果解析器在块中看到p，则存在shift/educe冲突。
回答 2
Stack Overflow用户
发布于 2013-05-02 01:54:18
您的语言是正则语言，等同于正则表达式\{(pq)*(pr)*\}。问题是，任何到语法的简单转换都需要两个字符的先行检查，以查看p后面是否有q或r
现在您已经将其标记为yacc和parsing，所以不清楚您是在寻找一个实用的答案“您如何处理这个问题”，还是一个理论上的答案“这种语言是否有一种LALR(1)语法”。
对于实际的答案，解决方案是将A和B的识别转移到词法分析器中，在该词法分析器中将字符序列pq和pr识别为标记A和B。因为lex/flex使用DFA并回溯到最长匹配的令牌，所以它们在这里没有任何问题。
对于理论上的答案，您需要转换语法以消除对先行的需要。有问题的构造是(pq)*(pr)* (大括号是不相关的)，它等同于p(qp)*(rp)*r | p(qp)*q | epsilon，它建议使用如下语法：
Block -> { p Astar Bstar r }
| { p Astar q }
| { }
A -> q p
B -> r p
Astar -> Astar A | epsilon
Bstar -> Bstar B | epsilon另一种方法是对star规则进行分解，使其不匹配空字符串：
Block -> { Aplus Bplus }
| { Aplus }
| { Bplus }
| { }
A -> p q
B -> p r
Aplus -> Aplus A | A
Bplus -> Bplus B | B为同一种语言提供了两种截然不同的LALR(1)语法。
Stack Overflow用户
发布于 2013-05-02 02:28:45
让我们首先看看为什么会出现LALR(1)冲突，然后看看是否可以重新编写语法，使其成为LALR(1)。
要了解语法不是LALR(1)的原因，让我们从计算语法的LR(1)配置集开始：
(1)
S' -> .Block [$]
Block -> .{ Astar Bstar } [$]
(2)
S' -> Block. [$]
(3)
Block -> { . Astar Bstar } [$]
Astar -> .Astar A [ }p ]
Astar -> .epsilon [ }p ]
(4)
Block -> { Astar . Bstar } [$]
Astar -> Astar .A [ }p]
A -> .pq [}p]
Bstar -> .epsilon [ }p ]
Bstar -> . Bstar B [ }p ]在这一点上，我们可以停止了，因为我们在符号p上的状态(4)中有一个shift/reduce混淆:你是为A -> .pq [ {p ]移位p，还是减少BStar -> .epsilon [ }p ]？由于LR(1)语法中存在移位/归约冲突，因此该语法根本不是LR(1)，这意味着它不可能是LALR(1) (因为每个LALR(1)语法也是LR(1)语法)。
从根本上说，问题是当解析器看到一个p时，它不能判断它是在看A的开头(意味着它需要移动它)，还是没有更多的A了，它正在看一个B的开头(意思是它需要减少Bstar -> epsilon)。
为了解决这个问题，让我们看看如果我们做一个小的调整会发生什么。我们遇到的问题是，解析器需要在看到p时立即确定是移位还是缩减。如果我们给它时间来推迟决定，先看p，然后再看后续字符，会怎么样？为此，让我们通过重写来稍微更改一下您的语法
Bstar -> epsilon
Bstar -> Bstar B作为
Bstar -> epsilon
Bstar -> B Bstar现在，解析器可以在决定要做什么之前查看更多的标记。如果它查看的是pq，那么它知道它没有查看任何与B相关的内容。如果它看到pr，它就知道它正在寻找B，因此可以开始进行第二种类型的生成。让我们看看如果我们这样做，LR(1)状态会发生什么：
(1)
S' -> .Block [$]
Block -> .{ Astar Bstar } [$]
(2)
S' -> Block. [$]
(3)
Block -> { . Astar Bstar } [$]
Astar -> .Astar A [ }p ]
Astar -> .epsilon [ }p ]
(4)
Block -> { Astar . Bstar } [$]
Astar -> Astar .A [ }p]
A -> .pq [}p]
Bstar -> .epsilon [ } ]
Bstar -> . B Bstar [ } ]
B -> .pr [}]
(5)
Block -> { Astar Bstar . } [$]
(6)
Block -> { Astar Bstar } . [$]
(7)
A -> p.q [}p]
B -> p.r [}]
(8)
A -> .pq [}p]
(9)
B -> pr. [}]
(10)
Bstar -> B . Bstar [ } ]
Bstar -> . B Bstar [ } ]
B -> .pr [}]
(11)
B -> p.r [}]请注意，我们原来的shift/reduce冲突已经消失了，并且这个新语法根本不再有任何shift/reduce冲突。此外，由于没有任何具有相同核心的状态对，因此上面的状态集也是我们的LALR(1)表中的状态集。因此，上面的语法确实是LALR(1)，并且我们根本没有改变语法的含义。
希望这能有所帮助！
https://stackoverflow.com/questions/16322348
复制相似问题
腾讯云开发者
