上下文无关文法

上下文无关文法基本概念

• 上下文无关文法（Context-Free Grammar, CFG）四大要素：

  1. 非终结符集合（V）：常用大写字母表示，类似变量
  2. 终结符集合（T）：常用小写字母表示，类似常量
  3. 开始符号（S）：$S \in V$，一种特殊的非终结符
  4. 产生式集合（P）：缩写记法形如$A \to \alpha_1 | \alpha_2|...|\alpha_n$，其中$A \in V, \alpha \in (V \cup T)^*$（希腊字母一般表示终结符与非终结符的混合）

  

归约与推导

• 归约（递归推理，recursive inference）：从结果出发逆向倒推，将产生式右边（body）的符号串替换为左边（head）的符号，最终都归约到开始符号S

• 推导：从开始符号出发正向推导结果，将产生式左边替换为右边

• 举例对比

• 推导的自反传递闭包（多步推导）：

  

• 最左推导（leftmost derivations）：推到过程中每一步总是替换最左边的非终结符（具有唯一性）

• 句型（sentential form）：符合语法推导条件的终结符与非终结符的混合式$\alpha$ （若仅由终结符组成（只有常量没有变量）则称为句子）

  

• （上下文无关文法的）语言：一个上下文无关文法能够推导出的所有句子（非终结符组成的字符串）的集合

  

上下文无关文法的设计与证明

• 上下文无关语言（Context-Free Language, CFL）：由上下文无关文法定义的语言
• 上下文无关文法设计：
• 上下文无关文法证明

语言的Chomsky分类

• 文法（Grammar)：四元组$G=(V,T,P,S)$
• 0型文法$\iff$0型语言$\iff$图灵机：$P$形如$\alpha \to \beta$，其中$\alpha,\beta \in (V\cup T)^*$，但$\alpha$中至少包含一个非终结符
• 1型文法$\iff$1型语言（上下文有关语言）$\iff$线性有界自动机：$P$形如$\alpha \to \beta$，要求除$S\to \epsilon$外$|\alpha| \le |\beta|$，且$S$不出现在任何产生式右部
• 2型文法（上下文无关文法，CFG）$\iff$2型语言（上下文无关语言，CFL）$\iff$下推自动机（Pushdown Automata）：$P$形如$A \to \alpha$，其中$A \in V, \alpha \in (V \cup T)^*$