LALR(1) 解析器根本不解析文本

Question

我不得不承认我是这方面的绝对新手，甚至可能不明白我在做什么。

我正在尝试制作一个至少包含来自 BABA IS YOU 的语法的语法，并在可能的情况下对其进行扩展。我正在使用这个工具来调试我的语法：http://jsmachines.sourceforge.net/machines/lalr1.html

无可否认，我的语法目前不是 LALR(1)（正如许多 shift/reduce 冲突所见，我不确定如何正确解决）。

所以，当我在解析器中输入“RED AND BLUE BABA IS YOU”时，这是我希望看到的：

然而我看到的是：

我不知道从哪里开始了解我的问题，我至少需要帮助

我使用的语法是这样的：https://pastebin.com/5MHZrFLe

sentence' -> sentence
 
sentence -> give
 
give -> giver property
giver -> noun IS
 
selector -> adjective noun
 
multinoun -> noun AND
multinoun -> multinoun AND
multinoun -> multinoun noun
 
multiadjective -> adjective AND
multiadjective -> multiadjective AND
multiadjective -> multiadjective adjective
 
noun -> multinoun
noun -> selector
 
noun -> BABA
noun -> KEKE
noun -> ROBOT
 
adjective -> RED
adjective -> BLUE
adjective -> GREEN
 
property -> YOU

Answer 1

为了识别该句子中的标记 AND，必须有一个从 sentence' 到 multiadjective 的推导序列。没有这样的顺序，可以通过简单的可达性图（这只是一个 DFS）轻松验证。

这使得 multiadjective 在该语法中毫无用处。令人惊讶的是，您使用的工具并未就此向您发出警告。

multinoun 不是这种情况，它可以通过 noun -> multinoun 产品获得。但是，这会产生一些歧义，导致 shift/reduce 冲突。一个例子：

noun -> multinoun -> multinoun AND

对

noun -> multinoun -> noun AND -> multinoun AND

表示令牌分隔项列表的自下而上语法的一般模式是：

list -> item
list -> list separator item

在这样的语法中，列表包含在使用非终结符 list 而不是 item 的外部产生式中。添加 item -> list 以便能够将其称为 item 会导致与 noun 非终端相同的歧义，这或多或少会重现此错误。

LALR(1) 解析器根本不解析文本

LALR(1) Parser Not Parsing The Text At All

parsing

lalr