语法规范解决移位/减少冲突

Question

我正在使用Jison(Bison)创建一种简单的标记语言。我显然是新手，但细微的变化效果很好。我只是不明白S/R冲突的根源。

"Text"是由两个lexer操作(具有不同的开始条件)返回的，这似乎并不重要，我喜欢这样，因为它似乎允许语法具有更少的规则，并且给用户的错误消息是一致的。我试着让"文本"规则变得通用，而不管上下文如何，我也试着给每个令牌一个不同的名称，但当它们结合在一起时，似乎对S/R冲突没有任何影响。

解析器用于创建一个带有纯文本、子数组和各种特殊节点的json对象。

规格：

/* lexical grammar */
%lex
%s bracketed
%%
<bracketed>(\.|[^\,[]])+       { yytext = yytext.replace(/\(.)/g, '$1'); return 'Text'; }
<INITIAL>(\.|[^\[])+             { yytext = yytext.replace(/\(.)/g, '$1'); return 'Text'; }
"["                                 { this.begin('bracketed'); return '['; }
"]"                                 { this.popState(); return ']'; }
","                                 return ','
<<EOF>>                             return 'END'
/lex
%start template
%%    
template
: sentence END
;
sentence
: /* empty */
| sentence Text
| sentence '[' ']'
| sentence '[' dynamic ']'
;
dynamic
: sentence
/*| dynamic ',' sentence*/
;

警告：

Conflict in grammar: multiple actions possible when lookahead token is ] in state 5
- reduce by rule: sentence ->
- shift token (then go to state 6)
States with conflicts:
State 5
sentence -> sentence [ .] #lookaheads= END Text [ ]
sentence -> sentence [ .dynamic ] #lookaheads= END Text [ ]
dynamic -> .sentence #lookaheads= ]
sentence -> . #lookaheads= ] Text [
sentence -> .sentence Text
sentence -> .sentence [ ]
sentence -> .sentence [ dynamic ]

不同的生成器算法或多或少都有问题，但它们似乎都有问题。

谢谢！

Answer 1

冲突从根本上来自这两条规则：

sentence: sentence '[' Text ']'
| sentence '[' sentenceList ']'

原因是，在看到sentence和[并看到下一个令牌是Text之后，解析器不知道是移动Text，匹配第一个规则，还是将该Text视为sentenceList的开始，以匹配第二个规则。

现在，如果您有一个使用2-令牌前瞻的解析器生成器，这不会是一个问题，但bison是LALR(1)(1是一个令牌前瞻)。

你可以尝试以下几种方法：

• 在lexer中进行额外的前瞻性操作，将后面跟-]的Text和后面不跟-]作为两个不同的标记进行区分，然后重写规则以使用这两个标记。

• 使用bison的%glr语法分析器功能来使用glr语法分析器。这将双向解析句子，然后丢弃与不匹配的句子

• 重构语法，使其不需要2个标记的前瞻。

在您的情况下，一种有效的重构是重写sentence规则，使它们都是右递归的，而不是左递归的：

sentence: /* empty */
| Text sentence 
| '[' ']' sentence
| '[' Text ']' sentence
| '[' sentenceList ']' sentence
;

这避免了sentence(或以sentence开始的任何其他规则，例如sentenceList)以sentence: /*empty*/规则的零缩减开始。因此，在有问题的情况下，解析器可以自由地移动Text，从而推迟缩减，直到它看到下一个令牌。然而，它确实有内存使用的含义，因为它产生了一个解析器，该解析器将把整个输入转移到解析器堆栈上，然后一次减少一句话。

您可以做的另一个重构是将[Text]和[]构造包含到[sentenceList]:中

sentence: /* empty */
| sentence Text 
| sentence '[' sentenceList ']'
;
sentenceList: sentence
| sentenceList ',' sentence

因此，现在sentenceList是一个或多个用逗号分隔的句子(而不是两个或更多)，在sentence '[' sentenceList ']'规则的操作中，您需要检查sentenceList，看看它是否是两个或两个以上的句子，并采取适当的行动。