2 文法和语言

文法的类型¶

  一个文法 $G$ 被定义为四元组 $(V _ N,V _ T,P,S)$，这些符号的定义可以在书上找到。不过很多时候文法都被简记为 $G[S]$。

0型文法¶

  属于是没有任何约束的文法，也可以说任意文法都是0型文法。任意文法的产生式 $\alpha\to\beta$，那么 $\alpha$ 至少含有一个非终结符。

1型文法¶

  又被称为上下文有关文法，在0型文法的基础上，对其规则 $P$ 进一步作出要求：任意产生式 $\alpha\to\beta$，要么 $\beta=\varepsilon$，要么 $|\alpha|\leq|\beta|$。
  被称作上下文有关文法，具体可以参考 $\gamma\red{A}\delta\to\gamma\red{\beta\theta}\delta$，这里 $A$ 被替换为 $\beta\theta$ 是存在上下文条件的。但其实1型文法只是被称为“上下文有关”，实际上并不一定满足，例如包含 $A\to ab$ 这种的文法也算是1型文法，但是和 $A$ 的上下文没关系。

2型文法¶

  又被称为上下文无关文法，在1型文法的基础上，对其规则 $P$ 进一步作出要求：任意产生式 $\alpha\to\beta$，有 $|\alpha|=1$。
  2型文法是真的“上下文无关”，因为任意规则的左部一定有且只有一个非终结符。

3型文法¶

  又被称为正规文法，在2型文法的基础上，对其规则 $P$ 进一步作出要求：任意产生式 $\alpha\to\beta$，以下条件必须成立一个：

• $\beta = \varepsilon$。
• $\beta$ 是一个终结符。
• $\beta$ 是一个终结符和一个非终结符的组合，且非终结符总是在终结符的左边（右边）。

如果非终结符总是在终结符的左边，称为左线性文法；如果在右边，称为右线性文法。注意这里的定义和课本上的定义是不一样的，这里是不严格的正则文法，课本上的拓展正则文法中 $\beta$ 可以是终结符串（即多个终结符）。

2型文法及其语法树¶

最左/最右推导/归约¶

  从 $S$ 出发到一个句子，其中会经过很多步推导。推导用的符号是“$\Rightarrow$”，规则用的符号是“$\to$”。根据每次选择进行推导的非终结符的位置，如果位于最左边称为最左（Left Most）推导，如果位于最右边则称为最右（Right Most）推导。相应地，也可以定义最左归约和最右归约。
  之所以把最右推导称为规范推导，是因为最左推导会产生左递归的严重问题，而最右推导则不会产生这样的问题。

语法树¶

  语法树中有两个概念：

• 子树：由某一结点连同所有分支组成的部分。
• 简单子树：仅具有单层分支的子树（树高为 $2$ 的子树）。

graph TD
    A1["F"] --> B1["T"]
    B1 --> C1["F"]
    B1 --> C2["*"]
    B1 --> C3["T"]
    C1 --> D1["i"]
    C3 --> D2["F"]
    D2 --> E1["("]
    D2 --> E2["E"]
    D2 --> E3[")"]
    E2 --> F1["E"]
    E2 --> F2["+"]
    E2 --> F3["T"]
    F1 --> G1["T"]
    F3 --> G2["F"]
    G1 --> H1["T"]
    G1 --> H2["/"]
    G1 --> H3["F"]

graph TD
    A1["F"] --> B1["T"]
    B1 --> C1["T"]
    B1 --> C2["*"]
    B1 --> C3["F"]
    C1 --> D1["F"]
    subgraph subtree1
    C3 --> D2["i"]
    end
    D1 --> E1["("]
    D1 --> E2["E"]
    D1 --> E3[")"]
    E2 --> F1["E"]
    E2 --> F2["+"]
    E2 --> F3["T"]
    F1 --> G1["T"]
    F3 --> G2["F"]
    G1 --> H1["T"]
    G1 --> H2["/"]
    G1 --> H3["F"]
    subgraph subtree2
    F3;G2
    end
    subgraph subtree3
    G1;H1;H2;H3
    end

  基于这个语法树的概念，又可以产生三个新的概念：

• 一个子树的树叶全体被称为短语，但是这个子树的树根不能是叶子结点，换句话说这个子树不能只有根。
• 一个简单子树的树叶全体被称为简单短语。
• 一个句型最左的简单短语被称为句柄。

文法的二义性¶

  定义：如果文法 $G$ 的某个句子存在至少两棵不同的语法树，则称文法 $G$ 是二义性的。没有二义性的文法，任意一个句子，无论是最左推导、最右推导还是随意推导，语法树都是一样的。
  需要注意的是，文法的二义性是不可判定问题。即不存在一个算法，在有限步骤内，确切地判定一个文法是不是二义性的。但是有些时候，有二义性是可以通过举出一个句子的多个不同语法树来证明的。