编译原理第04章

第四章程序语言的设计第2章和第3章分别讨论了程序设计语言的数据类型和控制结构，分别描述程序的数据结构和算法。本章介绍语言的设计方法。第一节语言的定义语言＝语法(规则)＋语义(规则)语法:用以构造程序及其成分(语法单位)的规则的集合语义:用以规定语法正确的语法单位的含义的规则的集合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|…|nxN2n1b1b2bm→b1b2…bmgb→b|g若一个终结符序列是合法的，那么,必须从语法图的入口边通过语法图而到达出口边，而且在通过的过程中,恰恰能识别该终结符序列。②识别原则③语言语法图能识别的所有终结符序列的集合。称为语言。Ⅰ.终结符框Ⅱ.非终结符框Ⅲ.分支、回溯参见图4-6~9字母字母数字标识符图4-6标识符表达式运算符表达式()表达式图4-9表达式高级语言语法规则的描述方法FORTRAN采用自然语言描述语法；ALGOL60首次用BNF对语法进行形式描述,为语言定义做出了重要贡献；Pascal首次采用语法图来定义语言，给出了较为直观的语法结构。语法描述方法等价文法和语法图是语言语法的等价表示文法从产生的观点来定义语言的语法，更通用、更准确。语法图以识别的观点定义语言的语法，更直观、更清晰。采用生成的方法还是采用识别的方法来定义语言由语言的设计者确定。①表达语言设计者的意图和设计目标；②指导语言的使用者编写正确的程序；③指导语言的实现者编写语法检查程序来识别所有语法单位。4.语法描述的用途1.语义（规则）定义语言的语法单位的作用和意义的规则组合。例：if(ab)thenmax:=aelsemax:=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.文法的形式定义产生式是一个有序偶对(，b)记为::=b或→b和b是由终结符、非终结符组成的串且至少应含有一个非终结符。即V*VNV*bV*其中V=VT∪VN产生式的简化→b1→b2…→bn→b1|b2|…|bn约定英文大写字母表示非终结符；第一个产生式的左边符号仅有1个即开始符号文法的表示描述文法，直接给出产生式集合即可。例算术表达式文法G0:E→E+T|E+T|TT→T*F|T/F|FF→(E)|i①0型文法→b②1型文法(上下文有关文法)|α|=|β|（S→例外）2.文法的分类→b③2型文法(上下文无关文法)A→b④3型文法(正则文法,右线性文法)A→u或A→wB其中uVT*，wVT+1.推导与归约①直接推导:wαwβ即由产生式右边替换产生式左边②推导:α1*αn、α1+αn二.文法产生的语言E→E+E│E*E│(E)│ii+i*i的（其中一种）最左推导过程已知G(E)EE+Ei+Ei+E*Ei+i*Ei+i*i最右推导（规范推导）EE+EE+E*EE+E*iE+i*ii+i*iEE*EE*iE+E*iE+i*ii+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|STT→L|DL→a|b|...|zD→0|1|2|...|9G2(I):S→aS|aPP→bP|bQQ→cQ|cL(G3)={aibjck│i,j,k1}G3(S):S→aSBC|aBCCB→BCaB→abbB→bbbC→bccC→ccL(G4)={anbncn│n0}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函数说明→integerfunction标识符(参数)；函数体参数→变量函数体→begin说明语句表；执行语句表end执行语句表→执行语句|执行语句表；执行语句执行语句→读语句|