《编译原理文法与语言》由会员分享，可在线阅读，更多相关《编译原理文法与语言（50页珍藏版）》请在金锄头文库上搜索。
1、编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院内容回顾 什么是编译程序 编译的过程 词法分析 语法分析 语义分析及中间代码生 成 优化 目标代码生成 编译程序的结构与组织编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院文法和语言 字母表和符号串的基本概念 文法和语言的形式定义 递归规则与递归文法 语法树与文法的二义性 文法的分类编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院字母表和符号串的基本概念 字母表：元素的非空有穷集合。记为 。 字母表包含了语言中所允许出现的一 切符号。例如： =
2、0，1 符号串(字)：字母表中的符号所组成的 有穷序列。一个语言的句子总是它的字母表的符 号串。这个符号串的组成必须是按照 文法规则组合而成的。 语法分析的一个重要任务就是：判断 一个符号串的组成是否满足某个文法 的规定。编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院字母表和符号串的基本概念 空串：不包含任何符号的串，记 为。 *：表示上所有符号串的全体。 空集：，不包含任何元素。在本课程中，语言被认为是句子 的集合。所以，一个语言就是对 应于它的字母表上的一个符号串 集合。编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院关
3、于符号串的运算 符号串的长度：指符号串x中所含符号的 个数，记为|x|。 符号串相等：若x、y是字母表上的两 个符号串，那么当且仅当组成x的各符号 与组成y的各符号依次相等时，则符号串 x与符号串y相等，记作x=y。 符号串的前缀：指从符号串x的末尾删除 0或多个符号后得到的符号串。 符号串的后缀：指从符号串x的开头删除 0或多个符号后得到的符号串。编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院关于符号串的运算 符号串的子串：指从符号串x的开头和末 尾删除0或多个符号后得到的符号串。 符号串的前缀、后缀都是它的子串。 连接(并置)：若x、y是两个符号串，则x
4、y 表示连接，是将符号串y连接在符号串x 的后面。若x、y是字母表上的两个符 号串，则xy也是字母表上的符号串。 注意：连接没有交换率，即 xy yx而对于空串有 x=x=x 方幂：x的n次方幂即将n个x连接。 x0 = , x1 = x, x2 = xx, xn=xxx=xx n-1=x n-1 x 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院符号串集合的运算 乘积：令A、B为两个符号串集合，A和B 的乘积AB定义为：AB = xy | xA且y BA=A =A A= A = 方幂：A的n次方幂就是将n个A相乘。A0= A1=A A2=AA An=AAA
5、=AA n-1 =A n-1 A 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院符号串集合的运算 集合的正则闭包和集合的闭包：设A为一个集合，则集合A的正则闭包用 A+表示，定义为：A+ =A1 A2 . A n 表示A上的所有的非空符号串的集合。集合A的闭包用A*表示，定义为： A* =A 0 A+ 表示A上的所有符号串（包括空字符串） 的集合。例如：A =a，b，则A+ =a,b,aa,ab,ba,bb,aaa,aab,A* = ,a,b,aa,ab,ba,bb,aaa,aab,编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工
6、程学院文法和语言的形式定义 形式语言描述的两种方法枚举方法使用文法来描述编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 文法是一种工具，它可用于严格定义句 子的结构。例如，能够描述句子“the monkey ate the banana”的文法如下： the ate banana monkey 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 文法的形式定义（产生式/规则） 产生式：一个产生式是一个有序对 (,)，通常写作 或 := 。其中 为左部； 为右部。产生式意味着能将一个符号串用另外 一个符号串替换。因而又被称为重写
7、 规则。一组规则规定了一个语言的语 法结构。 规则中的符号分为两类：终结符号、 非终结符号编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院终结符与非终结符 终结符：VT组成语言的基本符号。在程序设计语言 中就是以前屡次提到的单词符号。如： 基本字，标识符，常数，算符，界符等 。从语法分析的角度看，终结符是一个 语言的不可再分的基本符号。 非终结符：VN也称语法变量，用来代表语法单位。如“ 算术表达式”、“布尔表达式”、“赋值句” 、“子程序”、“函数”等。一个非终结符代 表一个一定的语法概念，是一个类（集 合）记号，而不是一个个体记号。 VT VN， VT V
8、N为该语言的字母表编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院文法的定义 Chomcky文法的定义：G=(VN,VT,P,S)其中：VN 非空有限的非终结符号 集VT 非空有限的终结符号集 P 产生式集S 开始符号/识别符号， S VN 文法被用来精确而无歧义地描述语 言的句子的构成方式。文法描述语言的时候不考虑语言的 含义。编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院例：按文法形式定义表示上例文法。解：根据文法的 形式定义，文 法 G1=（ VN， VT ，P，S） VN=句子，主 语，谓语，冠 词，名词，动 词，直
9、接宾语 VT= the，ate ，banana， monkey 产生式集合P由 右面8条规则组 成 开始符号S= the ate banana monkey 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院1. 2. 3. 4.0 5.1 6.2 7.3 8.4 9.5 10.6 11.7 12.8 13.9产生式的简写：A B , A C 可以简化为：A B | C 1. 2. | 3.0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院文法举例 G1=(
10、VN,VT,P,S)其中:VN=EVT= i, +, *, (, ) P= EE+E，E E *E，E (E) ，E iS=E编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院语言的形式定义 文法的作用是描述某种语言的句 子的构成方式。使用文法我们可 以产生对应语言的句子。 从识别符号开始，不断将当前符 号串中的非终结符号替换为该符 号的某个规则的右部。直到当前 的符号串中所有的符号都是终结 符号为止。编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院推导和直接推导 直接推导：v=A ，w= ， 并且 A 是文法中的一个 产生式，
11、那么 我们说v可以直接推导到w，或者w可 以直接规约到v。记作 v w。 其中 ，（VNVT）* 推导：若v= 0 1 2 n= w (n0),则符号串w为符号串v的一个推 导。记为v +wv *w含义: v=w或v +w 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院例3 : G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 表达式(i)和(i+i)*i的推导：E (E) (i) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*iE E 0步推导E (i + i)*i 6步推导E (i + i)*i 6步推导E (E) 直接推导编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院句型、句子 对于文法GS， 称为G的一个句型， 如果： S * 开始符号是最简单的句型。 GS
