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