第2章编译原理课程讲解PPT文法和语言讲解ppt课件.ppt

《第2章编译原理课程讲解PPT文法和语言讲解ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章文法和语言2021/7/301内容提要字母表与符号串文法(定义,推导,句型与句子)语言递归规则与递归文法语法树（短语、简单短语和句柄）语法树与文法的二义性2021/7/3022.1字母表与符号串字母表符号串符号串及集合的运算2021/7/3032.1.1字母表字母表是符号的非空有穷集合。例如：1.机器语言字母表：由符号“0”和“1”组成的字母表,∑={0，1}2.ASCII字符集3.Pascal字母表为：∑={AZ,az,09,+,-,*,/,<,=,>,:,',',;，.，,(,),{,},[

2、,]}……2021/7/3042.1.2符号串定义：(1)ε是∑上的一个符号串。(2)若x是∑上的符号串，而a是∑的元素,则xa和ax都是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。即：符号串由字母表中的符号所组成的任何有穷序列。2021/7/3052.1.3符号串及其集合的运算11.符号串的长度：指符号串x中所含符号的个数，记为

3、x

4、。如

5、xyz

6、=3，

7、123+321

8、=7，而

9、ε

10、=02.符号串相等：若x、y是字母表∑上的两个符号串，当且仅当组成x的各符号与组成y的各符号依次相

11、等时，则符号串x与符号串y相等，记作x=y。如：当x=abbc，y=abbc时，则x=y；而当x=ab，y=ba时，则x≠y3.符号串的前缀：指从符号串x的末尾删除0或多个符号后得到的符号串，如u、uni、university都是university的前缀。4.符号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串，如ty、sity、university都是university的后缀。2021/7/3062.1.3符号串及其集合的运算25.符号串的子串：指从符号串x的开头和末尾删除0或多个符号后得到的

12、符号串，如ver是university的子串,符号串的前缀、后缀都是它的子串。6.符号串的连接：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表∑上的两个符号串，则xy也是字母表∑上的符号串。例如：x=ab，y=ba，则xy=abba注意：连接没有交换律，即xy≠yx而对于空串ε有εx=xε=x2021/7/3072.1.3符号串及其集合的运算37.集合的乘积运算：令A、B为两个符号串集合，A和B的乘积AB定义为：AB={xy

13、x∈A，y∈B}例：A={a，b}B={c

14、，d}，则AB={ac，ad，bc，bd}对于空集合有{ε}有：{ε}A=A{ε}=A8.符号串的幂运算：若x是符号串，则x的幂运算定义为：x0=ε,x1=x,x2=xx,…，xn=xx…x=xxn-1=xn-1x,其中n>0例如：x=abc,x0=ε,x1=abc,x2=abcabc,…2021/7/3082.1.3符号串及其集合的运算49.集合的幂运算：设A为符号串集合，则A的幂运算定义为：A0={ε}A1=AA2=AA……An=AA…A=AAn-1=An-1A，其中n>0例如：A={a，b}，则A0={

15、ε}A1={a,b}A2={aa,ab,ba,bb}2021/7/3092.1.3符号串及其集合的运算410.集合的正闭包和集合的闭包：设A为一个集合，则集合A的正闭包用A+表示，定义为：A+=A1∪A2∪…∪An∪…集合A的闭包用A*表示，定义为：A*=A0∪A+例如：A=={a，b}，则A+={a,b,aa,ab,ba,bb,aaa,aab,…}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}2021/7/30102.2文法文法是描述语言语法结构的形式规则。用文法描述语言时，要说明语言允许

16、的符号，语法成分，语法结构。例：能够描述句子“themonkeyatethebanana”的文法：<句子>→<主语><谓语><主语>→<冠词><名词><冠词>→<谓语>→<动词><直接宾语><动词>→<直接宾语>→<冠词><名词><名词>→<名词>→该例中，语言允许的符号，语法成分，语法结构是什么？2021/7/30112.2.1文法形式定义文法的形式定义：文法可表示为一个四元组G=（Vn，Vt，P，Z）Vn:非空有穷集合,其元素为非终结符号。Vt:非空有穷

17、集合,其元素为终结符号且Vt∩Vn=Ф,Ｖ＝Vt∪Vn是该文法的字母表。P：非空有穷集合,其元素为产生式或规则。产生式的形式为:α→β或α::=β；α是产生式左部且不能为空,β是产生式右部,并且α、β∈（Vt∪Vn)*,“→”或“::=”含义相同，表示“定义为”或“由……组成”。Z：Vn中一个特殊的非终结符号，称为文法的识别符号或开始符号。必须至少在某个产生式的左部出现一次。2021/7/30122