1、第二章 高级语言及其语法描述程序语言的定义 一个程序语言是一个记号系统，包括语法和语义两个方面。语法：任何语言程序都可看成是一定字符集（称字母表）上的一字符串（有限序列）。语法包括了：词法规则和语法规则语义：对一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。离开语义，语言只不过是一堆符号的集合。所谓一个语言的语义是这样的一组规则，使用它可以定义一个程序的意义。这些规则称为语义规则。阐明语义要比阐明语法难的多，现在还没有一种形式系统描述语义。2.2 高级语言的一般特性 高级语言的分类：（1）强制式的高级语言（也称过程式语言）（2）应用式的高级语言（3）基于规则
2、的高级语言（4）面向对象的高级语言程序结构数据类型与操作：三要素（1）用于区别这种类型的数据对象的属性（2）这种类型的数据对象可以具有的值（3）可以作用于这种类型的数据对象的操作语句与控制结构：表达式语句：（1）赋值语句（2）控制语句（3）说明语句（4）简单 语句2.3 程序语言的语法描述 首先掌握几个概念：设设 是一个有穷是一个有穷字母表字母表，它的每个元素称为一个，它的每个元素称为一个符号符号。上的上的一个一个字符串字符串是指是指 中的符号所构成的一个有穷序列。不包含任中的符号所构成的一个有穷序列。不包含任何符号的序列称为何符号的序列称为空字空字，极为，极为。用用*表示表示 上的所有符号串
3、的全体，空字上的所有符号串的全体，空字 也包括在内。也包括在内。*的子集的子集U和和V的（连接）积定义为的（连接）积定义为 UV=|U U&VV注意：注意：UVVU UVVU 但但 (UV)W=U(VW)(UV)W=U(VW)V V自身的自身的n n次积记为：次积记为：V Vn n=VVV=VVV(n(n次重复）次重复）规定规定 V V0 0=V0 令 V*=V0 V1 V2 称V*为V的闭包。记V+=V V*，称V+为V的正则闭包。预备知识预备知识-语言概述语言概述语言是由句子组成的集合，是由一组记语言是由句子组成的集合，是由一组记号所构成的集合。号所构成的集合。汉语汉语-所有符合汉语语法的
4、句子的全体所有符合汉语语法的句子的全体英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言-所有该语言的程序的全所有该语言的程序的全体体 每个句子构成的规律每个句子构成的规律研究语言研究语言 每个句子的含义每个句子的含义 每个句子和使用者的关系每个句子和使用者的关系预备知识预备知识-语言概述语言概述研究程序设计语言研究程序设计语言 每个程序构成的规律每个程序构成的规律 每个程序的含义每个程序的含义 每个程序和使用者的关系每个程序和使用者的关系语言研究的三个方面语言研究的三个方面 语法语法 Syntax 语义语义 Semantics 语用语用 Pragmat
5、ics预备知识预备知识-语言概述语言概述语法语法-表示构成语言句子的各个记号之间表示构成语言句子的各个记号之间的组合规律的组合规律语义语义-表示按照各种表示方法所表示的各表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号个记号的特定含义。（各个记号和记号所表示的对象之间的关系）所表示的对象之间的关系）语用语用-表示在各个记号所出现的行为中，表示在各个记号所出现的行为中，它们的来源、使用和影响。它们的来源、使用和影响。预备知识预备知识-语言概述语言概述每每种种语语言言具具有有两两个个可可识识别别的的特特性性，即即语语言的形式和该形式相关联的意义。言的形式和该形式相关联的意义。语语言
6、言的的实实例例若若在在语语法法上上是是正正确确的的，其其相相关关联联的的意意义义可可以以从从两两个个观观点点来来看看，其其一一是是该该句句子子的的创创立立者者所所想想要要表表示示的的意意义义，另另一一是是接接收收者者所所检检验验到到的的意意义义。这这两两个个意意义义并并非非总总是是一一样样的的，前前者者称称为为语语言言的的语语义义，后后者者是是其其语语用用意意义义。幽幽默默、双双关关语语和和谜谜语语就就是是利利用用这这两两方方面面意意义义间间的的差差异。异。预备知识预备知识-形式语言形式语言如如果果不不考考虑虑语语义义和和语语用用，即即只只从从语语法法这这一一侧侧面面来来看看语语言言，这这种种
7、意意义义下下的的语语言言称称作作形形式式语语言言。形形式式语语言言抽抽象象地地定定义义为为一一个个数数学学系系统统。“形形式式”是是指指这这样样的的事事实实：语语言言的的所所有有规规则则只只以以什什麽麽符符号号串串能能出出现现的的方方式式来来陈陈述述。形形式式语语言言理理论论是是对对符符号号串串集集合合的的表表示示法法、结结构构及及其其特特性性的的研研究究。是是程程序序设设计计语语言言语语法法分分析析研研究的基础。究的基础。预备知识预备知识-有关定义和记有关定义和记号号符号：可以相互区别的记号（元素）。符号：可以相互区别的记号（元素）。字母表字母表：符号（元素）的非空有穷集合。：符号（元素）的
8、非空有穷集合。符号串：由字母表符号串：由字母表 中的符号组成的任何有穷中的符号组成的任何有穷序列称为该字母表上的符号串。序列称为该字母表上的符号串。1.空符号串空符号串(没有没有符号的符号串符号的符号串)是是 上的符号串上的符号串 2.若若x是是 上的符号串上的符号串,a是是 的元素的元素,则则xa是是 上的符号串上的符号串 3.y是是 上的符号串上的符号串,当且仅当它可以由当且仅当它可以由1和和2导导出。出。例如：例如：=a,b =a,b ,a,b,a,b,aaaa,abab,aabbaaabba都都是是 上的符号串上的符号串预备知识预备知识-有关定义和记有关定义和记号号符号串符号串s的前缀
9、：移走符号串的前缀：移走符号串s尾部的零个或多尾部的零个或多于零个符号得到的符号串于零个符号得到的符号串.如：如：b是符号串是符号串banana的一个前缀的一个前缀.符号串符号串s的后缀：删去符号串的后缀：删去符号串s头部的零个或多头部的零个或多于零个符号得到的符号串于零个符号得到的符号串.如如:nana是符号串是符号串banana的一个后缀的一个后缀.符号串符号串s的子串：从的子串：从s中删去一个前缀和一个后中删去一个前缀和一个后缀得到的符号串缀得到的符号串.如如:ana是是符号串符号串banana的一个子串的一个子串.对于每个符号串对于每个符号串s，s和和两者两者都都是符号串是符号串s的前
10、的前缀，后缀和子串。缀，后缀和子串。符号串符号串s的真前缀，真后缀，真子串：任何非空的真前缀，真后缀，真子串：任何非空符号串符号串 x,相应地，是相应地，是s的前缀，后缀或子串，并的前缀，后缀或子串，并且且 s x 符号串的运算符号串的运算符号串的长度：符号串中符号的个数符号串的长度：符号串中符号的个数.符号串符号串s的长的长度记为度记为|s|。的长度为的长度为0连接：符号串连接：符号串x x、y y的连接的连接,是把是把y y的符号写在的符号写在x x的符的符号之后得到的符号串号之后得到的符号串xy xy 如如 x=x=abab,y=,y=cd cd 则则 xyxy=abcd abcd 有有
11、aa=a a 方幂：符号串自身连接方幂：符号串自身连接n n次得到的符号串次得到的符号串 a an n 定义为定义为 aaaaaaaa n n个个a aa a1 1=a,a=a,a2 2=aaaa则则a a0 0=符号串集合：若集合符号串集合：若集合A中所有元素都是某字中所有元素都是某字母表母表 上的符号串，则称上的符号串，则称A为字母表为字母表 上的符上的符号串集合。号串集合。两个符号串集合两个符号串集合A和和B的乘积定义为的乘积定义为 AB=xyxy|x|x A A且且y y B B 若若 集合集合A=abab,cdecde B=0,10,1 则则 AB=ab1,ab0,cde0,cde1
12、ab1,ab0,cde0,cde1 使用使用 *表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集合。组成的集合。*称为称为的闭包的闭包。上的上的除除外外的所有符号串组成的集合记为的所有符号串组成的集合记为+。+称为称为的正闭包的正闭包。例：例：=a,b=a,b *=,a,b,a,b,aaaa,abab,baba,bb,bb,aaaaaa,aabaab,+=a,b,=a,b,aaaa,abab,baba,bb,bb,aaaaaa,aabaab,语言：字母表语言：字母表 上上的一个语言是的一个语言是 上的一些符号串上的一些符号串的集合的集合 (上上的每个语言是的每个语言是*的一个子集的
13、一个子集)。例如：例如：=a,b=a,b*=,a,b,a,b,aaaa,abab,baba,bb,bb,aaaaaa,aabaab,集合集合 abab,aabbaabb,aaabbbaaabbb,a,an nb bn n,或或 w|ww|w*且且w=aw=an nb bn n,n,n11为为字母表字母表 上上的一的一个语言。个语言。集合集合 a,a,aaaa,aaaaaa,或或 w|ww|w*且且w=aw=an n,n,n1 1 为为字母表字母表 上上的一的一个语言。个语言。是是一个语言。一个语言。即即 是一个语言。是一个语言。语言语言上上的运算的运算设设L是（是（上的）一个语言上的）一个语言
14、,M是（是（上的）一个语上的）一个语言言,语言语言L和和M的并，交，差，补的并，交，差，补是一个语言。是一个语言。如如语言语言L和和M的并为的并为 L M，是一个语言是一个语言:w|w w|w is in L or is in M is in L or is in M 如：如：L1=a,b,y,z M1=1,28,9 =a,b,y,z M1=1,28,9 L1 M1=a,b,y,z1=a,b,y,z，1,28,9 1,28,9 语言语言L和和M的连接的连接是一个语言，记是一个语言，记为为 LM LM=stst|s|sL且且 t tM 如：如：L1M1=a1,b1,y1,z1,a2,b2a9z9
15、 =a1,b1,y1,z1,a2,b2a9z9 有有L =L=L。L的的n次连接次连接Ln=LL.L 语言语言上上的运算的运算语言语言L的的 闭包闭包记记为为 L*，L*=L0 L1 L2 .L0=，Ln=L Ln-1=Ln-1 L,n 1语言语言L的正的正 闭包闭包记记为为 L+，L+=L1 L2 L3.L+=LL*=L*L L*=L+如：如：L1=a,b,y,z M1=1,28,9 =a,b,y,z M1=1,28,9 （L1 M1 1）=a,b,y,z=a,b,y,z，1,28,91,28,9 （L1 M1 1）*=a,b,y,za,b,y,z，1,28,91,28,9，aa,1a,xy
16、z,6789st.L1（L1 M1 1）*=所有字母打头的字母和数字符所有字母打头的字母和数字符号串号串 语言的描述语言的描述如何来描述一种语言？如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。两个途如果语言是无穷的，找出语言的有穷表示。两个途经：经：生生成方式成方式（文法）：语言中的每个句子可以用严格定（文法）：语言中的每个句子可以用严格定义的规则来构造。义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任识别方式（自动机）：用一个过程，当输入的一
17、任意串属于语言时，该过程经有限次计算后就会停止意串属于语言时，该过程经有限次计算后就会停止并回答并回答“是是”，若不属于，要麽能停止，若不属于，要麽能停止并回答并回答“不不是是”，（要麽永远继续下去。），（要麽永远继续下去。）文法文法 数学系统数学系统一个形式数学系统可由下列基本成分来一个形式数学系统可由下列基本成分来刻画：一组基本符号，一组形成规则，刻画：一组基本符号，一组形成规则，一组公理，一组推理规则。一组公理，一组推理规则。文法和语言的形式定义文法和语言的形式定义文法的定义文法的定义推导的定义推导的定义句型、句子、语言的定义句型、句子、语言的定义文法的定义文法的定义文法文法G定义为四元
18、组（定义为四元组（VN，VT，P，S）VN：非终结符集非终结符集VT：终结符集终结符集P：产生式（规则）集合产生式（规则）集合S：开始符号开始符号VNVT=，S SVNV=V=VNVT，称为文法称为文法G G的文法的文法符号集合符号集合规则的定义规则的定义规则（重写规则、产生式或生成式），规则（重写规则、产生式或生成式），是形如是形如或或=的（的（，）有有序对，且序对，且VV+，VV*。称为规则的左部称为规则的左部(或生成式或生成式的左部的左部)。称为规则的右部称为规则的右部(或生成式或生成式的右部的右部)。文法的定义文法的定义例例3.1 文法文法G=（VN，VT，P，S）VN=S,VT=0,
19、1 P=S0S1,S01 S为开始符号为开始符号文法的定义文法的定义习惯上只将产生式写出。并有如下约定：习惯上只将产生式写出。并有如下约定：第一条产生式的左部是开始符号第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符者大写字母表示非终结符，小写字母表示终结符G可写成可写成GS，S是开始符号是开始符号G：Sa aAb Aabab Aa aAb A GS：Aabab Aa aAb A Sa aSb 缩写形式 GS：Aabab|a aAb|Sa aSb例例3.2 文法文法G=（VN，VT，P，S
20、）VN=标识符，字母，数字标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,z z 0,0,99 S=推导的定义推导的定义直接推导直接推导“”是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w=v=,w=,其中其中VV*,V,V*则称则称v v直接推导到直接推导到w,w,记作记作 v v w w 或或w w直接归约到直接归约到v v例：例：G G：S0S1，S01 S 0S1 00S11 000S111 00001111 .VAR;BEGIN READ()END.VAR A;BEGIN READ(A)END.推导的定义推导的定义若存在若存在v w0
21、w1.wn=w,(n0)则称则称v w，v推导出推导出w，或或w归约到归约到v若有若有v w，或或v=w，则记为则记为v w文法的句型、句子的定义文法的句型、句子的定义句型句型有文法有文法G，若若S x，则称则称x是文法是文法G的句型。的句型。句子句子有文法有文法G，若若S x，且且xVVT T*，则称则称x是文是文法法G的句子。的句子。例：例：G G：S0S1，S01S 0S1 00S11 000S111 00001111例：例：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F
22、a+a*a表示一切能用符号表示一切能用符号a，+，*，(和和)构成的算构成的算术表达式术表达式文法，语言的定义文法，语言的定义由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的一切句子的集合的一切句子的集合:L(G)=x|S x，其中其中S为文法的开始符为文法的开始符号，且号，且x VVT T*例：例：G G：S0S1，S01L(G)=0n1n|n1例例3.3 文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L（G）=anbnen|n1 S a S BE (SaSBE)a aBEBE (SaBE)aabE
23、BE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)G生成的每个串都在生成的每个串都在L(G)中中L(G)中的每个串确实能被中的每个串确实能被G生成生成已知语言描述，写出文法已知语言描述，写出文法例：若语言由例：若语言由0、1符号串组成，串中符号串组成，串中0和和1的个的个数相同，构造其文法。数相同，构造其文法。A 0B|1CB 1|1A|0BBC 0|0A|1CC已知文法，写出语言描述已知文法，写出语言描述例：例：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|a推导的定义推导的定义若存在若存
24、在v w0 w1.wn=w,(n0)则称则称v w，v推导出推导出w，或或w归约到归约到v若有若有v w，或或v=w，则记为则记为v w文法的句型、句子的定义文法的句型、句子的定义句型句型有文法有文法G，若若S x，则称则称x是文法是文法G的句型。的句型。句子句子有文法有文法G，若若S x，且且xVVT T*，则称则称x是文是文法法G的句子。的句子。例：例：G G：S0S1，S01S 0S1 00S11 000S111 00001111例：例：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F
25、a+a*F a+a*a表示一切能用符号表示一切能用符号a，+，*，(和和)构成的算构成的算术表达式术表达式文法，语言的定义文法，语言的定义由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的一切句子的集合的一切句子的集合:L(G)=x|S x，其中其中S为文法的开始符为文法的开始符号，且号，且x VVT T*例：例：G G：S0S1，S01L(G)=0n1n|n1例例3.3 文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L（G）=anbnen|n1 S a S BE (SaSBE)a aBEBE (SaB
26、E)aabEBE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)G生成的每个串都在生成的每个串都在L(G)中中L(G)中的每个串确实能被中的每个串确实能被G生成生成已知语言描述，写出文法已知语言描述，写出文法例：若语言由例：若语言由0、1符号串组成，串中符号串组成，串中0和和1的个的个数相同，构造其文法。数相同，构造其文法。A 0B|1CB 1|1A|0BBC 0|0A|1CC已知文法，写出语言描述已知文法，写出语言描述例：例：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|a文法的等价文法的等
27、价若若L（G1）=L（G2），），则称文法则称文法G1和和G2是等价的。是等价的。如文法如文法G G1AA：A0R A0R 与与G G2SS：S0S1 S0S1 等等价价 A01 A01 S01 S01 RA1 RA1文法的类型文法的类型通过对产生式施加不同的限制，通过对产生式施加不同的限制，Chomsky将将文法分为四种类型：文法分为四种类型：0型文法：对任一产生式型文法：对任一产生式，都有都有(V(VN NVVT T)+，(V(VN NVVT T)*1 1型文法：型文法：对任一产生式对任一产生式，都有都有|，仅仅仅仅 SS除外除外2 2型文法：型文法：对任一产生式对任一产生式，都有都有VV
28、N N ，(V(VN NVVT T)*3 3型文法：型文法：任一产生式任一产生式的形式都为的形式都为AAaBaB或或AaAa，其中其中AVAVN N ，BVBVN N ，aVaVT T文法的类型文法的类型例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GS：SaSBESaBEEBBEaBabbBbbbEbeeEee文法的类型文法的类型例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS：S SCDCDAbAbbAbA C CaCAaCABaBaaBaB C CbCBbCBBbBbbBbBADADaDaD C CBDBDbDbD D DAaAabDbDL(G)
29、=L(G)=wwww|w|wa,ba,b*文法的类型文法的类型例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SaBaB|bAbAAa|a|aSaS|bAAbAABb|b|bSbS|aBBaBB 文法文法GS：S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0文法的类型文法的类型例：定义标识符的例：定义标识符的3 3型（正规）文法型（正规）文法 文法文法GI：I lT lTI l lT lTlTT dT dTT l lT d d文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（
30、型文法或上下文有关文法（CSG ）产生的语产生的语言称为言称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）2 2型文法或上下文无关文法（型文法或上下文无关文法（CFL ）产生的语产生的语言称为言称为2型语言型语言或上下文无关或上下文无关语言（语言（CF L）3 3型文法或正则（正规）文法（型文法或正则（正规）文法（RG）产生的语产生的语言称为言称为3型语言型语言正则（正规）正则（正规）语言（语言（RL）文法和识别系统文法和识别系统0型文法（短语文法）的能力相当于图灵型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且机，可以表征任何递归可枚举集，而且任何任何0
31、型语言都是递归可枚举的型语言都是递归可枚举的1型文法（上下文有关文法）：产生式的型文法（上下文有关文法）：产生式的形式为形式为1 1AA2 21 12 2，即只有即只有A A出现出现在在1 1和和2 2的上下文中时，才允许的上下文中时，才允许取代取代A A。其识别系统是线性界限自动机。其识别系统是线性界限自动机。文法的类型文法的类型2型文法（上下文无关文法、型文法（上下文无关文法、CFG）：）：产产生式的形式为生式的形式为AA，取代取代A A时与时与A A的上的上下文无关。其识别系统是不确定的下推下文无关。其识别系统是不确定的下推自动机。自动机。3型文法（正规文法、右线性文法）：产型文法（正规
32、文法、右线性文法）：产生的语言是有穷自动机（生的语言是有穷自动机（FA）所接受的所接受的集合集合上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法有足够的能力描述现今上下文无关文法有足够的能力描述现今程序设计语言的语法结构程序设计语言的语法结构算术表达式算术表达式语句语句赋值语句赋值语句条件语句条件语句读语句读语句算术表达式算术表达式上下文无关文法表上下文无关文法表示示文法文法G=(E,G=(E,+,*,+,*,I,(,),P,EI,(,),P,E P:P:E E i iE E+EE E+EE E*EE E*EE (E)E (E)条件语句条件语句上下文无关文法表示上下文无关文法表示
33、 ifif thenthen|ifif thenthen else else 上下文无关文法的语法树上下文无关文法的语法树用于描述上下文无关文法的用于描述上下文无关文法的句型推导句型推导的的直观方法直观方法 例例:GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的语法树（推导树）的语法树（推导树）叶子结点：树中没有子孙的结点。叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型为推导树的结果。也把该推导树称为该句型的语法树。型的语法树。上下文无关文
34、法的语法树上下文无关文法的语法树给定文法给定文法G，对于对于G的任何句型都能构造与的任何句型都能构造与之关联的语法树（推导树）。这棵树满足之关联的语法树（推导树）。这棵树满足下列下列4个条件：个条件：1、每个结点都有一个、每个结点都有一个V中的符号作标记中的符号作标记2、根的标记是开始符号、根的标记是开始符号S3、若一结点若一结点n至少有一个它自己除外的子孙，并至少有一个它自己除外的子孙，并且且n有标记有标记A，则则AVVN N4、如果结点如果结点n的直接子孙，从左到右的次序是结的直接子孙，从左到右的次序是结点点n1,n2,nk，其标记分别为其标记分别为A1,A2,Ak，那那么么AA1A2,A
35、k一定是一定是P中的一个产生式中的一个产生式上下文无关文法的语法树上下文无关文法的语法树推导过程中施用产生式的推导过程中施用产生式的顺序顺序 例例:GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步，其中其中、是句型，都是对是句型，都是对中中的最左（右）非终结符进行替换的最左（右）非终结符进行替换最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型问题：一个句型是否对应唯一的一棵语问题：一个句型是否对应唯一的一棵语法树？法树？例：例：GE:GE:E E i iE E+EE E+EE E*EE E*EE (E)E (E)E E E+E E+E E*E i E*E i i i i i E E E*E E*E i E+E i E+E i i i i句型句型 i*i+i 的两个不同的最左推导：的两个不同的最左推导：推导推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导推导2：E E*E i*E i*E+E i*i+E i*i+i
