程序设计语言及其文法

基本概念

字母表

一个有穷符号集合

字母表上的运算

• 乘积，n次幂，正闭包（长度为正数的符号串构成的集合），克林闭包（正闭包+空串）

串

字母表中符号的一个有穷序列

串上的运算

• 连接，幂

文法的定义

$G = (V_T, V_N, P, S)$

$V_T$：终结符集合 $a,b,c$

$V_N$：非终结符集合 $A,B,C$

$V_T \cup V_N$：文法符号集 $X,Y,Z$

$P$：产生式集合

$S$：开始符号

产生式的简写 $\alpha \rightarrow \beta_1 | \beta_2 | … | \beta_n$

语言的定义

推导/派生（Derivations）

用产生式的右部替换产生式的左部

归约（Reductions）

与上述相反

句型

$S\Rightarrow^* \alpha, \alpha \in (V_T \cup V_N)^*$，$\alpha$为$G$的一个句型 由推导得到的，既可以包含终结符，又可以包含非终结符，也可能是空串

句子

不包含非终结符的句型

语言

由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言

• $L(G)=\{w\mid S\Rightarrow ^ * w, w\in V_T^*\}$

文法的分类

Chomsky文法分类体系

0型文法（Type-0 Grammar）

无限制文法/短语结构文法

• $\forall \alpha \rightarrow \beta \in P$，$\alpha$中至少包含1个非终结符
• 由0型文法生成的语言为0型语言

1型文法（Type-1 Grammar）

上下文有关文法（CSG）

• $\forall \alpha \rightarrow \beta \in P, \mid \alpha \mid \leq \mid \beta \mid$
• 产生式的一般形式：$\alpha_1A\alpha_2 \rightarrow \alpha_1 \beta \alpha_2 (\beta \neq \varepsilon)$
• CSG中不包含$\varepsilon$-产生式

2型文法（Type-2 Grammar）

上下文无关文法（CFG）

• $\forall \alpha \rightarrow \beta \in P, \alpha \in V_N$
• 产生式的一般形式：$A \rightarrow \beta$

3型文法（Type-3 Grammar）

正则文法（RG）

• 右线性文法：$A\rightarrow wB$或$A\rightarrow w$
• 左线性文法：$A\rightarrow Bw$或$A\rightarrow w$

由正则文法G生成的语言叫正则语言 正则文法能够描述程序设计语言的多数单词

文法从上至下逐级包含

CFG的分析树

根节点的标号为文法开始符号，内部节点表示对一个产生式的应用，叶节点的标号既可以是非终结符，也可以是终结符。 从左到右排列叶节点得到的符号串称为是这棵树的产出或边缘。

• 对于每一个句型$\alpha_i$，都可以构造出一个边缘为$\alpha_i$的分析树

（句型的）短语

给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语

• 直接短语：如果子树中只有父子两代节点
  • 直接短语一定是某产生式的右部
  • 但产生式的右部不一定是给定句型的直接短语

二义性文法

如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的

• 无二义性文法的判定
  • 对于任意一个CFG，不存在一个算法，判定它是无二义性的；
  • 但能给出一组充分条件，满足这组充分条件的文法是无二义性的
    • 满足确定性，肯定是无二义性的（LL(1)文法）
• 对于无二义性的文法而言，最左推导和最右推导的语法树是相同的。