六、上下文无关文法-CFG

Definition-(Context-Free Grammar(CFG), 上下文无关文法)

上下文无关文法$G$是一个四元组$G = (T,N,S,P)$

$T$是终结符号（Terminal）集合，对应于词法分析器产生的词法单元
$N$是非终止符号（Non-terminal）集合
$S$是开始（start）符号$(S \in N)$且唯一
$P$是产生式（Production）集合
$$
A \in N \to \alpha \in (T \cup N)^*
$$
头部/左部（Head）A：单个非终结符

体部/右部（Body）$\alpha$：终结符与非终结符构成的串，也可以是空串$\epsilon$

[Entended] Backus-Naur form ([E]BNF)

CFG

语义

语义：上下文无关文法$G$定义了一个语言$L(G)$

语言是串的集合

推导

$$
E \to E + E \mid E * E \mid (E) \mid -E \mid id
$$

推导即是将某个产生式的左边替换成它的右边

每一步推导需要选择替换哪个非终结符号，以及使用哪个产生式
$$
E \Rightarrow -E \Rightarrow -(-E) \Rightarrow \ -(E+E) \Rightarrow -(id + E) \Rightarrow -(id+id) \
E \Rightarrow -E :经过一步推导得出 \
E \stackrel{\mathrm{+}}{\Rightarrow} -(id+E):经过一步或者多步推导得出 \
E \stackrel{\mathrm{*}}{\Rightarrow} -(id+E)：经过零步或者多步得出
$$

定义

Definition(Sentential Form-句型)

$$
如果 S \stackrel{\mathrm{}}{\Rightarrow} \alpha ,且 \alpha \in (T \cup U)^\ ,则称\alpha是文法G的一个句型
$$

Definition(Sentence-句子)

$$
如果S\stackrel{\mathrm{}}{\Rightarrow} w,且w \in T^ \
则称w是文法G的一个句子
$$

Definition(文法$G$生成的语言$L( G)$)

文法$G$生成的语言$L( G)$是它能够推导出的所有句子的构成的集合
$$
w \in L(G) \Leftrightarrow S \stackrel{\mathrm{*}}{\Rightarrow} w
$$

文法G的两个基本问题

Membership问题：给定字符串$x \in T^*,x \in L(G)$?

即检查$x$是否符合文法$G$

这就是语法分析器的任务：

为输入的词法单元流寻找推导，构建语法分析树，或者报错

$L(G)$究竟是什么

这是程序设计语言设计者需要考虑的问题

Example

$$
L(G) = \lbrace 良匹配括号串 \rbrace
$$

$$
L(G) = \lbrace a^n b^n \mid n \geqslant 0 \rbrace
$$

$$
字母表\Sigma = \lbrace a, b\rbrace上的所有回文串构成的语言
$$

$$
\lbrace x \in \lbrace a, b \rbrace^* \mid x中a,b个数相同\rbrace
$$

为什么不使用优雅，强大的正则表达式描述程序设计语言的语法

每个正则表达式$r$对应的语言$L®$都可以使用上下文无关文法来描述

此外，若$\delta(A_i,\epsilon)=A_j$，则添加$A_i \to A_j$

Theorem

$L = \lbrace a^n,bn \mid n \geqslant 0\rbrace$该语言无法使用正则表达式来描述
$$
反证法\
假设存在正则表达式r:L® = L \
则存在有限状态自动机D®: L(D®) = L;设状态数为k \
考虑输入a^m , m \gt k \
$$

$$
D®也能接受a^{i+j}bi \Rightarrow 矛盾！
$$