欢迎来到天天文库
浏览记录
ID:57031221
大小:497.50 KB
页数:20页
时间:2020-07-27
《编译原理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=>xy即:指用产生式的右部符号串替换左部非终结符。加推导算符加推导():β设x,y∈(VN+VT)*,A->∈P=>*=>*(当且仅当=>1=>2=>…=>β)即:指一步或一步以上的直接推导运算。(当且仅当=β或=>1=>2=>…β)即:指零步或零步以上的直接推导运算。直接推导算符星推导算符=>+=>+2.3.1文法的运算问题※实用中最常见的两种运算:最左推导()—每次推导
8、皆最左非终结符优先;最左归约()—每次归约皆最左可归约串优先。=>.+=>.+加归约():βⅡ.直接归约():xyxAy=>.=>.(当且仅当12…β)=>.=>.=>.=>.星归约():β=>.*=>.*(当且仅当=β或12…β)=>.=>.=>.=>.=>+ℓ=>.+ℓ即:直接归约是直接推导的逆运算,用产生式的左部非终结符替换右部符号串。即:指零步或零步以上的直接归约运算。即:指一步或一步以上的直接归约运算。直接归约算符加归约算符星归约算符这是相应的算符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),xy是一个句型,则:则是句型xy关于A的短语(A是的名字);=>+=
此文档下载收益归作者所有