编译原理复习资料

1编译程序的结构：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、表格管理程序+出错处理程序。2符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。（顺序）。3符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。4文法的类型：0型文法：对任一产生式α→β，都有α∈(VN∪VT)+，且至少有一个非终结符，β∈(VN∪VT)*1型文法(CSG,context-sensitive)：对任一产生式α→β，都有|β|≥|α|，仅仅S→ε除外2型文法(CFG,context-free)：对任一产生式α→β，都有α∈VN，β∈(VN∪VT)*3型文法(RG,regular)：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN，B∈VN，a∈VT5上下文无关文法满足下列4个条件：1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定A∈VN4.如果结点n有标记A，其直接子孙结点从左到右的次序是n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一个产生式6句型推导：最左推导：替换α中的最左非终结符。最右推导（规范推导）：替换α中的最右非终结符；其逆过程称为规范规约。例：G[E]:E→i|E+E|E*E|(E)句型i*i+i的语法树？推导1：E=E+E=E*E+E=i*E+E=i*i+E=i*i+i推导2：E=E*E=i*E=i*E+E=i*i+E=i*i+i二义文法：若一个文法存在某个句子对应两棵不同的语法树（有两个不同的最左/最右推导），则称这个文法是二义的。消除二义性：优先级、结合性。7句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。8在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。9分析算法可分为：自上而下分析法从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。自下而上分析法从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。10在分析程序工作中，从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。11句型的短语S->αAδ且A->β，则称β是句型αβδ相对于非终结符A的短语。句型的直接短语若有A->β，则称β是句型αβδ相对于非终结符A的直接短语。句型的句柄一个句型的最左直接短语称为该句型的句柄。12有关文法的实用限制：文法中不含有有害规则和多余规则。有害规则：形如U→U的产生式（会引起文法的二义性）多余规则：指文法中任何句子的推导都不会用到的规则。文法中不含有不可到达和不可终止的非终结符1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。13词法分析的主要任务：读源程序，产生单词符号。14单词符号一般可分为下列五种：关键字、标识符、常数、运算符、界符。输出表示：（单词种别，单词自身的值）、（标识符，指向该标识符所在符号表中位置的指针）。15例 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ：16一个有穷自动机可以通过消除无用状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。17确定的自顶向下分析思想：确定的自顶向下分析文法：它是从文法的开始符号出发，考虑如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符以往下推导，或如何构造一棵相应的语法树。18First(α)={a|α->aβ，a∈VT，α,β∈V*}，若α->ε,则 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 ε∈First(α)。Follow(A)={a|S->μAβ且a∈VT，a∈First(β)，μ∈VT*，β∈V+}　若S->μAβ且β->ε，则＃∈Follow(A)。19LL(1)文法的充要条件是，对每个非终结符A的两个不同产生式，Aα，Aβ，满足Select(Aα)∩Select(Aβ)＝Ф，其中α、β不能同时->ε。例：若文法G【S】：S->AB|bC,A->b|ε,B->aD|ε,C->AD|b,D->aS|c.1)求出能推出ε的非终结符：S、A、B2)计算First集:First(S)={First(A)-{ε}}∪{First(B)-{ε}}∪{ε}∪{b}={b,a,ε}First(A)={b}∪{ε}={b,ε}First(B)={ε}∪{a}={a,ε}First(C)={First(A)-{ε}}∪First(D)∪First(b)={b,a,c}First(D)={a}∪{c}={a,c}每个产生式的右部符号串的开始符号集合为：First(AB)={a,b,ε}First(bC)={b}First(ε)＝{ε}First(b)＝{b}First(aD)={a}First(AD)={a,b,c}First(b)={b}First(aS)={a}First(c)={c}3)计算Follow集:Follow(S)={#}∪Follow(D)Follow(A)=(First(B)－{ε})∪Follow(S)∪First(D)Follow(B)=Follow(S)Follow(C)=Follow(S)Follow(D)=Follow(B)∪Follow(C)由以上最终计算结果得：Follow(S)={#}Follow(A)={a,#,c}Follow(B)={#}Follow(C)={#}Follow(D)={#}4)计算Select集:Select(S→AB)=(First(AB)－{ε})∪Follow(S)={b,a,#}Select(S→bC)=First(bC)={b}Select(A→ε)=(First(ε)－{ε})∪Follow(A)={a,c,#}Select(A→b)=First(b)={b}Select(B→ε)=First(ε)∪Follow(B)={#}Select(B→aD)=First(aD)={a}Select(C→AD)=First(AD)={a,b,c}Select(C→b)=First(b)={b}Select(D→aS)=First(aS)={a}Select(D→c)=First(c)={c}20计算Follow集(a)设S为文法中开始符号，把{#}加入Follow(S)中(这里“#”为　句子结束标志)(b)若A→αBβ是一个产生式，则把First(β)的非空元素加入　Follow(B)中。　如果β　ε则把Follow(A)也加入Follow(B)中(c)反复使用(b)直到每个非终结符的Follow集不再增大为止21某些非LL(1)文法到LL（1）文法的等价变换：提取左公共因子、消除左递归（转成右递归）。22预测分析器的组成：预测分析程序、先进后出栈、预测分析表。23构造步骤：(1)判断文法是否为LL(1)文法。文法中含左递归，先消除左递归。(2)构造预测分析表。24自底向上分析（移进－归约分析），自左向右扫描输入符号串，边移入边分析。移进：将当前单词压入栈；归约：栈顶符号串形成句柄时归约到相应非终结符；25优先分析法可分为：简单优先分析法、算符优先分析法。算符优先分析法：只考虑终结符之间的优先关系，它不是规范归约。26算符优先文法：性质1　在算符文法中任何句型都不包含两个相邻的非终结符。性质2　如果Ab(或bA)出现在算符文法的句型γ中，其中A∈VN，b∈VT，则γ中任何含此b的短语必含有A。27最左素短语：设有文法G[S]，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他素短语，最左边的素短语称最左素短语。28自底向上分析有算符优先分析、LR类分析。294种LR类型：LR(0)、SLR(1)、LALR(1)、LR(1)（范围最大）。30LR分析：根据当前分析栈中的符号串和向右顺序查看输入串的k个(k≥0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，是一种规范归约过程。31动作：移近、归约、接受acc、报错。32（1）如果b是A的一个属性，c1,c2,…,ck是产生式右部文法，符号的属性或A的其他属性，则称b是A的综合属性。（2）如果b是产生式右部某个文法符号X的一个属性，并且c1,c2,…,ck是A或产生式右边任何文法符号的属性，则称b是文法符号X的继承属性。33综合属性沿属性语法树向上传递；继承属性沿属性语法树向下传递。34采用单表结构时,下推链域的构造用来处理解决分程序构造中同名标识符声明的可视性规则，采用分表结构不存在下推问题。分表结构很适合基于对象的语言的编译系统。35存储区划分成：目标区、静态数据区、栈区、堆区：36数据空间的使用和管理 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 分成三种：静态存储分配、栈式动态存储分配、堆式动态存储分配。37优化：对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少，或两者都有（即：提高时空效率）。38依据优化所涉及的范围分为：局部优化、循环优化、全局优化。