Resolving S/R Konflikte in Jison

Question

Ich habe einen sehr einfachen Parser in Jison geschrieben, aber es scheint ein S/R Konflikt in dieser Grammatik zu sein:

/* 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; 

Es ist beabsichtigt, Dokumente wie diese zu analysieren ein, die aus 4 Aussagen besteht:

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

aber als ich beabsichtigt nicht funktioniert:

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

Ist es möglich, r Lösen Sie diesen Konflikt, ohne die Syntax der Sprache zu ändern, die analysiert wird?

Answer 1

Die Grammatik geschrieben (und in der Tat jede plausible Grammatik für die Sprache) ist LR (2), weil es unmöglich ist, zu wissen, ob ein IDENTIFIER die Fortsetzung eines grammar_and ist oder der Beginn einer neuen statement, bis die folgendes Token wird überprüft. Im zweiten Fall wäre es notwendig, statement zu reduzieren, und diese Entscheidung kann nicht mit dem Single-Token-Look-Ahead getroffen werden.

Dies ist eine klassische LR (2) Grammatik - in der Tat ist es die natürliche Grammatik für Bison-Produktionen - und es gibt eine Reihe von Möglichkeiten, es zu lösen.

Die Sprache selbst ist LR (1). In der Tat gibt es keine LR (2) -Sprache, weil es möglich ist, mechanisch eine LR (1) -Grammatik aus irgendeiner LR (k) -Grammatik zu erzeugen. Ein Beispiel, wie dies mit im Wesentlichen der gleichen Grammatik zu tun ist, wird in der Antwort auf How do I rewrite a context free grammar so that it is LR(1)? bereitgestellt.

Eine etwas einfachere Lösung, die der von den meisten YACC-Alikes ähnlich ist, besteht darin, einen zusätzlichen Lookahead im lexikalischen Scanner hinzuzufügen (oder mit einem Shim zwischen Scanner und Parser). Ein Beispiel für einen C-Code, um dies zu tun, wird in der Antwort auf flex&bison shift/reduce conflict bereitgestellt. (Die Frage ist nicht identisch, aber ich denke, die Lösung könnte angepasst werden.)