02 程序设计语言及其文法 | 《编译原理》笔记

本系列是编译原理 (哈工大陈鄞、郭勇)视频课的课堂笔记，主要是课堂 PPT 和部分讲授内容的文字版，仅供参考。

基本概念

字母表 $\Sigma$ 是一个有穷符号集合，如二进制字母表（即 {0, 1}）、ASCII 字符集、Unicode 字符集等。

字母表上的运算包含以下几种：

• 乘法：
• 幂运算：
• 正闭包（positive closure）：
• 克林闭包（Kleene closure）：

文法的定义

• VT 和 VN 是互斥的集合
• $\alpha$ 和 $\beta$ 都是文法符号串
  

简化的算术表达式文法：

• id: 标识符
• E: expression，是最大的语法成分

语言的定义

现在给出语言的形式化定义：由文法 G 的开始符号 S 推导出的所有句子构成的集合称为文法 G 生成的语言，记为 L(G)。例如：

文法的分类

当上下文是 $\alpha_1$ 和 $\alpha_2$ 时，$A$ 才能被替换为 $\beta$。

上述右线性文法例子描述的是「字母开头的字母数字串」。

CFG 的分析树

正则文法可以描述程序设计语言中的大多数单词，但是生成能力有限，几乎描述不了程序设计语言中的句子构造，上下文无关文法则可以做到这一点。

分析树是推导的图形化表示。

「子树只有父子两代结点」即子树的高度为 2。

在这个例子中，「人民」、「生活」、「水平」是直接短语，即「直接短语一定是某产生式的右部」。「高人」、「民生」、「活水」不是边缘，所以不是直接短语，即「产生式的右部不一定是给定句型的直接短语」。

可以引入消歧规则：每个 else 和最近的尚未匹配的 if 匹配。

对于任意一个上下文无关文法，不存在一个算法，判定它有无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的：

• 满足，肯定无二义性
• 不满足，也未必就是有二义性的