编译原理复习提纲.doc

编译原理复习提纲第一章：概述考点1 编译程序的地位：系统软件2 编译程序和解释程序的根本区别：是否生成目标代码3 源程序的执行过程：两种形式4 编译程序的6个工作：词法分析、语法分析、语义分析、代码生成(4个必须完成)、中间代码生成、代码优化5 编译程序的每个工作阶段的主要任务6 编译程序的几种常用开发技术P13题型填空、判断、问答第二章：文法和形式语言考点1 基本概念：文法和语言、BNF表示法、推导和归约、规范推导(最右推导、最左归约)、句型、句子和语言2 写出句子或句型的最左推导和最右推导的过程，P54的2.5题3 给定文法，写出由此生成的语言，P55题2.8，2.114 给定语言，写出相应的文法，P55题2.7，2.9，2.105 根据句子或句型，画出语法树，求短语、简单短语和句柄6 证明文法的二义性，由句子或句型画出2棵不同的语法树，由此证明文法是二义性的。P55题2.167 可推出符号和活的非终结符，化简为等价文法。P56题2.198 文法和语言的分类：4种，了解包含关系，1型文法不允许空规则，2型(上下文无关文法)和3型(正则文法)文法的产生式的基本规则9 由正则表达式写出正则集。P56题2.2310将正则文法转换成正则式题型填空、判断、综合题例题1写出由GS S:=aSb|P P:=bPc|bQc Q:=Qa|a生成的语言解：L(GS)=ai bj ak cj bii0， j 1， k 13写出由文法GS S:=Aa|A:=Aa|Sb|a 转换成的正则表达式。解：A:=Aa|Aab|b|a =A(a|ab)|(b|a) =(b|a) (a|ab)*代回（1）得：S=(b|a) (a|ab)*a|第三章：自动机考点1 状态转换图的概念：描述有限自动机的工作状态，用于识别一定的符号串。2 有限自动机的分类：DFA和NFA3 DFA：初始状态仅有一个，单值映射4 已知语言，画出DFA。P79题3.55 已知DFA写出对应的语言。P61例题6 NFA：初始状态可以有多个，多值映射7 用子集法将NFA转换为DFA：改造(如果需要的话)使其仅有一个初态和一个终态，构造状态集的转换表，重新为状态编号，得到DFA8 自动机的简化：分割法9 由正则表达式，设计相应的最小DFA。三个步骤：由三个分裂规则画出NFA；确定化得到DFA；DFA的化简。P79题3.8题型填空、判断、综合题例题构造一个DFA M，它接受字母表=a,b,c上，以a或b开始的字符串，或以c开始但所含的a不多于一个的字符串解：1b cc b ac b023bacaca第六章：语法和语义分析考点1 求首符号集(对符号串)、向前看集(对非终结符)、可选集(对规则)2 语法分析方法分类：自顶向下分析和自底向上分析3 自顶向下分析法：回溯问题和左递归带来的无限循环问题4 消除文法的左递归的方法5 LL(1)分析法：含义：第一个“L”：从左到右扫描源程序，第二个“L”：最左推导，“1”：向前看1个符号，即查看输入串的当前符号6 LL(1)文法的概念：对于文法GS，其每个非终结符号的不同规则具有不相交的可选集Select，不含左递归7 自底向上分析法：移进-归约冲突和归约-归约冲突8 简单表达式的逆波兰表示法，P159题6.7，注意运算符的优先级，单目减运算符的优先级高于乘方、乘除运算 题型填空、判断、综合题例题1证明文法GS SBA ABSd BaAbSc是LL(1)文法解：对每个规则求其select集Select (SBA)=First(BA)=a,b,cSelect (ABS)=First(BS)=a,b,cSelect (Ad)=First(d)=dSelect (BaA)=First(aA)=aSelect (BbS)=First(bS)=bSelect (Bc)=First(c)=c因为该文法不含左递归规则；且文法中每一个非终结符号S，A，B的各个规则的可选集两两不相交 第八章：LR(k)分析法考点1 LR分析法的分析过程2 LR(0)、SLR(1)、LR(1)文法的判断，由状态描述序列中每个状态的项目集是否存在冲突，冲突能否解决来判断3 由状态描述序列得LR(1)分析表4 对句子进行LR(1)分析，写出分析过程题型综合题例题P224题8.3、8.6第九章：中间语言考点1 中间代码生成的目的：便于代码优化和便于目标程序的移植2 逆波兰表示法3 四元式表示法4 三元式表示法5 树表示法题型综合题例题P237题9.2、9.3将下面程序段分别用逆波兰、四元式表示Begin i:=1 10: if i=100 then Begin s:=s+i; i=i+1; goto 10 endend四元式表示：(1) (block , / , / , / )(2) (:= , 1 , / , i )(3) (=, i , 100 , t1)(4) (FJ , 8 , t1 , / )(5) (+ , s , i , s )(6) (+ , i , 1 , i )(7) (RJ , 3 , / , / )(8) ( )(9) (blockend, / , / , / )逆波兰表示：(1) block(2)