编译原理（五）习题1

给出它的左右推导怎么做？例如让你最左推导，你就用最右规约，让你最右推导，你就最左规约，规约比推导要方便。

语法分析树就是这样，没有什么神秘的。

一般来说，分析树与推导所用的顺序无关，甭管是最左最右，还是其他推导。但是说，如果一个文法里有类似加减运算符的那种类型的话，那么这个就是二义性的，判断一个文法是否是二义性的，就是看不同的形成方法是否会出现不同的语法树，精简一些，就是看是否出现运算符类型的终结符就行。

给定一个文法G，如果存在句子s，它有两棵不同的分析书，那么称他为二义性文法。解决方法是确定优先级和表达式重写，把优先级小的写入下一层。那么每次首先应该从最上层解决。

也就是说，你只要证明多次构造不存在不同文法树就行。

根据一个描述，是写出正则文法，还是一个自动机，还是一个正则表达式比较方便呢？感觉是正则文法是最简单的。

感觉并没有什么捷径。

感觉它的方法就是苦思冥想+极端条件想象。

这个哪里是苦思冥想出来的，这个分明就是死记住套路出来的。这看都看不懂。也不是说看不懂，就是死记住了，反正我是想不出来。

通过串相等实现，看来全世界范围内也没有好解法，这些题纯粹考验智商的。

光弄懂答案就费劲了。。。A是纯1串，B是纯0串，但是其中夹杂一个01的，卧槽这个真不懂了。。。

的确是不止一个，我也想出来一个：

S->0A1|1B0|empty

A->

不过自然没这么精简罢了。

若文法中存在形如：

A->ay|ab   两个产生式左部第一个符号相同，则不符合LL（1）文法，指代不明，会出现歧义就是，则表示存在左公因子，这个就叫左公因子啊。

解决方法：

转换成 A->aM1,aM2，aM3....的形式：

得：

A->aM

M->y|b

则成功提取左公因子；妙啊。。。

对于这种问题，解决方法就是找出每段的特征，要不就是写出尽可能全的例子，然后去适应它。

是不是二义的问题你就举出一个歧义的例子，然后通过造出两颗树就足够了。

这个的确有一点教育意义。其实一般就是这种做法：

有空串是例外，这样。