资源描述：
《编译原理复习资料》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1编译程序的结构：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、表格管理程序+出错处理程序。2符号串：由字母表S中的符号组成的任何有穷序列称为该字母表上的符号串。（顺序）。3符号串集合：若集合A中所有元素都是某字母表S上的符号串，则称A为字母表S上的符号串集合。4文法的类型：0型文法：对任一产生式α→β，都有α∈(VN∪VT)+，且至少有一个非终结符，β∈(VN∪VT)*1型文法(CSG,context-sensitive)：对任一产生式α→β，都有
2、β
3、≥
4、α
5、，仅仅S→ε除外2型文法(CFG,co
6、ntext-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句型推导：最左
7、推导：替换α中的最左非终结符。最右推导（规范推导）：替换α中的最右非终结符；其逆过程称为规范规约。例：G[E]:E→i
8、E+E
9、E*E
10、(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在语言的编译实现中，把完成句
11、型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。9分析算法可分为：自上而下分析法从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。自下而上分析法从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。10在分析程序工作中，从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。11句型的短语S->αAδ且A->β，则称β是句型αβδ相对于非终结符A的短
12、语。句型的直接短语若有A->β，则称β是句型αβδ相对于非终结符A的直接短语。句型的句柄一个句型的最左直接短语称为该句型的句柄。12有关文法的实用限制：文法中不含有有害规则和多余规则。有害规则：形如U→U的产生式（会引起文法的二义性）多余规则：指文法中任何句子的推导都不会用到的规则。文法中不含有不可到达和不可终止的非终结符1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。13词法分析的主要任务：读源程序，产生单词符号。14单词符号一
13、般可分为下列五种：关键字、标识符、常数、运算符、界符。输出表示：（单词种别，单词自身的值）、（标识符，指向该标识符所在符号表中位置的指针）。15例题：16一个有穷自动机可以通过消除无用状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。17确定的自顶向下分析思想：确定的自顶向下分析文法：它是从文法的开始符号出发，考虑如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符以往下推导，或如何构造一棵相应的语法树。18First(α)={a
14、α->aβ，a∈VT，α,β∈V*}，若α->ε,则规定ε∈F
15、irst(α)。Follow(A)={a
16、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
17、bC,A->b
18、ε,B->aD
19、ε,C->AD
20、b,D->aS
21、c.1)求出能推出ε的非终结符：S、A、B2)计算First集:First(S)={First(A)-{
22、ε}}∪{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}每个产
