grammar - あいまいな文法

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は2つの異なる解析ツリーを生成すると思いますが、間違っているかどうかはわかりません。

誰かが私の発見を確認できますか？

Answer 1

はい、あなたの文法は曖昧な文法です！
_{あなたは言及していませんが、私<SL>は実行可能であると思います}

文法規則を使用して、次のように、絞り用に1つ以上の解析ツリー（2つ）を描画でき ます。i5i5yey

       <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（これは演習として残しておきます）

重要なのは、この文法によって生成される言語があいまいな言語ではないことです。また、この文法と同等の明確な文法を記述して、文法の言語の各文字列に対して常に一意のツリーを生成することができます。

ヒント：曖昧さのない文法を書くこと。

文法はif loop、C言語の文法と非常によく似ています（異なる言語の構文が異なることに注意してif loopください）。そしてそれはほとんどすべてのコンパイラ設計書で解決しました。
一般的なぶら下がりElse/If-Elseのあいまいさの解決

参照： Aho-Ullmanによるブックコンパイラの原則、手法、およびツールセクション4.5は、Shiftおよび-Reduce解析中に競合します。