编译原理复习笔记 第二章
编译原理第二章
2-1 基本概念
- 字母表：有穷符号集合
- 字母表上的运算
字母表正闭包/克林闭包 - 串：字母表上的一个克林闭包元素，有穷序列
- 串上的运算：连接、幂
2-2 文法的定义
- 句子、单词的构成规则
- 基本符号
- 文法形式化定义
S：开始符号，“最大的语法成分” - 产生式的简写
（1）相同左部的简写 - 终结符
（1）排在前面的小写字母
（2）运算符
（3）标点
（4）数字
（5）粗体字符，id、if等 - 非终结符
（1）排在前面的大写字母
（2）S，开始符
（3）小写斜体的名字
（4）E表达式，T项，F因子
2-3 语言的定义
- 推导：自顶向下
规约：自底向上 - 句型：0由S克林闭包推导出的文法符号串，可含有终结符、非终结符、空串
- 句子：不包含非终结符的句型
- 语言：由S推导出的所有句子的集合，L（G）
- 语言上的运算
2-4 文法的分类
-
0型文法（无限制文法）
-
1型文法（上下文有关 CSG）
-
2型文法（上下文无关 CFG）
-
3型文法（正则文法RG）
（1）右线性文法
（2）左线性文法
2-5 CFG分析树
-
可以描述语法构造
-
（句型的）短语
短语：每一棵子树的边缘
直接短语：高度为2的子树边缘
直接短语一定是产生式的右部，产生式右部不一定是直接短语 -
二义性文法
讨论：
（1）计算机中如何表示语言
{0，1}的克林闭包
（2）每一类单词能否看作语言
可以，只要有文法能接受