解决 jison 中的 S/R 冲突

Question

我用 jison 写了一个非常简单的解析器，但这个语法中似乎存在 S/R 冲突：

/* lexical grammar */
%lex
%%
s+                   /* skip whitespace */
":"                   return ':'
"."                   return '.'
[a-zA-Z_][a-zA-Z0-9_]* return 'IDENTIFIER'
<<EOF>>               return 'EOF'
.                     return 'INVALID'
/lex
/* operator associations and precedence */

%start expressions
%% /* language grammar */
expressions
: statements EOF
{return $1;}
;
statements: statements statement {$$ = [$1].concat($2);} | statement {$$ =
[$1];};
statement:
IDENTIFIER ":" grammar_and {[$$ = ["grammar_rule",$1,$3]]};
grammar_and:
grammar_and IDENTIFIER {$$= [$1,$2]} | IDENTIFIER;

它旨在解析像这样的文档，它由 4 个语句组成：

first: this is a sentence
second: this is another sentence
something: more words here another: more words here

但它没有按我的预期工作：

Conflicts encountered:
Resolve S/R conflict (shift by default.)
(1,10, 2,4) -> 1,10

是否可以在不修改正在解析的语言的语法的情况下解决此冲突？

Answer 1

所写的语法(以及该语言的任何合理语法(是 LR(2(，因为在检查以下标记之前，不可能知道IDENTIFIER是grammar_and的延续还是新statement的开始。在第二种情况下，有必要减少statement，并且不能通过单一令牌前瞻做出决定。

这是一个经典的LR(2(语法——事实上，它是野牛生产的自然语法——有很多方法可以解决它。

语言本身是LR(1(。实际上，没有LR(2(语言这样的东西，因为可以从任何LR(k(语法机械地产生LR(1(语法。如何在如何重写上下文无关语法以使其成为 LR(1(？的答案中提供了如何使用基本相同的语法执行此操作的示例。

一个更简单的解决方案，类似于大多数yacc类似者使用的解决方案，是在词法扫描器中添加一个额外的前瞻(或在扫描器和解析器之间有一个垫片(。在 flex&bison shift/reduce 冲突的答案中提供了执行此操作的 C 代码示例。(这个问题并不相同，但我认为解决方案可以调整。