Differenza tra grammatica ambigua e non ambigua
Share
Il differenza principale tra grammatica ambigua e non ambigua è che il grammatica ambigua è una grammatica libera dal contesto per la quale esiste una stringa che può avere più di una derivazione più a sinistra mentre una grammatica non ambigua è una grammatica libera dal contesto per la quale ogni stringa valida ha una derivazione estrema più a sinistra.
La grammatica si riferisce alle regole sintattiche nelle lingue naturali. Nel 1956, gli scienziati informatici introdussero un modello matematico di grammatica per scrivere il linguaggio del computer. Se è possibile derivare tutte le stringhe di una lingua usando una certa grammatica, allora si dice che la lingua sia generata da quella grammatica. La grammatica libera dal contesto è un tipo di grammatica. Questa grammatica genera un linguaggio privo di contesto. La grammatica libera dal contesto può essere ambigua o non ambigua. Per una stringa particolare, se ci sono due o più derivazioni, quella grammatica si dice che sia ambigua. Per una stringa particolare, se esiste una sola derivazione più a sinistra, quella grammatica è detta grammatica non ambigua.
Aree chiave coperte
1. Cos'è la grammatica ambigua
- Definizione, Esempio
2. Cos'è la grammatica non ambigua
- Definizione, Esempio
3. Differenza tra grammatica ambigua e non ambigua
- Confronto tra le principali differenze
Parole chiave
Grammatica ambigua, grammatica non ambigua
Cos'è la grammatica ambigua
Si dice che una grammatica sia ambigua se esistono due o più derivazioni per una stringa.
Figura 1: Grammatica ambigua
Supponiamo che esista una grammatica definita come segue.
G = (S, a + b, +, *, P, S Le regole di produzione sono le seguenti: S -> S + S | S * S | a | b. Supponiamo che sia necessario genera la stringa a + a * b.
Considerare, S -> S + S
Sostituendo 'a' per sinistra più S darai il seguente.
S-> a + S
La sostituzione di S * S per S è la seguente.
S-> a + S * S
Sostituendo 'a' per il sinistro più S darai l'output sottostante.
S -> a + a * S
Sostituendo 'b' per S si otterrà il seguente risultato.
S -> a + a * b
Questa è la stringa richiesta da generare.
Quando si utilizza l'altra regola di produzione, lo darà
S -> S * S
Applicare S + S a sinistra più S darà il seguente.
S -> S + S * S
Sostituisci 'a' per sinistra più S,
S -> a + S * S
Sostituendo 'a' per la sinistra più S,
S -> a + a * S
La sostituzione di "b" per S darà il seguente risultato.
S -> a + a * b
Di nuovo, ha generato la stringa richiesta. Pertanto, esiste più di una derivazione per generare la stringa. Pertanto, è una grammatica ambigua.
Cos'è la grammatica non ambigua
In una grammatica ambigua, una determinata stringa ha una derivazione più a sinistra unica. Fare riferimento alle seguenti regole di produzione.
S -> L | a, L -> LS | S
Considera la regola S -> L. Sostituire LS invece di L.
S -> LS
Sostituto S, per primo L.
S -> S S
Sostituendo 'a' per la S più a sinistra otterrai l'output di sotto.
S -> a S
La sostituzione di "a" per S darà il seguente.
S -> a a
Pertanto, una stringa ha una derivazione più a sinistra unica. Quindi, è una grammatica non ambigua.
Differenza tra grammatica ambigua e non ambigua
Definizione
Una grammatica ambigua è una grammatica libera dal contesto per la quale esiste una stringa che può avere più di una derivazione o alberi di analisi più a sinistra. La grammatica non ambigua è una grammatica libera dal contesto per cui ogni stringa valida ha una derivazione o un albero di analisi più a sinistra.
Numero di derivazioni più a sinistra
Nella grammatica ambigua, una stringa può avere due o più derivazioni più a sinistra ma, in una grammatica non ambigua, una stringa ha una derivazione più a sinistra unica.
Conclusione
La grammatica libera dal contesto può essere ambigua o non ambigua. La differenza tra grammatica ambigua e non ambigua è che la grammatica ambigua è una grammatica libera dal contesto per la quale esiste una stringa che può avere più di una derivazione all'estrema sinistra mentre una grammatica non ambigua è una grammatica libera dal contesto per cui ogni stringa valida ha una derivazione estrema più a sinistra.
Riferimento:
1. "Grammatica ambigua." Wikipedia, Wikimedia Foundation, 17 luglio 2018, disponibile qui.
2. "Design del compilatore | Grammatica ambigua. "GeeksforGeeks, 10 febbraio 2018, disponibile qui.
3. "Grammatica ambigua", Neso Academy, 29 marzo 2017, disponibile qui.
Cortesia dell'immagine:
1. "Leftmostderivations jaredwf" di Jaredwf in Wikipedia in inglese - Trasferito da en.wikipedia a Commons da EdwardHades (dominio pubblico) tramite Commons Wikimedia
