Perché la ricorsione non è andata in loop?

Riscrittura grammaticale

Le grammatiche ricorsive a sinistra possono essere automaticamente riscritte per eliminare la ricorsione a sinistra. Ogni ricorsione deve avere qualche caso base, quindi possiamo sostituirlo. Supponi questa grammatica di esempio:

A ::= A B
    | A C
    | D
    | E

Possiamo introdurre una regola helper A_rest per raggruppare tutte le alternative ricorsive a sinistra in un'unica alternativa e una regola helper A_init che contiene tutte le alternative senza ricorsione a sinistra,

A ::= A A_rest | A_init
A_rest ::= B | C
A_init ::= D | E

Ora possiamo riscrivere A in

A ::= A_init | A_init A'
A' ::= A_rest | A_rest A'

e hanno scambiato la ricorsione a sinistra per la ricorsione a destra. Ciò consente a un parser LL di riconoscere le grammatiche ricorsive di sinistra - con un avvertimento: questa riscrittura cambia la struttura dell'albero di analisi risultante!

Assumi l'input 1 - 2 - 3 , dove - è il normale operatore di sottrazione sinistra. Poiché è associativo a sinistra, questo deve essere interpretato come (1 - 2) - 3 e l'interpretazione 1 - (2 - 3) non è valida. Quindi la descrizione di questo operatore è necessariamente ricorsiva a sinistra:

Subtraction ::= Subtraction '-' Number | Number

Questa regola ci darebbe l'albero di analisi

              Subtraction
                 / | \
      Subtraction '-' Number=3
           / | \
Subtraction '-' Number=2
    |
Number=1

, che corrisponde alla precedenza (1 - 2) - 3 . Ma se riscriviamo la regola per eliminare la ricorsione a sinistra, otteniamo la regola

Subtraction ::= Number | Number Subtraction'
Subtraction' ::= '-' Number | '-' Number Subtraction'

Questa regola ci darebbe l'albero di analisi

    Subtraction
        / \
Number=1   Subtraction'
          /     |     \
      '-'    Number=2  Subtraction'
                          / \
                       '-'   Number=3

, che corrisponde alla precedenza 1 - (2 - 3) che è errata. Inoltre, l'albero di analisi sembra gravemente deformato e non rappresenta più la struttura logica dell'input. Questo è male e inutilizzabile per le applicazioni pratiche. Potremmo provare a sistemare l'albero di analisi spostando i nodi in giro, ma c'è un'alternativa migliore:

Utilizza un algoritmo migliore: parser LR

Gli algoritmi di analisi top-down del tipo che stai probabilmente utilizzando (discesa ricorsiva?) sono limitati nella loro espressività, nella loro correttezza e nella loro efficienza. L'unica cosa che hanno per loro è che usano un approccio molto intuitivo, e questo è probabilmente l'unico motivo per cui sono ancora comunemente usati. Altri algoritmi di analisi come LR o LALR possono analizzare una gamma più ampia di grammatiche e possono farlo in tempo lineare, ma sono meno intuitivi e difficili da scrivere a mano. È per questo che generalmente usiamo generatori di parser per creare un parser da una grammatica, piuttosto che scrivere la grammatica a mano.

Il file di grammatica a cui sei collegato è una grammatica di Yacc. Yacc è uno strumento generatore di parser che utilizza l'algoritmo LALR - nessun problema con la ricorsione a sinistra, quasi come generale come LR, ma necessita di "tabelle di stato" più piccole di LR reale. LALR presenta alcune fastidiose limitazioni, ma al momento è l'algoritmo di parsing più comune in pratica per l'implementazione di linguaggi di programmazione "reali".

Gli algoritmi bottom-up come LR possono analizzare una gamma più ampia di grammatiche perché decidono quale alternativa applicare dopo hanno visto l'input appropriato. Utilizzando l'esempio Subtraction , supponiamo di vedere il flusso di token

Number=1 '-' Number=2 '-' Number=3

e avere la grammatica

Subtraction → Subtraction '-' Number
Subtraction → Number

. Userò un · per indicare la posizione corrente in una regola

• inizializza il parser. Abbiamo uno stack di token vuoto e siamo all'inizio di tutte le alternative:

  Subtraction → · Subtraction '-' Number
  Subtraction → · Number
  

• read token Number=1 . La pila di token del parser ora è

  | Number=1 |
  

  questo completa la regola Subtraction → Number · , quindi possiamo ridurre il lato destro della regola sul lato sinistro aggiungendo un frammento dell'albero di analisi allo stack. Lo stack del token ora è:

  | Subtraction |
  |     |       |
  |  Number=1   |
  

• read token '-' . Lo stack di token è

  | Subtraction | '-' |
  |     |       |     |
  |  Number=1   |     |
  

  siamo nelle regole

  Subtraction → Subtraction '-' · Number
  

• read token Number=2 . Lo stack di token è

  | Subtraction | '-' | Number=2 |
  |     |       |     |          |
  |  Number=1   |     |          |
  

  questo completa la regola

  Subtraction → Subtraction '-' Number ·
  

  quindi possiamo ridurre a

  |         Subtraction      |
  |            / | \         |
  | Subtraction '-' Number=2 |
  |     |                    |
  | Number=1                 |
  

• e così via per i token rimanenti, finché non vengono lasciati token di input e lo stack di token è costituito da un singolo elemento: l'albero di analisi finale.

Riconoscere dove siamo in quale regola e se una regola è stata completata da questo token viene generalmente eseguita da una macchina di stato DFA, motivo per cui abbiamo bisogno di calcolare le tabelle di stato dalla grammatica durante la costruzione del parser.

Le grammatiche ricorsive di sinistra possono generalmente essere riscritte aggiungendo simboli e riorganizzando leggermente. Wikipedia ha un buon esempio per una semplice grammatica della calcolatrice a quattro funzioni. Dal momento che sai che il primo terminale che vedi in top_statement_list deve essere un non-terminale valido per l'inizio di un top_statement , puoi riscrivere per verificare prima un top_statement invece di un top_statement_list .