编译原理基础——文法（1）
目录
以下截图大部分来自于《中国大学mooc中哈尔滨工业大学编译原理课程》，基础知识的文章均是自己学习的笔记
1.字母表和符号串
1.1 字母表
（1）什么是字母表
-
符号：字母、数字、标点符号、.......
- 例如：a，b，c......
-
字母表：符号的非空有限集，一般用
来表示
- 例如：以下都是字母表
- 二进制字母表：{0，1}
- ASCII字符集
- Unicode字符集
- 例如：以下都是字母表
（2）字母表运算
乘积：
- 例如：
- {0，1}{a，b} = {0a，0b，1a，1b}
幂运算：
-
字母表
- 例如：
- {0，1} ^3 = {000，001，010，011，100，101，110，111}
- 结论：
-
字母表的n次幂，就是字母表中的所有字符（每个字符出现的个数不限）能组成的长度为n的符号串构成的集合（n可以为0，
）
-
字母表的n次幂，就是字母表中的所有字符（每个字符出现的个数不限）能组成的长度为n的符号串构成的集合（n可以为0，
正闭包
-
- 例：
- 长度为1的字母的集合
长度为2的字母的集合
长度为3的字母的集合
长度为4的字母的集合
- 结论：
- 字母表的正闭包，就是长度为正数的符号串构成的集合
字母表的克林闭包
- 在
- 例：
- 结论：
- 字母表的克林闭包，就是任意长度（长度可以为0）的符号串构成的集合
1.2 符号串
（1）什么是符号串
定义：
-
符号串：符号的有穷序列
-
例如：a，ac，aa，abc......
-
空符号串：无任何符号的符号串，用
表示
-
符号串集合：符号串组成的集合
-
-
符号串s的长度：
-
记作|s|，指s中的符号的个数
-
-
-
-
符号串相等：
-
若x x 、y y 是集合上的两个符号串 ，则x x ＝y y当且仅当组成xx的每一个符号和 组 成y y的每 一个符号依次相等
-
-
表示：
（2）符号串的运算
连接（符号串的乘法运算）
- 定义：
- 空串的连接：
- 空串是连接运算的单位元，在它前后连接一个s，得到的还是s
- 前缀和后缀
幂运算
- 符号串s的n次幂表示将n个s进行连接
- 例：
2.文法
2.1 文法的定义
- 文法，即语法，形式化地描述语言的结构，但注意不涉及语义的问题
- 不管是我们的自然语言还是我们的编程语言它能组合的语义的范围都是无限的，而文法是用有限去表示无限
- 示例：
- 接下来先用中文来解释文法的含义 ::= 符号表示由......组成
- 在中文中，一个句子 ，由主语和谓语组成，可如下表示
- 而右边的主语，又可以由代词或名词组成，谓语可以由动词和直接宾语组成，可如下表示
- 而右边的代词、名词、动词、直接宾语最终又可以有如下右边的表示：
- 对于上述的关系，我用如下的图来表示每一层（如下也叫语法推导树）
- 而最终右边便无法再被表示，而将它们替换每一个上一层，即用上图中的最终的叶子节点来替换上一层，直到反推导到句子，就组成了句子
- 比如用“大学生”（叶子节点）来替换组成<主语>的<名词>，用“学习”（叶子节点）来替换组成<谓语>的<动词>，用“英语”来替换组成<直接宾语>的名词，最终就组成了句子“大学生学习英语”
- 接下来先用中文来解释文法的含义 ::= 符号表示由......组成
通过上面的示例，我们得出文法的形式化定义：
- 我们用一个四元组来表示文法：
-
- 非终结符号是用来表示语法成分的符号，它本身是对一类符号的总结，有时也称为“语法变量”
- 例如：
- Vn={<句子>，<名词短语>，<动词短语>，<名词>，<谓语>}
- 通过上面的组成结构的示例：可以看到它既可以出现在::=的左侧，也可以出现在::=的右侧
- 即上图的非叶子节点
-
- 文法中定义的基本符号
- 例如：
- 中文句子的基本符号，有汉字和相应的词语如你、学习、工人
- 英文句子的基本符号，英文单词如apple、a、you
- 它最大的特点就是：不能在此文法中再拆分，只能出现在::=的右侧
- 即上图的叶子节点
-
- .......
- 上述推导“组成式”的集合就是产生式集合，即文法的规则
- 它的一般形式为：
（读作
定义为
）
-
-
-
-
- Z表示这个文法中最大的语法成分
- 例如上述的
- 即上图的根节点
-
2.2 符号约定
- 终结符：
- 非终结符：
- 既可以表示终结符号，也可以表示非终结符号
- 终结符号串：
- 文法符号串：
总结：
2.3 示例和注意事项
示例：
注意：
- 有些产生式有相同的左部，可以合并在一起
-
------------->
- 给定一个文法，需要给出产生式规则，还需要给出开始符号
3.推导
待更新
4.语言
5.递归文法