Come aggiungere precedenza al parser LALR come in YACC?

Question

Come aggiungere precedenza al parser LALR come in YACC?

#1 da (5 voti)

3

Tieni presente che sto chiedendo di scrivere un parser LALR, non per scrivere regole per il parser LALR.

Quello di cui ho bisogno è ...

... per imitare le definizioni di precedenza di YACC. Non so come sia implementato, e di seguito descrivo quello che ho fatto e letto finora.

Per ora ho scritto un parser LALR di base. Passaggio successivo: aggiunta della precedenza, quindi 2+3*4 potrebbe essere analizzato come 2+(3*4) .

Ho letto sui parser di precedenza, tuttavia non vedo come adattarlo a LALR. Non capisco due punti:

come calcolare quando si inserisce il generatore di parentesi
come calcolare quante parentesi il generatore dovrebbe creare

Inserisco i generatori quando i simboli sono presi dall'input e messi in pila, giusto? Quindi diciamo che ho qualcosa del genere ( | denota il confine tra stack e input):

ID = 5 | + ... , a questo punto aggiungo aperto, quindi restituisce
ID = < 5 | + ... , poi ho letto più input
ID = < 5 + | 5 ... e altro
ID = < 5 + 5 | ; ... e altro
ID = < 5 + 5 ; | ...

A questo punto dovrei avere diversi movimenti di riduzione nel normale LALR, ma la parentesi aperta non corrisponde, quindi continuo a leggere più input. Il che non ha senso.

Quindi questo era quando problema.

E a proposito di conteggio , supponiamo di avere tali dati < 2 + < 3 * 4 > . Come umano posso vedere che l'ultimo generatore dovrebbe creare 2 parentesi, ma come calcolarlo? Dopotutto potrebbero esserci due scenari:

( 2 + ( 3 *4 )) - parentesi viene utilizzata per mostrare il risultato del generatore
o (2 + (( 3 * 4 ) ^ 5) perché c'era più input

Si noti che in entrambi i casi prima del 3 era aperto il generatore e dopo 4 c'era il generatore chiuso. Comunque in entrambi i casi, dopo aver letto 4 devo ridurre, quindi devo sapere che cosa "crea" il generatore.

parsing

posta greenoldman 03.12.2012 - 22:29

fonte

1 risposta

Leggi altre domande sui tag parsing

Un progettista può avviare un progetto open source? [chiuso] Memorizza molte stringhe di grandi dimensioni con frequenti "accodamenti" e poche letture

score 5 · Accepted Answer

Considera le seguenti regole:

[1] E -> E + E
[2] E -> E * E
[3] E -> num

Senza la precedenza, produrrebbe un errore di spostamento / riduzione quando si incontra il secondo operatore. La tabella ha un aspetto simile al seguente:

    num     +       *       $       E
0   S2      ---     ---     ---     1
1   ---     S3      S4      Accept  ---
2   ---     R3      R3      R3      ---
3   S2      ---     ---     ---     5
4   S2      ---     ---     ---     6
5   ---     R1/S3   R1/S4   R1      ---
6   ---     R2/S3   R2/S4   R2      ---

Con la precedenza, stai dicendo quale di "shift" e "riduzione" vuoi in caso di conflitti.

Se il primo operatore ha una precedenza inferiore, si sposta.
Se il primo operatore ha una precedenza più alta, lo riduci.
Se gli operatori hanno precedenti uguali, ed entrambi lo sono
- left associative, riduci.
- diritto associativo, si sposta.
- altrimenti, fallisci.

Ripulendo gli errori nella tabella, ottieni qualcosa del tipo:

    num     +       *       $       E
0   S2      ---     ---     ---     1
1   ---     S3      S4      Accept  ---
2   ---     R3      R3      R3      ---
3   S2      ---     ---     ---     5
4   S2      ---     ---     ---     6
5   ---     R1      S4      R1      ---
6   ---     R2      R2      R2      ---