程序设计语言与编译原理-第四章程序语言的设计课件.ppt

1、程序设计语言与编译 第第2章和第章和第3章分别讨论了程序设计章分别讨论了程序设计语言的语言的数据类型数据类型和和控制结构控制结构，分别描述程序的分别描述程序的数据结构数据结构和和算法算法。本章介绍本章介绍语言的设计方法语言的设计方法。程序设计语言与编译 主要内容主要内容1.1.语言的定义语言的定义语法：定义语言是否合法的一组规则语法：定义语言是否合法的一组规则语义：用以规定程序或其成分的含义语义：用以规定程序或其成分的含义2.2.文法：定义语言语法的形式化规则文法：定义语言语法的形式化规则3.3.语言的设计语言的设计2 2程序设计语言与编译3 34.1 4.1 程序语言的定义程序语言的定义u语

2、言定义是语言实现的基础：语言定义是语言实现的基础：u从语言用户角度看从语言用户角度看语言初等成分的实际含义是什么？语言初等成分的实际含义是什么？如何有意义地使用它们？如何有意义地使用它们？怎样以有意义的方式组合它们？怎样以有意义的方式组合它们？u从编译程序设计者角度看从编译程序设计者角度看哪些构造允许出现哪些构造允许出现即使一时不能看出某种构造的实际应用，或者判断实现该结即使一时不能看出某种构造的实际应用，或者判断实现该结构会导致严重的困难，但仍必须严格根据语言的定义实现它构会导致严重的困难，但仍必须严格根据语言的定义实现它程序设计语言程序设计语言是用来描述计算机所执行的算法的形式表示；程序设

3、计语言与编译4 4一个程序语言是一个一个程序语言是一个记号系统记号系统程序语言由两方面定义：程序语言由两方面定义：语法语法语义语义语用语用语言语法语义语言语法语义语法语法:用以构造程序及其成分的一组规则的集合用以构造程序及其成分的一组规则的集合语义语义:用以规定语法正确的程序或其成分的含义的一组规用以规定语法正确的程序或其成分的含义的一组规 则的集合则的集合语用分析语用分析:是对自然真实语言经过语法分析，语义分析后，是对自然真实语言经过语法分析，语义分析后，更高级的语言学分析。更高级的语言学分析。程序设计语言与编译5 51.语语 法法程序本质上是一定字符集上的字符串。程序本质上是一定字符集上的

4、字符串。语法语法：一组规则：一组规则，用它可以形成和产生一用它可以形成和产生一个个合式合式(well-formed)的程序的程序。其中，其中，0.5、x1、等称等称单词符号单词符号，而表达，而表达式称语言的一个式称语言的一个语法范畴语法范畴或或语法单位语法单位。例：字符串例：字符串 0.5 x1+c程序设计语言与编译6 6u词法规则词法规则：单词符号的形成规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、一般包括：常数、标识符、基本字、算符、界符等。界符等。描述工具：有限自动机描述工具：有限自动机u

5、语法规则语法规则：语法单位的形成规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、语法单位通常包括：表达式、语句、分程序、过程、函数、程序等过程、函数、程序等;描述工具：上下文无关文法描述工具：上下文无关文法本课程中，有限自动机和上下文无关文本课程中，有限自动机和上下文无关文法是词法分析和语法分析的主要理论基础。法是词法分析和语法分析的主要理论基础。程序设计语言与编译7 72.语语 义义语义语义：一组规则：一组规则，用它可以定义一个程用它可以定义一个程序的意义序的意义。描述方法：描述方法：自然语言描述：隐藏错误、二义性和不完整自然语言描述：隐藏错误、二义性和不完整性性形式描述：

6、形式描述：F 操作语义操作语义(PL/1)(PL/1)F 指称语义指称语义(ADA)(ADA)F 代数语义代数语义(PASCAL)(PASCAL)程序设计语言与编译8 8u程序语言的基本功能：描述数据和对数据程序语言的基本功能：描述数据和对数据的运算。的运算。u所谓程序，本质上说是描述一定数据的处所谓程序，本质上说是描述一定数据的处理过程。理过程。程序设计语言与编译9 9程序程序子程序或分程序子程序或分程序语句语句表达式表达式数据引用数据引用算符算符函数调用函数调用自上而下：自上而下：每一层由其每一层由其下层部分组下层部分组成。成。自 下 而 上：自 下 而 上：通过对下层成通过对下层成分的理

7、解来掌分的理解来掌握上层成分，握上层成分，从而掌握整个从而掌握整个程序。程序。程序设计语言与编译 字字 母母 表表:语言允许使用字符的集合,其元素称为字符 符符 号号:由字符组成的有限串（字符串）字字 汇汇 表表:由符号组成的集合，其元素称为字 词法规则词法规则:规定什么样的字符串可以构成语言的有效符号 语法规则语法规则:确定一个符号序列是否为一个句子,并提供句子的结构（什么样的符号序列是合法的）一一.语法语法1.1.几个术语几个术语 1010程序设计语言与编译u语言的定义可以从语言的定义可以从生成生成（文法）（文法）和和识别识别（语法图）的观点进行。（语法图）的观点进行。程序设计语言与编译2

8、.2.生成的观点生成的观点 一个简单英语句子的描述一个简单英语句子的描述 I/Students Study/Run如何描述？如何描述？I|StudentsStudy|Run每一行称为一条每一行称为一条；终结符、非终结符终结符、非终结符注意：注意：描述以上规则的符号系统称为巴科斯描述以上规则的符号系统称为巴科斯-诺诺尔范式，即通常的尔范式，即通常的BNFBNF（Backus-Naur FormBackus-Naur Form）。）。1212程序设计语言与编译 文法文法在形式语言中，上述例子可写成文法G=(N,T,P,S)其中=,=I,students,study,run=,I|Students,

9、Study|Run=语言语言:所有句子的集合所有句子的集合 标识符和表达式描述标识符和表达式描述1313程序设计语言与编译 A|Z|a|zA|Z|a|z 0|90|91414程序设计语言与编译 ()+|-|+|-|*|/|/1515程序设计语言与编译3.3.识别的观点：识别的观点：语法图语法图每一非终结符N连同相应的产生式对应一个语法图；具体对应如下：终结符终结符x x对应于对应于x非终结符非终结符N N对应于对应于N 定义定义1616程序设计语言与编译 b b1 1 b b2 2 b bm m g g b b b b1 1b b2 2b bm m bb|g gNN 1 1|2 2|n n 2

10、 2n n1 1 1717程序设计语言与编译 标识符标识符表达式表达式运算符运算符()表达式表达式表达式表达式字母字母字母字母数字数字+-*/字母字母字母字母数字数字表达式表达式()表达式表达式+表达式表达式-*/1818程序设计语言与编译 若一个终结符序列是合法的，那么,必须从语法图的入口边通过语法图而到达出口边，而且在通过的过程中,恰恰能识别该终结符序列。具体如下：终结符框:标识的终结符与被识别的终结符刚好符合标识的终结符与被识别的终结符刚好符合非终结符框:由该非终结符的语法图来识别；由该非终结符的语法图来识别；分支:若遇到分支，则任选一分支来识别；若遇到分支，则任选一分支来识别；回溯:若

11、一个分支识别不成功，则选另一分支来识别若一个分支识别不成功，则选另一分支来识别 语言语言 识别原则识别原则语法图能识别的所有终结符序列的集合1919程序设计语言与编译uFORTRAN采用采用自然语言自然语言描述语法；描述语法；uALGOL 60首次首次用用BNF对语法进行对语法进行形式描述形式描述,为语言定义做出了重要贡献；为语言定义做出了重要贡献；uPascal首次首次采用采用语法图语法图来定义语言，来定义语言，给出了较为直观的语法结构。给出了较为直观的语法结构。程序设计语言与编译 文法文法和和语法图语法图是语言语法的是语言语法的等价等价表示表示 文法从文法从产生产生的观点来定义语言的语法，

12、的观点来定义语言的语法，更通用、更准确。更通用、更准确。语法图以语法图以识别识别的观点定义语言的语法，的观点定义语言的语法，更直观、更清晰。更直观、更清晰。程序设计语言与编译 采用采用生成生成的方法还是采用的方法还是采用识别识别的方的方法来定义语言法来定义语言 由语言的设计者确定。由语言的设计者确定。程序设计语言与编译表达语言表达语言设计者设计者的意图和设计目标的意图和设计目标;指导语言的指导语言的使用者使用者如何写一个正确的程序；如何写一个正确的程序；指导语言的指导语言的实现者实现者如何编写一个语法检查程如何编写一个语法检查程序来识别所有合法的程序。序来识别所有合法的程序。4.4.语法描述的

13、基本用途语法描述的基本用途 2323程序设计语言与编译二二.语义语义例：大象吃花生例：大象吃花生 Elephants eat peanutsElephants eat peanuts1.1.何谓语义何谓语义定义语言合法句子的含义，即句子的作用和意义。定义语言合法句子的含义，即句子的作用和意义。例：例：if(ab)max=a;else max=bif(ab)max=a;else max=b2.2.语义的描述：语义的描述：GAMGAM指令指针指令指针+代码存储器代码存储器C+C+数据存储器数据存储器D D 2424程序设计语言与编译语言的语义规则定义语言合法句子的含义。例如，C语言的语义帮助理解语

14、句 if(ab)maxa else maxb；必须先计算关系表达式ab的值，然后按照所得值决定计算maxa或maxb。*语法规则告诉我们如何形成这个语句，语义规则告诉我们这个语句的作用和意义是什么。程序设计语言与编译 文法文法和和语法图语法图已成为已成为语法语法描述的典描述的典型工具，但型工具，但语义语义描述至今描述至今尚无尚无人们普人们普遍接受的典型描述工具。遍接受的典型描述工具。许多语言仍采用许多语言仍采用自然语言自然语言描述描述语义语义。程序设计语言与编译u本章的本章的语言设计语言设计，采用自然语言来，采用自然语言来描述语义。描述语义。u(下篇的下篇的)语言实现涉及到的语义，将语言实现涉

15、及到的语义，将以以操作语义学操作语义学的方法来描述。的方法来描述。程序设计语言与编译操作语义学的方法以一个抽象机(Abstract Machine)的行为来描述语言的各个结构的作用和含义。抽象机不是实际机器,它能简单地表示程序设计语言运行时的需要，并非要实际有效地执行。实际上，在实际机器上实现时，仅需实现与抽象机同样的作用，但必须给出实际机器的具体限制和结构，因此，应当将语言的语义问题和实现问题分开。程序设计语言与编译u即以一个即以一个抽象机抽象机的的行为行为来来描述语言描述语言的各个结构的作用和意义。的各个结构的作用和意义。uGAM抽象机的组成：抽象机的组成：存储器、控制器、处理器，指令指针

16、存储器、控制器、处理器，指令指针ip。存储器分为代码区和数据区存储器分为代码区和数据区程序设计语言与编译 ipip存储可执行的指令代码存储可执行的指令代码存放程序中被操纵的数据存放程序中被操纵的数据指令指针指令指针3030程序设计语言与编译程序设计语言与编译(l)l)执行执行 ip ip 所指向的所指向的指令指令；(2)(2)修改修改 ip ip 的内容的内容；若所执行的指令已修改过若所执行的指令已修改过ipip，则不再修改，则不再修改ipip(显然刚执行的指令是一条转移指令显然刚执行的指令是一条转移指令)。执行的。执行的指令未修改指令未修改ipip，那么修改，那么修改ipip使之指向下一条指

17、令，使之指向下一条指令，即即ipip:=ip+1,:=ip+1,使之指向下一条指令使之指向下一条指令(3)(3)若若 ip ip 指向特殊的指向特殊的STOPSTOP指令，则终指令，则终止执行，否则转回止执行，否则转回执行执行(1)(1)。程序设计语言与编译u假设假设 GAM GAM 对各种程序设计语言所常对各种程序设计语言所常用的运算符用的运算符 如如 ，-，*,/,/,=,=等等 都有相应的都有相应的指令指令与之对应。与之对应。程序设计语言与编译 以以GAMGAM的的操作行为操作行为来定义语言的语来定义语言的语义，是基于已经义，是基于已经“理解理解”GAMGAM的语义的语义 因此，一旦用因

18、此，一旦用 GAM GAM 的操作行为来的操作行为来定义语言结构的作用时，就知道了语定义语言结构的作用时，就知道了语言的意义。言的意义。程序设计语言与编译uGAMGAM应该是一个应该是一个简单简单的的模型工具模型工具。u为了成功地应用这种方法，为了成功地应用这种方法，GAMGAM自身自身的语义应尽可能地简单，的语义应尽可能地简单，u以便把问题集中到语言的语义上，以便把问题集中到语言的语义上，而不是抽象机自身的复杂性上。而不是抽象机自身的复杂性上。程序设计语言与编译u文法自从乔姆斯基文法自从乔姆斯基(ChomskyChomsky)于于1956 1956 年建立语言的形式描述以来，形式年建立语言的

19、形式描述以来，形式语言的理论发展很快。语言的理论发展很快。u该理论对计算机科学，特别是对该理论对计算机科学，特别是对程程序语言的设计、编译方法、计算复序语言的设计、编译方法、计算复杂性杂性等方面，产生了深刻影响。等方面，产生了深刻影响。程序设计语言与编译 同时，它还促进了计算机科学的理同时，它还促进了计算机科学的理论研究工作，并取得了不少的成果。论研究工作，并取得了不少的成果。计算机的理论工作走在计算机发展计算机的理论工作走在计算机发展的前面。的前面。但随着计算机及其应用的迅速发展，但随着计算机及其应用的迅速发展，今天的今天的理论工作理论工作远远落后了。远远落后了。程序设计语言与编译 基本概念

20、基本概念例句：例句：int i=0;int i=0;包含字母包含字母i,n,t,=,0,;,i,n,t,=,0,;,所有字母形成字母表；所有字母形成字母表；符号串，如符号串，如intint定义定义1 1 字母表字母表：字母表：字母表是符号元素的非空有限集合。是符号元素的非空有限集合。定义定义2 2 符号符号（字符）：字母表中的元素。（字符）：字母表中的元素。定义定义3 3 符号串符号串（字符串）：字母表中的符号所组成的任何（字符串）：字母表中的符号所组成的任何有穷有穷序列。序列。如字母表如字母表=a,b=a,b，则，则a,ba,b是字母表是字母表中的元素，中的元素，a,b,aa,ab,a,b,

21、aa,ab,都是符号串。都是符号串。空符号串空符号串：不含任何符号的符号串，用：不含任何符号的符号串，用 表示。表示。字母表，符号，符号串字母表，符号，符号串程序设计语言与编译基本概念基本概念o定义定义4 4 符号串符号串x x和和y y的的连接连接：指：指x x和和y y的符号按的符号按先后先后顺序排列顺序排列在一起组成的新的符号串，用在一起组成的新的符号串，用xyxy表示。表示。例：若例：若=a,b,x=ab,y=ba,=a,b,x=ab,y=ba,则则xy=abba,yx=baabxy=abba,yx=baab。注意：（注意：（1 1）xyyxxyyx；（2 2）x=x=xx=x=x。o

22、定义定义5 5 符号串的长度符号串的长度：指符号串中符号的个数。：指符号串中符号的个数。例：例：|ab|=2,|aabb|=4,|=0|ab|=2,|aabb|=4,|=0。字符串连接、字符串长度字符串连接、字符串长度程序设计语言与编译基本概念基本概念o定义定义6 符号串的符号串的前缀前缀和和后缀后缀：分别指符号串的左部和右部任意字符：分别指符号串的左部和右部任意字符串。串。例：例：ab的前缀有的前缀有、a、ab；后缀有；后缀有、b、ab。o定义定义7 符号串集合的符号串集合的乘积乘积：设：设A、B是字母表是字母表上的符上的符号串集合，则定义号串集合，则定义A与与B的乘积：的乘积：AB=xy|

23、xA，yB。o例：设例：设=a，b，c，d，令，令A=aa,bb，B=cc,dd,则则AB=aacc,aadd,bbcc,bbdd,BA=ccaa,ccbb,ddaa,ddbb。显然。显然ABBA定义定义空集合空集合：=，有，有A=A=A。前缀、后缀、乘积前缀、后缀、乘积程序设计语言与编译基本概念基本概念o定义定义8 符号串的符号串的方幂方幂：设：设x是符号串，则：是符号串，则：x0=,x1=x,x2=xx,xn=xx(n个个)o定义定义9 符号串集合符号串集合A的的方幂方幂：A0=,A1=A,A2=AA,An=AA(n个个A)oA的的正闭包正闭包：A+=A1A2oA的的闭包闭包：A*=A0A

24、1A2o显然：显然：A*=A0A+,A+=AA*o问题问题：A=0,1,则则A+表示的集合意义？表示的集合意义？方幂、正闭包、闭包方幂、正闭包、闭包程序设计语言与编译o什么是文法什么是文法n文法是定义或描述语法结构的一组形式规则，是规文法是定义或描述语法结构的一组形式规则，是规则的非空有穷集合则的非空有穷集合n规则又称为重写规则，产生式或生成式，每个产生规则又称为重写规则，产生式或生成式，每个产生式为式为 或或 :=:=，是某字母表是某字母表A A的正闭包的正闭包A A+的一的一个符号称为规则的左部；个符号称为规则的左部；是是A A*中的一个符号，称中的一个符号，称为规则的右部。为规则的右部。

25、文法文法程序设计语言与编译o什么是文法什么是文法n文法是定义或描述语法结构一组形式规则，是规则的非空又穷集合文法是定义或描述语法结构一组形式规则，是规则的非空又穷集合n规则又称为重写规则，产生式或生成式，每个产生式为规则又称为重写规则，产生式或生成式，每个产生式为 或或 :=:=，是某字母表是某字母表A A的正闭包的正闭包A A+的一个符号称为规则的左部；的一个符号称为规则的左部；是是A A*中中的一个符号，称为规则的右部。的一个符号，称为规则的右部。n 与与 的区别？的区别？例句：例句：He gave me a book.He gave me a book.英语中的基本语法规则：英语中的基本

26、语法规则：|He He|me|me book book gave gave a|an|the a|an|the例句：例句：He gave me a book.He gave me a book.根据上述语法规则对例句进行分析，可推出该例句。根据上述语法规则对例句进行分析，可推出该例句。=He He =He He =He gave He gave =He gave He gave =He gave me He gave me =He gave me He gave me =He gave me a He gave me a =He gave me a book =He gave me a boo

27、k文法文法程序设计语言与编译int i=0;int i=0;i=i+1;i=i+1;+|=+=(a|z|A|Z|_)(a|z|A|Z|_|0|9)(a|z|A|Z|_)(a|z|A|Z|_|0|9)int|char|int|char|文法包含的要素：文法包含的要素：终极字符集：终极字符集：如如int iint i非终非终极极字符集：字符集：如如 、产生式：产生式：如如 +开始符号：开始符号：文法文法程序设计语言与编译一一.文法的定义文法的定义文法是描述语言的文法是描述语言的语法结构语法结构的形式规则的形式规则,必须准确必须准确,易于理解易于理解,且描述能力强。且描述能力强。文法G定义成一个四元

28、式：其中是非终结符的集合；是终结符的集合；是开始符号；是的非空有限集 4545o例例 G=(N,0,1,N0N,N1N,N0,N1,N)，其中：，其中：VN=N;VT=0,1;P=N0N,N1N,N0,N1;S=N。程序设计语言与编译表达式表达式 项项|表达式表达式+项项项项 因子因子|项项*因子因子因子因子 (表达式表达式)|i无二义文法：无二义文法：G(E)：E T|E+T T F|T*F F (E)|iG G0 0=(V=(VT T,V,VN N,S,P,S,P）：）：EE+T|T EE+T|T TT TT*F|FF|F F(E)|I F(E)|I显然显然 V VT T=+,=+,*,(

29、,),(,),i i V VN N=E,T,F=E,T,FS=ES=EP P为上述产生式的集合为上述产生式的集合程序设计语言与编译说明:b的读法,其中 V*VNV*,b V*，VVT VN b1 b2 .bn 约定：用英文大写字母表示非终结符；小写字母表示终结符；希腊小写字母表示串缩写为缩写为 b b1|1|b b2|2|b bn n 4747程序设计语言与编译uChomsky于于1956年建立形式语言体系，年建立形式语言体系，他把文法分成四种类型：他把文法分成四种类型：0，1，2，3型型。u与上下文无关文法一样，它们都由四部与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。

30、分组成，但对产生式的限制有所不同。程序设计语言与编译o0型文法（短语文法）型文法（短语文法）：要求每个产生式：要求每个产生式,有有V*VNV*，V*,即即 中至少含有一个非终结中至少含有一个非终结符。符。o1型文法型文法(上下文有关文法上下文有关文法)：如果对：如果对0型文法施加以下型文法施加以下的限制，就得到的限制，就得到1型文法：型文法：对除对除S外的任何产生式外的任何产生式，要求，要求1|即规则左部符号个数不超过右部符号个数，即规则左部符号个数不超过右部符号个数，S除外除外如：如：A是是1型文法的一个产生式，型文法的一个产生式，和和非空非空，则只有在，则只有在和和这样一个上下文中这样一个

31、上下文中A才能替换为才能替换为。文法分类文法分类注意：注意：如果规则左部有如果规则左部有终结符终结符，则该文法一定属于，则该文法一定属于0或或1型文法。型文法。0、1型文法的型文法的区别区别：规则左、右部的长度：规则左、右部的长度 如果文法中所有规则左部符号串长度均如果文法中所有规则左部符号串长度均小于或等于小于或等于右部符号右部符号串长度，则称为串长度，则称为1型文法，否则为型文法，否则为0型文法。型文法。程序设计语言与编译o2型文法型文法(上下文无关文法上下文无关文法)：如果对：如果对1型文法施加以下型文法施加以下的限制，就得到的限制，就得到2型文法：型文法：G的任何产生式为的任何产生式为

32、A,AVN,(VNVT)*这种文法意味着，每一规则左部只有一个非终结符，这种文法意味着，每一规则左部只有一个非终结符，无需考虑该非终结符在上下文中的出现情况。无需考虑该非终结符在上下文中的出现情况。o3型文法型文法(正则文法正则文法)：如果对如果对2型文法施加以下的限制型文法施加以下的限制，就得到，就得到3型文法：型文法：G的任何产生式为的任何产生式为AB|,或者或者AB|,其中其中 A,BVN,VT3型文法称为型文法称为右线性文法或左线性文法右线性文法或左线性文法；3型文法等价型文法等价于正规式，所以又称正规文法。于正规式，所以又称正规文法。文法分类文法分类程序设计语言与编译总结：总结：2、

33、3型文法规则左部仅为非终结符，若规则型文法规则左部仅为非终结符，若规则右部形式仅为右部形式仅为AB|,或者或者AB|（A,BVN,VT）则为）则为3型文法，否则为型文法，否则为2型文法型文法程序设计语言与编译5252四类文法的定义是逐渐增加限制的，对应的语言四类文法的定义是逐渐增加限制的，对应的语言描述能力越来越弱，描述能力越来越弱，程序设计语言与编译5353u判断一个文法时应该以什么规则来判断呢？u这个规则是：3-2-1-0.也就是说，我们判断是从高到低来判断的，一旦判断其属于正规文法之后就没必要再判断其是否属于上下文无关的了(因为它必定属于上下文无 关，我们应该以最高规则来判定其属于的文法

34、类型)，其它情况与此类推。只有当我们判断不属于3型文法时，才向下判断，其是不是属于2型的，若不属于2 型的，则依此类推再向下判断。最终的结果如果不属于3，2和1三种类型，那就只有属于0型了。程序设计语言与编译 S SaB|bAaB|bAA AaS|bAA|aaS|bAA|aB BbS|aBB|bbS|aBB|bS SbAbAA A(B|a(B|aB BaAaA2 2型文法（无关）型文法（无关）3 3型文法（正则）型文法（正则）5454程序设计语言与编译uL5=anbn|n 1 不能由正规文法产生，但可不能由正规文法产生，但可由上下文无关文法产生：由上下文无关文法产生：G5(S)：S aSb|a

35、buL6=anbncn|n 1不能由上下文无关文法产不能由上下文无关文法产生，但可由上下文有关文法产生：生，但可由上下文有关文法产生：G6(S)：S aSBC|aBC CB BC aB ab bB bb bC bc cC cc程序设计语言与编译内容回顾内容回顾语言语法语义语言语法语义语法语法1.1.生成的观点：文法生成的观点：文法2.2.识别的观点：语法图识别的观点：语法图语义语义1.1.抽象机抽象机G=(VG=(VT T,V,VN N,S,S，P)P)3.3.文法的分类文法的分类5656程序设计语言与编译直接推导直接推导:即由产生式右边替换产生式左边 推导推导:1 n、1 n归约归约:推导的

36、逆过程*+三三.文法产生的语言文法产生的语言1.1.推导与归约推导与归约5757+*归约归约0程序设计语言与编译5858u例例:G=(E,i,+,*,(,),P,E)(1.1)P：E E+E|E*E|(E)|i 表达式表达式(i)和和(i+i)*i的推导：的推导：E (E)(i)E E*E (E)*E (E+E)*E (i+E)*E(i+i)*E (i+i)*i E E 0步推导步推导 E (i+i)*i 6步推导步推导 E (i+i)*i 6步推导步推导 E (E)直接推导直接推导*程序设计语言与编译o若推导过程中，总是最先替换最右若推导过程中，总是最先替换最右(左左)的非终结符，则称的非终

37、结符，则称为为最右最右(左左)推导推导o若归约过程中，总是最先归约最右若归约过程中，总是最先归约最右(左左)的非终结符，则称的非终结符，则称为为最右最右(左左)归约归约句型的最右推导称为句型的最右推导称为规范推导规范推导，其逆过程最左规约称为，其逆过程最左规约称为规范归约规范归约。i*i+i的规范推导的规范推导规范推导、规范规约规范推导、规范规约程序设计语言与编译*2.2.句型和句子句型和句子设文法G=(VT,VN,S,P),若S,V*,则称为文法G的一个。若上述 VT，则称是一个句子，即只含终结符的句型是一个例例 文法文法GSGS：S0S1S0S1，S01S01因为因为S S 0 0S S1

38、 1 00 00S S11 11 000 000S S111 111 00001111 00001111所以所以S,S,0S1,00S11,000S111,000011110S1,00S11,000S111,00001111都是都是G G的句型的句型0000111100001111是是G G的句子的句子6060程序设计语言与编译句型句型与与句子句子的关系是？的关系是？只含终结符的句型就是一个句子。只含终结符的句型就是一个句子。一个句子是句型。一个句子是句型。一个句型不一定是句子。一个句型不一定是句子。程序设计语言与编译 文法G=(VT,VN,S,P)的句子的全体,称为由文法 G产生的语言,记为

39、L(G),即 L(G)=S 其中 VT +*3.3.文法产生的语言文法产生的语言6262要求：要求：（1）能根据文法分析其所产生的语言；）能根据文法分析其所产生的语言；（2）能根据语言构造其文法。）能根据语言构造其文法。程序设计语言与编译G2(I):ILLS STST TLD Lab.z D012.9例例1 16363根据文法分析其所产生的语言；根据文法分析其所产生的语言；程序设计语言与编译G3(S):SaSaP PbPbQ QcQcL(GL(G3 3)=a)=ai ib bj jc ck ki,j,ki,j,k 11例例2 26464程序设计语言与编译G4(S):SaSPQabQ QPPQ

40、bPbb bQbc cQcc例例3 3L(GL(G4 4)=a)=ai ib bi ic ci ii i 116565程序设计语言与编译Sai-1S(PQ)i-1 (i-1次使用第一个产生式)aibQ(PQ)i-1 (使用第二个产生式)aib(PQ)i-1Q (i-1次使用第三个产生式)aib2(QP)i-2Q2 (使用第四个产生式)aib3(QP)i-3Q3 (i-2次使用第三个产生式)aibiQi aibicQi-1 (使用第五个产生式)aibici (i-1次使用第六个产生式)*6666程序设计语言与编译例例 构造文法构造文法G，使其描述的语言为，使其描述的语言为正奇数正奇数集合。集合。

41、令令G=VN,VT,P,VT=0,1,2,3,4,5,6,7,8,9P:1|3|5|7|9|0|2|4|6|8VN=,分析分析：正奇数要求，要么是一位奇数数字，要么是以奇：正奇数要求，要么是一位奇数数字，要么是以奇数数字结尾的十进制数字。数数字结尾的十进制数字。根据语言构造文法根据语言构造文法程序设计语言与编译例：构造语言的文法例：构造语言的文法 L(G)=anbn|n0o可能的句子可能的句子：ooaboaabboaaabbboa bababSSaSbGS=(S,a,b,S根据语言构造文法根据语言构造文法程序设计语言与编译文法的重要特性文法的重要特性:用用规则描述规则描述语言语言q文法和语言的

42、关系：文法和语言的关系：文法文法G G生成的每个串都在生成的每个串都在L(G)L(G)中中L(G)L(G)中的每个串确实能被中的每个串确实能被G G生成生成文法的等价文法的等价:两个文法两个文法G G和和G,G,如果有如果有 L(G)=L(G),L(G)=L(G),则称则称G G和和GG等价等价6969程序设计语言与编译设是上下文无关文法G的一个句型,如果有S A,并且A ,则称是句型关于非终结符A的一个短语,或称是句型的一个短语。直接短语直接短语：A 句柄：句柄：一个句型的最左直接短语*+4.4.短语、句柄短语、句柄7070程序设计语言与编译例例:G(E)EE+T|T TT*F|F F(E)

43、|i求E+T*F的短语、直接短语、句柄E E E+T E+T E+TE+T*F F 因为因为E E E+T E+T且且T T T T*F F，所以所以T T*F F是关于是关于T T的短语的短语因为因为E=EE=E且且E E T+T T+T*F,F,所以所以T+TT+T*F F是关于是关于E E的短语的短语直接短语直接短语:T:T*F F句柄句柄:T:T*F F7171程序设计语言与编译例:G(E)EE+T|T TT*F|F F(E)|i求T*F+i的短语、直接短语、句柄E E E+T E+T T+T T+T T T*F+T F+T T T*F+F F+F T T*F+iF+i因为因为E=E=

44、E E且且E E T T*F+iF+i，所以，所以T T*F+iF+i是关于是关于E E的短语的短语因为因为E E T TT T且且T T T T*F F，所以所以T T*F F是关于是关于T T的短语、直接短语、句柄的短语、直接短语、句柄因为因为E E E ET T且且E E T T*F F，所以，所以T T*F F是关于是关于E E的短语的短语因为因为E E T T*F+F+T T且且T T i i，所以，所以i i是关于是关于T T的短语的短语因为因为E E T T*F+F+F F且且F F i i，所以，所以i i是关于是关于F F的短语、直接短语的短语、直接短语*7272程序设计语言

45、与编译 以图的方式表示推导过程推导树是一棵有序的标记树推导树是一棵有序的标记树 每个结点的标记是文法G的非终结符或终结符；标记为A的内部结点从左到右有子结点X1，X2，,Xn,则AX1Xn是一个产生式;5.5.语法树（推导树）语法树（推导树）7373程序设计语言与编译语法树（推导树）语法树（推导树）语法树是一种语法树是一种描述上下文无关文法句型推导描述上下文无关文法句型推导的直观方法，定义为：的直观方法，定义为：给定文法给定文法GS,对于对于G的任何句型都能构造与之关联的语法树，这棵树满足以下的任何句型都能构造与之关联的语法树，这棵树满足以下4个个条件条件:(1)每个每个节点节点都有一个都有一

46、个标记标记，此标记是，此标记是V的一个符号的一个符号(2)根的标记是根的标记是S，即文法的，即文法的标识符号标识符号(3)若一个节点若一个节点n至少有一个它自己除外的子孙至少有一个它自己除外的子孙,并且有标记并且有标记A,则则A肯定在肯定在VN中中(4)若节点若节点n的直接子孙从左到右的次序是节点的直接子孙从左到右的次序是节点n1,n2,nk,其节点分别为其节点分别为A1,A2,Ak,那么那么A A1A2Ak一定是一定是GS中的一条规则。中的一条规则。构造过程：构造过程：（1）从）从识别符号识别符号开始，向下画一个分支，表示第一个直接开始，向下画一个分支，表示第一个直接推导推导（2）再从非终结

47、符号往下画分支，表示即将进行的直接推）再从非终结符号往下画分支，表示即将进行的直接推导，如此进行下去，直到全部推导都在树上表示出来，即可导，如此进行下去，直到全部推导都在树上表示出来，即可得到语法树得到语法树程序设计语言与编译语法树（推导树）语法树（推导树）已知已知G1S:S A|S-A,A a|b|c已知已知G2S:S A|A-S,A a|b|cSS-A句子句子a-b-c的推导过程的推导过程(规范推导规范推导)：ScS-AbAa句子句子a-b-c的推导过程的推导过程(规范推导规范推导)：SSA-SA-SabAa程序设计语言与编译7676从语法分析树来识别：从语法分析树来识别：u一语法分析树的

48、一棵一语法分析树的一棵子树子树是由该树的某个结是由该树的某个结点连同它的所有子孙组成的。点连同它的所有子孙组成的。u一个子树的所有树叶结点自左至右排列起来一个子树的所有树叶结点自左至右排列起来形成一个相对于子树根的形成一个相对于子树根的短语。短语。u只有父子两代结点形成的子树的树叶结点自只有父子两代结点形成的子树的树叶结点自左至右排列起来就形成相对于子树根的左至右排列起来就形成相对于子树根的直接直接短语短语；u一个句型的一个句型的句柄句柄是这个句型所对应的语法树是这个句型所对应的语法树中最左那个构成直接短语的子树的树叶结点中最左那个构成直接短语的子树的树叶结点自左至右的排列自左至右的排列 EE

49、 +TTFi3i2i1T *FF从语法树可以看出：从语法树可以看出：i1,i2,i3,i1*i2,i1*i2+i3是句型是句型i1*i2+i3的短语的短语直接短语有：直接短语有：i1,i2,i3 句柄是：句柄是：i1ET|E+TTF|T*FFi|(E)对下述文法的的句型对下述文法的的句型i1*i2+i3的语法树如图：的语法树如图：程序设计语言与编译7777u例：下述文法的另一个句型：E+T*F+i 其短语、直接短语、句柄分别是？ET|E+TTF|T*FFi|(E)EE +TFiE +TT *F短语有：短语有：i,T*F,E+T*F,E+T*F+i直接短语有：直接短语有：i,T*F句柄是：句柄是

50、：T*F程序设计语言与编译推导树的边缘：推导树的边缘：一棵推导树所有叶结点的从左到右的连接。文法的二义性：文法的二义性：一个有两棵不同的推导树。由推导树确定短语由推导树确定短语7878程序设计语言与编译（i+i*i）E E（E E）E EE E*E EE E+i ii ii iE E（E E）E EE E+E EE Ei ii ii i*7979o若一个文法存在某个句型对应两棵不同的语法树，则称此文法是若一个文法存在某个句型对应两棵不同的语法树，则称此文法是二义性文二义性文法法。o例例2 G=(E,+,*,i,(,),P,E),其中其中P为：为：EE+E|E*E|(E)|i,则则E*E+i对应