La riformulazione della grammatica per rimuovere lo spostamento riduce il conflitto in if-then-else

Question

Come si rimuove il conflitto di riduzione del turno per il bisonte per la grammatica specificata?

selection-stmt -> if (expression) statement | 
         if (expression) statement else statement 

Una soluzione che dà la grammatica modificata sarebbe molto apprezzata.

Answer 1

C'è una soluzione molto più semplice. Se sai come funzionano i parser LR, poi si sa che il conflitto accade qui:

if (expression) statement * else statement 

dove la stella indica la posizione corrente del cursore. La domanda a cui deve rispondere il parser è "dovrei cambiare, o dovrei ridurre". Di solito, si desidera associare lo else allo if più vicino, il che significa che si desidera spostare il token else ora. Ridurre ora significherebbe che si desidera che else attenda di essere associato a un "vecchio" if.

Ora si vuole "dire" al proprio generatore di parser che "quando c'è uno spostamento/riduzione del conflitto tra il token "else" e la regola" stm -> if (exp) stm ", allora il token deve vincere". Per fare ciò, "dai un nome" alla precedenza della regola (ad es. "then") e specifica che "then" ha meno precedenza di "else". Qualcosa del tipo:

// Precedences go increasing, so "then" < "else". 
%nonassoc "then" 
%nonassoc "else" 
%% 
stm: "if" "(" exp ")" stm   %prec "then" 
    | "if" "(" exp ")" stm "else" stm 

utilizzando la sintassi Bison.

In realtà, la mia risposta preferita è anche dare "then" e "else" la stessa precedenza. Quando le precedenze sono uguali, per spezzare il legame tra il token che vuole essere spostato e la regola che vuole essere ridotta, Bison/Yacc esaminerà l'associatività. Qui, si vuole promuovere il tasto destro del associatività per così dire (più esattamente, si vuole promuovere "shift"), in modo da:

%right "then" "else" // Same precedence, but "shift" wins. 

sarà sufficiente.

Answer 2

è necessario riconoscere il fatto che la metà statement nel caso if-else non può essere (o terminare con) un penzoloni se (un caso con nessun altro.) Il modo più semplice per farlo è quello di dividere la regola stmt in due:

stmt -> stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if 
stmt-not-ending-with-dangling-if -> 
    if (expression) stmt-not-ending-with-dangling-if else stmt-not-ending-with-dangling-if | 
    ...other statements not ending with dangling if... 
stmt-ending-with-dangling-if -> 
    if (expression) stmt | 
    if (expression) stmt-not-ending-with-dangling-if else stmt-ending-with-dangling-if | 
    ...other statements ending with dangling if... 

qualsiasi altra stmt -> whatever regola dove whatever non si esaurisce con un stmt va nella regola stmt-not-ending-with-if, mentre ogni stmt regola che si esaurisce in stmt get diviso in due versioni; una versione not-ending-with-if nella regola not-ending-with-if e una versione dangling-if nella regola dangling-if.

modificare

Una grammatica più completa con altre produzioni:

stmt : stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if 
stmt-not-ending-with-dangling-if : 
    IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-not-ending-with-dangling-if | 
    WHILE '(' expr ')' stmt-not-ending-with-dangling-if | 
    DO stmt WHILE '(' expr ')' ';' | 
    expr ';' | 
    '{' stmt-list '}' 
stmt-ending-with-dangling-if: 
    IF '(' expr ')' stmt | 
    IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-ending-with-dangling-if | 
    WHILE '(' expr ')' stmt-ending-with-dangling-if 

regole come WHILE (expr) stmt get diviso in due (come si concludono con stmt), mentre le regole come expr; non lo fanno.

Answer 3

fare se altra cosa di più alto livello di dichiarazioni normali, come:

statements: 
    statements lineEnd statement 
| statements lineEnd IfStat 
| statements lineEnd IfElseStat 
| IfStat 
| IfElseStat 
; 
IfStat: 
    if (statement) 
; 
IfElse: 
    IfStat else statement 
;