编译原理

编译原理讲义什么是编译把高级语言程序翻译成等价的低级语言的过程。Thisistrialversion解释程序解释程序由总控程序和各类指令或语句的解释函数组成，它按照源程序的逻辑流程，直接解释执行源程序或源程序的内部形式。•编译技术和解释技术的结合;•纯碎的解释和纯碎的编译是两个极端情况,很少使用它们;•采用哪一种处理方式，是由被实现的语言和实现环境（在什么计算机系统上实现）两者决定的;•编译:C、C++、FORTRAN、PASCAL和ADA•解释:LISP、ML、Prolog和Smalltalk•Java不象LISP，而更象C++，但由于Java运行在网络环境上，解释方式.•发展趋势:尽量采用编译技术.Thisistrialversion编译器各阶段的工作源程序：main（）{inta,b,c;read(b,c);a=b+c*60;printf(“%d”,a);}经词法分析源程序被加工成单词流……….保留字，int标识符，a……标识符，a算符，=标识符，b算符，+标识符，c算符，*常数，60……赋值语句经语法分析生成分析树Thisistrialversion=inttoreal(60);temp2=c*temp1;temp3=b+temp2;a=temp3;Thisistrialversion变量real1d+81.7错误的诊查处理编译程序在各个阶段应诊断和报告源程序中的错误，包括词法错误，语法错误，语义错误。编译程序应报告出错地点，并给出简明准确的提示信息。编译程序（器）的组织：把前端组织成一遍扫描Thisistrialversion编译器的设计„首先研究源程序的语法和语义及运行模型，源是设计编译程序的出发点。„研究目标计算机，设计目标代码的指令系统，它是由目标计算机扩充而成，扩充后的计算机称作抽象计算机。目前的通用计算机往往和源语言执行模型不一致。„设计编译程序由几遍完成，每遍的工作等。2程序语言语法的形式定义2.1字母表和符号串字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如:计算机语言：由符号“0”和“1”组成的字母表,∑={0，1}。ASCII字符集。Thisistrialversion由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作字。符号串的运算1）连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2）方幂：x0=ε；x1=x；x2=xx；……;；xn=xn-1x例如,x=ba,x1=ba,x2=baba,x3=bababa,…...符号串集合(语言）的运算设L和M是两个符号串集合，则:1）合并：L∪M＝｛s|s∈Lors∈M}2）连接：LM＝｛st|s∈Landt∈M}3）方幂：L0={ε}，L1＝L，L2＝LL,...,Ln＝Ln-1L4）语言L的Kleene闭包，记作L*，L*＝∪Li(i=0)=L0∪L1∪L2∪L3∪…5）语言L的正闭包，记作L+（L+＝LL*）L+＝∪Li(i=1)=L1∪L2∪L3∪L4∪…例：L={A~Z,a~z}D={0~9}1）L∪D={A~Z,a~z,0~9}2）LD是由所有用一个字母后跟一个数字组成的符号串所构成的集合。3）L4是由所有的四个字母的符号串构的集合。4）L（L∪D)*是由所有的字母打头的字母和数字组成的符号串所构成的集合。5）D+是由所有的长度大于等于1的数字串所构成的集合。2.2文法和语言的定义2.2.1引子分析：Thegreywolfwilleatthegoat为了进行机械分析，“句子由主语后跟随谓语组成”表示为：句子→主语谓语（1）主语→冠词形容词名词（2）冠词→the形容词→grey谓语→动词直接宾语（5）动词→助动词动词原形（6）助动词→will动词原形→eat直接宾语→冠词名词（9）名词→wolf名词→goat句子的语法有四部分：终结符号集，非终结符号集，开始符号，语法规则。终结符号集VT={the，grey,wolf,will,eat,goat}非终结符号集VN={句子，主语，谓语，冠词，形容词，名词，动词，直接宾语，助动词，动词原形}开始符号S=句子语法规则集P={句子→主语谓语,……}句子根据规则推导出来句子⇒主语谓语⇒冠词形容词名词谓语⇒the形容词名词谓语⇒thegrey名词谓语⇒thegreywolf谓语⇒thegreywolf动词直接宾语⇒…...⇒thegreywolfwilleatthegoatThisistrialversion合符语法且合符语义的句子仅是：thegreywolfwilleatthegoat2.2.2文法和语言的定义文法的定义G=（VT,VN,S,P），其中：VT是一个非空有穷终结符号集合；VN是一个非空有穷的非终结符号集合，且VT∩VN＝Φ；S∈VN，称为开始符号。P={A→α|A∈VN，α∈(VT∪VN）*}S必须在某个产生式的左部至少出现一次。产生式或写成A::＝α。缩写形式：A→α1|α2算术表达式的文法G:G=({a,+,*,(,)},{表达式，项，因子}，表达式，P)P：表达式→表达式＋项⏐项项→项*因子⏐因子因子→(表达式)⏐aE→E+T⏐TT→T*F⏐FF→(E)⏐a(2.1)推导定义直接推导和推导的定义:令G=(VT,VN,S,P),若A→γ∈P,且α,β∈(VT∪VN)*,则称αAβ直接推出αγβ,表示成αAβ⇒αγβαAβ直接推出αγβαγβ直接归约到αAβ如果存在一个直接推导序列：α0⇒α1⇒α2⇒…⇒αn（n＞0）例：E⇒E+T⇒T+T⇒F+T⇒a+T⇒a+F⇒a+a语言的定义设文法G＝（VT，VN，S,P）。如果Sα,则称α是一个句型。仅含终结符号的句型是一个句子。语言L(G）是由文法G产生的所有句子所组成的集合：L(G)＝{α|Sα且α∈VT*}考虑一个文法G＝({a,b},{S},S，P）其中，P：S→aSb⏐abS⇒aSb⇒aaSbb⇒a3Sb3⇒……⇒an-1Sbn-1⇒anbn2.2.3昀左推导和昀右推导对于w和G,w∈L(G)？是否存在Sw，如何构造这个推导?例如，G[E]（例2.2）和w=a+a*aE⇒E+T⇒T+T⇒F+T⇒a+T⇒a+T*F⇒a+F*F⇒a+a*F⇒a+a*a（昀左）特点：αAβ⇒βγα(Aγ→)，∈αVT*E⇒E+T⇒E+T*F⇒E+T*a⇒E+F*a⇒E+a*a⇒T+a*a⇒F+a*a⇒a+a*a特点：αAβ⇒βγα(Aγ→)，β∈VT*（昀右）Thisistrialversion[S]是一个文法，如果有SαAδ且Aβ则称β是一个关于非终结符号A的，句型αβδ的短语。其次如果有SαAδ且A⇒β则称β是直接短语。一个句型的昀左直接短语称为该句型的句柄。例：文法（2.1）的一个句型a1*a2+a3，尽管有Ea2＋a3，但是a2＋a3并不是该句型的一个短语,因为不存在Ea1*E。短语：a1,a2,a3，a1*a2,a1*a2+a3直接短语:a1，a2,a3句柄:a12.4分析树和二义性分析树的定义设G=（VT，VN，S，P）,G的一棵分析树满足如下条件：1.每个结点用VT∪VN∪{ε}中的一个符号作标记。2．根的标记是S。3．如果一个结点是内部结点，且有标记A,那么A必在VN中。4．如果编号为n的结点有标记A,结点n1,n2,…,nk是点n的从左到右的儿子，并分别有标记X1,X2,…,Xk，则A→X1X2…Xk∈P。5.如果结点n有标记ε，那么结点n是叶子，且是它父亲唯一的儿子。例G=(VT,VN,S,P),其中P:S→aAS⏐aA→SbA⏐SS⏐ba如何画出分析树(自顶向下）根据推导序列，对每步推导画相应分枝如何画出分析树(自底向上）根据归约序列，对每步归约画相应分枝关于分析树的几点说明Thisistrialversion一个句型推导或分析用一棵树结构图示出来，它反应了一个句子语法结构的层次。2.对于一个句子的多种推导（若文法是无二义性的），采用各种推导过程，画出的分析树是一样的。分析树并未描述推导过程。3.在书中，用画分析树的过程解释语法分析过程，用分析树图解语法结构。分析树是推导的形表示。图子树:一棵分析树中一个特有的结点连同它的全部后裔，连接这些后裔的边以及这些结点的标记。用子树解释短语，直接短语，句柄:短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中昀左昀下那棵只有父子两代的子树的所有叶子的自左至右排列。例如，对表达式文法G[E]和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。Thisistrialversion文法的二义性的定义描述一个句子的文法不是唯一的；对于一个句子的分析应是唯一的。考虑表达式下面的文法G[E],其产生式如下：E→E+E⏐E*E⏐(E)⏐a对于句子a+a*a,有如下两个昀左推导：E⇒E+E⇒a+E⇒a+E*E⇒a+a*E⇒a+a*aE⇒E*E⇒E+E*E⇒a+E*E⇒a+a*E⇒a+a*aThisistrialversion二义性（或歧义性，ambiquity)的定义:如果一个文法的句子存在两棵分析树,那么,该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的;否则，该文法是无二义性的。几点说明：1.一般来说，程序语言存在无二义性文法，对于表达式来说，文法（2.1）是无二义性的。2.在能驾驭的情况下，经常使用二义性文法(简单）。对于条件语句，经常使用二义性文法描述它：S→i