编译原理复习

《编译原理》复习绪论主要内容：翻译、编译、目标语言和源语言这几个概念的理解。编译的总体过程：词法分析，语法分析、语义分析与中间代码的生成、代码优化、目标代码的生成，以及伴随着整个过程的表格管理与出错处理。思考：编译过程主要包括五个阶段，每个阶段的主要任务是什么？编译程序是否都需要实现这五个阶段？（不需要，只有词法分析、语法分析、语义分析和目标代码生成是必要的，而中间代码生成和代码优化并不是必须的。）编译方式与解释方式有什么异同？编译方式和解释方式都对源程序进行了翻译，只是前者相当于实际生活中的笔译，而后者相当于口译。虽然有些解释程序对源程序进行了某些形式上的转换，但最终并没有生成目标代码。因此两者的根本区别在于是否生成目标代码，而不是是否进行了翻译。文法和语言主要内容：与文法相关的概念：字母表，符号及符号串、闭包和正闭包，连接，空集，产生式，推导，直接推导，归约，句子，句型，句柄，，语法树，语言，最左推导，最右推导（规范推导），文法的递归等。文法的定义：文法是一个四元组：（终结符号集，非终结符号集，开始符号、产生式集）。用文法来描述语言及通过文法能分析该文法所描述的语言。二义性的概念、能通过画语法树来分析一个文法描述的语言是否具有二义性。Chomsky对文法和所对应语言的分类。特别是上下文无关文法的定义和正规文法的定义。能判断一个语言的文法是哪一类文法。思考：已知文法G1=({A,B,C},{a,b,c},P,A)，其中P由以下产生式组成：A→abcA→aBbcBb→bBBc→CbccbC→CbaC→aaBaC→aa此文法所表示的语言是什么？此文法所描述的语言是{anbncn|n>0}。构造描述语言L(G[S])={(n)n|n≥0}的文法。过程：（1）找出该语言的一些典型的句子。（2）分析句子的特点。（3）凑规则。（4）写文法。（5）验证。最后构造的文法是G[S]:S→(S)|ε构造描述某种子语言，比如十进制带符号的整常数、C语言的标识符等的文法。设有文法G[S]:S→a|ε|(T)T→T,S|S给出句子(a,(a,a))的最左、最右推导。已知文法G[E]:E→T|E+T|E-TT→F|T*F|T/FF→(E)|i该文法的开始符号（识别符号）是什么？给出该文法的终结符号集合VT和非终结符号集合VN。找出句型T+T*F+i的所有短语、直接短语和句柄。消除该文法的直接左递归。判别一个文法是否有二义性？可以采用什么方法消除二义性？在语法分析中，是否必须消除二义性文法？词法分析主要内容：词法分析程序的任务。单词的类别和单词的输出形式。程序语言中单词符号的分类：比如关键字、标识符、常数、运算符、界符。正规集与正规式,正规式的递归定义。DFA是一个五元组：（状态、字母表、唯一初态、映射关系、终态集）。DFA的表示形式：转换矩阵、状态转换图。状态转换图的相关概念：状态（结点）、初态、终态、接受（识别）。非确定有限自动机（NFA）的定义及NFA与DFA的区别。NFA到DFA的转换：子集构造法（Subset）。DFA的化简。由正规表达式构造确定的有穷自动机的步骤。由状态转换图编写词法分析程序的步骤。1）画出状态转换图。2）将状态转换图看作是通常的程序框图，按如下方法写出相应的词法分析程序：对于状态图中的每一个状态（代表一个非终结符）构造一段代码，代码的功能为从输入串中读一个字符；判明读入的字符与由此状态出发的哪条弧上的标记相匹配，便转至相匹配的那条弧所指向的状态；均不匹配时便失败（不能正常出口）。具体构造程序时，对于不含回路的分叉结点，对应一个switch语句或一组if…then…else语句；含回路的结点，对应一个while和if语句构成的程序段；终态结点对应一个形如return(code,value)的语句，意为返回调用者。思考：如何求一个状态子集的ε闭包？DFA和NFA的区别是什么？3、为正规式(a|b)*a(a|b)(a|b)构造DFA。4、设计一个DFA，其输入字母表是{0,1}，接受以0开始以1结尾的所有序列。5、给出一个文法，写出对应的词法分析程序。第四章语法分析主要内容：语法分析器的功能。自上而下分析法自上而下分析法：从文法开始符号出发，自上而下地为输入串建立一棵语法树，或者说为输入串寻找一个最左推导。自上而下分析面临的问题：左递归（直接左递归和间接左递归）和回溯，如何解决？递归下降分析程序的设计思路。LL（1）分析法的基本思路。首字符集FIRST（A）及后跟字符集FOLLOW（A）的定义求某一文法中各文法符号的首字符集和后跟字符集LL（1）分析的条件：沿某一文法规则进行推导时，可能出现的下一个终结符是唯一的。在实际问题分析中要先求出各个文法符号的FIRST集及FOLLOW集，根据它们之间是否相交来判定是否满足条件。预测分析程序的设计思路。预测分析表的构造方法。自下而上分析法自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号，从输入串的语法树上直观地看就是沿着语法树的底部向上分析归约，最终能到达根结点的就认为当前的输入串能被接受。大部分现代的编译器都采用LR分析作为语法分析的方式。因此本章的学习重点是学习如何构造LR分析表。基本概念：移进、归约、直接短语、句柄、规范归约、规范推导、活前缀、项目集、项目集规范族等。语法分析栈的四个基本动作：移进，归约，接受，出错处理，各表示什么意义，具体如何完成。LR分析法的关键在于如何确定可归约串？进一步如何识别可归约串？由LR（0）的分析的实例理解LR分析的基本过程（即LR总控程序所完成的功能）。理解LR分析表中状态、action、goto的含义。LR（0）项目集族和LR（0）分析表的构造方法。构造识别活前缀的DFA。SLR（1）是基于LR（0）进行优化而形成：通过向前看一个输入字符来扩展LR分析的语法范围。SLR（1）主要是为了解决什么问题？SLR（1）分析表的构造。思考：消除下列文法的左递归G[A]:A→Ba|Aa|cB→Bb|Ab|d设文法G[E]:E→T+E|T-E|TT→F*T|F/T|FF→(E)|i该文法能否直接应用自上而下分析技术来实现其识别程序？说明理由。设法为该文法构造LL(1)分析表，写出构造过程。给出某个文法，求每一个非终结符号的FIRST集合FOLLOW集合。给出一个LR分析表，写出对某个输入串的“移进—归约”的分析过程。LR(0)和SLR(1)分析表的主要区别。有文法G[S]：S→a|b|(T)T→T,S|S（1）试写出产生式T→T,S的所有LR(0)项目。（2）构造CLOSURE({S→(.T)}),并写出它的后继项目集。已知文法G[A]：A→(A)|a构造该文法的以LR(0)项目集为状态的识别活前缀的DFA。构造该文法的LR(0)分析表，该文法是LR(0)文法吗？构造该文法的SLR(1)分析表，该文法是SLR(1)文法吗？8、已知算术表达式文法G[E]:E→E+E|E*E|(E)|i（1）该文法是二义性文法吗？说明理由。（2）若要对其进行语法分析，你准备如何进行处理？（3）若采用LR分析，试构造该文法的LR分析表。它是LR(0)文法吗？它是SLR(1)文法吗？若不是，如何解决？（提示：在不修该文法的情况下，考虑引入运算符的优先级和结合律来解决“移进—归约”冲突。主要侧重理解二义性文法的应用。）第五章语法制导翻译和中间代码的表示主要内容：语法制导翻译的概念。属性文法的相关基本概念：属性，语义规则，综合属性，继承属性，属性文法。属性文法处理的一般过程：对单词符号串进行语法分析，构造语法分析树（注释分析树），然后构造属性依赖图，最后根据需要遍历语法树并在语法树的各结点处按语义规则进行属性的计算或其他处理。中间代码的形式：逆波兰式、三元式、四元式。思考：为什么要使用中间代码形式？简单台式计算器的语法制导定义如下：L→En{Print(E.val)}E→E（1）+T{E.val:=E（1）.val+T.val}E→T{E.val:=T.val}T→T（1）*F{T.val:=T（1）.val´F.val}T→F