模棱两可的语法

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,(我将此作为练习留给您)

重要的是,这种语法生成的语言不是含糊不清的语言.它可以为这种语法编写一个等效的明确语法,它总是为语法语言中的每个字符串生成唯一的树.

提示:编写明确的语法.

该语法与if loopC语言中的语法非常相似(注意具有不同语法的不同语言if loop).它几乎在所有编译器设计书中都得到了解决.
解决一般悬空/如果不明确的歧义

参考:Book Compilers原理,技术和工具Aho-Ullman 第4.5节在转换和减少解析期间的冲突.