编译原理复习资料.doc

1 编译程序的结构：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、表格管理程序+出错处理程序。2 符号串：由字母表S中的符号组成的任何有穷序列称为该字母表上的符号串。（顺序）。3 符号串集合：若集合A中所有元素都是某字母表S上的符号串，则称A为字母表S上的符号串集合。4 文法的类型：0型文法：对任一产生式，都有(VNVT)+，且至少有一个非终结符，(VNVT)*1型文法(CSG,context-sensitive)：对任一产生式，都有|， 仅仅 S除外2型文法(CFG,context-free)：对任一产生式，都有VN ， (VNVT)*3型文法(RG,regular)：任一产生式的形式都为AaB或Aa，其中AVN ，BVN ，aVT5 上下文无关文法满足下列4个条件：1. 每个结点都有一个标记，此标记是V的一个符号2. 根的标记是S3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4. 如果结点n有标记A，其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式6 句型推导：最左推导：替换中的最左非终结符。最右推导（规范推导）：替换中的最右非终结符；其逆过程称为规范规约。例：GE:Ei|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有关文法的实用限制： 文法中不含有有害规则和多余规则。有害规则：形如UU的产生式（会引起文法的二义性）多余规则：指文法中任何句子的推导都不会用到的规则。文法中不含有不可到达和不可终止的非终结符1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。13 词法分析的主要任务：读源程序，产生单词符号。14单词符号一般可分为下列五种：关键字、标识符、常数、运算符、界符。输出表示：（单词种别，单词自身的值）、（标识符，指向该标识符所在符号表中位置的指针）。15例题：16 一个有穷自动机可以通过消除无用状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。17确定的自顶向下分析思想：确定的自顶向下分析文法：它是从文法的开始符号出发，考虑如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符以往下推导，或如何构造一棵相应的语法树。18 First()=a | -a ， a VT， , V*，若-,则规定 First()。 Follow(A)=a | S-A且a VT， a First()， VT*， V+ 若S-A且- ，则 Follow(A)。19 LL(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,cFirst(D)=ac=a,c每个产生式的右部符号串的开始符号集合为：First(AB)=a,b,First(bC)=bFirst()First(b)bFirst(aD)=aFirst(AD)=a,b,cFirst(b)=bFirst(aS)=aFirst(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,#,cFollow(B)=#Follow(C)=#Follow(D)=#4)计算Select集:Select(SAB)=(First(AB) Follow(S)=b,a,#Select(SbC)=First(bC)=bSelect(A)=(First() Follow(A)=a,c,#Select(Ab)=First(b)=bSelect(B)=First()Follow(B)=#Select(BaD)=First(aD)=aSelect(CAD)=First(AD)=a,b,cSelect(Cb)=First(b)=bSelect(DaS)=First(aS)=aSelect(Dc)=First(c)=c20 计算Follow集(a)设S为文法中开始符号，把#加入Follow(S)中(这里“#”为句子结束标志)(b)若AB是一个产生式，则把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)出现在算符文法的句型中，其中AVN，bVT，则中任何含此b的短语必含有A。27 最左素短语：设有文法GS，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他素短语，最左边的素短语称最左素短语。28 自底向上分析有算符优先分析、LR类分析。29 4种LR类型：LR(0) 、SLR(1) 、 LALR(1) 、 LR(1)（范围最大）。30 LR分析：根据当前分析栈中的符号串和向右顺序查看输入串的k个(k0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，是一种规范归约过程。31 动作：移近、归约、接受acc、报错。32 （1）如果b是A的一个属性，c1,c2,ck是产生式右部文法，符号的属性或A的其他属性，则称b是A的综合属性。（2）如果b是产生式右部某个文法符号X的一个属性，并且c1,c2,ck是A或产生式右边任何文法符号的属性，则称b是文法符号X的继承属性。33 综合属性沿属性语法树向上传递；继承属性沿属性语法树向下传递。34 采用单表结构时,下推链域的构造用来处理解决分程序构造中同名标识符声明的可视性规则，采用分表结构不存在下推问题。分表结构很适合基于对象的语言