问有没有办法把这个语法变成LALR(1)？
EN

Stack Overflow用户

提问于 2013-05-01 16:35:19

回答 2查看 580关注 0票数 1

我有一个包含如下规则的语法

A -> pq
B -> pr

Block -> { Astar Bstar }

Astar -> Astar A
       | epsilon

Bstar -> Bstar B
       | epsilon

有没有办法把这个语法转换成LALR(1)？据我所知，如果解析器在块中看到p，则存在shift/educe冲突。

grammar

yacc

lalr

parsing

电商安全场景方案

帮助电商行业客户一站式解决Web安全、黑产羊毛党对抗、高危漏洞、BOT工具、恶意入侵门户服务器等安全问题

回答 2

Stack Overflow用户

回答已采纳

发布于 2013-05-01 17: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)语法。

票数 4

Stack Overflow用户

发布于 2013-05-01 18: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 [}]