程序语言的设计

第一节语言的定义语言＝语法(规则)＋语义(规则)语法:用以构造程序及其成分(语法单位)的规则的集合语义:用以规定语法正确的语法单位的含义的规则的集合1.几个术语①字母表:语言允许使用字符的集合,其元素称为字符②符号:由字符组成的有限串(字符串)③字汇表:由符号组成的集合，其元素称为字

一.语法④词法规则:规定什么样的字符串可以构成语言的有效符号(单词符号)⑤语法规则:确定一个符号序列是否为一个句子,并提供句子的结构（什么样的符号序列是合法的）语言的定义语言的定义可以从生成（文法）和识别（语法图）的观点进行。①一个简单英语句子的描述

I/Studentsstudy/run②文法:记为(N,T,P,S)<句子>→<主语><谓语><主语>→I|Students<谓语>→study|run③语言:所有句子的集合2.生成的观点<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→A|…|Z|a|…|z<数字>→0|…|9标识符<表达式>→<标识符><表达式>→(<表达式>)<表达式>→<表达式><运算符><表达式><运算符>→+|-|*|/表达式(算术)3.识别的观点用语法图来定义给定的语言①语法图的构造N→

1|2|…|n对应一个语法图终结符x非终结符NN→

1|2|…|n

xN

2

n

1

b1

b2

bm

→

1

2…m

g

b

→|

若一个终结符序列是合法的，那么,必须从语法图的入口边通过语法图而到达出口边，而且在通过的过程中,恰恰能识别该终结符序列。②识别原则③语言语法图能识别的所有终结符序列的集合。Ⅰ.终结符框Ⅱ.非终结符框Ⅲ.分支、回溯参见图4-6~9

字母字母

数字标识符图4-6标识符表达式运算符表达式()表达式表达式图4-9语法描述方法FORTRAN采用自然语言描述语法；ALGOL

60首次用BNF对语法进行形式描述,为语言定义做出了重要贡献；Pascal首次采用语法图来定义语言，给出了较为直观的语法结构。语法描述方法等价文法和语法图是语言文法的等价表示。文法从产生的观点来定义语言，更通用、更准确地给出语言的语法结构。语法图以识别的观点定义语言，更直观、更清晰地给出语言的语法结构。是采用生成的方法还是采用识别的方法来定义语言，由语言的设计者确定。①表达语言设计者的意图和设计目标；②指导语言的使用者编写正确的程序；③指导语言的实现者编写语法检查程序来识别所有语法单位。4.语法描述的用途语义（规则）定义语言合法句子的含义（即句子的作用和意义）的规则组合。例：if(a>b)max=a;elsemax=b;二.语义文法和语法图已成为语法描述的典型工具，但语义描述至今尚无人们普遍接受的典型描述工具。许多语言仍采用自然语言描述语义。本章的语言设计，采用自然语言来描述语义。(下篇的)语言实现涉及到的语义，将以操作语义学的方法来描述。即以一个抽象机的行为来描述语言的各个结构的作用和意义。抽象机GAM的组成由存储器,控制器,处理器，指令指针ip

组成。存储器分为代码区(段)和数据区(段)。ip代码存储器（C）数据存储器（D）抽象机GAM的模型抽象机GAM的结构代码区又称代码存储器，用以存放程序指令。代码存储器的内容不允许被修改。数据区又称数据存储器，用以存放必要的信息和程序中的数据。GAM抽象机的结构ip的内容是代码区单元的地址，该单元的内容是一条指令。C[i]和D[i]表示相应存储区第i个单元ip:=ip+

4

表示指针指向下一条指令假定每条指令占4个存储单元(字节)GAM抽象机的结构GAM一旦启动，由专门的装入程序将一个要运行的程序装入代码存储器，并置ip

指向该程序的第一条指令。然后依次完成下述工作：GAM抽象机的结构(l)执行ip

所指向的指令。(2)修改ip

的内容。若所执行的指令未修改ip,则ip+4,使之指向下一条指令。(3)若ip

指向特殊的STOP指令，则终止执行，否则转回执行(1)。GAM抽象机的结构假设GAM对各种程序设计语言所常用的运算符如＋，-，*,/,＞,＜,>=等都有相应的指令与之对应。GAM抽象机的结构以GAM的操作行为来定义语言的语义，是基于已经“理解”了GAM的语义。因此，一旦用GAM的操作行为来定义语言结构的作用时，就知道了语言结构的意义。GAM抽象机的结构GAM应该是一个简单的模型工具。为了成功地应用这种方法，GAM自身的语义应尽可能地简单，以便把问题集中到语言的语义上，而不是抽象机自身的复杂性上。文法自从乔姆斯基(Chomsky)于1956年建立语言的形式描述以来，形式语言的理论发展很快。该理论对计算机科学，特别是对程序语言的设计、编译方法、计算复杂性等方面，产生了深刻影响。第二节文法同时，它还促进了计算机科学的理论研究工作，并取得了不少的成果。使得计算机的理论工作走在计算机发展的前面。但随着计算机及其应用的迅速发展，今天的理论工作远远落后了。文法是描述语言的语法结构的形式规则。通用，准确,易于理解,描述能力强一.文法的定义

G=(VT，VN，S，P)

VT为终结符的非空有限集；

VN为非终结符的非空有限集；

S是文法的开始符号，S∈VN

；

P为产生式的非空有限集，1.文法的形式定义产生式是一个有序偶对(

，

)记为

::=

或

→

和

均是由终结符和／或非终结符组成的符号串但

至少应含有一个非终结符。即

V*VN

V*

V*产生式的简化

→

1

→

2…

→

n

→

1|

2|…|

n约定

英文大写字母表示非终结符；小写字母表示终结符；希腊字母表示终结符和非终结符的串。文法的表示描述文法，直接给出产生式集合即可。例算术表达式文法G0:E→E+T|TT→T*F|F

F→(E)|i①0型文法

→

②1型文法(上下文有关文法)|α|<=|β|（S→

例外）*2.文法的分类

→

③2型文法(上下文无关文法)

A→

④3型文法(正则文法,右线性文法)

A→w或A→wB

其中wVT*1.推导与归约①直接推导:wα

wβ

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

*αn、α1

+αn

二.文法产生的语言E→E+E│E*E│(E)│i

i+i*i的最左推导过程已知G(E)

EE+E

i+Ei+E*Ei+i*Ei+i*i最右推导（规范推导）EE+EE+E*EE+E*iE+i*ii+i*i

EE*EE*iE+E*iE+i*ii+i*i文法G=(VT,VN,S,P),S

*α若αV*,

则称α为文法G的一个句型。若αVT*,则称α是一个句子2.句型和句子思考句型与句子的关系是？只含终结符的句型就是一个句子。一个句子是句型。一个句型不一定是句子。文法G=(VT,VN,S,P)产生的所有句子的集合,称为由文法G产生的语言,记为L(G),即

L(G)={α│S

+α且αVT*

}3.文法产生的语言I→L|LSS→T|ST

T→L|D

L→a|b|...|zD→0|1|2|...|9G2(I):

S→aS|aP

P→bP|bQ

Q→cQ|cL(G3)={aibjck│i,j,k

1}G3(S):

S→aSBC|aBC

CB→BC

aB→ab

bB→bb

bC→bc

cC→ccL(G4)={anbncn│n

>0}G4(S):

有限规则描述无穷语言。文法的重要特性文法等价

两个文法G和G’,如果有L(G)=L(G’),则称G和G’等价①推导树是一棵有序的标记树每个结点的标记是文法G的非终结符或终结符；标记为A的内部结点从左到右有子结点X1，X2，…,Xn,则A→X1…Xn是一个产生式;4．推导树（语法树）对于文法E→E+E│E*E│(E)│I

句子

i+i*iE（E）EE*EE+iiiE（E）EE+EEiii*②推导树:i+i*i③推导树的边缘：推导树所有叶结点的从左到右的连接。④文法的二义性：一个句子有两棵不同的推导树。设计的依据：面向的问题和面向的机器设计内容(语法)：表达式、语句、程序单元、程序描述方式：语法-BNF语义-自然语言第三节语言的设计一.表达式的设计

逻辑表达式

关系表达式

算术表达式第三节语言的设计1.逻辑表达式<逻辑表达式>→<布尔常量>|<布尔变量>|<关系表达式>|

<逻辑表达式>|<逻辑表达式>

<逻辑表达式>|<逻辑表达式>

<逻辑表达式>

1.逻辑表达式<布尔常量>

→true|false<布尔变量>

→<标识符>、、的优先顺序由低到高1.逻辑表达式<关系表达式>→<算术表达式><关系运算符><算术表达式><关系运算符>

→<|<=|>|>=|=|<>2.关系表达式2.关系表达式关系运算符没有优先顺序、没有重载<算术表达式>→<常量>|<变量>|

(<算术表达式>)|<算术表达式><算术运算符><算术表达式>3.算术表达式算术运算符有优先顺序、允许重载算术运算符服从左结合上述描述具有二义性<算术表达式>→<算术表达式>+<项>|<算术表达式>-<项>|<项><项>→<项>*<因子>|<项>/<因子>|<因子><因子>→(<算术表达式>)|<常量>|<变量>没有二义性的描述<变量>→<标识符><常量>→<各种常量>1.说明语句<说明语句>→<常量说明>|<类型说明>|<变量说明>二.语句的设计<常量说明>→const<标识符>=<常量><类型说明>→type

<类型名>=<用户定义类型><变量说明>→var<变量表>：<类型><变量表>→<变量>|<变量表>，<变量><类型>→

int|real|char|boolean|<类型名>

<变量>→<标识符><类型名>→<标识符><执行语句>→<赋值语句>|<控制语句>|

<复合语句>|<I/O输出语句><赋值语句>→<变量>:=<表达式>

<控制语句>→<顺序>|<选择>|<重复>针对面向的问题选择一个方案

2.执行语句<复合语句>→begin<语句表>end<语句表>→<执行语句>|<执行语句表>；<执行语句><I/O输出语句>→read(<变量>)|write(<变量>)<程序单元>→<程序单元关键字><程序单元名>(<形参表>)；<程序单元体><程序单元关键字>→procedure|function|…<程序单元名>→<标识符><形参表>→<形参>|<形参表>；<形参>3.程序单元的设计形参可以没有；如果有，可以是变量、数组、过程等，必须说明类型及与实参的绑定方式<程序单元体>→begin<说明部分>;<执行部分>end<说明部分>→<说明语句表><说明语句表>→<说明语句>|<说明语句表>;<说明语句><执行部分>→<执行语句表><执行语句表>→<执行语句>|<执行语句表>;<执行语句><分程序>→begin<说明部分>；

<执行部分>end<说明部分>→<变量说明表>；

<数组说明表>；

<过程说明表>；

<分程序表>

<变量说明表>→<变量说明>|<变量说明表>；<变量说明><数组说明表>→<数组说明>|<数组说明表>；<数组说明><过程说明表>→<过程说明>│<过程说明表>；<过程说明><分程序表>→<分程序>│<分程序表>；<分程序><程序>→<分程序>4.程序的设计5.语言设计实例问题：设计一个极小的语言，求n！ifn<=0thenF:=1elseF:=n*F(n-1)<程序>→<分程序><分程序>→begin<说明语句表>；<执行语句表>end<说明语句表>→<说明语句>|<说明语句表>；<说明语句><说明语句>→<变量说明>|<函数说明><变量说明>→integer<变量><变量>→<标识符><标识符>→<字母>│<标识符><字母>│<标识符><数字><字母>→a│…│z<数字>→0│1│2│3│4│5│6│7│8│9<函数说明>→

integer

function<标识符>(<参数>)；<函数体><参数>→<变量><函数体>→begin<说明语句>；<执行语句表>end<执行语句表>→<执行语句>|<执行语句表>；<执行语句><执行语句>→<读语句>|<写语句>|<赋值语句>|<条件语句><读语句>→read(<变量>)<写语句>→write