编译原理第二章-(2).ppt

《编译原理第二章-(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.2.4语法树与文法二义性11.文法（Grammar）的定义文法的定义一个文法G是一个四元组:G=(VN,VT,S,P)其中：VT(TerminalVocabulary)是一个非空的有限集合，它的每个元素称为终极符号或终极符，一般用小写字母表示。从语法分析的角度看，终极符号是一个语言不可再分的基本符号。2.2.1文法的定义相关概念复习2VN(NonterminalVocabulary)是一个非空的有限集合，它的每个元素称为非终极符号、非终极符或中间符，一般用大写字母表示。非终极符是一个语法范畴，表示一类具有

2、某种性质的符号，它不出现在句子中。注：设V是文法G的符号集，则有:V=VN∪VT,VN∩VT=2.2.1文法的定义3S(Start)是特殊的非终极符号，称为文法的开始符号,S∈VN。2.2.1文法的定义4P(production)是产生式的有限集合。所谓的产生式，也称为产生规则（简称为规则），是按照一定格式书写的定义语法范畴的文法规则。产生式的形式为：或::=2.2.1文法的定义52.直接推导若是文法G=（VN,VT,S,P）中的一条产生式，、∈(VT∪VN)*，若有符号串v,w满足：v

3、=,w=则称v（应用规则）直接推导出w，或者说w是v的直接推导，记作：vw。又称w直接归约到v。2.2.3推导和归约63.直接推导序列如果存在：v=01,12,…,n-1n=w(n≥1)则说：v经过n(n＞0)步推导出w,记作：v+w。若有v+w，或v=w，则说v经过n(n≥0)步推导出w，记作：v*w。即“*”表示0步或多步直接推导。推导的逆过程称为归约。2.2.3推导和归约74.最右推导在推导过程中，总是对当前符号串中最右边的非终极符进行替换，称为最右推导，又

4、称之为规范推导,并用符号rm表示。规范推导的逆过程称为规范归约。85.最左推导在推导过程中，总是对当前符号串中最左边的非终极符进行替换，称为最左推导，并用符号lm表示。96.句型设有文法G=（VN,VT,S,P），S是文法G的开始符号，如果有:S*,∈(VT∪VN)*则称为G的句型。最右推导得到的句型称为最右句型或规范句型，最左推导得到的句型称为最左句型。2.2.3推导和归约107.句子设有文法G，S是文法G的开始符号，如果有:S+,∈VT*则称为G的句子。7.语言所有句子的集合称为文法的

5、语言。记作:L(G)={α

6、S*,∈VT*}2.2.3推导和归约112.2.4语法树与文法二义性一、语法树（推导树、生成树或分析树）目的：直观地描述句型的推导过程。设G是给定的文法，称满足下列条件的树为G的一棵语法树：1.每个节点都标有G的一个文法符号，且根节点标有初始符S，非叶节点标有非终极符，叶节点标有非终极符或终极符。2.如果一个非叶节点A按从左到右顺序有n个儿子节点B1、B2、…、Bn，则:AB1B2…Bn一定是G的一个产生式。2.2.4语法树12例1:文法G=({E},{+,*,i,(,)}

7、,E,P),其中P为：EiEE+EEE*EE(E)考虑句型i*i+i的语法树：2.2.4语法树13G（E）：Ei

8、E+E

9、E*E

10、(E)句型i*i+i的推导过程1（最左推导）:EE+E①E*E+E②i*E+E③i*i+E④i*i+i⑤EE+EE*Eii推导1的语法树i2.2.4语法树14句型i*i+i的推导过程2（非最左和最右推导）:EE+E①E*E+E②E*E+i③E*i+i④i*i+i⑤EE+EE*Eii推导2的语法树i2.2.4语法树15EE*E(1)i*E(2)i*

11、E+E(3)i*i+E(4)i*i+i(5)推导3的语法树EE*EE+Eiii2.2.4语法树G（E）：Ei

12、E+E

13、E*E

14、(E)句型i*i+i的推导过程3（另一个最左推导）:16语法树表示了在推导过程中施用了哪个产生式和施用在哪个非终极符上，它没有表明施用产生式的顺序。一棵语法树表示了一个句型的种种可能的不同推导过程，但未必是所有的不同推导过程。一个句型未必对应唯一的一棵语法树。一个句型未必只有唯一的一个最左（最右）推导。2.2.4语法树17二、文法二义性对一个文法G，如果至少存在一个句子，有两棵（

15、或两棵以上）不同的语法树，则称该句子是二义性的。包含有二义性句子的文法称为二义性文法，否则，该文法是无二义性的。2.2.4语法树18例2:→ifthenelse→ifthen→......假设有条件语句：ife1thenife2thens1elses2则可有下图所示的两棵不同的语法分析树：if语句的二义性ififthen