资源描述：
《编译原理整理资料》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、名词解释编译：编译程序的翻译过程。词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成.语言：由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)={x
2、S=>*x，其中S为文法的开始符号，且x∈VT*}二义文法：若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。二义语言：如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。属性文法：属性文法(attributegrammar)是一个三元组：A=(G,V,F),其中G:是一个上下文无关文法,V:有穷的属
3、性集,F:关于属性的属性断言或一组属性的计算规则(称为语义规则)。活动记录：一个过程的一次执行所需要的信息，使用一个连续的存储区来管理这个区（块），叫做一个活动记录AR。词法：规定什么是正确的单词，boy不能写成byo等等。语法（文法）：是指一组规则，用它可以形成和产生一个合适的程序。（定义什么样的符号序列是合法的）语义：自然语言中词语的意义，逻辑形式系统中符号的解释。（定义什么样的符号序列是有含义的）句子：有文法G[s]，若S=>*x，且x∈VT*，则称x是文法G的句子。句型：有文法G[s]，若S=>*x，则称x是文法G的句型。语法树：设G=(VN,VT,P,S)为一cfg，若一棵树满足下
4、列4个条件，则此树称作G的语法树。最左/最右推导：在推导的任何一步αÞβ，其中α、β是句型，都是对α中的最左（右）非终结符进行替换。自上而下分析：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。自下而上分析：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。短语：存在文法G[s],S=>*αAδ且A=>+β，则称β是句型αβδ相对于非终结符A的短语。句柄：一个句型的最左直接短语称为该句型的句柄项目：在右端某一位置有圆点的G的产生式语法制导翻译：在语法分析的同时，执行语义规则描述的动作：16回填：一旦真假出口确定下来之后,用顺着
5、真链和假链把真假出口补上.拉链：为了记录需回填地址的四元式,把需要回填的真出口的四元式拉成链,把需要回填家出口的四元式拉成一链,分别称作真链假链.目标程序运行时存储区划分图：简答题：一．给出一个句子的最左，最右推导，语法树。例:G[S]:S→aASA→SbAA→SSS→aA→ba最右推导：SÞaASÞaAaÞaSbAaÞaSbbaaÞaabbaa最左推导：SÞaASÞaSbASÞaabASÞaabbaSÞaabbaa任意推导：SÞaASÞaSbASÞaSbAaÞaabAaÞaabbaa语法树：二.判定文法的类型（0，1，2，3型）：运用知识：文法的类型：通过对产生式施加不同的限制，Choms
6、ky将文法分为四种类型：0型文法：对任一产生式α→β，都有α∈(VN∪VT)+，β∈(VN∪VT)*1型文法：对任一产生式α→β，都有
7、β
8、≥
9、α
10、，仅仅S→ε除外162型文法：对任一产生式α→β，都有α∈VN3型文法：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN，B∈VN，a∈VT*1型文法例：1型（上下文有关）文法文法G[S]：S→CDAb→bAC→aCABa→aBC→bCBBb→bBAD→aDC→aBD→bDD→bAa→bD2型文法例：2型（上下文无关）文法文法G[S]：S→ABA→BS
11、0B→SA
12、13型文法例子G[S]：S→0A
13、1B
14、0A→0A
15、1B
16、0SB→1B
17、1
18、
19、0三．正规式，正规文法，自动机之间的转换正规式到正规文法的转换运用知识：对å上的正规式r,存在一个RG=(VN,VT,P,S)：L(G)=L(r)(R.0)VT=å,SÎVN,生成正规产生式：S®r(R.1)对形如A®r1r2的正规产生式：A®r1BB®r2BÎVN(R.2)对形如A®r*r1的正规产生式：A®rAA®r1(R.3)对形如A®r1½r2的正规产生式:A®r1A®r2不断应用(R.x)做变换，直到每个产生式右端至多有一个VN例子r=a(a½d)*解：(1)S®a(a½d)*(S®r)(2)S®aAA®(a½d)*(A®r1B,B®r2)(3)A®(a½d)A(A®rA,A®r
20、1)A®eG[s]:S®aAAe®VT={a,d}A®aBVN={S,A}A®dB16正规文法到正规式的转换运用知识：对G=(VN,VT,P,S),存在一个å=VT上的正规式r:L(r)=L(G)A®xB,B®y形成正规式A=xyA®xA½y形成正规式A=x*yA®x½y形成正规式A=x½y例子：由NFAM构造正规式r运用知识：从Σ上的一个NFAM，构造Σ上的,一个正规式r，使得L(M)=L(r)的方法。由N
