编译原理-西安交通大学(冯博琴)第三章上下文无关文法

程序语言的语法描述与分析目的：语言的语法结构的形式描述从形式描述中，研究语法分析器的构造（算符优先分析法和递归子程序分析法）本章内容引言-文法文法与语言-上下文无关文法-推导与语言语法树与二义性第三章上下文无关文法(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不存在不终结的回路