ricorsione sinistra - Left recursion

Nella teoria dei linguaggi formali di informatica , la ricorsione a sinistra è un caso particolare di ricorsione in cui una stringa viene riconosciuto come parte di un linguaggio per il fatto che si decompone in una stringa da quella stessa lingua (a sinistra) e un suffisso (su la destra). Ad esempio, può essere riconosciuto come somma perché può essere suddiviso in , anche una somma, e , un suffisso adeguato. ${\ Displaystyle 1 + 2 + 3}$ ${\ Displaystyle 1 + 2}$ ${\ Displaystyle {}} +3$

In termini di grammatica libera dal contesto , un non terminale è il left-recursive se il simbolo più a sinistra in una delle sue produzioni è di per sé (nel caso di ricorsione diretta a sinistra) o può essere si è fatto da una sequenza di sostituzioni (nel caso di indiretta ricorsione a sinistra).

Definizione

Una grammatica è lasciato ricorsiva se e solo se esiste un simbolo non terminale che può derivare ad un modulo sentenziale con se stesso come il simbolo più a sinistra. simbolicamente, ${\ A displaystyle}$

{\ Displaystyle A \ Rightarrow ^ {+} A \ alpha}

,

dove indica l'operazione di produzione di una o più sostituzioni, ed è qualsiasi sequenza di simboli terminali e non terminali. ${\ Displaystyle \ Rightarrow ^ {+}}$ ${\ Displaystyle \ alpha}$

ricorsione diretta sinistra

ricorsione diretto sinistro si verifica quando la definizione può essere soddisfatta con un solo sostituzione. Si richiede una regola della forma

{\ Displaystyle A \ A \ alpha}

dove è una sequenza di non-terminali e terminali. Ad esempio, la regola ${\ Displaystyle \ alpha}$

{\ Displaystyle {\ mathit {espressione}} \ a {\ mathit {espressione}} + {\ mathit {Term}}}

è direttamente left-recursive. A sinistra a destra parser discesa ricorsiva per questa regola potrebbe essere simile

void Expression() {
  Expression();
  match('+');
  Term();
}

e tale codice dovrebbe cadere in una ricorsione infinita quando viene eseguito.

Indiretta ricorsione sinistra

Indiretta ricorsione sinistra si verifica quando la definizione di ricorsione sinistra è soddisfatto tramite diverse sostituzioni. Esso comporta una serie di regole seguendo il modello

{\ Displaystyle A_ {0} \ a \ beta _ {0} {1} A_ \ alpha _ {0}}

{\ A_ displaystyle {1} \ a \ beta _ {1} A_ {2} \ alpha _ {1}}

{\ displaystyle \ cdots}

{\ A_ displaystyle {n} \ a \ beta _ {n} A_ {0} \ alpha _ {n}}

dove sono sequenze che possono ogni producono la stringa vuota , mentre può essere qualsiasi sequenza di simboli terminali e non terminali affatto. Si noti che queste sequenze possono essere vuote. la derivazione ${\ Displaystyle \ beta _ {0}, \ beta _ {1}, \ ldots, \ beta _ {n}}$ ${\ Displaystyle \ alpha _ {0}, \ alpha _ {1}, \ ldots, \ alpha _ {n}}$

{\ Displaystyle A_ {0} \ Rightarrow \ beta _ {0} A_ {1} \ alpha _ {0} \ Rightarrow ^ {+} A_ {1} \ alpha _ {0} \ Rightarrow \ beta _ {1} A_ {2} \ alpha _ {1} \ alpha _ {0} \ Rightarrow ^ {+} \ cdots \ Rightarrow ^ {+} A_ {0} \ alpha _ {n} \ dots \ alpha _ {1} \ alpha _ {0}}

poi dà come più a sinistra nella sua forma definitiva sentenziale. ${\ A_ displaystyle {0}}$

Rimozione di ricorsione sinistra

Ricorsione sinistra pone spesso problemi per i parser, sia perché li conduce in una ricorsione infinita (come nel caso della maggior parte dei parser top-down ), o perché si aspettano le regole in una forma normale che vieta (come nel caso di molti bottom-up parser , tra cui l' algoritmo di CYK ). Pertanto, una grammatica è spesso pre-elaborato per eliminare la ricorsione sinistra.

Rimozione ricorsione diretta sinistra

L'algoritmo generale per rimuovere sinistra ricorsione diretta segue. Diversi miglioramenti a questo metodo sono state fatte. Per un non terminale sinistra ricorsiva , scartare le regole della forma e non quelli che rimangono: ${\ A displaystyle}$ ${\ Displaystyle A \ rightarrow A}$

{\ Displaystyle A \ rightarrow A \ alpha _ {1} \ metà \ ldots \ mid A \ alpha _ {n} \ metà \ beta _ {1} \ metà \ ldots \ metà \ beta _ {m}}

dove:

ognuno è una sequenza non vuota di non terminali e terminali, e ${\ Displaystyle \ alpha}$
ognuno è una sequenza di non-terminali e terminali che non iniziano con . ${\ Displaystyle \ beta}$ ${\ A displaystyle}$

Sostituire questi con due serie di produzioni, una serie per : ${\ A displaystyle}$

{\ Displaystyle A \ rightarrow \ beta _ {1} A {^ \ prime} \ metà \ ldots \ metà \ beta _ {m} A ^ {\ prime}}

e un altro set per il fresco non terminale (spesso chiamato la "coda" o il "riposo"): ${\ A displaystyle '}$

{\ A displaystyle ^ {\ prime} \ rightarrow \ alpha _ {1} A {^ \ prime} \ metà \ ldots \ metà \ alpha _ {n} A ^ {\ prime} \ metà \ epsilon}

Ripetere questa operazione fino a quando non resti diretti ricorsione sinistra.

A titolo di esempio, si consideri il set di regole

{\ Displaystyle {\ mathit {espressione}} \ rightarrow {\ mathit {espressione}} + {\ mathit {espressione}} \ metà {\ {mathit Integer}} \ metà {\ mathit {string}}}

Questo potrebbe essere riscritta per evitare la ricorsione sinistra come

{\ Displaystyle {\ mathit {espressione}} \ rightarrow {\ {mathit Integer}} \, {\ mathit {espressione}} '\ metà {\ mathit {string}} \, {\ mathit {espressione}}'}

{\ Displaystyle {\ mathit {espressione}} '\ rightarrow {} + {\ mathit {espressione}} \, {\ mathit {espressione}}' \ mid \ epsilon}

Rimozione di tutte ricorsione sinistra

Attraverso la creazione di un ordinamento topologico sul non terminali, il processo di cui sopra può essere esteso per eliminare anche la ricorsione indiretta sinistra:

Ingressi Una grammatica: una serie di non-terminali e le loro produzioni ${\ A_ displaystyle {1}, \ ldots, A_ {n}}$

Uscita Una grammatica modificato generare la stessa lingua, ma senza ricorsione sinistra

Per ogni non terminale : ${\ A_ displaystyle {i}}$
1. Ripetere fino a quando un'iterazione lascia invariata la grammatica:
  1. Per ogni regola , essendo una sequenza di terminali e non terminali: ${\ A_ displaystyle {i} \ rightarrow \ alpha _ {i}}$ ${\ Displaystyle \ alpha _ {i}}$
    1. Se inizia con un non terminale e : ${\ Displaystyle \ alpha _ {i}}$ ${\ Displaystyle A_ {j}}$ ${\ J displaystyle <i}$
      1. Lasciate stare senza il suo leader . ${\ Displaystyle \ beta _ {i}}$ ${\ Displaystyle \ alpha _ {i}}$ ${\ Displaystyle A_ {j}}$
      2. Rimuovere la regola . ${\ A_ displaystyle {i} \ rightarrow \ alpha _ {i}}$
      3. Per ogni regola : ${\ Displaystyle A_ {j} \ rightarrow \ alpha _ {j}}$
        Aggiungere la regola . ${\ A_ displaystyle {i} \ rightarrow \ alpha _ {j} \ beta _ {i}}$
2. Rimuovere ricorsione diretta fianco destro come descritto sopra. ${\ A_ displaystyle {i}}$

Si noti che questo algoritmo è molto sensibile a l'ordinamento non terminale; ottimizzazioni spesso si concentrano su come scegliere bene questo ordinamento.

insidie

Anche se le trasformazioni di cui sopra conservano il linguaggio generato da una grammatica, possono cambiare gli alberi di analisi che testimoniano il riconoscimento stringhe. Con adatto contabilità, albero riscrittura può recuperare gli originali, ma se questo passaggio viene omesso, le differenze possono cambiare la semantica di un parse.

Associatività è particolarmente vulnerabile; operatori di sinistra-associativi compaiono di solito in diritto associativo simile regime riservato dalla nuova grammatica. Per esempio, a partire da questa grammatica:

{\ Displaystyle {\ mathit {espressione}} \ rightarrow {\ mathit {espressione}} \, - \, {\ mathit {Term}} \ metà {\ mathit {Term}}}

{\ Displaystyle {\ mathit {Term}} \ rightarrow {\ mathit {Term}} \, * \, {\ mathit {fattore}} \ metà {\ mathit {fattore}}}

{\ Displaystyle {\ mathit {fattore}} \ rightarrow ({\ mathit {espressione}}) \ metà {\ {mathit Integer}}}

le trasformazioni standard di rimuovere ricorsione sinistra dare il seguente:

{\ Displaystyle {\ mathit {espressione}} \ rightarrow {\ mathit {Term}} \ {\ mathit {espressione}} '}

{\ Displaystyle {\ mathit {espressione}} '\ rightarrow {} - {\ mathit {Term}} \ {\ mathit {espressione}}' \ mid \ epsilon}

{\ Displaystyle {\ mathit {Term}} \ rightarrow {\ mathit {fattore}} \ {\ mathit {Term}} '}

{\ Displaystyle {\ mathit {Term}} '\ rightarrow {} * {\ mathit {fattore}} \ {\ mathit {Term}}' \ mid \ epsilon}

{\ Displaystyle {\ mathit {fattore}} \ rightarrow ({\ mathit {espressione}}) \ metà {\ {mathit Integer}}}

Parsing della stringa "1 - 2 - 3" con la prima grammatica in un parser LALR (in grado di gestire grammatiche sinistra-ricorsive) avrebbe comportato l'albero sintattico:

analisi Sinistra-ricorsiva di una doppia sottrazione

Questo parse gruppi di alberi i termini a sinistra, dando la semantica corretta (1 - 2 - 3) .

Analisi con il secondo la grammatica dà

analisi destro del ricorsivo di una doppia sottrazione

che, opportunamente interpretati, significa 1 + (-2 + (-3)) , anche corretti, ma meno fedele all'ingresso e molto più difficile da implementare per alcuni operatori. Avviso come termini a destra appaiono più profondo nella struttura, tanto quanto una grammatica destro ricorsiva li avrebbe organizzare per 1 - (2 - 3) .

Accogliere la ricorsione sinistra in analisi top-down

Una grammatica formale che contiene la ricorsione sinistra non può essere analizzato da un LL (k) -parser o altro ingenuo parser discesa ricorsiva a meno che non viene convertito in un debolmente equivalente giusta forma-ricorsiva. Al contrario, la ricorsione sinistra è preferito per parser LALR perché comporta utilizzo pila inferiore ricorsione a destra . Tuttavia, più sofisticati parser top-down possono implementare generali grammatiche context-free per uso di riduzione. Nel 2006, Frost Hafiz descritto un algoritmo che accoglie grammatiche ambigue con scalo sinistra-ricorsiva regole di produzione . Tale algoritmo è stato esteso ad una completa analisi algoritmo per ospitare indiretta nonché ricorsione diretta fianco in polinomiale tempo, e per generare rappresentazioni compatte polinomio dimensioni del numero potenzialmente esponenziale di alberi di analisi per le grammatiche altamente ambigue di Frost, Hafiz e Callaghan in 2007 . Gli autori hanno poi implementato l'algoritmo come un insieme di combinatori parser scritti nel Haskell linguaggio di programmazione.

Guarda anche

ricorsione di coda

Riferimenti

^ Note sulla teoria formale del linguaggio e di analisi , James Potenza, Dipartimento di Informatica National University of Ireland, Maynooth Maynooth, Co Kildare, Irlanda. JPR02
^ Moore, Robert C. (maggio 2000). "Rimozione di ricorsione sinistra da Context-Free grammatiche" (PDF) . 6 ° Applied Natural Language Processing Conference : 249-255.
^ Gelo, R .; R. Hafiz (2006). "Un nuovo top-down-Analisi Algoritmo per ospitare Ambiguità e ricorsione sinistra in tempo polinomiale" . ACM SIGPLAN Annunci . 41 (5): 46-54. doi : 10,1145 / 1.149.982,1149,988 mila ., Disponibile presso l'autore a http://hafiz.myweb.cs.uwindsor.ca/pub/p46-frost.pdf Archiviato 2015/01/08 alla Wayback Machine
^ Gelo, R .; R. Hafiz; P. Callaghan (giugno 2007). "Modulare ed efficiente top-down di analisi per ambigui sinistra ricorsive grammatiche" (PDF) . 10 ° Workshop internazionale sul parsing Technologies (IWPT), ACL-SIGPARSE : 109-120. Archiviata da quello originale (PDF) su 2011-05-27.
^ Gelo, R .; R. Hafiz; P. Callaghan (gennaio 2008). Parser combinatori per ambigui sinistro ricorsivi Grammatiche (PDF) . 10 ° Simposio Internazionale sugli aspetti pratici della dichiarative Lingue (PADL), ACM-SIGPLAN . Lecture Notes in Computer Science. 4902 . pp. 167-181. doi : 10.1007 / 978-3-540-77442-6_12 . ISBN 978-3-540-77441-9.

link esterno

Considerazioni pratiche per LALR (1) Grammatiche

[1] Note sulla teoria formale del linguaggio e di analisi , James Potenza, Dipartimento di Informatica National University of Ireland, Maynooth Maynooth, Co Kildare, Irlanda. JPR02

[Moore2000-2] Moore, Robert C. (maggio 2000). "Rimozione di ricorsione sinistra da Context-Free grammatiche" (PDF) . 6 ° Applied Natural Language Processing Conference : 249-255.

[FrostHafiz2006-3] Gelo, R .; R. Hafiz (2006). "Un nuovo top-down-Analisi Algoritmo per ospitare Ambiguità e ricorsione sinistra in tempo polinomiale" . ACM SIGPLAN Annunci . 41 (5): 46-54. doi : 10,1145 / 1.149.982,1149,988 mila ., Disponibile presso l'autore a http://hafiz.myweb.cs.uwindsor.ca/pub/p46-frost.pdf Archiviato 2015/01/08 alla Wayback Machine

[FrostHafizCallaghan2007-4] Gelo, R .; R. Hafiz; P. Callaghan (giugno 2007). "Modulare ed efficiente top-down di analisi per ambigui sinistra ricorsive grammatiche" (PDF) . 10 ° Workshop internazionale sul parsing Technologies (IWPT), ACL-SIGPARSE : 109-120. Archiviata da quello originale (PDF) su 2011-05-27.

[FrostHafizCallaghan2008-5] Gelo, R .; R. Hafiz; P. Callaghan (gennaio 2008). Parser combinatori per ambigui sinistro ricorsivi Grammatiche (PDF) . 10 ° Simposio Internazionale sugli aspetti pratici della dichiarative Lingue (PADL), ACM-SIGPLAN . Lecture Notes in Computer Science. 4902 . pp. 167-181. doi : 10.1007 / 978-3-540-77442-6_12 . ISBN 978-3-540-77441-9.

Languages

In other projects