计算理论导引 (3-上下文无关文法)
上下文无关文法
上下文无关文法（context-free grammar) ，它能够描述某些应用广泛的具有递归结构特征的语言。
语法分析器（parser) ,它在生成编译代码或解释程序执行前，提取出程序的语义。
与上下文无关文法相关的语言集合称为 上下文无关语言（context-free language) 。
上下文无关文法概述
上下文无关文法的形式化定义
上下文无关文法 是一个4元组$(V,Σ,R,S)$,且
- $V$是一个有穷集合，称为 变元集 。
- $Σ$是一个与$V$不相交的有穷集合，称为 终结符集 。
- $R$是一个 有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成。
- $S∈V$是 起始变元 。
设$u、v和w$和切是由变元及终结符构成的字符串，$A→w$是文法的一条规则，称 $uAv$生成$uwv$ ，记作$uAv⇒uwv$。如果$u=v$，或者存在序列$u_1，u_2，…，u_k$，使得$u⇒u_1⇒u_2⇒…⇒u_k⇒v$其中$k>0$，则称 $u$派生$v$
上下文无关文法举例
编译程序提取被编译代码的语义，这一过程称为 语法分析 。在关丁该程序设计语言的上下文无关文法中，编译代码的意思可以用代码的语法分析树进行表达。
设计上下文无关文法
歧义性
把歧义性的概念形式化，一个文法歧义地产生一个字符串的意思是指：该字符串有两棵不同的语法分析树，而不是两种不问的派生，两种不问的派生可能仅仅是替换变元的次序不同，而不是整个结构的不同。为了专注于结构，定义一种以固定次序替换变元的派生类型，对于文法$G$中的一个字符串$w$的派生，如果在每一步都是替换最左边剩下的变元，则称这个派生是 最左派生 。
如果字符串$w$在上下文无关文法$G$中有两个或两个以上不同的最左派生，则称$G$ 歧义地（ambiguously)产生字符串$w$，如果文法$G$歧义地产生某个字符串，则称$G$是 歧义的 。
有时对于一个歧义文法，能够找到一个产生相同语言的非歧义文法。但是，某些上下文无关语言只能用歧义文法产生，这样的语言称为 固有歧义的 (inherentlyambiguous) 。
乔姆斯基范式
称一个上下文无关文法为 乔姆斯基范式 (Chomsky normal form)，如果它的每一个规则具有如下形式：
$A→BC$
$A→a$
其中，$a$是任意的终结符，$A、B和C$是任意的变元，且$B和C$不能是起始变元。此外，允许规则$S→ε$，其中$S$是起始变元。
任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。
Backus–Naur form
Backus–Naur form (BNF) is a notation for Chomsky’s context-free grammars.
下推自动机
下推自动机在能力上与上下文无关文法等价。因此，在证明一个语言是上下文无关的时候，有两种选择：可以给出生成它的上下文无关文法，或者给出识别它的下推自动机。某些语言用文法生成器描述要容易些，另一些用自动机识别器描述更容易。
下推自动机(Pushdown Automata, PDA) 能够把符号写到栈上并在随后读取它，向栈中写人一个符号将把栈中其他的所有符号 下推 。
在任何时刻，可以读和删去栈项的符号，其余的符号向上移动。向栈写一个符号，常常称为 推入 (pushing) 这个符号，而删除一个符号称为 弹出 (popping) 它。需要注意的是，对栈的所有访问，无论读写，都只能在栈顶进行，换言之，栈是一个“先进后出”的存储设备。
下推自动机的形式化定义
下推自动机（pushdownautomaton)是6元组$(Q,Σ,Γ,δ,q_0,F)$，其中$Q,Σ,Γ,F$都是有穷集合,并且
- $Q$是状态集。
- $Σ$是输入字母表。
- $Γ$是栈字母表。
- $δ：Q×Σ ε × Γ ε →P(Q × Γ_ ε)$是转移函数。
- $q_0∈Q$是起始状态。
- $F⊆Q$是接受状态集。
与上下文无关文法的等价性
—个语言是上下文无关的，当且仅当存在一台下推自动机识别它。
非上下文无关语言
转载请注明：转载自srzyhead的博客(https://srzyhead.github.io)
本文链接地址: 计算理论导引 (3-上下文无关文法)
