编译原理PPT第二章形式语言基础资料课件.ppt

《编译原理PPT第二章形式语言基础资料课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译程序的设计原理与实现如何让计算机认识、理解和执行高级程序设计语言？【内容提要】第2章形式语言基础(2)2.1形式语言是符号串集合2.2形式语言是由文法定义的2.3主要语法成分的定义2.4两类特性文法2.5文法变换方法2.6关于形式语言的分类问题※上节课主要内容回顾：⒈文法是规则集合，四元组：G(Z)=(VN,VT,Z,P)⒉文法所定义的语言：⒊文法应用示例：⑴简单语言的文法构造：①无符号整数文法：G(N):N->dN

2、dL(G)={x

3、Zx,x∈VT*}=>+I->ℓA

4、ℓA->ℓA

5、dA

6、⑵求解文法所定义的语言(或句子)方法：形式语言是符号串集合且由文法定义！①正规方程组迭代求语言（

7、如标识符文法）直接由定义求解句子(如算术表达式文法)。②标识符文法：G(I):d(数字),ℓ(字母)文法有两种基本运算：推导，归约。星推导():αβ2.3主要语法成分的定义Ⅰ．直接推导(=>):xAy=>xy即：指用产生式的右部符号串替换左部非终结符。加推导算符加推导():β设x,y∈(VN+VT)*，A->∈P=>*=>*（当且仅当=>1=>2=>…=>β）即：指一步或一步以上的直接推导运算。（当且仅当=β或=>1=>2=>…β)即：指零步或零步以上的直接推导运算。直接推导算符星推导算符=>+=>+2.3.1文法的运算问题※实用中最常见的两种运算：最左推导()—每次推导

8、皆最左非终结符优先；最左归约()—每次归约皆最左可归约串优先。=>.+=>.+加归约():βⅡ．直接归约():xyxAy=>.=>.（当且仅当12…β）=>.=>.=>.=>.星归约()：β=>.*=>.*（当且仅当=β或12…β)=>.=>.=>.=>.=>+ℓ=>.+ℓ即：直接归约是直接推导的逆运算，用产生式的左部非终结符替换右部符号串。即：指零步或零步以上的直接归约运算。即：指一步或一步以上的直接归约运算。直接归约算符加归约算符星归约算符这是相应的算符i+i*i给定一个符号串i+i*i：T->F

9、T*F

10、T/FF->i

11、(E)G(E):E->T

12、E+T

13、E-T文法运

14、算示例：【例2.8】算数表达式文法：=>.=>.=>.=>.=>.=>.=>.=>.最左归约(从符号串出发)过程：E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i∴E=>+ℓi+i*iF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TE∴i*i+i=>.+ℓE1.最左推导(从开始符号出发)过程：最左非终结符最左可归约串即：句型是由文法开始符号加推导出的任一符号串。2.3主要语法成分的定义(续1)2.3.2句型、句子和语法树若有且∈VT*，则是句子；Z=>+若有，则是句型；Z=>+2.句子即：句子是由开始符号加推导出的

15、任一终结符号串。1.句型设有文法G(Z)=(VN,VT,Z,P)，则：3.语法树句型(句子)产生过程的一种树结构表示；树根--开始符号；树叶—给定的句型(句子)。AX1X2…Xn2.3主要语法成分的定义(续2)③重复步骤②，直到再没有推导产生式为止。①置树根为开始符号；【语法树的构造算法】：②若采用了推导产生式：A->x1x2…xn，则有子树：※如此构造的语法树，其全体树叶（自左至右）恰好是给定的句型。E=>T=>T*F=>F*F=>(E)*F=>(E+T)*F=>(T+T)*F=>(T/F+T)*F=>(T/F+F)*F=>(T/F+F)*i※句型、句子和语法树示例：【例2.10】算术表达

16、式文法：⑴证明(T/F+F)*i是一个句型(表达式型)；⑵画出该句型的语法树。E->T

17、E+T

18、E-TT->F

19、T*F

20、T/FF->i

21、(E)【证】即：E(T/F+F)*i=>+证闭※句型(T/F+F)*i的语法树构造：ETT*FF(E)E+TTT/FFiE->T

22、E+T

23、E-TT->F

24、T*F

25、T/FF->i

26、(E)【注】关于语法树：子树：以任何具有分支的结点为根所形成的树，称为原树的子树。简单子树：仅具有单层分支的子树。<句型><名短><动短><代词><名词><动短><名短><副词><动词><名词>(他)(哥哥)(喜欢)(看)图2.2他哥哥喜欢看书的语法树(书)2.3.3短语、简单短语和

27、句柄【例2.11】图2.2为一个中文句型的语法树：短语--他哥哥<名短>,喜欢看<动短>,书<名词>，喜欢看书<动短>，他哥哥喜欢看书<句子>简单短语--他哥哥，喜欢看，书句柄--他哥哥（最左边的简单短语!）⒊句柄-一个句型的最左简单短语称为该句型的句柄。2.3主要语法成分的定义(续3)2.3.3短语、简单短语和句柄※设文法G(Z),xy是一个句型，则:则是句型xy关于A的短语(A是的名字)；=>+=