资源描述：
《编译原理文法与语言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、内容回顾什么是编译程序编译的过程词法分析语法分析语义分析及中间代码生成优化目标代码生成编译程序的结构与组织文法和语言字母表和符号串的基本概念文法和语言的形式定义递归规则与递归文法语法树与文法的二义性文法的分类字母表和符号串的基本概念字母表：元素的非空有穷集合。记为∑。 字母表包含了语言中所允许出现的一切符号。例如：∑={0，1}符号串(字)：字母表中的符号所组成的有穷序列。一个语言的句子总是它的字母表的符号串。这个符号串的组成必须是按照文法规则组合而成的。语法分析的一个重要任务就是：判断一个符号串的组
2、成是否满足某个文法的规定。字母表和符号串的基本概念空串：不包含任何符号的串，记为ε。Σ*：表示Σ上所有符号串的全体。空集：φ，不包含任何元素。在本课程中，语言被认为是句子的集合。所以，一个语言就是对应于它的字母表上的一个符号串集合。关于符号串的运算符号串的长度：指符号串x中所含符号的个数，记为
3、x
4、。符号串相等：若x、y是字母表∑上的两个符号串，那么当且仅当组成x的各符号与组成y的各符号依次相等时，则符号串x与符号串y相等，记作x=y。符号串的前缀：指从符号串x的末尾删除0或多个符号后得到的符号串。符
5、号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串。关于符号串的运算符号串的子串：指从符号串x的开头和末尾删除0或多个符号后得到的符号串。符号串的前缀、后缀都是它的子串。连接(并置)：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表∑上的两个符号串，则xy也是字母表∑上的符号串。注意：连接没有交换率，即xy≠yx而对于空串ε有εx=xε=x方幂：x的n次方幂即将n个x连接。x0=ε,x1=x,x2=xx,…xn=xx…x=xxn-1=xn-1x符号串集
6、合的运算乘积：令A、B为两个符号串集合，A和B的乘积AB定义为：AB={xy
7、xA且yB}{ε}A=A{ε}=AΦA=AΦ=Φ方幂：A的n次方幂就是将n个A相乘。A0={ε}A1=AA2=AA…An=AA…A=AAn-1=An-1A符号串集合的运算集合的正则闭包和集合的闭包：设A为一个集合，则集合A的正则闭包用A+表示，定义为：A+=A1∪A2∪….∪An∪…表示A上的所有的非空符号串的集合。集合A的闭包用A*表示，定义为：A*=A0∪A+表示A上的所有符号串（包括空字符串）的集合。例如：A={a
8、，b}，则A+={a,b,aa,ab,ba,bb,aaa,aab,…}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}文法和语言的形式定义形式语言描述的两种方法 枚举方法使用文法来描述文法是一种工具，它可用于严格定义句子的结构。例如，能够描述句子“themonkeyatethebanana”的文法如下：<句子>→<主语><谓语><主语>→<冠词><名词><冠词>→the<谓语>→<动词><直接宾语><动词>→ate<直接宾语>→<冠词><名词><名词>→banana<名词>→monk
9、ey文法的形式定义（产生式/规则）产生式：一个产生式是一个有序对(α,β)，通常写作α→β或α::=β。其中α为左部；β为右部。产生式意味着能将一个符号串用另外一个符号串替换。因而又被称为重写规则。一组规则规定了一个语言的语法结构。规则中的符号分为两类：终结符号、非终结符号终结符与非终结符终结符：VT组成语言的基本符号。在程序设计语言中就是以前屡次提到的单词符号。如：基本字，标识符，常数，算符，界符等。从语法分析的角度看，终结符是一个语言的不可再分的基本符号。非终结符：VN也称语法变量，用来代表语法单
10、位。如“算术表达式”、“布尔表达式”、“赋值句”、“子程序”、“函数”等。一个非终结符代表一个一定的语法概念，是一个类（集合）记号，而不是一个个体记号。VT∩VN＝Φ，VT∪VN为该语言的字母表文法的定义Chomcky文法的定义：G=(VN,VT,P,S)其中：VN—非空有限的非终结符号集VT—非空有限的终结符号集P—产生式集S—开始符号/识别符号，S∈VN文法被用来精确而无歧义地描述语言的句子的构成方式。文法描述语言的时候不考虑语言的含义。例：按文法形式定义表示上例文法。解：根据文法的形式定义，文法
11、G1=（VN，VT，P，S）VN={句子，主语，谓语，冠词，名词，动词，直接宾语}VT={the，ate，banana，monkey}产生式集合P由右面8条规则组成开始符号S=<句子><句子>→<主语><谓语><主语>→<冠词><名词><冠词>→the<谓语>→<动词><直接宾语><动词>→ate<直接宾语>→<冠词><名词><名词>→banana<名词>→monkey1.<无符号整数>→<数字串>2.<数字串>→<数字串><数字>3.<数字串>→<数字
