Wie kann ich shift-reduce Konflikte vom selben Betreiber beseitigen

Question

ich Bison verwenden soll einige Skriptsprache zu analysieren, in dieser Sprache kann ich Code wie folgt schreiben:

a = input() 
b = a + 1 
function myfunc 
    a = input() 
    b = a + 1 
end function 

fand ich, dass der Block

a = input() 
b = a + 1 

, die sowohl in die und aus der Funktionsdefinition erscheinen stmts, durch die gleiche Regel reduziert werden, so schreibe ich Code wie folgt

%{ 
#include <stdio.h> 
#include <string> 
#include <sstream> 
#include <iostream> 
#include <stdarg.h> 
#include <tuple> 

using namespace std; 
%} 

%debug 

%token CRLF EXP FUNCTIONBEGIN FUNCTIONEND 

%start program 

%% 

stmt : EXP 
    | 
stmts : stmt CRLF stmts 
    | stmt 
function : FUNCTIONBEGIN CRLF stmts CRLF FUNCTIONEND 
unit : function 
    | stmts 
program : unit 
    | unit CRLF program 

%% 

Natürlich kann dieser Code nicht aufgrund einer Schichtarbeit/reduzieren Konflikt

State 3 

    3 stmts: stmt . CRLF stmts 
    4  | stmt . 

    CRLF shift, and go to state 9 

    CRLF  [reduce using rule 4 (stmts)] 
    $default reduce using rule 4 (stmts) 

Ich dachte, dieser Konflikt ist darauf zurückzuführen, sowohl meine program Regel und stmts Regel unter Verwendung der gleichen Klemme CRLF als „Binäroperators“ Daher kann ich diesen Konflikt nicht lösen, indem ich den Operatoren Priorität einräume.

Vielleicht kann ich program Regel und stmts Regel zusammen irgendwie verschmelzen durch zwei weitere Regeln hinzufügen

stmts : function CRLF stmts 
    | function 

stmt Jedoch habe ich diese Methode gedacht (ob es praktisch arbeiten) ist nicht sehr schön, so frage ich, wenn Es gibt einige andere Lösungen

Answer 1

Das Problem hat nichts mit CRLF-Tokens zu tun. Vielmehr ist es Ihre Definition von program. A program ist eine Reihe von unit s, wobei jede Einheit eine function oder eine stmts ist. Aber stmts ist keine "Einheit", was durch die Tatsache, dass der Name Plural ist, angedeutet wird. A stmts ist eine Serie von stmt s.

Angenommen, wir haben ein Programm, das aus drei Anweisungen besteht. Wie viele unit s ist das? Ist es ein stmts bestehend aus allen drei Aussagen? Oder zwei von ihnen, einer mit zwei Aussagen und der andere mit nur einem? Oder umgekehrt? Oder sogar drei unit s, jeweils bestehend aus einem stmts mit einer einzigen Aussage?

Der Parser kann nicht sagen, welche dieser Alternativen gewünscht wird, weil die Grammatik mehrdeutig ist. Und genau das schafft den Konflikt.

Die einfachste Lösung ist es, die Produktion unit: stmts zu ändern Singular zu sein: unit: stmt. Dann gibt es keine Zweideutigkeit; die Drei-Aussage program hat genau drei unit s, jeweils eine einzelne stmt.

Übrigens sollten Sie beim Schreiben von LR-Grammatiken immer die linke Rekursion bevorzugen. Rechte Rekursion erzeugt normalerweise keine Konflikte und hat nichts mit Ihrem aktuellen Problem zu tun, aber es führt zu unnötigen Stapelanalysen, und die Reduzierung von Listen wie units und stmts wird von rechts nach links als Komponenten ausgeführt werden vom Stapel geknallt, was oft nicht beabsichtigt ist.