Grammatica ambigua

Question

Sto osservando la seguente grammatica e credo che sia ambigua alla riga 3, ma non è sicura.

<SL> → <S> 
<SL> → <SL> <S> 
<S> → i <B> <S> e <S> 
<S> → i <B> <S> 
<S> → x 
<S> → y 
<B> → 5 
<B> → 13 

Ho trovato questa stringa xi13yi5xeyx Credo genera due diversi alberi di analisi, ma non sono sicuro se im facendo male.

Qualcuno può verificare i miei risultati?

Answer 1

Sì, la tua grammatica è una grammatica ambigua!
_{Non hai parlare Ma penso <SL> è iniziare valida}

Usando le regole di grammatica possiamo trarre più di un albero sintattico (due) per strizzare i5i5yey come followes:

 <SL>        <SL> 
     |         | 
     <S>        <S> 
    //|\ \       /| \ 
    // | \ \      /| \ 
// | \ \      / | \ 
// | \ \      i <B> <S>  
/| | | \       |//|\ \  
i <B> <S> e <S>      5// | \ \ 
// | \  |      // | \ \ 
// | \ y      // | \ \ 
5 i <B> <S>       /| | | \ 
     | |       i <B> <S> e <S> 
     5 y        | |  | 
              5 y  y 

Struttura di entrambi gli alberi di analisi sono diversi due la grammatica è una grammatica ambigua!

È possibile estendere sopra schema per generare stringa albero xi13yi5xeyx, (lascio questo come un esercizio per voi)

Importante è la lingua di generare da questa grammatica è not ambiguous language .E la sua possibile scrivere un grammatica equivalente non ambigua per questa grammatica che genera sempre un albero univoco per ogni stringa nella lingua della grammatica.

SUGGERIMENTO: per scrivere una grammatica non ambigua.

La grammatica è molto simile alla grammatica per if loop in linguaggio C (notare una lingua diversa con sintassi diversa per if loop). e ha risolto in quasi tutti i libri di progettazione del compilatore.
Resolving the General Dangling Else/If-Else Ambiguity

Riferimento: Libro compilatori Principi, la tecnica e gli strumenti di Aho-Ullman paragrafo 4.5 conflitti durante il turno e-Ridurre l'analisi.