在jison

Question

解決S/R衝突

我已經寫在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 

是否有可能與r在不修改正在分析的語言的語法的情況下解決衝突？

Answer 1

書面（事實上，對於語言的任何合理的語法）是LR語法（2），因爲它是不可能知道的IDENTIFIER是否是grammar_and的延續或新statement，直到開始以下標記被檢查。在第二種情況下，有必要減少statement，並且這個決定不能用單個令牌預先做出。

這是一個經典的LR（2）語法 - 事實上，它是野牛製作的自然語法 - 並且有很多方法可以解決它。

語言本身是LR（1）。實際上，沒有LR（2）語言這樣的東西，因爲可以從任何LR（k）語法機械地生成LR（1）語法。在How do I rewrite a context free grammar so that it is LR(1)?的回答中提供了一個基本上具有相同語法的例子。

一個比較簡單的解決方案，類似於大多數yacc-alike使用的解決方案，是在詞法掃描器（或掃描器和解析器之間的墊片）中添加一個額外的超前功能。在flex&bison shift/reduce conflict的答案中提供了一個C代碼的例子。 （問題不一樣，但我認爲解決方案可以調整。）