Come estrarre gli operatori dalle produzioni grammaticali per la risoluzione dei conflitti nel parser LALR?

Convertito da un commento, in primo luogo, una riformulazione della tua domanda:

Supponiamo di avere la seguente grammatica ambigua:

E ::= E + E
E ::= E * E
E ::= num

Nell'automa LR, avremo il seguente conflitto di riduzione del turno (tra gli altri):

E ::= E * E •, +
E ::= E • + E

Come è noto, ridurre qui renderà "*" più stretto come "+" (come normale), mentre lo spostamento renderà "+" più stretto.

I generatori di parser come Yacc e Bison consentono all'utente di contrassegnare i token come vincolanti più strettamente di altri token. Come normale, diciamo che '* > +'.

Tuttavia, sembra che ci sia una mancata corrispondenza da qualche parte: il ">" usiamo sopra è un operatore tra due token , ma il conflitto di riduzione del turno è un conflitto tra un token e una produzione .

In Yacc e Bison, non solo i token, ma anche le produzioni hanno una priorità. L'utente può contrassegnare i token con priorità (come è normalmente fatto) e le produzioni (a cui non è stata data una priorità esplicita) hanno la loro priorità desunta. La priorità di una produzione è uguale alla priorità del token più a destra nella produzione.

In "E :: = E * E", il token più a destra è "*", quindi nel turno ridurre il conflitto sopra la priorità della riduzione è '*', e la priorità dello spostamento è '+', e poiché la priorità di '*' è superiore a '+', decidiamo di ridurre piuttosto che spostare. Come altro esempio, il token più a destra di "A :: = a b B c d C D E" è "d" (con lettere maiuscole che non sono minuti).

L'aggiunta di "A :: = a b B c d C D E% prec a" a una produzione in Yacc e Bison dà esplicitamente a quella produzione la priorità di 'a', ma questo non è normalmente fatto. Si noti che alcune produzioni potrebbero non avere un token più a destra, o la priorità tra i token non è definita, in cui i casi Yacc e Bison ricadono per spostarsi sempre per risolvere i conflitti (Yacc e Bison creano sempre una tabella completamente deterministica, a meno che non sia in modalità GLR) .

Per completezza: l'azione con priorità più alta vince, quindi se la produzione ha una priorità più alta del token, riduciamo invece di spostare. Se le priorità sono uguali, osserviamo l'associatività: l'associatività di sinistra significa riduzione, l'associatività giusta significa spostamento. 'nonassoc' è il terzo tipo di 'associatività' e indica un errore: il conflitto di shift / riduzione viene risolto rimuovendo le voci entrambe nella tabella, quindi il parser rifiuta gli input che entrano in quello stato con quello lookahead.

Bene, permettimi di prendere il primo parser che riesco a trovare per risolvere questo tipo di problema automaticamente e vedere cosa fa. Secondo il link il loro valore predefinito è di scegliere lo spostamento su una riduzione se c'è un conflitto di riduzione del turno e per scegliere la prima regola nel file di grammatica se esiste un conflitto di riduzione-riduzione. (Considerano i conflitti di riduzione della riduzione come problemi più seri).