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我相信会生成两个不同的解析树，但我不确定我是否做错了。

有人可以验证我的发现吗？

Answer 1

是的，您的语法是模棱两可的语法！
_{你没有提到但我认为<SL>开始可行}

使用您的语法规则，我们可以绘制一个以上的解析树（两个）进行拧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   

两种解析树的结构不同，两种文法都是二义文法！

您可以扩展上图以生成树字符串xi13yi5xeyx，（我将其作为练习留给您）

重要的是该语法生成​​的语言不是歧义语言。并且可以为该语法编写一个等效的明确语法，该语法总是为语法语言中的每个字符串生成唯一的树。

提示：编写明确的语法。

语法与 C 语言中的 for 语法非常相似if loop（注意不同的语言具有不同的语法 for if loop）。它在几乎所有编译器设计书中都得到了解决。
解决一般悬空 Else/If-Else 歧义

参考： Aho-Ullman 的书籍编译器原理、技术和工具第 4.5 节在 Shift 和归约解析期间发生冲突。