资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2021/9/24,*,*,程序语言的语法描述与分析,目的：,语言的语法结构的形式描述,从形式描述中，研究语法分析器的构造,（算符优先分析法和递归子程序分析法）,2021/9/24,1,本章内容,引言,-,文法,文法与语言,-,上下文无关文法,-,推导与语言,语法树与二义性,第三章 上下文无关文法,(context-free grammar),2021/9/24,2,文法（,grammar),问题：,如何描述语言,定义：,文法,是描述语言的语法结构的形式规则（即语法规则),目的：,解决语言的有穷说明问题，包含对语法的描述，但,却不表达任何语义,一、引言,2021/9/24,3,1、文法的描述应达到要求：,2、文法分类：,分为四类（0、1、2、3型文法），对应四类语言；,与程序语言语法有关的是,上下文无关文法,形式上严格、准确；,易于理解；,具有较强的描述能力；,有利于句子的分析和翻译，构造语法分析器,2021/9/24,4,3、上下文无关文法的特点：,它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的,说明,上下文无关文法只能描述一部分语言，但已足够,描述现今的程序设计语言,自然语言要用其他的文法来描述,2021/9/24,5,二、文法与语言,1、,一个,上下文无关文法G,是一个四元式（V,T,V,N,S,P,），其中:,V,T,：是非空有限集，它的每个元素是终结符号；,V,N,：是非空有限集，它的每个元素是非终结符号；V,T,V,N,=,;V,T,V,N,=V;,P,：产生式集合（有限），每个产生式形式是,P-,|PV,N,，,(V,T,V,N,)*，S至少一次为P；,S：SV,N,，称为开始符号；,2021/9/24,6,例1、,考虑下面的算术表达式的文法及语言,V,T,：id +*/(),V,N,：表达式、运算符,S：表达式,P,：表达式-表达式 运算符 表达式,表达式-（表达式）,表达式-表达式,表达式-id,运算符-+|*|/|,得到,文法G1(E):,E-EAE|(E)|E|id,A-+|*|/|,2021/9/24,7,该文法的：V,N,是出现,P,的左部所有符号集合,V是,P,的所有符号,V,T,=V V,N,S是该文法所定义的句子名字,写出了,P,，就能找出其它三元素,由此可见，文法G1(E)所定义的语言是上述算术表达式，,如：id+id，id*(id+id)等,它表达了简单算术表达式由id用A连接起来,2021/9/24,8,2、从此可见,终结符：,是用以组成语言中的串的基本符号，与程序语言中“,单词,”是同义语；,如：表达式id+(id)*(-id)中，+、*、/、id均为终结符,非终结符：,是标记某种串的集合的特定符号，与“,语法变量,”、“,语法范畴,”是同义词；,如：表达式、运算符都表示一个串的集合,2021/9/24,9,该语法范畴叫“,句子,”，在程序语言中叫“,程序,”,语言的句子是由一串,V,N,定义，到最后才是一串,V,T,开始符号：,一个V,N,，标记感兴趣的语法范畴。其它非终结符用以定义其它的串集，这有助于定义该语言，也有助于为它处理的语言提供一个分层的结构；,2021/9/24,10,产生式：,规定由终结符和别的语法范畴组成一个新的语法范畴的办法；,结构：非终结符-一串非终结符和终结符,如：A-,A -,左部符号 右部,候选式,V,N,=X,1,X,2,X,n,，X,i,V,2021/9/24,11,3、习惯记号,V,N,:大写字母A、B、C、S等,V,T,:小写字母，09，+、等运算符，,标点，分界符，黑体字母串id、if,X、Y、Z：文法符号，或V,N,或V,T,一个符号,u、v、wz：V,T,中串,、,、,:文法符号串(V,T,V,N,)*,S:开始符号，第一个产生式中出现,-:定义为（元语言符号）,|：或（元语言符号）,2021/9/24,12,有穷条产生式，产生无穷集，要求产生式必须递归,定义算术表达式，用了两条浓缩的产生式，一般定义一个语言的产生式是很复杂的,对递归的算术表达式的产生式，进行反复,推导,产生表达式语言,问题：,表达式语言无穷，如何定义？,2021/9/24,13,4、推导与语言,问题：,用文法如何定义一个语言？,思路：,从S出发，反复使用,P，对非终结符,替换,展开，最后得到全由终结符串组成的一个串,涉及到：,替换,-,推导,-,句型,-,句子,-,语言,2021/9/24,14,推导：,如两个串u,0,、u,n,，存在一个串序列,u,0,u,1,u,n,则,u,0,R,1,u,n,，,R,1,记为 或,u,0,u,n,：,表示从u,0,出发，经一步或若干步，可推导出u,n,u,0,u,n,：,表示从u,0,出发，经0步或若干步，可推导出u,n,直接推导：,是两个字符串之间的一种关系,R,如：（,A,）,R,（,），它表示：,若A-,P，,、,V*,则,R,就是,直接推导,，,R,记为,即：,A ,2021/9/24,15,如令,u,0,为,S,，即推导要从开始符号开始，那么,：,S,，,V*,，称,为,G,的,句型,如再要求,V,T,*,，则,为,G,的,句子,文法,G,所产生的句子的全体是一个,语言,，记为,L(G),L(G)=,|S,&,V,T,*,怎样由推导引出语言？,只需在推导中加一些限制,即对：,u,0,u,n,或,u,0,u,n,2021/9/24,16,由文法G定义语言L是依赖一种运算，关系,V*中有许多的串，仅有那些(S,u)(S,v)存在 关系的u、v才有可能成为语言中的,句子,。,、,、,是,句型,，表示(S，,)(S，)，有 的关系，但它的构成不全为V,T,的字符。,G的,句型集,，是指存在S,关系的所有,，该集的子集是L(G),V*句型集 L(G),说明,2021/9/24,17,例2,根据文法G:,E-E+E|E*E|(E)|i,句子i,1,*(i,2,+i,3,)推导过程如下：,E=E*E=E*(E)=E*(E+E)=E*(E+i,3,)=E*(i,2,+i,3,),=i,1,*(i,2,+i,3,),E=E*E=i,1,*E=i,1,*(E)=i,1,*(E+E)=i,1,*(i,2,+E),=i,1,*(i,2,+i,3,),注意：从一个句型到另一个句型的推导过程并不唯一，但通常只考虑,最左推导,和,最右推导。,最左推导,最右推导,最左推导,是指，任何一步,=,都是对,中的,最左非终结符,进行替换的,最右推导,是指，任何一步,=,都是对,中的,最右非终结符,进行替换的,2021/9/24,18,三、语法树与二义性,1、语法树,定义：,句型推导的图形表示，它与替换顺序的选取无关,作用：,明显的形成文法所暗含的句子分层语法结构，,为语法分析提供一些新的途径,目的：,为了理解句子的语法，得到句子如何从开始符,号推导得到，因此引入“图”,2021/9/24,19,树的叶：,非终结符,|,终结符，对应一个句型,语法树为语法分析提供一些新的途径,树的内节点：,非终结符,A,标记,若,A-,，则该产生式的一棵子树为,A,X,Y,Z,2021/9/24,20,在语法树中找出文法中的概念,内结点,AV,N,叶文法符号,子树直接推导,根结点,S,任一次全剪句型,叶子,V,T,时，将叶子顺序排列句子,2021/9/24,21,例3,E (id+id)的语法树,最左推导：,E -E -(E)-(E+E)-(,id+E,),(,id+id,),最右推导：,E -E -(E)-(E+E)-(,E+id,),(,id+id,),E,E,id,id,(,E,),E,+,E,语 法 树,2021/9/24,22,由此可见，,每一中间过程，句型很容易获得,树忽略了符号的替换顺序的不同，不同推导过程得到相同的语法树,有的语法，对于同一句子、应用不同规则进行推导得到不同的语法树,例4,根据文法G对句子id+id*id进行推导,2021/9/24,23,文法G,E-E+E|E*E|(E)|i,推导1,E=E+E=id+E=id+E*E=id+id*E,=id+id*id,推导2,E=E*E=E+E*E=id+E*E=id+id*E,=id+id*id,与 两种推导对应两棵不同的语法树，如下所示：,2021/9/24,24,推导1的语法树,推导2的语法树,E,E,*,id,id,E,id,E,+,E,+,id,id,E,E,E,E,*,E,id,E=E+E=id+E,=id+E*E=id+id*E,=id+id*id,E=E*E=E+E*E,=id+E*E=id+id*E,=id+id*id,2021/9/24,25,2、二义性问题,定义：,文法G的某一句子有两棵不同的树，则G为,二义的。,二义性对语法分析不便，因此希望：,1）判定二义否,2）无二义性的充分条件,3）如何消除二义性,2021/9/24,26,解决办法：尽量去掉二义性,如对上例，可以通过阐明运算符的优先性和结合性来解除文法的二义性,通过重写一个文法，把结合性和优先规则结合进文法本身中去,注意到，L(G)=L(G)，GG,2021/9/24,27,语言的二义性问题与文法的二义性问题,如L找到一个文法是无二义的，则L是无二义的；,如未找到一个文法是无二义的，则也不能断定它二义，但先天二义也存在；,文法的二义性是不可判定的。（因为文法的二义性由句子的语法树决定，不可能对无穷句子来判别）,2021/9/24,28,最后，作为描述程序语言的上下文无关文法，,我们限制：,G不含下面的产生式,P-P,每一PV,N,，必须都有用处，即,S,P，P在句型中出现,V,T,*,P,，即对P不存在不终结的回路,2021/9/24,29,
展开阅读全文