我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019跑狗图高清彩图 > 指称语义 >

编译原理精品教学课件(华南理工大学)第二章文法和语言ppt

归档日期:07-20       文本归类:指称语义      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  对定义的分析: 在短语的定义中包括了三个条件: αβδ是文法的一个句型; S=*αAδ; A=+β 。 S α A δ … β … 这三个条件都必须满足。 (1)(2)说明αβδ 、 αAδ都必须是句型 (2)(3)说明,将αβδ中的β归约称A后,得到的αAδ一定要是句型。 假如符号串β ,将其归约成A后得到的符号串不能由开始符号推出,则β不是短语。 例:文法G[E]:E→E+TT T→T×FF F→(E)i 的一个句型 是T×F+i,相应的语法树见右图: E E T + T T F × F i 因为E=* T+i且T=T×F,所以T × F是句型相对于T的短语,且是相对于 T-T × F的直接短语 因为E=* T × F+F且F=i,所以i是句型相对于F的短语,且是相对于F-i的直接短语 因为E=* E且E=+ T × F+i,所以T × F+i是句型相对于E的短语 T × F是最左直接短语,即句柄 文法G[E]: E→E+TT T→T×FF F→(E)i 的一个句型 是T×F+i E E T + T T F × F i 虽然F+i是句型T×F+i的一部分, 但不是短语,因为尽管有E=+F+i, 但是不存在从文法开始符 E=*T×E的推导 短语与语法树 从句型的语法树上很容易找出句型的短语 语法树中每棵子树的末端结点构成相对于子树根的短语 例:文法G[E]的句型T*F+i语法树: E E T + T T F * F i 五棵子树对应三个短语T*F,i,T*F+i 两层子树的末端结点构成直接短语 两棵两层子树对应两个直接短语: T*F,i 位于最左边的两层子树的末端结点构成句柄: T*F 本章小结 本章出现的概念较多,应重点理解文法,语言,推导,句型句子及句柄等概念。本章的内容是学习语法分析的基础 作业 P34 11.一个上下文无关文法生成句子abbaa的推导树如下: (1)给出该句子相应的最左推导,最右推导。 (2)给出该文法的产生式集合P可能有哪些元素? (3)找出该句子的所有短语,简单短语,句柄。 作业 P35 15 分以下两种情形,各写一个文法,使其语言是十进制非负偶数的集合: (1)允许0打头; (2)不允许0打头。 C * S ? (S) a * 例 文法G: E→E+TT T→T×FF F→(E)i “i+i×i”的推导过程如下: 最左推导: E=E+T=T+T=F+T=i+T=i+T×F=i+F×F =i+i×F=i+i×i 最右推导: E=E+T=E+T×F=E+T×i=E+F×i=E+i×i = T+i×i=F+i×i=i+i×i 4.句型、句子、语言的定义 句型和句子 设有文法G[S],若符号串x是从开始符推导出来的,即S =*x,则称x是文法G的句型 若x仅由终结符组成,即S =*x,且x∈VT*,则称x是文法G的句子 由规范推导所得的句型称为规范句型 例 文法G[S]: S→0S1, S→01 S ?0S1 ?00S11 ?000S111 ?00001111 S,0S1 ,00S11 ,000S111,00001111都是G的句型 00001111是G的句子 提问 以下哪个符号串是文法的句子 语言的定义 由文法G生成的语言记为L(G),它是文法G的一切句子的集合,即 L(G)={xS =*x,其中S为文法的开始符号, 且x ∈VT*} 例 文法G: S→0S1, S→01 S?0S1 ? 00S11 ? 03S13? …… ? 0n-1S1n-1 ? 0n1n L(G)={0n1nn≥1} 根据文法,可以通过推导得到该文法相应的语言; 例:G[E]:E→E+TT T→T×FF F→(E)a E ?E+T ?T+T ?F+T ?a+T ?a+T×F ?a+F×F ?a+a×F ?a+a×a 表示一切能用符号a,+,×,(和)构成的算术表达式 有了语言的要求,也可以为该语言设计文法 例:若语言由0、1符号串组成,串中0和1的个数相同,构造其文法为: A → 0B1C B → 11A0BB C → 00A1CC 提问 根据文法,可以通过推导得到该文法相应的语言; S → S + a a 有了语言的要求,也可以为该语言设计文法 L(G) = { a,(a),((a)),(((a))),…} 5.文法的等价 若L(G1)=L(G2),则称文法G1和G2是等价的。 例如 文法 G1[A]:A→0R A→01 R→A1 G2[S]:S→0S1 S→01 所定义的语言都是0n1n 两文法等价 2.4 文法的类型 通过对产生式施加不同的限制, Noam Chomsky将文法分为 四种类型: 0型文法(短语文法):对任一产生式α→β,都有α∈(VN∪VT)*且至少含有一个非终结符, β∈(VN∪VT)* 1型文法(上下文有关):它是0型文法的特例,设文法G=(VN,VT,P,S),对P中的任一产生式α→β,都有β≥α, 仅仅 S→ε除外 例 文法G[S]: S-aSBA AA’-AB BA-BA’ S-abB bA-bb BA’-AA’ 1型文法产生式的一般形式是?A?→???, ?,? ∈ V* ,A∈VN , β∈V+ ,它表示当A的上文为?且下文为?时可把A替换成?,因此称1型文法为上下文有关文法。 2型文法(上下文无关文法) :它是1型文法的特例,对任一产生式α→β,都有α∈VN , β∈(VN∪VT)* 例 文法G[S]: S→AB A→BS0 B→SA1 2型文法产生式的一般形式是:A→?,它表示不管A的上下文如何即可把A替换成?,因此被称为上下文无关文法。 产生式A→ε称为ε规则 通常程序设计语言的文法,可用2型文法来描述,因此我们重点研究2型文法。 3型文法(正规文法):它是2型文法的特例,任一产生式α→β的形式都为A→aB或A→a,其中A ,B∈VN ,a∈VT 例如 文法G[S]: S→0A1B0 A→0A1B0S B→1B10 在程序设计语言中,3型文法通常用来描述单词的结构。 文法类别 产生式形式 产生的语言 说明 0型文法 (短语文法) α→β α∈V+ ,且至少含一个非终结符,β∈V* 0型语言 对产生式基本无限制 1型文法 (上下文有关文法) α→β,β≥α≥1或 ?A?→???, ?,? ∈ V* A∈VN , β∈V+ 1型语(上下文有关语言) 将A替换成?时,必须考虑A的上下文?,? 2型文法 (上下文无关文法) A→β,A∈VN , β∈V* 2型语(上下文无关语言) 无需考虑A在上下文中的出现情况 3型文法 (正规文法) A→aB或A→a, A,B∈VN ,a∈VT 3型语(正规语言) 产生式全部是规定的形式 四种文法之间的逐级“包含”关系 2型文法 1型文法 3型文法 0型文法 2.5上下文无关文法及其语法树 1.上下文无关文法(Context-Free Grammar) 上下文无关文法有足够的能力描述现今程序设计语言的语法结构 例:算术表达式:E→iE+EE*E(E) 赋值语句-i:=E 条件语句-if 条件then 语句 if 条件 then 语句 else 语句 所以我们只关心上下文无关文法形成的语言的句子的分析和分析方法 2.语法树(推导树Parse Tree) 作用:直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S),对于G的任何句型都能构造与之关联的语法树 例:文法G:E→E+TT T→T×FF F→(E)i 句型T+T×F的推导过程与语法树 E E T + T F T × E=E+T E E T + T F T × E=E+T =E+T×F =T+T×F =T+T =T+T×F 从语法树中看不出句型中的符号被替代的顺序 从左到右读出叶子结点得到的符号串,为文法的句型。也把该语法树称为该句型的语法树。 语法树定义: 给定文法G=( VN,VT,P,S),若一棵树满足下列4个条件,则称此树为G的语法树: 每个结点都有一个标记,此标记是V的一个符号 根的标记是S 若一结点n至少有一个它自己除外的子孙,并且有标记A,则肯定A∈VN 如果结点n有标记A,其直接子孙结点从左到右的次序是n1,n2,…,nk,其标记分别为A1,A2,…,Ak,那么A→A1A2…Ak一定是P中的一个产生式 语法树和推导的关系 句型的每个推导都产生相应的一棵语法树 一个句型的不同推导产生相同的语法树 每棵语法树对应唯一的最左推导或最右推导 通常,一个句型有唯一的语法树、最左推导和最右推导,它们代表了句型的语法结构,但是一个句型可以有多个不同的推导,它不能代表句型的语法结构 E E T + T F T × E=E+T =T+T =T+T×F E=E+T =E+T×F =T+T×F 3.文法的二义性(Ambiguity) 通常,一个句型对应一棵语法树,它表示该句型的不同推导过程 句型“T+T ×F”对应的语法树: 文法G:E→E+EE×E(E)i 句子 i×i+i 对应的语法树 两个不同的最左推导: 推导1:E ? E+E ? E×E+E ? i×E+E ? i×i+E ? i×i+i 推导2:E ? E×E ? i×E ? i×E+E ? i×i+E ?i×i+i i E E + E E E × i i E E E × i E E + i i 二义性: 如果一个文法存在某个句子对应两棵不同的语法树,则说这个文法是二义的 二义性文法存在某个句子,它有两个不同的最左(右)推导 对于一个程序设计语言来说,希望它的文法是无二义的,因为希望对它的每个语句的分析是唯一的。 构造无二义性文法 文法G: E→ E+E E×E (E) i 文法G: E-TE+T T-FT×F F-(E) i 等价的无二义文法 句子 i×i+i 对应的语法树 F E T + E T F × i F T i i 2.6 句型的分析 任务:句型分析就是识别一个符号串是否为某文法的句型,是某个推导的构造过程。 对于程序设计语言来说,句型分析就是一个识别输入符号串是否为语法上正确的程序的过程。 从左到右的分析算法,即总是从左到右地识别输入符号串.句型分析算法采用从左到右的分析算法 句型的分析算法分类 自上而下分析法(Top-Down parsing) 自下而上分析法(Bottom-Up parsing) 2.6.1自上而下的分析方法 定义: 从文法的开始符号出发,反复使用文法的产生式,寻找与输入符号串匹配的推导。 语法树的构造:将文法的开始符号作为语法树的根,向下逐步建立语法树,使语法树的末端结点符号串正好是输入符号串。 例 文法G:S → cAd A → ab A → a 识别输入串w=cabd是否为该文法的句子 S 推导过程: c A d a b =cabd S =cAd 自上而下方法的主要问题 对输入串cabd自上而下构造语法树的另一过程 不成功,不成功的原因是选错产生式A→a 自上而下分析的主要问题是选择产生式 : 假定要被代换的最左非终结符号是B,且有n条规则:B→A1A2…An,那么如何确定用哪个右部去替代B? S c A d a 2.6.2自下而上的分析方法 定义:从输入符号串开始,利用文法的产生式逐步进行归约,试图归约到文法的开始符号。 语法树的构造:从输入符号串开始,以它作为语法树的末端结点符号串,自底向上的构造语法树,使文法开始符正好是该语法树的根。如果最终根结点是开始符,则输入符号串是语言的一个句子,否则不是。 例 文法G:S → cAd A → ab A → a 识别输入串w=cabd是否为该文法的句子 c a b d 归约过程: 用“-”表示归约,下划线部分为被归约符号 cabd -cAd -S A S 自下而上分析的主要问题 对输入串cabd的两种归约过程 (1)cabd-cAd-S 归约到开始符 (2)cabd-cAbd 不能归约到开始符 在自下而上的分析方法中,每一步都是从当前串中选择一个子串加以归约,该子串暂称“可归约串”。 如何确定“可归约串”是自下而上分析的主要问题。 不同的确定“可归约串”的方法,形成了不同的自下而上分析方法 在一种“规范归约”方法中,“可归约串”被称为“句柄” 短语,直接短语和句柄 定义: 设αβδ是文法G[S]中的一个句型,如果有S=*αAδ且A=+β,则称β是句型αβδ相对于非终结符A的短语 特别的如有A=β,则称β是句型αβδ相对于规则A→β的直接短语。 一个句型的最左直接短语称为该句型的句柄(Handle)。 S α A δ … β … S α A δ … β 第二章 文法和语言 学习目标: 掌握:自上而下与自下而上的分析思想 理解:文法的形式定义,推导,归约,句型,句子,语言,上下文无关文法,规范句型,语法树,短语,直接短语,句柄 了解:文法的类型,文法实用中的限制,文法的二义性 2.1 语言和文法的直观概念 2.2 符号和符号串 2.3 文法和语言的形式定义 2.4 文法的类型 2.5 上下文无关文法及其语法树 2.6 句型的分析 2.1 语言和文法的直观概念 程序设计语言的直观定义 程序设计语言是一个记号系统,它的定义包括语法和语义。 语法(syntax) 定义:是一组规则,用它可以形成和产生一个合适的程序 描述工具:文法 作用:定义什么样的符号序列是合法的,与符号的含义无关。 语义(semantics) 分类: 静态语义:一系列限定规则,确定哪些合乎语法的程序是合适的 动态语义:表明程序要做什么 描述工具:指称语义,操作语义等 作用:检查类型匹配,变量作用域等 文法的直观概念 如何来描述一种语言? 如果语言是有穷的(只含有有穷多个句子),可以将句子逐一列出来表示 如果语言是无穷的,要找出语言的有穷表示。 有两个途经: 生成方式 (文法):语言中的每个句子可以用严格定义的规则来构造 识别方式(自动机):用一个过程,当输入的一任意串属于语言时,该过程经有限次计算后就会停止并回答“是”,若不属于,要么能停止并回答“不是”,要么永远继续下去。 文法:是语言语法的描述工具,实现用有穷的规则把语言的无穷句子集描述出来。 例:“我是大学生”是汉语的一个句子 汉语句子的构成规则表示如下: 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉|〈名词〉 〈代词〉∷=我|你|他 〈名词〉∷=王明|大学生|工人|英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷=是|学习 〈直接宾语〉∷=〈代词〉|〈名词〉 例:“(34-3)*42 ”是一个表达式 表达式的构成规则表示如下: Exp ∷= Exp op Exp (Exp) Number Op ∷= + – * 由规则推导句子 方法: 用一条规则∷=的右端符号串代替::=的左端. 表示: 用“ = ”表示推导,含义是,使用一条规则,代替=左边的某个符号,产生=右端的符号串. 例如:句子“我是大学生”的推导过程如下: 〈句子〉 ? 〈主语〉〈谓语〉 ? 〈代词〉〈谓语〉 ?我〈谓语〉  ?我〈动词〉〈直接宾语〉 ?我是〈直接宾语〉 ?我是〈名词〉 ?我是大学生 文法的作用 严格定义句子的结构,是判断句子结构合法与否的依据 用有穷的规则把无穷的句子集合描述出来 2.2 符号和符号串 字母表 定义:元素的非空有穷集合 例:∑={0?1} Α={a?b,c} 元素也称为符号,字母表也称符号集。 程序语言的字母表由字母数字和若干专用符号组成。 符号串 定义:由字母表中的符号组成的任何有穷序列 例: 0,00,10是字母表∑={0?1}上的符号串 a,ab,aaca是Α={a?b,c}上的符号串 在符号串中,符号是有顺序的,顺序不同,代表不同的符号串,如:ab和ba不同 不含任何符号的符号串称为空串,用ε表示 注意:{ε}并不等于空集合{ } 符号串长度: 符号串中含有符号的个数 如: abc=3 ε=0 符号串的运算 符号串的连接:设x、y是符号串,它们的连接是把y的符号写在 x的符号之后得到的符号串xy 例如 x=ST,y=abu 则 xy=STabu 显然εx = xε=x 符号串的方幂:把符号串a自身连接n次得到的符号串an = aa…aa 例如 a1=a a2=aa a0=ε 符号串集合: 定义:若集合A中所有元素都是某字母表?上的符号串,则称A为字母表?上的符号串集合。 符号串集合的乘积:符号串集合A和B的乘积定义为: AB ={xyx∈A且y∈B},即AB是由A中的串x 和B中的串y连接而成的串xy组成的集合。 若集合A=?ab,cde? B = ?0,1? 则 AB =?ab0,ab1,cde0,cde1? 显然{ε}A=A{ε}=A 符号串集合的方幂: 设A是符号串的集合,则称Ai为符号串集A的方幂,其中i是非负整数。具体定义如下: A0 ={ε } A1 = A , A2 = A A AK = AA......A(k个) 集合的闭包 闭包 集合Σ的闭包Σ *定义如下: Σ * = Σ 0∪ Σ1∪ Σ 2∪ Σ 3∪… 例:设有字母表Σ={0,1} 则Σ*=Σ0∪Σ1∪Σ2∪… ={ε,0,1,00,01,10,11,000,…} 即Σ*表示Σ上所有有穷长的串的集合。 正闭包 Σ += Σ 1∪ Σ 2∪ Σ 3∪…称为Σ的正闭包。 ?+ 表示?上的除ε外的所有用穷长串的集合 Σ *= Σ 0∪ Σ + Σ += Σ Σ *= Σ * Σ 字母表?上的一个语言是?上的一些符号串的集合 即是?*的一个子集 例如:Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…} 集合{ab,aabb,aaabbb,…,anbn,…}或 {ww∈Σ*且w=anbn,n≥1}为字母表?上的一个语言。 集合{a,aa,aaa,…}或{ww∈Σ*且w=an,n≥1}为字母表?上的一个语言 ?ε?是一个语言 ?即? ?是一个语言。 2.3文法和语言的形式定义 1.文法的定义 2.文法的简化表示法 3.推导与归约 4.句型、句子、语言的定义 5.文法的等价 1.文法的定义 产生式(规则) 产生式是一个有序对(α,β),通常写作 α→β(或α::=β ) 文法定义: 文法G(Grammar)定义为四元组(VN,VT,P,S) VN (Nonternimal):非终结符集 VT (Terminal):终结符集 P (Production): 产生式(规则)集合 S(Start Symbol): 开始符号或识别符号 说明: V=VN∪VT,V称为文法G的字母表 P中产生式形如:α→β,其中α∈V+且至少含一个非终结符,β∈V* VN,VT和P是非空有穷集 VN∩VT=φ S是一个非终结符,且至少要在一条产生式的左部出现 汉语句子的构成规则表示如下: 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉|〈名词〉 〈代词〉∷=我|你|他 〈名词〉∷=王明|大学生|工人|英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷=是|学习 〈直接宾语〉∷=〈代词〉|〈名词〉 例1:文法G=(VN,VT,P,S) 其中VN={S},VT={0,1}, P={S-0S1,S-01},开始符为S 例2:文法G=(VN,VT,P,S) VN ={标识符,字母,数字}, VT ={a,b,c,…x,y,z,0,1,…,9} P={标识符→字母, 标识符→标识符字母 标识符→标识符数字, 字母→a,…, 字母→z, 数字→0,…,数字→9 },S=标识符 2.文法的简化表示法 简化:通常不用将文法的四元组表示出来,只写出产生式 约定: 第一条产生式的左部是开始符号或用G[S]表示S是开始符号 用大写字母(或用尖括号括起来)表示非终结符 用小写字母表示终结符 左部相同的产生式A-α,A-β可以记为A-αβ,其中“”是“或”的意思,α,β分别称为侯选式 例如: 文法G[S]: S-ASASD A-ab…z D-01…9 3.推导(Derivation)与归约(Reduction) 直接推导和直接归约: α→β是文法G的产生式,若有v,w满足:v=γαδ,w= γβδ, 其中γ,δ∈V* 则称v直接推导到w,也称w直接归约到v,记作 v ? w 直接推导就是用产生式的右部替换产生式的左部的过程 直接归约就是用产生式的左部替换产生式的右部的过程 例 文法G: S→0S1,S→01 有直接推导: 0S1 ?00S11 ( S→0S1 ) 00S11 ?000S111 ( S→0S1 ) 000S111 ?00001111 ( S→01 ) S ?0S1 ( S→0S1 ) 推导和归约 若存在v=w0 ?w1 ?... ?wn=w ,(n0) 则称v推导出w,或w归约到v,记为v=+w 若有v =+w,或v=w,则记作v=*w 例 文法G: S→0S1, S→01 S ?0S1 ?00S11 ?000S111 ?00001111 S =+00001111 S =*00001111 S =*S 规范推导 如果在推导的任何一步α?β,都是对α中的最左(最右)非终结符进行替换,则称这种推导为最左(最右)推导 最右推导被称为规范推导 例如:句子“我是大学生”的推导过程如下: 〈句子〉 ? 〈主语〉〈谓语〉 ? 〈代词〉〈谓语〉 ?我〈谓语〉 ?我〈动词〉〈直接宾语〉 ?我是〈直接宾语〉 ?我是〈名词〉 ?我是大学生 C * S ? (S) a *

本文链接:http://capstonebake.com/zhichenyuyi/343.html