高级语言及其语法描述1.ppt

1、第二章 高级语言及其语法描述,内容,程序语言定义 高级语言的一般特性 程序语言的语法描述,高级程序语言,高级程序语言是用来描述算法和计算机实现双重目的的。 常用的高级语言 FORTRAN数值计算 COBOL事务处理 PASCAL结构程序设计 ADA大型程序、嵌入式实时系统 PROLOG逻辑程序设计 ALGOL算法语言 C系统程序设计 与机器语言或汇编语言比较，高级语言的优点： 较接近于数学语言和工程语言，比较直观、自然和易于理解; 便于验证其正确性，易于改错; 编写效率高; 易于移植.,2.1 程序语言的定义,语言是由句子组成的集合，是由一组符号所构成的集合。 汉语-所有符合汉语语法的句子的全

2、体 英语-所有符合英语语法的句子的全体 程序设计语言-所有该语言的程序的全体 研究语言 每个句子构成的规律 每个句子的含义 每个句子和使用者的关系,2.1 程序语言的定义,语言定义是语言实现的基础。 程序语言由两方面组成： 语法 语义,2.1.1 语法,语言的语法是指用以形成和产生一个合式的程序的一组规则。规则包括词法规则和语法规则。 0.5 * X1 + C 0.5、X1、C、*和+为语言的单词符号 0.5 * X1 + C为语言的一个语法范畴（语法单位）,2.1.1 语法,词法规则确定语言的单词符号 一个程序语言只使用一个有限字符集作为字母表，词法规则规定了字母表中哪样的字符串是一个单词符

3、号。 单词符号是语言中具有独立意义的最基本结构,一般包括：常数、标识符、基本字、算符、界符等。 词法规则是指单词符号的形成规则。 描述工具：正规式和有限自动机,2.1.1 语法,语法规则是语法单位的形成规则 语法规则规定了如何从单词符号形成更大的结构（语法单位）。 语法单位：表达式、语句、分程序、函数、过程和程序等。 描述工具：上下文无关文法 语法规则和词法规则定义了程序的的形式结构。定义语法单位的意义属于语义问题。,2.1.2 语义,语义：一组规则，用它可以定义一个程序的意义 描述方法： 自然语言描述：隐藏错误、二义性和不完整性 形式描述： 操作语义 指称语义 代数语义 语义规则：基于属性文

4、法的语法制导翻译方法,2.2 高级语言的一般特性,程序语言的基本功能：描述数据及对数据的运算。 程序是描述一定数据的处理过程。 程序的层次结构：,2.2.1 高级语言的分类,程序语言的每个组成成分都有逻辑和计算机实现两方面的意义。 高级语言从语言范型分类： 强制式语言；如C、Pascal、Ada 应用式语言；如LISP、ML 基于规则的语言；如Prolog 面向对象语言；如C+、Java,2.2.2 程序结构,FORTRAN 一个程序由一个主程序段和若干辅程序段组成。 辅程序段可以是子程序、函数段或数据块。 每个程序段有一系列的说明语句和执行语句组成。各段可以独立编译。 模块结构，没有嵌套和递

5、归。 各程序段中的名字相互独立，同一个标识符在不同的程序段中代表不同的名字。 公共区具有全局性。,2.2.2 程序结构,FORTRAN 程序结构形式：,主程序： PROGRAM MAIN END 辅程序1：SUBROUTINE SUB1 END 辅程序2： SUBROUTINE SUB2 END,2.2.2 程序结构,Pascal PASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。 一个PASCAL过程： 过程头； 说明段（由一系列的说明语句组成）； begin 执行体（由一系列的执行语句组成）； end PASCAL提供了丰富的数据类型和运算方式，它允许用户动态地申

6、请和退还存贮空间。,2.2.2 程序结构,Pascal 作用域：一个名字能被使用的区域范围称作这个名字的作用域。 允许同一个标识符在不同的过程中代表不同的名字。 名字作用域规则“最近嵌套原则” 一个在子程序B1中说明的名字X只在B1中有效（局部于B1）； 如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2对X的任何引用都是指重新说明过的这个X。,2.2.2 程序结构,Pascal 作用域说明：,program main var A, B : real; procedure P1 var B:boolean; beg

7、in end procedure P2 var A:integer; begin end begin end,A(real),B(real),B(boolean),A(integer),2.2.3 数据类型与操作,数据类型的三种要素： 用于区别这种类型的数据对象的属性； 这种类型的数据对象可以具有的值； 可以作用于这种类型的数据对象的操作。,2.2.3 数据类型与操作,一、初等数据类型 数值类型：整型、实型、复数、双精度，运算有+，-，*，/等 逻辑类型：布尔型数据，运算and,or,not等 字符类型：字符或字符串数据，符号处理 指针类型,2.2.3 数据类型与操作,标识符：由字母或数字组成

8、的以字母为开头的一个字符串。 标识符与名字两者有本质区别： 标识符是语法概念 名字有确切的意义和属性 名字： 值：单元中的内容 属性：类型和作用域 名字的性质的说明方式： 由说明语句来明确规定的 隐含说明：FORTRAN 以I,J,K,N为首的名字代表整型，否则为实型。 动态确定：走到哪里，是什么，算什么,2.2.3 数据类型与操作,二、数据结构 1、数组 逻辑上，数组是由同一类型数据所组成的某种n维矩形结构，沿着每一维的距离，称为下标。 数组可变与不可变：编译时能否确定其存贮空间的大小。 访问：给出数组名和下标值 存放方式: 按行存放,按列存放,2.2.3 数据类型与操作,二、数据结构 1、

9、数组 把数组的有关信息记录在一个“内情向量”中，每个数组的内情向量必须包括：维数，各维的上、下限，首地址，以及数组（元素）的类型。,数组元素地址计算,2.2.3 数据类型与操作,二、数据结构 2、记录 逻辑上说，记录结构由已知类型的数据组合在一起的一种结构。 record char NAME20; integer AGE; bool MARRIED; CARD1000 访问：复合名 CARDk.NAME 存储：连续存放 域的地址计算：相对于记录结构起点的相对数OFFSET。,2.2.3 数据类型与操作,二、数据结构 3、字符串、表格、栈和队列 字符串：符号处理、公式处理 表格：本质上是一种记录

10、结构 线性表：一组顺序化的记录结构 栈：一种线性表，后进先出，POP, PUSH 队列：线性表，先进先出,2.2.4 语句与控制结构,一、表达式 表达式由运算量（也称操作数，即数据引用或函数调用）和算符（操作符）组成。 形式： 中缀、前缀、后缀 X*Y -A P 表达式形成规则： （1）变量、常数是表达式； （2）若E1、E2是表达式，Q为二元运算符，则E1QE2是表达式； （3）若E为表达式，Q为一元算符，则QE是表达式； （4）若E为表达式，则（E）为表达式。,2.2.4 语句与控制结构,一、表达式 算符的优先次序 一般的规定 PASCAL：左结合A+B+C=(A+B)+C FORTRAN

11、：对于满足左、右结合的算符可任取一种，如A+B+C就可以处理成(A+B)+C，也可以处理成A+(B+C)。 注意两点： 代数性质能引用到什么程度视具体的语言不同而不同； 在数学上成立的代数性质在计算机上未必完全成立。,2.2.4 语句与控制结构,二、语句 1、赋值语句： A := B 名字左值：该名字代表的那个单元（地址）称为该名字的左值。(所代表的存贮单元的地址) 右值：一个名字的值称为该名字的右值。(所代表的存贮单元的内容),2.2.4 语句与控制结构,二、语句 2、控制语句：,2.2.4 语句与控制结构,二、语句 3、说明语句 说明语句：定义各种不同数据类型的变量或运算，定义名字的性质。

12、 4、简单句和复合句 简单句：不包含其他语句成分的基本句 复合句：句中有句的语句,2.2.5 参数传递,过程是模块程序设计的主要手段，同时也是节省程序代码和扩充语言的主要途径。 过程定义： procedure add(x,y:integer; var z:integer) begin z：=x+y; end; 过程调用 add(a,b,c);,2.2.5 参数传递,参数传递方式 一、传地址 把实在参数的地址传递给相应的形式参数 方法： 调用段预先把实在参数的地址传递到被调用段可以拿到的地方； 程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中； 过程体对形式参数的引

13、用域赋值被处理成对形式单元的间接访问。 PASCAL的变量参数方式,2.2.5 参数传递,参数传递方式 一、传地址,procedure swap (var m:integer; var n: integer); var i:integer; begin i:=m; m:=n; n:=i; end,swap(a,b) 把a,b的地址送到已知单元j1和j2中 m:=j1; n:=j2; i:=m; m:= n; n:=i;,2.2.5 参数传递,参数传递方式 二、得结果 传地址的一种变形 方法： 每个形参对应两个形式单元，第一个形式单元存放实参地址，第二个单元存放实参的值。 在过程体中对形式参数的

14、任何引用或赋值都看作对它的第二个单元的直接访问。 过程完成返回前把第二个单元的内容存放到第一个单元所指的实参单元中。 有些Fortran采用这种方式；,2.2.5 参数传递,参数传递方式 三、传值 把实在参数的值传递给相应的形式参数 方法： 调用段预先把实在参数的的值计算出来并放在被调用段可以拿到的地方； 被调用段开始工作时，首先把实参的值抄入形式参数相应的单元； 被调用段中，象引用局部数据一样引用形式单元。 PASCAL的值参数,2.2.5 参数传递,参数传递方式 四、传名 过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实参。 方法： 在进

15、入被调用段的之前不对实在参数预先进行计值，而是让过程体中每当使用到相应的形式参数时才逐次对它实行计值（或计算地址）。因此，通常把实在参数处理成一个子程序（称为参数子程序），每当过程体中使用到相应的形式参数时就调用这个子程序。,2.2.5 参数传递,参数传递方式 四、传名,PROGRAM EX var A:integer; PROCEDURE P(B:integer) var A:integer; BEGIN A:=0; B:=B+1; A:=A+B; END;,BEGIN A:=2; TA:=0; A:=A+1; TA:=TA+A; write(A); END,BEGIN A:=2; P(A)

16、; write(A); END,2.2.6 存储管理,一、静态存储分配 如果在编译时就能确定一个程序运行时所需要的全部数据空间的大小，那么在编译的时候就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项目的单元地址。,2.2.6 存储管理,二、动态存储分配 如果一个程序语言允许递归过程、可变数组(或可变长度的字符串)或可变数据结构，对于这种程序在编译时无法知道它在运行时需要多大的存储空间。它所需的数据空间的大小须待程序运行时动态地确定。 栈(stack)式法：先请求后归还，后请求先归还-适合于嵌套递归调用的语言 堆(heap)式法：不遵循“先请求后归还，后请求先归还”,2.3 程序语言

17、的语法描述,有关定义和记号 符号：可以相互区别的记号（元素）。 字母表：符号（元素）的非空有穷集合。 符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。 1.空符号串(没有符号的符号串)是上的符号串 2.若x是上的符号串，a是的元素，则xa是上的符号串 3. y是上的符号串，当且仅当它可以由1和2导出。 例如： =a,b ，a，b，aa，ab，aabba都是上的符号串,2.3 程序语言的语法描述,有关定义和记号 符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串。如：b是符号串banana的一个前缀。 符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符

18、号得到的符号串。如：nana是符号串banana的一个后缀。 符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。如:ana是符号串banana的一个子串。 对于每个符号串s， s和两者都是符号串s的前缀，后缀和子串。,2.3 程序语言的语法描述,有关定义和记号 符号串s的真前缀，真后缀，真子串：任何非空符号串 x，相应地，是s的前缀，后缀或子串，并且 s x 符号串的运算 符号串的长度：符号串中符号的个数。符号串s的长度记为|s|。 的长度为0 连接：符号串x、y的连接，是把y的符号写在x的符号之后得到的符号串xy。如 x=ab,y=cd 则 xy=abcd。有a = a 方幂：符号串

19、自身连接n次得到的符号串。 an 定义为 aaaa n个a a1=a, a2=aa则a0=,2.3 程序语言的语法描述,有关定义和记号 符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。 两个符号串集合A和B的乘积定义为 AB =xy|xA且yB 若集合A=ab,cde B = 0,1 则 AB =ab0,ab1,cde0,cde1 使用 * 表示上的一切符号串（包括）组成的集合。*称为的闭包。 上的除外的所有符号串组成的集合记为+ 。+称为的正闭包。,2.3 程序语言的语法描述,有关定义和记号 例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aa

20、b, +=a,b,aa,ab,ba,bb,aaa,aab,2.3 程序语言的语法描述,有关定义和记号 语言是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合 (字母表上的每个语言是*的一个子集)。 例如：字母表=a,b，则*=,a,b,aa,ab,ba,bb,aaa,aab, 集合ab,aabb,aaabbb,anbn, 或表示为w|w*且w=anbn,n1为字母表上的一个语言。 集合a,aa,aaa,或表示为w|w*且w=an,n1 为字母表上的一个语言。 是一个语言。 即 是一个语言。,2.3 程序语言的语法描述,语言上的有关运算 设L是（上的）

21、一个语言，M是（上的）一个语言，语言L和M的并，交，差，补是一个语言。 语言L和M的并为 LM，是一个语言：w|w is in L or is in M 如： L1 =a,b,y,z M1 =1,28,9 L1M1=a,b, y,z,1,28,9 语言L和M的连接是一个语言，记为 LM，LM=st |sL且tM 如：L1M1 =a1,b1,y1,z1,a2,b2a9z9 有L= L=L。 L的n次连接Ln= LL.L,2.3 程序语言的语法描述,语言上的有关运算 语言L的闭包记为L*， L*= L0 L1 L2 . L0= ， Ln= L Ln-1= Ln-1 L，n1 语言L的正闭包记为L+

22、，L+= L1 L2 L3 . L+= LL*= L*L，L*= L+ 如： L1 =a,b,y,z M1 =1,28,9 (L1M1)=a,b, y,z，1,28,9 (L1M1)*=, a,b, y,z，1,28,9 ，aa，1a，xyz，6789st. L1(L1M1)*=所有字母打头的字母和数字符号串,2.3 程序语言的语法描述,要进行语法分析，必须对语言的语法结构进行描述。 采用正规式和有限自动机可以描述和识别语言的单词符号； 用上下文无关文法来描述语法规则。 如果不考虑语义，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。 形式语言抽象地定义为一个数学系统。“形式”是指这

23、样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。 形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,2.3 程序语言的语法描述,如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示。 如果语言是无穷的，找出语言的有穷表示。 语言的有穷表示有两个途经： 生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。 识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）,2.3.1 文法,文法即是描述语言

24、的生成方式：语言中的每个句子可以用严格定义的规则来构造。 文法：描述语言的语法结构的形式规则 He gave me a book。 He me book a gave,2.3.1 文法,文法的定义 文法G定义为四元组(VN，VT，P，S )，其中 VN为非终结符号(或语法实体，或变量)集； VT为终结符号集； P为产生式(也称规则)的集合；VN，VT和P是非空有穷集； S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，称为文法G的字母表或字汇表 规则，也称重写规则、产生式或生成式，是形如或=的(，)

25、有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。,2.3.1 文法,文法示例 文法G1=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,2.3.1 文法,文法示例 文法G2=（VN，VT，P，S） VN =标识符，字母，数字 VT =a,b,c,x,y,z,0,1,9 P= a, z 0, 9 S=,2.3.1 文法,几点规定： “ ”也可以用“:=表示，这种表示称为巴科斯范式(BNF) P 1 P 2 P n 可缩写为 P 1|2|n 其中，“|”读成“或”，称为P的一个候选式。 表示一

26、个文法时，通常只给出开始符号和产生式，如上例，可表示为：G(E)：E i | E+E | E*E | (E),2.3.1 文法,文法的写法 1 G：SaAb Aab AaAb A 2 GS： Aab AaAb A SaSb 3 GS： Aab | aAb | SaSb,2.3.1 文法,文法的写法 元符号: = | 习惯表示 大写字母：非终结符 小写字母：终结符 S AB A Ax | y B z,2.3.1 文法,例，定义只含+，*的算术表达式的文法 G3=， 其中，P由下列产生式组成： E i E E+E E E*E E (E),定义：称A直接推出，即 A 仅当A 是一个产生式， 且， (

27、VT U VN)* 。 如果1 2 n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。或称n归约到1 。 例：对文法(1) E (E) (E+E) (i+E) (i+i),2.3.1 文法,定义：假定G是一个文法，S 是它的开始符号。如果 ，则称一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为 L(G)。,通常，用 表示：从1出发，经过一步或若干步，可以推出n。,用 表示：从1出发，经过0步或若干步，可以推出n。,所以 ： 即 或,例： (i*i+i)是文法G3的一个句子。 E (E) (E+E) (E*E+E) (i*

28、E+E) (i*i+E) (i*i+i) E，(E)，(E*E+E)，(i*i+i)是句型。 例：G： S0S1， S01 L(G)=0n1n|n1,2.3.1 文法,例：文法G1(S)： S AB A aA|a B bB|b G1(S)的语言? L(G1)=ambn|m，n0,2.3.1 文法,例： 文法GS： SaSBE SaBE EBBE aBab bBbb bEbe eEee L（G）= anbnen | n1 ,2.3.1 文法,2.3.1 文法,例：文法G2(A)： A c|Ab G2(A)的语言? L(G2)=c，cb，cbb， 以c开头，后继若干个b,2.3.1 文法,例：给出

29、产生语言为anbn|n1的文法。 G3(S)： S aSb S ab 例：给出产生语言为anbm|1nm2n的文法。 G4(S)： S aSb | aSbb S ab,2.3.1 文法,文法的等价 若L（G1）=L（G2），则称文法G1和G2是等价的。 如文法G1A： A0R A01 RA1 与G2S： S0S1 S01 等价,2.3.2 文法的类型,Chomsky(乔姆斯基)于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。 文法都由四部分组成，但对产生式的限制有所不同。,2.3.2 文法的类型,通过对产生式施加不同的限制，Chomsky将文法分为四种类型： 0型文法：对

30、任一产生式，都有(VNVT)+， (VNVT)* 1型文法：对任一产生式，都有|， 仅仅 S除外 2型文法：对任一产生式，都有VN ， (VNVT)* 3型文法：任一产生式的形式都为AaB或Aa，其中AVN ，BVN ，aVT,2.3.2 文法的类型,例：1型（上下文有关）文法 文法GS： SCDAbbA CaCABaaB CbCBBbbB ADaD C BDbD D AabD,2.3.2 文法的类型,例：2型（上下文无关）文法 文法GS：SAB ABS|0 BSA|1,2.3.2 文法的类型,例： 3型（正规）文法 GS： S0A|1B|0 A0A|1B|0S B1B|1|0 GI：I lT

31、 I l T lT T dT T l T d,2.3.2 文法的类型,四种文法之间的逐级“包含”关系,L5=anbn|n1 不能由正规文法产生，但可由上下文无关文法产生： G5(S)： S aSb| ab L6=anbncn|n1不能由上下文无关文法产生，但可由上下文有关文法产生： G6(S)： S aSBC| aBC CB BC aB ab bB bb bC bc cC cc,程序设计语言不是上下文无关语言，甚至不是上下文有关语言。 L7= c| (a|b)*不能由上下文无关文法产生，也不可由上下文有关文法产生。 标识符引用 过程调用过程中，形-实参数地对应性(如个数，顺序和类型一致性) 有

32、的语言甚至连上下文有关文法也不能产生，只能由0型文法产生。但是现今程序设计语言的语言结构，用上下文无关文法描述就足够了。,2.3.2 文法的类型,文法和语言 0型文法产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CFL ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ） 四种文法之间的关系是将产生式做进一步限制而定义的。 语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不

33、是正则语言的上下文无关语言。,2.3.2 文法的类型,文法和语言 0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。,2.3.2 文法的类型,文法和语言 2型文法（上下文无关文法CFG）：产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。 3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合,2.3.3 上下文无关文法,上下文无关文法(CFG)的定义： 一个上下文无关文法

34、G是一个四元式G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT VN= S：文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为 P， PVN， (VT VN)* 开始符S至少必须在某个产生式的左部出现一次。 上下文无关文法有足够的能力描述程序设计语言的语法结构,2.3.3 上下文无关文法,例：文法G=(E,+,*,i,(,), P, E )其中P为： Ei , EE+E , EE*E , E(E) E表示算术表达式, i表示程序的“变量”，该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构，即： 变量是算术表达式；若E1和E

35、2是算术表达式，则E1+ E2，E1*E2和(E1)也是算术表达式 描述一种简单赋值语句的产生式： 赋值语句i=E 描述条件语句的产生式： 条件语句if条件then语句 if条件then语句else语句,2.3.3 上下文无关文法,句型、推导 GE： EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,规范推导 规范句型 从一个句型到另一个句型

36、的推导往往不唯一。 E+Ei+Ei+i E+EE+ii+i 最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型,2.3.3 上下文无关文法,2.3.4 语法树,设G=( VN,VT,P,S)为一CFG，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）： 1. 每个结点都有一个标记，此标记是V的一个符号 2. 根的标记是S 3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN 4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1

37、，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式 语法树的结果： 从左到右读出叶子的标记而构成的行谓之,2.3.4 语法树,构造语法树 GE： EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,E E E + T E + T T E E + T T F,2.3.4 语法树,语法树-句型推导的直观表示 给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树) 定理： G为上下文无关文法， 对于，有S ，当且仅当 文法G有以为结果的一棵语法树(推导树),2.3.4 语法树,语法树用一张图

38、表示一个句型的推导。 例：（i*i+i)的语法树,E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i),E (E) (E+E) (E+i) (E*E+i) (E*i+i) (i*i+i),一棵语法树是不同推导过程的共性抽象。,2.3.4 语法树,上下文无关文法的语法树的用处,用于描述上下文无关文法句型推导的直观方法,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记连接成的文法符号串，为GS的句型。也把该推导树称为该句

39、型的语法树。,上下文无关文法的语法树,推导过程中施用产生式的顺序,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,2.3.5 二义文法,如果使用最左(右)推导，则一个最左(右)推导与语法树一一对应。 一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。 但是，一个句型是否只对应唯一的一棵语法树呢？一个句型是否只有唯一的一个最左(最右)推导呢？,2.3.5 二义文法,例：GE:E i E E+E E E*E E (E),E E + E E * E i i i,E E * E i E + E i i,句型 i*i+i 的两个不