编译原理 - 陈火旺版 - 第二章

1编译方法中国人民大学信息学院陈文萍2第二章高级语言及其语法描述•高级程序语言:描述算法和计算机实现•不同的应用侧重点不同:数值计算--FORTRAN系统程序设计---C事务处理--COBOLVLSI设计---VHDL人工智能---PROLOG大型嵌入式实时处理---Ada符号处理---SNOBOL3内容•2.1程序语言的定义•2.2高级语言的一般特性•2.3程序语言的语法描述42.1程序语言的定义•程序设计语言：是由一组记号所构成的集合。•语言的定义–语言用户：语言的成分，使用意义–编译程序：语言的规则，语法单位对应的含义•组成部分–语法（Syntax）–语义（Semantics）–语用（Pragmatics）5语法•语法（Syntax）：程序构成的一组规则–词法规则：单词符号的形成规则•单词符号：语言中具有独立意义的最基本的结构–类型：常数，标识符，基本字，算符，界符–例如：字符串100-(8＋a)*0.5100，8：整型常数；0.5：实型常数；-,=,*：算符；(,)：界符•分析工具：正规式和有限自动机6语法–语法规则：语法单位的形成规则•语法单位：比单词符号更大的语法结构–例如：表达式，语句，分程序，函数，过程，程序–分析工具：上下文无关文法7语义•语义（Semantics）定义程序的含义的一组规则–例如：C语句•a=18+b;–分析方法：基于属性文法的语法制导翻译方法•语用（Pragmatics）程序设计技术和语言成分的使用方法8程序的层次结构程序子程序语句表达式数据引用算符函数调用92.2高级语言的一般特性•高级高级语言的分类：按语言范型–强制式语言，应用式语言，基于规则的语言，面向对象的语言•强制式语言：命令驱动，面向语句。一个强制式语言程序由一系列的语句组成，每个语句的执行引起若干存储单元中的值的改变，这种语言的语法形式通常具有如下形式：语句1；语句2；…语句n；例如---C,Fortran,Pascal10应用式语言•注重程序所表示的功能，而不是一个语句接一个语句地执行•程序的开发过程是从前面已有的函数出发构造出更复杂的函数•这种语言通常的语法形式是：Functionn(…function2(function1(data))…)•程序执行：执行一个个函数，得到数据上的变换，最终得到的结果•例如：ML，Lisp11基于规则的语言•程序的执行过程：检查一定的条件，当它满足值，则执行适当的动作。•也称逻辑程序设计语言：基本允许条件是谓词逻辑表达式。•这类语言的语法形式通常为：条件1动作1条件2动作2条件3动作3•例如：Prolog12面向对象的语言•主要特征：封装性，继承性和多态性•例如：C++,JAVA13程序结构•不同的语言，如Fortran,Pascal，Ada，Java–程序结构不同–名字的作用域不同•例如：Pascal的最近嵌套原则procedureP;varx:interger;procedureQ;varx:real;beginx:=1.2;end;beginx:=5;end;14数据类型•数据类型的三要素：属性，值，操作–属性：包括类型和作用域–类型：决定数据可以是什么样的值，允许的运算，计算机内如何表示–作用域：值的有效范围•初等数据类型–数值数据：如整型，实型–逻辑数据：布尔型–字符数据：字符型（字符串型）–指针类型：指向另一种数据类型15数据类型•数据结构：从初级数据定义的复杂（高级）数据–数组•内情向量：便于计算数据元素的地址，包括：维数，各维的上、下限，首地址，数组元素类型等。•例如：Pascal的说明vara:array[1..50]ofchar是一个下标从1至50的字符数组–记录：由已知类型的数据组合而成•例如：Pascal语言中Student:recordname:array[1…20]ofchar;age:integer;id:array[1…8]ofchar;major:integer;classid:integer;end;–字符串，表格，栈，队列•抽象数据类型：数据对象，运算，封装16语句与控制结构•表达式：由操作数和算符组成–例如：x-y,-x–通常的形成规则•变量，常数是表达式•若E1,E2是表达式，θ是二元算符，则E1θE2是表达式•若E是表达式，θ是一元算符，则Eθ或θE是表达式•若E是表达式，则(E)是表达式–算符的优先级17语句•分类：按功能–说明性语句：定义名字的性质–执行性语句：描述程序动作•赋值语句•控制语句–转移语句：goto–条件语句：如if…then…else–循环语句：如while…do–过程调用语句：如call–返回语句：如return•输入/输出语句:如read,write182.3程序语言的语法描述•预备知识•上下文无关文法•语法分析与二义性•形式语言概述19预备知识•符号：可以相互区别的记号（元素）•字母表：符号（元素）的非空有穷集合，用∑表示•符号串：由字母表中的符号组成的任何有穷序列–1.空符号串ε(没有符号的符号串)是上的符号串–2.若x是上的符号串,a是的元素,则xa是上的符号串–3.y是上的符号串,当且仅当它可以由1和2导出。•例如，字母表Σ={a,b}，则ε,a,b,aa,ab,ba,bb,aaa,aab,…都是Σ上的符号串20预备知识•符号串的运算–符号串的长度：符号串中符号的个数.•符号串s的长度记为|s|，ε的长度为0–连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy•如x=ab,y=cd则xy=abcd•有εa=aε–方幂：符号串自身连接n次得到的符号串an定义为aa…aa（n个a）a1=a,a2=aaa0=ε21预备知识•符号串的集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。•∑*：表示∑上的所有符号串的全体•空集：φ，不含任何元素•符号串集合的运算：–积（连接）：两个符号串集合A和B的积定义为AB=xy|xA且yB例如：集合A=ab,cdeB=0,1，则AB=ab1,ab0,cde0,cde1–闭包：V*=V0V1V2V3...,Σ*称为Σ的闭包•V0=ε22预备知识•正则闭包：V+=V1V2V3...,–V*=V+ε，–Σ+称为Σ的正闭包。例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}23上下文无关文法•语言的表示–语言有穷：将句子逐一列出–语言无穷：找出语言的有穷表示，两个途径：•生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。•识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”；若不属于，要么能停止并回答“不是”，要么永远继续下去24上下文无关文法•文法：描述语言的语法结构的形式规则。–形式数学系统：可由下列基本成分来刻画：一组基本符号，一组形成规则，一组公理，一组推理规则•上下文无关文法：所定义的语法范畴完全独立于语法范畴可能出现的环境。–例如：语法规则：句子→主语谓语宾语主语→代词谓语→动词宾语→冠词名词代词→I动词→am冠词→a名词→student25上下文无关文法•分析句子：Iamastudent〈句子〉主语谓语宾语代词谓语宾语I谓语宾语I动词宾语Iam宾语Iam冠词名词Iamastudent语法树：如右图Iamastudent.代词动词冠词名词主语谓语宾语句子26上下文无关文法•四个组成部分：四元式（VT,VN,S,P）–终结符号：VT,不可再分的基本符号，如基本字、标识符、常数、算符、界符等词法符号。–非终结符号：VN,语法范畴，表示类记号，不是个体记号。•VN和VT不含公共的元素，即VN∩VT=φ,•用V表示VN∪VT，称为文法G的字母表或字汇表–开始符号：S,特殊的非终结符号，至少要在一条产生式中作为左部出现。–产生式：P，定义语法范畴的一种书写规则。•形如→或∷=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。•例如：E→i|E+E|E*E|(E)•候选式27上下文无关文法•举例–文法G=（VN，VT，P，S）VN={S},VT={0,1}P={S→0S1,S→01}S为开始符号•习惯上只将产生式写出，并有如下约定：–第一条产生式的左部是开始符号–用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符–G可写成G[S]，S是开始符号G：S→aAbA→abA→aAbA→εG[S]：S→aAbA→abA→aAbA→ε缩写形式G[S]：S→aAbA→ab|aAb|ε28上下文无关文法•直接推出：“”–定义：α→β是文法G的产生式，若有v,w满足：v=γαδ,w=γβδ,其中γ,δ∈（VT∪VN），则称v直接推出到w,记作vw•推导：若存在vw0w1...wn=w,(n0)，则称此序列为v到w的一个推导记为–：经过至少一步推导–：经0步或若干步–推导每前进一步总是引用文法中的一个产生式•若有则或v=wn，或nwv*nwvnwvnwv*29上下文无关文法•句型对文法G，若，则称α是文法G的句型。•句子有文法G，若，且α∈VT*，则称α是文法G的句子。例：G：S→0S1，S→01S0S100S11000S11100001111G的句型：S,0S1,00S11,000S111,00001111G的句子：00001111,01•由文法G生成的语言记为L(G),它是文法G的一切句子的集合:*S}&|{)(*TVSGL*S30上下文无关文法•例：文法G:S→AB，A→aA|a，B→bB|b从开始符号出发，可以推出如下句子：……所以，最左推导：任何一步推导，都对右部最左非终结符进行替换最右推导：任何一步推导，都对右部最右非终结符进行替换abABSaabaaBaABABSabbabBaBABS}1,|{)(nmbaGLnmabbAbbAbBABS31思考1，文法G：S→0S1，S→01，L(G)？2，文法G[S]：（1）S→aSBE（2）S→aBE（3）EB→BE（4）aB→ab（5）bB→bb（6）bE→be（7）eE→eeL(G)？32上下文无关文法•已知语言描述，写出文法–例：若语言由0、1符号串组成，串中0和1的个数相同，构造其文法G(A)•A→0B|1CB→1|1A|0BBC→0|0A|1CC33上下文无关文法•文法G1[A]：A→DB与G2[S]：S→0S1A→DES→01E→ABD→0B→1•文法的等价：若L（G1）=L（G2），则称文法G1和G2是等价的。34语法分析树•语法分析树：句型推导的直观方法文法：，推导（i*i+i)E→i|E+E|E*E|(E)EE）（＋EEEE*iiEE）（*EEEE+iiii35语法分析树•给定文法G，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树满足下列4个条件：1、每个结点都有一个V中的符号作标记2、根的标记是开始符号S3、若一结点n至少有一个子孙，并且n有标记A，则A∈VN4、如果结点n的直接子孙，从左到右的次序是结点n1,n2,…,nk，其标记分别为A1,A2,…,Ak，那么A→A1A2,…,Ak一定是P中的一个产生式36二义性•文法的二义性：一个文法存在某个句子对应两个不同的语法树，或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。–上例中，句型（i*i+i）的两个不同的最左推导：•推导1：E（E）（E+E）（E*E+E）（i*E+E）（i*i+E）（i*i+i）•