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

第四章程序语言的设计第2章和第3章分别讨论了程序设计语言的数据类型和控制结构，分别描述程序的数据结构和算法。本章介绍语言的设计方法。第四章程序语言的设计第2章和第3章分别讨论了程序

主要内容1.语言的定义语法：定义语言是否合法的一组规则语义：用以规定程序或其成分的含义2.文法：定义语言语法的形式化规则3.语言的设计2主要内容23§4.1程序语言的定义语言定义是语言实现的基础：从语言用户角度看语言初等成分的实际含义是什么？如何有意义地使用它们？怎样以有意义的方式组合它们？从编译程序设计者角度看哪些构造允许出现即使一时不能看出某种构造的实际应用，或者判断实现该结构会导致严重的困难，但仍必须严格根据语言的定义实现它程序设计语言是用来描述计算机所执行的算法的形式表示；3§4.1程序语言的定义语言定义是语言实现的基础：程序设计4一个程序语言是一个记号系统程序语言由两方面定义：语法语义语用语言＝语法＋语义语法:用以构造程序及其成分的一组规则的集合语义:用以规定语法正确的程序或其成分的含义的一组规

则的集合语用分析:是对自然真实语言经过语法分析，语义分析后，更高级的语言学分析。4一个程序语言是一个记号系统程序语言由两方面定义：语言＝语法51.语法程序本质上是一定字符集上的字符串。语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序。其中，0.5、x1、等称单词符号，而表达式称语言的一个语法范畴或语法单位。例：字符串0.5x1+c51.语法程序本质上是一定字符集上的字符串。其中，0.56语法词法规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。描述工具：有限自动机语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;描述工具：上下文无关文法本课程中，有限自动机和上下文无关文法是词法分析和语法分析的主要理论基础。6语法词法规则：单词符号的形成规则。本课程中，有限自动机72.语义语义：一组规则，用它可以定义一个程序的意义。描述方法：自然语言描述：隐藏错误、二义性和不完整性形式描述：操作语义(PL/1)

指称语义(ADA)

代数语义(PASCAL)72.语义语义：一组规则，用它可以定义一个程序的意义。8程序语言的基本功能和层次结构程序语言的基本功能：描述数据和对数据的运算。所谓程序，本质上说是描述一定数据的处理过程。8程序语言的基本功能和层次结构程序语言的基本功能：描述数据和9程序子程序或分程序语句表达式数据引用算符函数调用自上而下：每一层由其下层部分组成。自下而上：

通过对下层成分的理解来掌握上层成分，从而掌握整个程序。9程序子程序或分程序语句表达式数据引用算符函数调用自上而下：

①字母表:语言允许使用字符的集合,其元素称为字符

②符号:由字符组成的有限串（字符串）

③字汇表:由符号组成的集合，其元素称为字

④词法规则:规定什么样的字符串可以构成语言的有效符号

⑤语法规则:确定一个符号序列是否为一个句子,并提供句子的结构（什么样的符号序列是合法的）一.语法1.几个术语

10①字母表:语言允许使用字符的集合,其元素称为字符一.语言的定义语言的定义可以从生成（文法）和识别（语法图）的观点进行。语言的定义语言的定义可以从生成（文法）和识别（语法图）的观点2.生成的观点①一个简单英语句子的描述

I/StudentsStudy/Run如何描述？<语句>→<主语><谓语><主语>→I|Students<谓语>→Study|Run每一行称为一条语法规则；终结符、非终结符注意：描述以上规则的符号系统称为巴科斯-诺尔范式，即通常的BNF（Backus-NaurForm）。

122.生成的观点①一个简单英语句子的描述如何描述？<语句>→

②文法在形式语言中，上述例子可写成文法G=(N,T,P,S)其中N={<语句>,<主语>,<谓语>}T={I,students,study,run}P={<语句>→<主语><谓语>,<主语>→I|Students,<谓语>→Study|Run}S=<语句>③语言:所有句子的集合④标识符和表达式描述13②文法在形式语言中，上述例子可写成文法③语言:所有句子标识符

<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→A|…|Z|a|…|z<数字>→0|…|914标识符<标识符>→<字母>14表达式

<表达式>→<标识符><表达式>→(<表达式>)<表达式>→<表达式><运算符><表达式><运算符>→+|-|*|/15表达式<表达式>→<标识符>153.识别的观点：语法图每一非终结符N连同相应的产生式N→a1|a2|…|an对应一个语法图；具体对应如下：终结符x对应于x非终结符N对应于N

①定义163.识别的观点：语法图每一非终结符N连同相应的产生式终结符xb1b2bmgb→12…m

→|N→1|2|…|n2n1

17b1b2bmgb→12…m

N→1|

表达式标识符表达式运算符()表达式表达式字母字母数字标识符+-*/运算符字母字母数字表达式()表达式+表达式-*/表达式语法图的一些例子18表达式标识符表达式运算符()表达式表达式字母字母数字标识符

若一个终结符序列是合法的，那么,必须从语法图的入口边通过语法图而到达出口边，而且在通过的过程中,恰恰能识别该终结符序列。具体如下：终结符框:标识的终结符与被识别的终结符刚好符合非终结符框:由该非终结符的语法图来识别；分支:若遇到分支，则任选一分支来识别；回溯:若一个分支识别不成功，则选另一分支来识别③语言②识别原则语法图能识别的所有终结符序列的集合19若一个终结符序列是合法的，那么,必须从语法图的入口边通过语高级语言语法规则的描述方法FORTRAN采用自然语言描述语法；ALGOL

60首次用BNF对语法进行形式描述,为语言定义做出了重要贡献；Pascal首次采用语法图来定义语言，给出了较为直观的语法结构。高级语言语法规则的描述方法FORTRAN采用自然语言描述语法语法描述方法等价文法和语法图是语言语法的等价表示文法从产生的观点来定义语言的语法，更通用、更准确。语法图以识别的观点定义语言的语法，更直观、更清晰。语法描述方法等价文法和语法图是语言语法的等价表示采用生成的方法还是采用识别的方法来定义语言由语言的设计者确定。采用生成的方法还是采用识别的方法来定义语言①表达语言设计者的意图和设计目标;②指导语言的使用者如何写一个正确的程序；③指导语言的实现者如何编写一个语法检查程序来识别所有合法的程序。4.语法描述的基本用途

23①表达语言设计者的意图和设计目标;4.语法描述的基本用途2二.语义例：大象吃花生

Elephantseatpeanuts1.何谓语义定义语言合法句子的含义，即句子的作用和意义。例：if(a>b)max=a;elsemax=b2.语义的描述：GAM指令指针+代码存储器C+数据存储器D

24二.语义例：大象吃花生1.何谓语义定义语言合法句子的含义，即

语言的语义规则定义语言合法句子的含义。例如，C语言的语义帮助理解语句

if(a>b)max＝aelsemax＝b； 必须先计算关系表达式a>b的值，然后按照所得值决定计算max＝a或max＝b。**语法规则告诉我们如何形成这个语句，语义规则告诉我们这个语句的作用和意义是什么。 语言的语义规则定义语言合法句子的含义。例如，C语言的语义帮文法和语法图已成为语法描述的典型工具，但语义描述至今尚无人们普遍接受的典型描述工具。许多语言仍采用自然语言描述语义。文法和语法图已成为语法描述的典型工具，但语义描述至今尚无本章的语言设计，采用自然语言来描述语义。(下篇的)语言实现涉及到的语义，将以操作语义学的方法来描述。本章的语言设计，采用自然语言来描述语义。

操作语义学的方法以一个抽象机(AbstractMachine)的行为来描述语言的各个结构的作用和含义。

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

ip代码存储器（C）数据存储器（D）存储可执行的指令代码存放程序中被操纵的数据指令指针30ip代码存储器（C）数据存储器（D）存储可执行的指令代码存程序设计语言与编译原理_第四章程序语言的设计课件GAM抽象机的结构(l)执行ip所指向的指令；(2)修改ip的内容；若所执行的指令已修改过ip，则不再修改ip(显然刚执行的指令是一条转移指令)。执行的指令未修改ip，那么修改ip使之指向下一条指令，即ip:=ip+1,使之指向下一条指令(3)若ip指向特殊的STOP指令，则终止执行，否则转回执行(1)。GAM抽象机的结构(l)执行ip所指向的指令；GAM抽象机的结构假设GAM对各种程序设计语言所常用的运算符如＋，-，*,/,＞,＜,>=等都有相应的指令与之对应。GAM抽象机的结构假设GAM对各种程序设计语言所常用GAM抽象机的结构以GAM的操作行为来定义语言的语义，是基于已经“理解”GAM的语义因此，一旦用GAM的操作行为来定义语言结构的作用时，就知道了语言的意义。GAM抽象机的结构以GAM的操作行为来定义语言的语GAM抽象机的结构GAM应该是一个简单的模型工具。为了成功地应用这种方法，GAM自身的语义应尽可能地简单，以便把问题集中到语言的语义上，而不是抽象机自身的复杂性上。GAM抽象机的结构GAM应该是一个简单的模型工具。文法自从乔姆斯基(Chomsky)于1956年建立语言的形式描述以来，形式语言的理论发展很快。该理论对计算机科学，特别是对程序语言的设计、编译方法、计算复杂性等方面，产生了深刻影响。第二节文法文法自从乔姆斯基(Chomsky)于1956年建立语言的形同时，它还促进了计算机科学的理论研究工作，并取得了不少的成果。计算机的理论工作走在计算机发展的前面。但随着计算机及其应用的迅速发展，今天的理论工作远远落后了。同时，它还促进了计算机科学的理论研究工作，并取得了不少

基本概念例句：inti=0;包含字母i,n,t,=,0,;,所有字母形成字母表；符号串，如int定义1字母表：字母表∑是符号元素的非空有限集合。定义2符号（字符）：字母表中的元素。定义3符号串（字符串）：字母表中的符号所组成的任何有穷序列。如字母表∑={a,b}，则a,b是字母表∑中的元素，a,b,aa,ab,…都是符号串。空符号串：不含任何符号的符号串，用ε表示。字母表，符号，符号串基本概念例句：inti=0;定义1字母表：字母表∑基本概念定义4符号串x和y的连接：指x和y的符号按先后顺序排列在一起组成的新的符号串，用xy表示。例：若∑={a,b},x=ab,y=ba,则xy=abba,yx=baab。注意：（1）xy≠yx；（2）εx=xε=x。定义5符号串的长度：指符号串中符号的个数。例：|ab|=2,|aabb|=4,|ε|=0。字符串连接、字符串长度基本概念定义4符号串x和y的连接：指x和y的符号按先后顺序基本概念定义6符号串的前缀和后缀：分别指符号串的左部和右部任意字符串。例：ab的前缀有ε、a、ab；后缀有ε、b、ab。定义7符号串集合的乘积：设A、B是字母表∑上的符号串集合，则定义A与B的乘积：AB={xy|x∈A，y∈B}。例：设∑={a，b，c，d}，令A={aa,bb}，B={cc,dd},则 AB={aacc,aadd,bbcc,bbdd}, BA={ccaa,ccbb,ddaa,ddbb}。显然AB≠BA定义空集合：Φ={ε}，有{ε}A=A{ε}=A。前缀、后缀、乘积基本概念定义6符号串的前缀和后缀：分别指符号串的左部和右部基本概念定义8符号串的方幂：设x是符号串，则：x0=ε,x1=x,x2=xx,…,xn=x…x(n个)定义9符号串集合A的方幂：A0={ε},A1=A,A2=AA,…,An=A…A(n个A)A的正闭包：A+=A1∪A2∪…A的闭包：A*=A0∪A1∪A2∪…显然：A*=A0∪A+,A+=AA*问题：A={0,1},则A+表示的集合意义？方幂、正闭包、闭包基本概念定义8符号串的方幂：设x是符号串，则：x0=ε,什么是文法文法是定义或描述语法结构的一组形式规则，是规则的非空有穷集合规则又称为重写规则，产生式或生成式，每个产生式为αβ或α::=β，α是某字母表A的正闭包A+的一个符号称为规则的左部；β是A*中的一个符号，称为规则的右部。文法什么是文法文法什么是文法文法是定义或描述语法结构一组形式规则，是规则的非空又穷集合规则又称为重写规则，产生式或生成式，每个产生式为αβ或α::=β，α是某字母表A的正闭包A+的一个符号称为规则的左部；β是A*中的一个符号，称为规则的右部。α与β的区别？例句：Hegavemeabook.英语中的基本语法规则：<句子><主语><谓语><间接宾语><直接宾语><主语><代词>|<名词><谓语><动词><间接宾语><代词><直接宾语><冠词><名词><代词>He|me<名词>book<动词>gave<冠词>a|an|the例句：Hegavemeabook.根据上述语法规则对例句进行分析，可推出该例句。<句子>=><主语><谓语><间接宾语><直接宾语>

=><代词><谓语><间接宾语><直接宾语>=>He<谓语><间接宾语><直接宾语>=>He<动词><间接宾语><直接宾语>=>Hegave<间接宾语><直接宾语>=>Hegave<代词><直接宾语>=>Hegaveme<直接宾语>=>Hegaveme<冠词><名词>=>Hegavemea<名词>=>Hegavemeabook文法什么是文法例句：Hegavemeabook.例句：Hinti=0;i=i+1;<程序>{<句子>}+<句子><声明语句>|<赋值语句>|……<声明语句><数据类型>{<变量>[=<常量>]}+<赋值语句><变量>=<表达式><变量>(a|…|z|A|…|Z|_)(a|…|z|A|…|Z|_|0|…|9)<数据类型>int|char|………文法包含的要素：终极字符集：如inti非终极字符集：如<程序>、<句子>产生式：如<程序>{<句子>}+开始符号：<程序>文法inti=0;文法一.文法的定义文法是描述语言的语法结构的形式规则,必须准确,易于理解,且描述能力强。文法G定义成一个四元式：

G=(VT,VN,S,P)其中VT是非终结符的集合；VN是终结符的集合；S

VN是开始符号；P是产生式的非空有限集

45例G=({N},{0,1},{N0N,N1N,N0,N1},N)，其中：

VN={N};

VT={0,1};

P={N0N,N1N,N0,N1};

S=N。一.文法的定义文法是描述语言的语法结构的形式规则,必须准确表达式项|表达式+项项因子|项*因子因子

(表达式)|i无二义文法：G(E)：ET|E+TTF|T*FF(E)|iG0=(VT,VN,S,P）：E→E+T|TT→T*F|FF→(E)|I显然VT={+,*,(,),i}VN={E,T,F}S=EP为上述产生式的集合表达式项|表达式+项无二义文法：G0=(VT,VN,S说明:①→的读法,

其中

V*VNV*,V*，V＝VTVN②→1

→2...

→n

③约定：用英文大写字母表示非终结符；小写字母表示终结符；希腊小写字母表示串缩写为→1|2|…|n

47说明:缩写为→1|2|…|n47文法的分类Chomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。文法的分类Chomsky于1956年建立形式语言体系，他把文0型文法（短语文法）：要求每个产生式αβ,有α∈V*VNV*，β∈V*,即α中至少含有一个非终结符。1型文法(上下文有关文法)：如果对0型文法施加以下的限制，就得到1型文法： 对除Sε外的任何产生式αβ，要求1≤|α|≤|β|

即规则左部符号个数不超过右部符号个数，Sε除外

如：αAβαγβ是1型文法的一个产生式，α和β非空，则只有在α和β这样一个上下文中A才能替换为γ。文法分类注意：

如果规则左部有终结符，则该文法一定属于0或1型文法。0、1型文法的区别：规则左、右部的长度如果文法中所有规则左部符号串长度均小于或等于右部符号串长度，则称为1型文法，否则为0型文法。0型文法（短语文法）：要求每个产生式αβ,有α∈V*VNV2型文法(上下文无关文法)：如果对1型文法施加以下的限制，就得到2型文法：

G的任何产生式为Aβ,A∈VN,β∈(VN∪VT)*

这种文法意味着，每一规则左部只有一个非终结符，无需考虑该非终结符在上下文中的出现情况。3型文法(正则文法)：如果对2型文法施加以下的限制，就得到3型文法：

G的任何产生式为AαB|β,或者ABα|β,

其中A,B∈VN,α,β∈VT 3型文法称为右线性文法或左线性文法；3型文法等价于正规式，所以又称正规文法。文法分类2型文法(上下文无关文法)：如果对1型文法施加以下的限制，就总结：2、3型文法规则左部仅为非终结符，若规则右部形式仅为AαB|β,或者ABα|β（A,B∈VN,α,β∈VT）则为3型文法，否则为2型文法总结：52四种类型描述能力比较四类文法的定义是逐渐增加限制的，对应的语言描述能力越来越弱，52四种类型描述能力比较四类文法的定义是逐渐增加限制的，对应53判断一个文法时应该以什么规则来判断呢？这个规则是：3->2->1->0.也就是说，我们判断是从高到低来判断的，一旦判断其属于正规文法之后就没必要再判断其是否属于上下文无关的了(因为它必定属于上下文无关，我们应该以最高规则来判定其属于的文法类型)，其它情况与此类推。只有当我们判断不属于3型文法时，才向下判断，其是不是属于2型的，若不属于2型的，则依此类推再向下判断。最终的结果如果不属于3，2和1三种类型，那就只有属于0型了。53判断一个文法时应该以什么规则来判断呢？

S—>aB|bAA—>aS|bAA|aB—>bS|aBB|bS—>bAA—>(B|aB—>aA2型文法（无关）3型文法（正则）54S—>aB|bAS—>bA2型文法（无关）3型文法（正则）L5={anbn|n1}不能由正规文法产生，但可由上下文无关文法产生：

G5(S)：

SaSb|abL6={anbncn|n1}不能由上下文无关文法产生，但可由上下文有关文法产生：

G6(S)：SaSBC|aBCCB

BCaB

abbBbbbCbccC

ccL5={anbn|n1}不能由正规文法产生，但可由上下文内容回顾语言＝语法＋语义语法1.生成的观点：文法2.识别的观点：语法图语义1.抽象机G=(VT,VN,S，P)3.文法的分类56内容回顾语言＝语法＋语义语法语义G=(VT,VN,S，P)3①直接推导:αβ

α

即由产生式右边替换产生式左边②推导:α1

αn、α1αn③归约:推导的逆过程*+三.文法产生的语言1.推导与归约57若α1,α2,α3,…αn∈V*,且α1α2,α2α3,…,αn-1αn,则α1可推导出αn，记作α1αn+若α1αn或者α1=αn，则记为α1αn+**归约是推导的逆过程，若存在α1αn，则认为αn能归约为α10①直接推导:αβα*+三.文法产生的语言1.推58例:G=({E},{i,+,*,(,)},P,E)(1.1)

P：EE+E|E*E|(E)|i

表达式(i)和(i+i)*i的推导：E(E)(i)

EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i

EE

0步推导

E(i+i)*i6步推导

E(i+i)*i

6步推导

E(E)

直接推导58例:G=({E},{i,+,*,(,)若推导过程中，总是最先替换最右(左)的非终结符，则称为最右(左)推导若归约过程中，总是最先归约最右(左)的非终结符，则称为最右(左)归约句型的最右推导称为规范推导，其逆过程最左规约称为规范归约。例如：G的产生式：EE+E|E*E|(E)|i，其中VT={+,*,(,),i}i*i+i的规范推导：EE*EE*E+EE*E+iE*i+ii*i+i规范推导是规范规约的逆过程规范推导、规范规约若推导过程中，总是最先替换最右(左)的非终结符，则称为最右(**2.句型和句子设文法G=(VT,VN,S,P),若Sα,αV*,则称α为文法G的一个句型。若上述αVT，则称α是一个句子，即只含终结符的句型是一个句子例文法G[S]：S→0S1，S→01

因为S0S100S11000S11100001111

所以S,0S1,00S11,000S111,00001111都是G的句型00001111是G的句子

60**2.句型和句子设文法G=(VT,VN,S,P),若S思考句型与句子的关系是？只含终结符的句型就是一个句子。一个句子是句型。一个句型不一定是句子。思考句型与句子的关系是？

文法G=(VT,VN,S,P)的句子的全体,称为由文法G产生的语言,记为L(G),即

L(G)={α│Sα其中

αVT}+*3.文法产生的语言62要求：（1）能根据文法分析其所产生的语言；（2）能根据语言构造其文法。文法G=(VT,VN,S,P)的句子的全体,称为由文法G2(I):I→L│LSS→T│STT→L│DL→a│b│...│zD→0│1│2│...│9例163根据文法分析其所产生的语言；G2(I):例163根据文法分析其所产生的语言；G3(S):S→aS│aPP→bP│bQQ→cQ│cL(G3)={aibjck│i,j,k1}例264G3(S):L(G3)={aibjck│i,j,k1}例2G4(S):S→aSPQ│abQQP→PQbP→bbbQ→bccQ→cc例3L(G4)={aibici│i1}65G4(S):例3L(G4)={aibici│i1}65Sai-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次使用第六个产生式)*********66Sai-1S(PQ)i-1例

构造文法G，使其描述的语言为正奇数集合。令G={VN,VT,P,<正奇数>}VT={0,1,2,3,4,5,6,7,8,9}P:<一位奇数>1|3|5|7|9 <正奇数><一位奇数>|<数字串><一位奇数> <数字串><数字串><数字>|<数字> <数字><一位奇数>|0|2|4|6|8VN={<正奇数>,<一位奇数>,<数字串>,<数字>}分析：正奇数要求，要么是一位奇数数字，要么是以奇数数字结尾的十进制数字。根据语言构造文法例构造文法G，使其描述的语言为正奇数集合。令G={VN,V例：构造语言的文法L(G)={anbn|n≥0}可能的句子：εabaabbaaabbb……abababSεSaSbG[S]=({S},{a,b},{Sε|aSb},S)根据语言构造文法例：构造语言的文法L(G)={anbn|n≥0}可能①文法的重要特性:用有限规则描述无穷语言文法和语言的关系： 文法G生成的每个串都在L(G)中

L(G)中的每个串确实能被G生成②文法的等价:两个文法G和G’,如果有L(G)=L(G’),则称G和G’等价69①文法的重要特性:用有限规则描述无穷语言②文法的等价:两个文短语:设αβ是上下文无关文法G的一个句型,如果有S

αA,并且Aβ,则称β是句型αβ关于非终结符A的一个短语,或称β是句型αβ的一个短语。

直接短语：Aβ

句柄：一个句型的最左直接短语*+4.短语、句柄70短语:设αβ是上下文无关文法G的一个句型,如果有S例:G(E)E→E+T|TT→T*F|FF→(E)|i求E+T*F的短语、直接短语、句柄EE+TE+T*F因为EE+T且TT*F，所以T*F是关于T的短语因为E=E且ET+T*F,所以T+T*F是关于E的短语直接短语:T*F句柄:T*F71例:G(E)E→E+T|TEE+TE例:G(E)E→E+T|TT→T*F|FF→(E)|i求T*F+i的短语、直接短语、句柄EE+TT+TT*F+TT*F+FT*F+i因为E=E且ET*F+i，所以T*F+i是关于E的短语因为ET＋T且TT*F，所以T*F是关于T的短语、直接短语、句柄因为EE＋T且ET*F，所以T*F是关于E的短语因为ET*F+T且Ti，所以i是关于T的短语因为ET*F+F且Fi，所以i是关于F的短语、直接短语******72例:G(E)E→E+T|TEE+TT+T

——以图的方式表示推导过程①推导树是一棵有序的标记树

每个结点的标记是文法G的非终结符或终结符；标记为A的内部结点从左到右有子结点X1，X2，…,Xn,

则A→X1…Xn是一个产生式;5.语法树（推导树）73——以图的方式表示推导过程5.语法树（推导树语法树（推导树）语法树是一种描述上下文无关文法句型推导的直观方法，定义为：给定文法G[S],对于G的任何句型都能构造与之关联的语法树，这棵树满足以下4个条件:每个节点都有一个标记，此标记是V的一个符号

根的标记是S，即文法的标识符号

若一个节点n至少有一个它自己除外的子孙,并且有标记A,则A肯定在VN中

若节点n的直接子孙从左到右的次序是节点n1,n2,…,nk,其节点分别为A1,A2,…,Ak,那么AA1A2…Ak一定是G[S]中的一条规则。构造过程：（1）从识别符号开始，向下画一个分支，表示第一个直接推导（2）再从非终结符号往下画分支，表示即将进行的直接推导，如此进行下去，直到全部推导都在树上表示出来，即可得到语法树语法树（推导树）语法树是一种描述上下文无关文法句型推导的直观语法树（推导树）已知G1[S]:S

A|S-A,Aa|b|c已知G2[S]:S

A|A-S,Aa|b|cSS-A句子a-b-c的推导过程(规范推导)：SS-AS-cS-A-cS-b-cA-b-ca-b-ccS-AbAa句子a-b-c的推导过程(规范推导)：SA-SA-S-AA-S-cA-A-cA-b-ca-b-cSA-SA-SabAa语法树（推导树）已知G1[S]:SA|S-A,A76从语法分析树来识别：一语法分析树的一棵子树是由该树的某个结点连同它的所有子孙组成的。一个子树的所有树叶结点自左至右排列起来形成一个相对于子树根的短语。只有父子两代结点形成的子树的树叶结点自左至右排列起来就形成相对于子树根的直接短语；一个句型的句柄是这个句型所对应的语法树中最左那个构成直接短语的子树的树叶结点自左至右的排列

EE+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的语法树如图：76从语法分析树来识别：EE+TTFi3i2i77例：下述文法的另一个句型：

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句柄是：T*F77例：下述文法的另一个句型：ET|E+TEE+③推导树的边缘：一棵推导树所有叶结点的从左到右的连接。④文法的二义性：一个句子有两棵不同的推导树。④由推导树确定短语78③推导树的边缘：一棵推导树所有叶结点的从左到右的连接。78（i+i*i）E（E）EE*EE+iiiE（E）EE+EEiii*79若一个文法存在某个句型对应两棵不同的语法树，则称此文法是二义性文法。例2G=({E},{+,*,i,(,)},P,E),其中P为：

EE+E|E*E|(E)|i,则E*E+i对应的语法树：（i+i*i）E（E）EE*EE+iiiE（E）EE+EEi内容回顾1.语法生产的观点：文法识别的观点：语法图2.句型和句子3.短语、直接短语和句柄4.推导树E→E+E│E*E│(E)│i(i+i*i）80内容回顾1.语法生产的观点：文法识别的观点：语法图2.句型和EET+TTFFi*例:G(E)E→E+T|TT→T*F|FF→(E)|i求T*F+i的短语、直接短语、句柄81EET+TTFFi*例:G(E)E→E+已知文法G（S）:S->a|b|(A)A->SdA|S1．证明(bdS)是文法G(S)的句型；2．画出(bdS)的推倒树；3．求句型(bdS)的短语，直接短语，句柄。课堂练习82已知文法G（S）:课堂练习82已知文法G（S）：S->aAD|aBe|bBS|bAeA->gA|gB->gD->d1.证明bgagAd是G（S）的句型；2.画出bgagAd的推倒树；3.求句型bgagAd的短语、直接短语、句柄课堂练习83已知文法G（S）：课堂练习83

主要目的：

给出设计一个强制式语言的入门知识和方法。表达式的设计逻辑表达式关系表达式算术表达式第三节语言的设计语句的设计

说明语句

执行语句单元的设计

84主要目的：表达式的设计第三节语言的设计语句的设计单元的设

（非）、

（与）、

（或）要求满足优先次序；

>

>

满足左结合；<逻辑表达式><布尔常量>|<布尔变量>|<关系表达式>|

<逻辑表达式>|<逻辑表达式><逻辑表达式>|<逻辑表达式><逻辑表达式><布尔常量>true|false<布尔变量><标识符>1.逻辑表达式一.表达式的设计BNF范式运算符85（非）、（与）、（或）要求满足优先次序；>>

<（小于），<=（小于等于），>（大于），>=（大于等于），=（等于），<>（不等于）运算符之间没有优先次序；运算符没有重载；<关系表达式>

<关系表达式><关系运算符><关系表达式><关系运算符><|<=|>|>=|=|<>2.关系表达式运算符要求BNF范式86<（小于），<=（小于等于），>（大于），>=（大于等于）

各种算术运算，+(加)，-(减)，*(乘)，/(除)等运算符的优先次序，*,/>+,

-；同优先级算符左结合；运算符要求BNF范式3.算术表达式<算术表达式><算术表达式>+<项>|<算术表达式>-<项>|

-<项>|<项><项><因子>|<项>*<因子>|<项>/<因子><因子>(<算术表达式>)|<常量>|<变量><变量><标识符><常量><整形常量>|<实型常量>。。。87各种算术运算，+(加)，-(减)，*(乘)，/(除)等运算

强制式语言是面向语句的语言，通过语句描述问题的求解过程。语句通常分为：说明语句：不生成目标代码，用来告诉编译程序一些实体的属性；执行语句：生成目标代码二.语句的设计88强制式语言是面向语句的语言，通过语句描述问题的求解过程。语

主要包括变量说明和类型说明；1.说明语句<说明语句><常量说明>|<变量说明>|<类型说明><常量说明>const<标识符>=<常量><变量说明>var<变量表>:<类型><变量表><变量>|<变量表>,<变量><变量><标识符><类型>integer|real|char|boolean<类型说明>type<类型名>=<用户定义类型><类型名><标识符><用户定义类型>（从略）89主要包括变量说明和类型说明；1.说明语句<说明语句><

执行语句主要包括赋值语句、控制语句和复合语句；赋值语句<赋值语句><变量>:=<表达式>控制语句顺序、控制和循环语句的选择：在多样性和效率之间折衷语句的结束符：两个含义，控制执行顺序和语句结束复合语句<复合语句>begin<语句表>end<语句表><语句>|<语句表>;<语句>2.执行语句90执行语句主要包括赋值语句、控制语句和复合语句；赋值语句控制

程序单元是程序可以独立调用的成分，在设计时要考虑下面的问题：程序单元的局部环境如何定义；程序单元的头尾标识；程序单元的名字及参数如何定义；程序单元如何被调用及参数如何传递；三.程序单元的设计91程序单元是程序可以独立调用的成分，在设计时要考虑下面的问题

<程序单元><程序单元关键字><程序单元名字>(<形参表>)；<程序单元体><程序单元关键字>procedure|function|class|…<程序单元名><标识符><形参表><形参>|<形参表>;<形参><程序单元体>begin<说明部分>;<执行部分>end<说明部分><说明语句表><说明语句表><说明语句>|<说明语句表>;<说明语句><执行部分><执行语句表><执行语句表><执行语句>|<执行语句表>;<执行语句>程序单元的BNF范式92<程序单元><程序单元关键字><程序单元名字>(<形参

程序通常由一个关键字，后跟程序名，参数表以及程序体构成，即：<程序>program<程序名>(<参数表>);程序体不同的语言有细微的差别；四.程序的设计93程序通常由一个关键字，后跟程序名，参数表以及程序体构成，即

给出一个极小的强制式语言的设计，它面向阶乘n!的求解，最后用该语言写出求阶乘的程序。问题：阶乘n!的求解

ifn<=0thenF:=1elseF:=n*F(n-1)第四节语言设计实例94给出一个极小的强制式语言的设计，它面向阶乘n!的求解，最后

<程序>→<分程序><分程序>→begin<说明语句表>；<执行语句表>end<说明语句表>→<说明语句>│<说明语句表>；<说明语句><说明语句>→<变量说明>│<函数说明><变量说明>→integer<变量><变量>→<标识符><标识符>→<字母>│<标识符><字母>│<标识符><数字><字母>→a│b│c│d│e│f│g│h│i│j│k│l│m│n│o│p│q│r│s│t│u│v│w│x│y│z95<程序>→<分程序>95

<数字>→0│1│2│3│4│5│6│7│8│9<函数说明>→integerfunction<标识符>（<参数>）；<函数体><参数>→<变量><函数体>→begin<说明语句>；<执行语句表>end<执行语句表>→<执行语句>│<执行语句表>；<执行语句><执行语句>→<读语句>│<写语句>│<赋值语句>│<条件语句><读语句>→read(<变量>)<写语句>→write(<变量>)96<数字>→0│1│2│3│4│5│6│7│8│996<赋值语句>→<变量>:=<算术表达式><算术表达式>→<算术表达式>-<项>│<项><项>→<项>*<因子>│<因子><因子>→<变量>│<常数>│<函数调用><常数>→<无符号整数><无符号整数>→<数字>│<无符号整数><数字><条件语句>→if<条件表达式>then<执行语句>else<执行语句><条件表达式>→<算术表达式><关系运算符><算术表达式><关系运算符>→<│<=│>│>=│=│<>

97<赋值语句>→<变量>:=<算术表达式>97beginintegerk;integerfunctionF(n);beginintegern;ifn<=0thenF:=1elseF:=n*F(n-1)end;read(m);k:=F(m);write(k)end求n!的程序

98求n!的程序98(1)可写性：语言提供一些机制来方便地表达设计方法以帮助完成程序设计。使得程序员可以把注意力集中在理解问题和求解问题上。6.一些设计准则(1)可写性：语言提供一些机制来方便地表达设计方法以帮助完成

可写性表现在简单性、可表达性、正交性和准确性等方面。可写性表现在简单性、可表达性、正交性和准确性等方面。6.一些设计准则(2)可读性：抽象、注解；影响可修改性和可维护性(3)可靠性:软件系统正常工作的能力。数据抽象、信息隐蔽、异常处理机制有利于提高可靠性。6.一些设计准则(2)可读性：抽象、注解；影响可修改性和可维定义一个文法，能生产偶数。练习

N->TST->TD|D->0|1|2|…|9S->0|2|4|6|8102练习N->TS102

作业4.2，4.3，10-1，10-2103作业4.2，4.3，10-1，10-2103第四章程序语言的设计第2章和第3章分别讨论了程序设计语言的数据类型和控制结构，分别描述程序的数据结构和算法。本章介绍语言的设计方法。第四章程序语言的设计第2章和第3章分别讨论了程序

主要内容1.语言的定义语法：定义语言是否合法的一组规则语义：用以规定程序或其成分的含义2.文法：定义语言语法的形式化规则3.语言的设计105主要内容2106§4.1程序语言的定义语言定义是语言实现的基础：从语言用户角度看语言初等成分的实际含义是什么？如何有意义地使用它们？怎样以有意义的方式组合它们？从编译程序设计者角度看哪些构造允许出现即使一时不能看出某种构造的实际应用，或者判断实现该结构会导致严重的困难，但仍必须严格根据语言的定义实现它程序设计语言是用来描述计算机所执行的算法的形式表示；3§4.1程序语言的定义语言定义是语言实现的基础：程序设计107一个程序语言是一个记号系统程序语言由两方面定义：语法语义语用语言＝语法＋语义语法:用以构造程序及其成分的一组规则的集合语义:用以规定语法正确的程序或其成分的含义的一组规

则的集合语用分析:是对自然真实语言经过语法分析，语义分析后，更高级的语言学分析。4一个程序语言是一个记号系统程序语言由两方面定义：语言＝语法1081.语法程序本质上是一定字符集上的字符串。语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序。其中，0.5、x1、等称单词符号，而表达式称语言的一个语法范畴或语法单位。例：字符串0.5x1+c51.语法程序本质上是一定字符集上的字符串。其中，0.5109语法词法规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。描述工具：有限自动机语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;描述工具：上下文无关文法本课程中，有限自动机和上下文无关文法是词法分析和语法分析的主要理论基础。6语法词法规则：单词符号的形成规则。本课程中，有限自动机1102.语义语义：一组规则，用它可以定义一个程序的意义。描述方法：自然语言描述：隐藏错误、二义性和不完整性形式描述：操作语义(PL/1)

指称语义(ADA)

代数语义(PASCAL)72.语义语义：一组规则，用它可以定义一个程序的意义。111程序语言的基本功能和层次结构程序语言的基本功能：描述数据和对数据的运算。所谓程序，本质上说是描述一定数据的处理过程。8程序语言的基本功能和层次结构程序语言的基本功能：描述数据和112程序子程序或分程序语句表达式数据引用算符函数调用自上而下：每一层由其下层部分组成。自下而上：

通过对下层成分的理解来掌握上层成分，从而掌握整个程序。9程序子程序或分程序语句表达式数据引用算符函数调用自上而下：

①字母表:语言允许使用字符的集合,其元素称为字符

②符号:由字符组成的有限串（字符串）

③字汇表:由符号组成的集合，其元素称为字

④词法规则:规定什么样的字符串可以构成语言的有效符号

⑤语法规则:确定一个符号序列是否为一个句子,并提供句子的结构（什么样的符号序列是合法的）一.语法1.几个术语

113①字母表:语言允许使用字符的集合,其元素称为字符一.语言的定义语言的定义可以从生成（文法）和识别（语法图）的观点进行。语言的定义语言的定义可以从生成（文法）和识别（语法图）的观点2.生成的观点①一个简单英语句子的描述

I/StudentsStudy/Run如何描述？<语句>→<主语><谓语><主语>→I|Students<谓语>→Study|Run每一行称为一条语法规则；终结符、非终结符注意：描述以上规则的符号系统称为巴科斯-诺尔范式，即通常的BNF（Backus-NaurForm）。

1152.生成的观点①一个简单英语句子的描述如何描述？<语句>→

②文法在形式语言中，上述例子可写成文法G=(N,T,P,S)其中N={<语句>,<主语>,<谓语>}T={I,students,study,run}P={<语句>→<主语><谓语>,<主语>→I|Students,<谓语>→Study|Run}S=<语句>③语言:所有句子的集合④标识符和表达式描述116②文法在形式语言中，上述例子可写成文法③语言:所有句子标识符

<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→A|…|Z|a|…|z<数字>→0|…|9117标识符<标识符>→<字母>14表达式

<表达式>→<标识符><表达式>→(<表达式>)<表达式>→<表达式><运算符><表达式><运算符>→+|-|*|/118表达式<表达式>→<标识符>153.识别的观点：语法图每一非终结符N连同相应的产生式N→a1|a2|…|an对应一个语法图；具体对应如下：终结符x对应于x非终结符N对应于N

①定义1193.识别的观点：语法图每一非终结符N连同相应的产生式终结符xb1b2bmgb→12…m

→|N→1|2|…|n2n1

120b1b2bmgb→12…m

N→1|

表达式标识符表达式运算符()表达式表达式字母字母数字标识符+-*/运算符字母字母数字表达式()表达式+表达式-*/表达式语法图的一些例子121表达式标识符表达式运算符()表达式表达式字母字母数字标识符

若一个终结符序列是合法的，那么,必须从语法图的入口边通过语法图而到达出口边，而且在通过的过程中,恰恰能识别该终结符序列。具体如下：终结符框:标识的终结符与被识别的终结符刚好符合非终结符框:由该非终结符的语法图来识别；分支:若遇到分支，则任选一分支来识别；回溯:若一个分支识别不成功，则选另一分支来识别③语言②识别原则语法图能识别的所有终结符序列的集合122若一个终结符序列是合法的，那么,必须从语法图的入口边通过语高级语言语法规则的描述方法FORTRAN采用自然语言描述语法；ALGOL

60首次用BNF对语法进行形式描述,为语言定义做出了重要贡献；Pascal首次采用语法图来定义语言，给出了较为直观的语法结构。高级语言语法规则的描述方法FORTRAN采用自然语言描述语法语法描述方法等价文法和语法图是语言语法的等价表示文法从产生的观点来定义语言的语法，更通用、更准确。语法图以识别的观点定义语言的语法，更直观、更清晰。语法描述方法等价文法和语法图是语言语法的等价表示采用生成的方法还是采用识别的方法来定义语言由语言的设计者确定。采用生成的方法还是采用识别的方法来定义语言①表达语言设计者的意图和设计目标;②指导语言的使用者如何写一个正确的程序；③指导语言的实现者如何编写一个语法检查程序来识别所有合法的程序。4.语法描述的基本用途

126①表达语言设计者的意图和设计目标;4.语法描述的基本用途2二.语义例：大象吃花生

Elephantseatpeanuts1.何谓语义定义语言合法句子的含义，即句子的作用和意义。例：if(a>b)max=a;elsemax=b2.语义的描述：GAM指令指针+代码存储器C+数据存储器D

127二.语义例：大象吃花生1.何谓语义定义语言合法句子的含义，即

语言的语义规则定义语言合法句子的含义。例如，C语言的语义帮助理解语句

if(a>b)max＝aelsemax＝b； 必须先计算关系表达式a>b的值，然后按照所得值决定计算max＝a或max＝b。**语法规则告诉我们如何形成这个语句，语义规则告诉我们这个语句的作用和意义是什么。 语言的语义规则定义语言合法句子的含义。例如，C语言的语义帮文法和语法图已成为语法描述的典型工具，但语义描述至今尚无人们普遍接受的典型描述工具。许多语言仍采用自然语言描述语义。文法和语法图已成为语法描述的典型工具，但语义描述至今尚无本章的语言设计，采用自然语言来描述语义。(下篇的)语言实现涉及到的语义，将以操作语义学的方法来描述。本章的语言设计，采用自然语言来描述语义。

操作语义学的方法以一个抽象机(AbstractMachine)的行为来描述语言的各个结构的作用和含义。

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

ip代码存储器（C）数据存储器（D）存储可执行的指令代码存放程序中被操纵的数据指令指针133ip代码存储器（C）数据存储器（D）存储可执行的指令代码存程序设计语言与编译原理_第四章程序语言的设计课件GAM抽象机的结构(l)执行ip所指向的指令；(2)修改ip的内容；若所执行的指令已修改过ip，则不再修改ip(显然刚执行的指令是一条转移指令)。执行的指令未修改ip，那么修改ip使之指向下一条指令，即ip:=ip+1,使之指向下一条指令(3)若ip指向特殊的STOP指令，则终止执行，否则转回执行(1)。GAM抽象机的结构(l)执行ip所指向的指令；GAM抽象机的结构假设GAM对各种程序设计语言所常用的运算符如＋，-，*,/,＞,＜,>=等都有相应的指令与之对应。GAM抽象机的结构假设GAM对各种程序设计语言所常用GAM抽象机的结构以GAM的操作行为来定义语言的语义，是基于已经“理解”GAM的语义因此，一旦用GAM的操作行为来定义语言结构的作用时，就知道了语言的意义。GAM抽象机的结构以GAM的操作行为来定义语言的语GAM抽象机的结构GAM应该是一个简单的模型工具。为了成功地应用这种方法，GAM自身的语义应尽可能地简单，以便把问题集中到语言的语义上，而不是抽象机自身的复杂性上。GAM抽象机的结构GAM应该是一个简单的模型工具。文法自从乔姆斯基(Chomsky)于1956年建立语言的形式描述以来，形式语言的理论发展很快。该理论对计算机科学，特别是对程序语言的设计、编译方法、计算复杂性等方面，产生了深刻影响。第二节文法文法自从乔姆斯基(Chomsky)于1956年建立语言的形同时，它还促进了计算机科学的理论研究工作，并取得了不少的成果。计算机的理论工作走在计算机发展的前面。但随着计算机及其应用的迅速发展，今天的理论工作远远落后了。同时，它还促进了计算机科学的理论研究工作，并取得了不少

基本概念例句：inti=0;包含字母i,n,t,=,0,;,所有字母形成字母表；符号串，如int定义1字母表：字母表∑是符号元素的非空有限集合。定义2符号（字符）：字母表中的元素。定义3符号串（字符串）：字母表中的符号所组成的任何有穷序列。如字母表∑={a,b}，则a,b是字母表∑中的元素，a,b,aa,ab,…都是符号串。空符号串：不含任何符号的符号串，用ε表示。字母表，符号，符号串基本概念例句：inti=0;定义1字母表：字母表∑基本概念定义4符号串x和y的连接：指x和y的符号按先后顺序排列在一起组成的新的符号串，用xy表示。例：若∑={a,b},x=ab,y=ba,则xy=abba,yx=baab。注意：（1）xy≠yx；（2）εx=xε=x。定义5符号串的长度：指符号串中符号的个数。例：|ab|=2,|aabb|=4,|ε|=0。字符串连接、字符串长度基本概念定义4符号串x和y的连接：指x和y的符号按先后顺序基本概念定义6符号串的前缀和后缀：分别指符号串的左部和右部任意字符串。例：ab的前缀有ε、a、ab；后缀有ε、b、ab。定义7符号串集合的乘积：设A、B是字母表∑上的符号串集合，则定义