您好,欢迎访问三七文档
当前位置:首页 > 行业资料 > 交通运输 > 编译原理-西安交通大学(冯博琴)第三章上下文无关文法
程序语言的语法描述与分析目的:语言的语法结构的形式描述从形式描述中,研究语法分析器的构造(算符优先分析法和递归子程序分析法)本章内容引言-文法文法与语言-上下文无关文法-推导与语言语法树与二义性第三章上下文无关文法(context-freegrammar)文法(grammar)问题:如何描述语言定义:文法是描述语言的语法结构的形式规则(即语法规则)目的:解决语言的有穷说明问题,包含对语法的描述,但却不表达任何语义一、引言1、文法的描述应达到要求:2、文法分类:分为四类(0、1、2、3型文法),对应四类语言;与程序语言语法有关的是上下文无关文法形式上严格、准确;易于理解;具有较强的描述能力;有利于句子的分析和翻译,构造语法分析器3、上下文无关文法的特点:它所定义的语法范畴(或语法单位)是完全独立于这种范畴可能出现的环境的上下文无关文法只能描述一部分语言,但已足够描述现今的程序设计语言自然语言要用其他的文法来描述二、文法与语言1、一个上下文无关文法G是一个四元式(VT,VN,S,P),其中:VT:是非空有限集,它的每个元素是终结符号;VN:是非空有限集,它的每个元素是非终结符号;VT∩VN=Φ;VT∪VN=V;P:产生式集合(有限),每个产生式形式是{P-α|P∈VN,α∈(VT∪VN)*,S至少一次为P};S:S∈VN,称为开始符号;例1、考虑下面的算术表达式的文法及语言VT:id+-*/↑()VN:表达式、运算符S:表达式P:表达式-表达式运算符表达式表达式-(表达式)表达式--表达式表达式-id运算符-+|-|*|/|↑得到文法G1(E):E-EAE|(E)|-E|idA-+|-|*|/|↑该文法的:VN是出现P的左部所有符号集合V是P的所有符号∴VT=V\VNS是该文法所定义的句子名字∴写出了P,就能找出其它三元素由此可见,文法G1(E)所定义的语言是上述算术表达式,如:id+id,id*(id+id)等它表达了简单算术表达式由id用A连接起来2、从此可见终结符:是用以组成语言中的串的基本符号,与程序语言中“单词”是同义语;如:表达式id+(id)*(-id)中,+、-、*、/、↑、id均为终结符非终结符:是标记某种串的集合的特定符号,与“语法变量”、“语法范畴”是同义词;如:表达式、运算符都表示一个串的集合该语法范畴叫“句子”,在程序语言中叫“程序”语言的句子是由一串VN定义,到最后才是一串VT开始符号:一个VN,标记感兴趣的语法范畴。其它非终结符用以定义其它的串集,这有助于定义该语言,也有助于为它处理的语言提供一个分层的结构;产生式:规定由终结符和别的语法范畴组成一个新的语法范畴的办法;结构:非终结符-一串非终结符和终结符如:A-αA-α↓↓左部符号右部候选式VNα=X1X2…Xn,Xi∈V3、习惯记号VN:大写字母A、B、C、S等VT:小写字母,0~9,+、-等运算符,标点,分界符,黑体字母串id、ifX、Y、Z:文法符号,或VN或VT一个符号u、v、w…z:VT中串α、β、γ:文法符号串∈(VT∪VN)*S:开始符号,第一个产生式中出现-:定义为(元语言符号)|:或(元语言符号)有穷条产生式,产生无穷集,要求产生式必须递归定义算术表达式,用了两条浓缩的产生式,一般定义一个语言的产生式是很复杂的对递归的算术表达式的产生式,进行反复推导产生表达式语言问题:表达式语言无穷,如何定义?4、推导与语言问题:用文法如何定义一个语言?思路:从S出发,反复使用P,对非终结符替换展开,最后得到全由终结符串组成的一个串涉及到:替换-推导-句型-句子-语言②推导:如两个串u0、un,存在一个串序列u0u1…un则u0R1un,R1记为或u0un:表示从u0出发,经一步或若干步,可推导出unu0un:表示从u0出发,经0步或若干步,可推导出un①直接推导:是两个字符串之间的一种关系R如:(αAβ)R(αγβ),它表示:若A-γ∈P,α、β∈V*则R就是直接推导,R记为即:αAβαγβ如令u0为S,即推导要从开始符号开始,那么:Sα,α∈V*,称α为G的句型如再要求α∈VT*,则α为G的句子文法G所产生的句子的全体是一个语言,记为L(G)L(G)={α|Sα&α∈VT*}③怎样由推导引出语言?只需在推导中加一些限制即对:u0un或u0un①由文法G定义语言L是依赖一种运算,关系V*中有许多的串,仅有那些(S,u)(S,v)存在关系的u、v才有可能成为语言中的句子。②α、β、γ是句型,表示(S,α)(S,β),有的关系,但它的构成不全为VT的字符。③G的句型集,是指存在Sα关系的所有α,该集的子集是L(G)④V*句型集L(G)例2根据文法G:E-E+E|E*E|(E)|i句子i1*(i2+i3)推导过程如下:②E=E*E=E*(E)=E*(E+E)=E*(E+i3)=E*(i2+i3)=i1*(i2+i3)①E=E*E=i1*E=i1*(E)=i1*(E+E)=i1*(i2+E)=i1*(i2+i3)注意:从一个句型到另一个句型的推导过程并不唯一,但通常只考虑最左推导和最右推导。最左推导最右推导最左推导是指,任何一步α=β都是对α中的最左非终结符进行替换的最右推导是指,任何一步α=β都是对α中的最右非终结符进行替换的三、语法树与二义性1、语法树定义:句型推导的图形表示,它与替换顺序的选取无关作用:明显的形成文法所暗含的句子分层语法结构,为语法分析提供一些新的途径目的:为了理解句子的语法,得到句子如何从开始符号推导得到,因此引入“图”树的叶:非终结符|终结符,对应一个句型语法树为语法分析提供一些新的途径树的内节点:非终结符A标记若A-α,则该产生式的一棵子树为AXYZ在语法树中找出文法中的概念•内结点AVN•叶文法符号•子树直接推导•根结点S•任一次全剪句型•叶子∈VT时,将叶子顺序排列句子例3E-(id+id)的语法树最左推导:E-E-(E)-(E+E)-(id+E)-(id+id)最右推导:E-E-(E)-(E+E)-(E+id)-(id+id)E-Eidid(E)E+E语法树由此可见,•每一中间过程,句型很容易获得•树忽略了符号的替换顺序的不同,不同推导过程得到相同的语法树•有的语法,对于同一句子、应用不同规则进行推导得到不同的语法树例4根据文法G对句子id+id*id进行推导①文法GE-E+E|E*E|(E)|i②推导1E=E+E=id+E=id+E*E=id+id*E=id+id*id③推导2E=E*E=E+E*E=id+E*E=id+id*E=id+id*id②与③两种推导对应两棵不同的语法树,如下所示:推导1的语法树推导2的语法树EE*ididEidE+E+ididEEEE*EidE=E+E=id+E=id+E*E=id+id*E=id+id*idE=E*E=E+E*E=id+E*E=id+id*E=id+id*id2、二义性问题定义:文法G的某一句子有两棵不同的树,则G为二义的。二义性对语法分析不便,因此希望:1)判定二义否2)无二义性的充分条件3)如何消除二义性解决办法:尽量去掉二义性①如对上例,可以通过阐明运算符的优先性和结合性来解除文法的二义性②通过重写一个文法,把结合性和优先规则结合进文法本身中去注意到,L(G)=L(G’),G≠G’语言的二义性问题与文法的二义性问题①如L找到一个文法是无二义的,则L是无二义的;②如未找到一个文法是无二义的,则也不能断定它二义,但先天二义也存在;③文法的二义性是不可判定的。(因为文法的二义性由句子的语法树决定,不可能对无穷句子来判别)最后,作为描述程序语言的上下文无关文法,我们限制:①G不含下面的产生式P-P②每一P∈VN,必须都有用处,即SαPβ,P在句型中出现γ∈VT*,Pγ,即对P不存在不终结的回路
本文标题:编译原理-西安交通大学(冯博琴)第三章上下文无关文法
链接地址:https://www.777doc.com/doc-237145 .html