Mostrare una grammatica è ambiguo

Question

Mostrare una grammatica è ambiguo

#1 da (6 voti)

3

Ho preso la seguente domanda da un esame del corso compilatori:

Show that the following grammar is ambiguous.

S = XcY
X = a
Y = b | Z
Z = bW
W = d | ϵ

Ho disegnato il seguente albero:

Ho ragione nel ritenere che sia ambiguo perché acY può finire a acb (uno dei quali è seguito da un epslion) seguendo percorsi diversi?

grammar compiler parsing ambiguity

posta TomSelleck 01.01.2013 - 23:14

fonte

1 risposta

Leggi altre domande sui tag grammar compiler parsing ambiguity

Questo è un esempio di composizione o aggregazione? [duplicare] Quali sono le differenze tra i linguaggi di programmazione? [chiuso]

score 6 · Accepted Answer

Sì. Poiché epsilon significa che puoi riscrivere W come stringa vuota, acbW - > ACB. Come hai mostrato, ci sono due derivazioni più a sinistra per la stringa acb, che per definizione indica che la grammatica è ambigua.