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