語法規格解析Shift/Reduce衝突

Question

我正在使用Jison（Bison）創建簡單的標記語言。我顯然對此很陌生，但輕微的變化非常有效。我只是不明白S/R衝突的來源。

兩個詞法分析器操作（具有不同的開始條件）返回'文本'似乎並不重要，我喜歡這樣，因爲它似乎允許語法具有較少的規則，並且因爲錯誤消息給用戶是一致的。我已經試過使'文本'規則不受上下文影響，我也試着給每個令牌一個不同的名字，但是當它們在一起時，它似乎對S/R衝突沒有任何影響。

解析器被SUPPOSED創建一個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-token前瞻的解析器生成器，這不會是一個問題，但野牛是LALR（1）（1是一個令牌lookahead）。

有一對夫婦的事情，你可以嘗試：

• 做額外的先行在詞法分析器來區分文本，隨後逐]從文本未遵循逐]爲兩個不同的令牌然後重寫規則以使用這兩個令牌。

• 使用bison的％glr-parser特性來使用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以查看它是否是兩個或更多句子，並採取適當的行動。