编译原理学习之：上下文无关文法（Context-free Grammar）和下推自动机（Push-down automata）

文章目录

上下文无关文法上下文无关文法的定义上下文无关文法举例上下文无关文法的二义性（Ambiguity）下推自动机下推自动机的定义下推自动机举例判断一个字符串是否属于 PDA 表示的语言（是不是 PDA 可以 accept 的）下推自动机举例2渐进式下推自动机（progressive push-down automata）确定性下推自动机（Deterministic Pushdown Automata）通过上下文无关文法构造下推自动机（CFG ⇒\Rightarrow⇒ PDA）上下文无关文法和下推自动机是等价的，就像正则文法和 NFA, DFA 等价一样

上下文无关文法

文法是一组替换规则，例如下面的例子

在下面的例子中，有几个重要的概念：变量 / 非终结符（variable）终结符（teminals）句子（sentence）句型（sentential forms）：变量 + 终结符

上面的例子中的语法规则可以表示语言 L(G)={wwR∣w∈0,1∗}L(G) = \{ww^R | w ∈ {0, 1}^∗\}L(G)={wwR∣w∈0,1∗}我们把使用上下文无关文法表示的语言称为上下文无关语言；有些 context-free 语言并不是 regular 的例如 {0n1n∣n≥1}\{0^n1^n | n ≥ 1\}{0n1n∣n≥1}

上下文无关文法的定义

VVV 是所有非终结符的集合Σ\SigmaΣ 是所有终结符的集合RRR 是所有语法规则的集合；其中语法规则的组成是“任意终结符和非终结符的组合”，符号表示为 (V∪Σ)∗(V\cup \Sigma)^*(V∪Σ)∗SSS 表示开始状态用 ⇒∗\Rightarrow^*⇒∗ 来表示 ⇒\Rightarrow⇒ 的自反闭包

上下文无关文法举例

如果我们没有特殊说明，那么规则的第一条使用的最左端的非终结符（variable）被认为是起始状态（start variable）假设我们现在有一个语言的某个句子为：

根据我们的文法规则，我们可以构造它的语法分析树

注意，一棵语法书的推导形式可以有很多种，它取决于我们想替换的非终结词的顺序；一般我们使用 leftmost（最左推导）方法进行推导：最左推导的意思就是永远都最先替换左侧的非终结符。

上下文无关文法的二义性（Ambiguity）

按照下面给定的语法规则：

如果我们要构造 3+7∗23+7*23+7∗2 的语法分析树，我们会得到下面的情况：

当我们构造语法分析树的时候，如果对于某一个句子，出现了多棵语法分析书，我们就认为他是具有歧义性（二义性）的

下推自动机

对于下面的语法规则

对句子 (3+7)∗2( 3 + 7 ) ∗ 2(3+7)∗2 采用最左推导可以得到：

之前我们使用的 NFA 和 DFA 受限于存储空间的问题，不能识别类似于 {0n1n,n>=0}\{0^n1^n, n>=0\}{0n1n,n>=0} 这种语言下推自动机通过一个 stack（栈）结构解决了这个问题

我们通过下面的这个过程，就能判断 aaa 和 bbb 存在的数量，从而判断一个语句（input）是否符合上述语言的定义

每一步的判断取决于三个部分输入的字符栈顶的元素当前的状态根据这三个部分，决定要不要进入下一个状态，以及要对栈中的元素执行什么样的操作。每一个 transition 步骤，PDA 都会从 input 读一个字符，然后对栈进行压入或者弹出操作，或者两种操作一起执行我们还将讨论 non-deterministic 的 PDA，他可以忽略输入（input）

下推自动机的定义

QQQ 是状态集合Σ\SigmaΣ 是有限的输入集合Γ\GammaΓ 是栈中的元素集合δ\deltaδ 是转换函数：根据当前状态，输入的字符，栈中元素，共同决定了 “下一个状态” 和 “下一个栈的状态”q0q_0q0 是起始状态，只有一个FFF 是接受状态，可以是一个集合δ(q5,a,b)={(q7,ϵ)}δ(q_5, a, b) = \{(q_7, \epsilon)\}δ(q5,a,b)={(q7,ϵ)} 表示：在状态节点 q5q_5q5 如果栈顶元素是 bbb，这时候如果读入 input 为 aaa 那么就会把这个 aaa 消耗掉，并将 bbb 弹出栈；进而进入新的状态 q7q_7q7δ(q5,ϵ,b)={(q6,a),(q7,b)}δ(q_5, \epsilon, b) = \{(q_6, a), (q_7, b)\}δ(q5,ϵ,b)={(q6,a),(q7,b)} 表示在状态节点 q5q_5q5 如果栈顶元素是 bbb，这时候如果读入 input 为 ϵ\epsilonϵ 空；那么有两种可能的选择：使用 aaa 代替了栈顶的 bbb；并进入新的状态 q6q_6q6让栈保持原样（bbb 依然在栈顶），并进入新的状态 q7q_7q7这两种情况都不会消耗输入的字符。