あいまいな文法

Question

私は次の文法を見ていますが、私はそれが3行目のあいまいだと思います。

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

は、私は二つの異なる構文解析ツリーを生成し、信じて、この文字列 xi13yi5xeyxを見つけましたが、イムは、それは間違っているのかどうかはわかりません。

私の調査結果を確認できますか？

Answer 1

はい、あなたの文法はあいまいな文法です！
_{あなたは言及していないが、私は<SL>は我々がfollowes i5i5yeyを絞るためにもっとして1つのパースツリー（）を描くことができ、あなたの文法規則を使用して実行可能な}

を開始していると思う：

 <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 

構造2つの構文木の文法は全く異なります。あいまいな文法です！あなたは木の文字列xi13yi5xeyxを生成するために、図の上に拡張することができ

、（私はあなたのための練習としてこれを残しています）

重要

言語は、この文法によって生成されnot ambiguous languageある.AND書くことがその可能文法の言語で各文字列に固有のツリーを常に生成する、この文法のための同等の明瞭な文法。

HINT：曖昧さのない文法を書く。

文法は、C言語でif loopの文法（文法が異なるif loop）に似ています。ほぼすべてのコンパイラデザインブックで解決されました。
Resolving the General Dangling Else/If-Else Ambiguity

参考：シフト中アホ、ウルマン4.5節競合によってブックコンパイラの原則、テクニック、およびツールと-減らし解析を。