知识点

• 推导
  • 最左推导（只变换最左边的非终结符）与最右推导
• 归约
• n步推导符号：*
• 推导树（语法树，语法分析树）
  • 根：文法的起始非终结符
  • 非叶子结点：文法的非终结符
  • 叶子结点：文法的终结符和$\epsilon$ϵ
  • 边缘：文法可以推导出的句子
• 文法从起始非终结符可以n步推导出一个句子，当且仅当至少存在一个以该句子为边缘的推导树
  • 同样的文法推导出同样的句子，可以有不止一个推导树
• 二型文法的二义性：
  • 定义：2型文法是二义的,当且仅当$\exists \omega \in L(G)$∃ω∈L(G),对于该句子存在两棵不同的具有边缘为ω的推导树。
  • 如果文法是二义的, 则一定存在某个由该文法产生的句子，必然能从不同的最左和最右推导推出。
• 上下文无关文法的简化

  • 消去无用符号

    1. 有用符号=生成符号+可达符号，有用符号之外的符号就是无用符号
    2. 第一步：找出所有生成符号——即从生成字符串归约到S遇到的所有非终结符，除了这些非终结符之外，其它的所有非终结符都是非生成符号。将包含有这些非生成符号的推导规则全部删除

    这里的生成字符串必须是纯字符串，不能带有非终结符

    3. 第三部：找出所有可达符号——即从S推导出到纯字符串遇到的所有非终结符。剩余同第二部。

重难点

二型文法的二义性

下述截图 From 《自动机理论、语言和计算导论》第三版

• 可见，若一个文法只要产生一个句子，可以被多个推导树表示，这个文法就有问题。此时就用二义性来说明这个文法。

• 不一样的推导也可以具有相同的推导树
• 接下来是2型文法二义性的严格定义：

上下文无关文法的简化

无用符号

注意：简化是文法的简化

• 简化的字符只考察非终结符
• 注意：在第二步化简时，只能从已知生成字符进行归约（纯字符串也是已知生成字符）。如果某一步归约右端中同时存在已知生成字符和非生成字符，这样的归约也是不成立的。即，归约的右端必须完全由已知生成字符构成。

因此务必确保要逐层归约，每一层完全归约后再归约下一层。否则遇到的在已知生成字符集之外的字符可能只是不已知的生成字符而不一定是非生成字符

• 第三步化简也是同理（起始非终结符S也是已知可达字符）

杂项

• 以下命题等价
  1. 字符串 $\omega \in T^*$ω∈T∗ 可以归约（递归推理）到非终结符A；
  2. A可以n步推导出w
  3. A可以n步最左推导出w（每一步都是最左推导）
  4. A可以n步最右推导出w（每一步都是最右推导）
  5. 存在一棵根结点为 A 的分析树，其边缘为 w.