Grammatica ambigua - Ambiguous grammar

In informatica , una grammatica ambigua è una grammatica context-free per la quale esiste una stringa che può avere più di una derivazione o albero di analisi più a sinistra , mentre una grammatica univoca è una grammatica context-free per la quale ogni stringa valida ha un unico più a sinistra derivazione o albero di analisi. Molte lingue ammettono sia grammatiche ambigue che non ambigue, mentre alcune lingue ammettono solo grammatiche ambigue. Qualsiasi lingua non vuota ammette una grammatica ambigua prendendo una grammatica non ambigua e introducendo una regola o un sinonimo duplicato (l'unica lingua senza grammatiche ambigue è la lingua vuota). Un linguaggio che ammette solo grammatiche ambigue è chiamato linguaggio intrinsecamente ambiguo e ci sono linguaggi privi di contesto intrinsecamente ambigui . Le grammatiche deterministiche libere dal contesto sono sempre non ambigue e sono un'importante sottoclasse di grammatiche non ambigue; ci sono grammatiche univoche non deterministiche, tuttavia.

Per i linguaggi di programmazione per computer , la grammatica di riferimento è spesso ambigua, a causa di problemi come il problema del dangling else . Se presenti, queste ambiguità vengono generalmente risolte aggiungendo regole di precedenza o altre regole di analisi sensibili al contesto , quindi la grammatica della frase complessiva non è ambigua. Alcuni algoritmi di analisi (come ( parser Earley o GLR ) possono generare set di alberi di analisi (o "foreste di analisi") da stringhe sintatticamente ambigue .

Esempi

Linguaggio banale

L'esempio più semplice è la seguente grammatica ambigua per il linguaggio banale, che consiste solo nella stringa vuota:

A → A | ε

…significa che una produzione può essere di nuovo se stessa o la stringa vuota. Quindi la stringa vuota ha derivazioni più a sinistra di lunghezza 1, 2, 3, e in effetti di qualsiasi lunghezza, a seconda di quante volte viene usata la regola A → A.

Questa lingua ha anche la grammatica univoca, costituita da un'unica regola di produzione :

A →

…il che significa che la produzione univoca può produrre solo la stringa vuota, che è l'unica stringa nella lingua.

Allo stesso modo, qualsiasi grammatica per una lingua non vuota può essere resa ambigua aggiungendo duplicati.

Stringa unaria

Il linguaggio regolare di stringhe unarie di un dato carattere, diciamo 'a'(l'espressione regolare a*), ha la grammatica non ambigua:

A → aA | ε

…ma ha anche la grammatica ambigua:

A → aA | Aa | ε

Questi corrispondono a produrre un albero associativo destro (per la grammatica univoca) oa consentire l'associazione sia sinistra che destra. Questo è elaborato di seguito.

Addizione e sottrazione

La grammatica libera dal contesto

A → A + A | A − A | un

è ambiguo poiché ci sono due derivazioni più a sinistra per la stringa a + a + a:

     UN → LA + LA      UN → LA + LA
     → a + LA      → A + A + A (la prima A è sostituita da A+A. La sostituzione della seconda A produrrebbe una derivazione simile)
     → la + LA + LA      → la + LA + LA
     → a + a + A      → a + a + A
     → a + a + a      → a + a + a

Come altro esempio, la grammatica è ambigua poiché ci sono due alberi di analisi per la stringa a + a - a:

Leftmostderivations jaredwf.svg

Il linguaggio che genera, tuttavia, non è intrinsecamente ambiguo; la seguente è una grammatica non ambigua che genera la stessa lingua:

A → A + a | A − a | un

Penzolando altro

Un esempio comune di ambiguità nei linguaggi di programmazione dei computer è il problema del penzolante else . In molte lingue, l' istruzione elsein un'istruzione If–then(–else) è facoltativa, il che si traduce in condizionali nidificati che hanno più modi di essere riconosciuti in termini di grammatica libera dal contesto.

Concretamente, in molte lingue si possono scrivere condizionali in due forme valide: la forma if-then e la forma if-then-else – in effetti, rendendo facoltativa la clausola else:

In una grammatica contenente le regole

Statement → if Condition then Statement |
            if Condition then Statement else Statement |
            ...
Condition → ...

possono apparire alcune strutture di frase ambigue. L'espressione

if a then if b then s else s2

può essere analizzato come

if a then begin if b then s end else s2

o come

if a then begin if b then s else s2 end

a seconda che elsesia associato al primo ifo al secondo if.

Questo viene risolto in vari modi in diverse lingue. A volte la grammatica viene modificata in modo che non sia ambigua, ad esempio richiedendo una endifdichiarazione o rendendola elseobbligatoria. In altri casi la grammatica viene lasciata ambigua, ma l'ambiguità viene risolta rendendo la grammatica della frase complessiva sensibile al contesto, ad esempio associando an elseal più vicino if. In quest'ultimo caso la grammatica è univoca, ma la grammatica libera dal contesto è ambigua.

Una grammatica univoca con molteplici derivazioni

L'esistenza di più derivazioni della stessa stringa non basta a indicare che la grammatica è ambigua; solo più derivazioni più a sinistra (o, equivalentemente, più alberi di analisi) indicano ambiguità.

Ad esempio, la semplice grammatica

S → A + A
A → 0 | 1

è una grammatica non ambigua per la lingua { 0+0, 0+1, 1+0, 1+1 }. Mentre ognuna di queste quattro stringhe ha solo una derivazione più a sinistra, ha due diverse derivazioni, per esempio

S  A + A ⇒ 0 + A ⇒ 0 + 0

e

S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0

Solo la prima derivazione è quella più a sinistra.

Riconoscere grammatiche ambigue

Il problema della decisione se una grammatica arbitraria sia ambigua è indecidibile perché si può dimostrare che è equivalente al problema della corrispondenza di Post . Almeno, ci sono strumenti che implementano una procedura semi-decisiva per rilevare l'ambiguità delle grammatiche context-free.

L'efficienza dell'analisi grammaticale senza contesto è determinata dall'automa che la accetta. Le grammatiche deterministiche context-free sono accettate dagli automi pushdown deterministici e possono essere analizzate in tempo lineare, ad esempio dal parser LR . Questo è un sottoinsieme delle grammatiche context-free che sono accettate dall'automa pushdown e possono essere analizzate in tempo polinomiale, ad esempio dall'algoritmo CYK . Le grammatiche senza contesto non ambigue possono essere non deterministiche.

Ad esempio, il linguaggio dei palindromi di lunghezza pari sull'alfabeto di 0 e 1 ha la grammatica libera dal contesto univoca S → 0S0 | 1S1 | . Una stringa arbitraria di questo linguaggio non può essere analizzata senza prima leggere tutte le sue lettere, il che significa che un automa pushdown deve provare transizioni di stato alternative per adattarsi alle diverse lunghezze possibili di una stringa semi-parsata. Tuttavia, la rimozione dell'ambiguità grammaticale può produrre una grammatica deterministica libera dal contesto e quindi consentire un'analisi più efficiente. I generatori di compilatori come YACC includono funzionalità per la risoluzione di alcuni tipi di ambiguità, ad esempio utilizzando i vincoli di precedenza e associatività.

Linguaggi intrinsecamente ambigui

L'esistenza di linguaggi intrinsecamente ambigui è stata dimostrata con il teorema di Parikh nel 1961 da Rohit Parikh in un rapporto di ricerca del MIT.

Mentre alcuni linguaggi context-free (l'insieme di stringhe che può essere generato da una grammatica) hanno grammatiche sia ambigue che non ambigue, esistono linguaggi context-free per i quali non può esistere una grammatica priva di contesto univoca. Un esempio di linguaggio intrinsecamente ambiguo è l'unione di con . Questo insieme è context-free, poiché l'unione di due linguaggi context-free è sempre context-free. Ma Hopcroft e Ullman (1979) danno una prova che non c'è modo di analizzare senza ambiguità le stringhe nel sottoinsieme comune (non-context-free) .

Guarda anche

Riferimenti

  1. ^ Willem JM Levelt (2008). Introduzione alla teoria dei linguaggi formali e degli automi . Edizioni John Benjamins. ISBN 978-90-272-3250-2.
  2. ^ Scott, Elizabeth (1 aprile 2008). "Analisi in stile SPPF da Earley Recognizers" . Appunti elettronici in informatica teorica . 203 (2): 53-67. doi : 10.1016/j.entcs.2008.03.044 .
  3. ^ Tomita, Masaru. " Un efficiente algoritmo di analisi senza contesto aumentato ." Linguistica computazionale 13.1-2 (1987): 31-46.
  4. ^ Hopcroft, Giovanni ; Motwani, Rajeev ; Ullman, Jeffrey (2001). Introduzione alla teoria degli automi, ai linguaggi e al calcolo (2a ed.). Addison-Wesley. Teorema 9.20, pp. 405-406. ISBN 0-201-44124-1.
  5. ^ Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). "Analisi di grammatiche senza contesto utilizzando un risolutore SAT incrementale" (PDF) . Atti del 35th International Colloquium on Automata, Languages ​​and Programming (ICALP'08), Reykjavik, Islanda . Appunti delle lezioni di Informatica . 5126 . Springer-Verlag. pp. 410-422. doi : 10.1007/978-3-540-70583-3_34 .
  6. ^ Knuth, DE (luglio 1965). "Sulla traduzione delle lingue da sinistra a destra" (PDF) . Informazione e controllo . 8 (6): 607–639. doi : 10.1016/S0019-9958(65)90426-2 . Archiviato dall'originale (PDF) il 15 marzo 2012 . Estratto il 29 maggio 2011 .
  7. ^ Hopcroft, Giovanni ; Motwani, Rajeev ; Ullman, Jeffrey (2001). Introduzione alla teoria degli automi, ai linguaggi e al calcolo (2a ed.). Addison-Wesley. pp. 249-253. ISBN 0-201-44124-1.
  8. ^ Parikh, Rohit (gennaio 1961). Dispositivi generatori di linguaggio . Rapporto trimestrale sui progressi, Laboratorio di ricerca di elettronica, MIT.
  9. ^ p.99-103, Sez.4.7

Appunti

link esterno

  • dk.brics.grammar - un analizzatore di ambiguità grammaticale.
  • CFGAnalyzer - strumento per l'analisi di grammatiche context-free rispetto all'universalità del linguaggio, all'ambiguità e a proprietà simili.