编译原理考题答案(一二三章).doc

第一章 能够完成从一种语言到另一种语言的变换的软件称为翻译器编译器是一种翻译器，他进行语言变换的特点是目标语言比源语言低级编译的各个阶段：字符流-词法分析器-记号流-语法分析器-语法树-中间代码生成器-中间表示-独立与机器的代码优化器-中间表示-代码生成器-目标机器代码-依赖于机器的代码优化器-目标机器代码第二章 语法分析器的任务是把构成源程序的字符流翻译成词法记号流。2.1词法分析是编译的第一阶段，它的主要任务是扫描输入字符流，产生用于词法分析的词法记号序列。完成的其他任务（实验一）其一是剥去源程序的注解和由空格、制表或换行符等引起的空白，另一任务是把来自编译器各个阶段的错误信息和源程序练习起来。2.12词法记号的属性 必考 略2.21 字母表上的串是该字母表符号的有穷序列术语语言表示字母表上的一个串集，属于该语言的串称为该语言的句子或字。如果x和y都是串，那么x和y的链接（xy）是吧y加到x后边形成的串。对连接运算而言，空串是一个恒等元素。表2.2 语言运算的定义 （未打印）例2.2 略2.3 语言的识别器是一个程序，它取串x作为输入，当x是语言的句子时，他回答是，否则回答不是。可以通过构造称为优先自动机的更一般的转换图，把正规式翻译成识别器。有限自动机分为确定的和不确定的两种情况。不确定的含义是：存在这样的状态，对于某个输入符号，它存在不止一种转换。 表2.6 在NFA状态上的运算运算描述E-closure(s)从NFA的状态s出发，只用E转换能到达的NFA状态集合E-closure(T)NFA 状态转换集合s|s属于E-closure(t)并t属于TMove（T,a）NFA的状态集合s|s属于move(t,a)并t属于T(move被拓展成多台函数)NFA转化为DFA 略DFA 化简略课后习题：第三章词 法分析器记 号取下一个记号源程序图3.1 分析器在编译器模型中的位置分析树前端的其余部分分析器分析树符号表3.1 一个上下文无关文法G是一个四元组（Vt,Vn,S,P），其中：Vt是一个终结符集合，Vn是非终结符集合 Vt并Vn=空集 ，S是一个终结符，称为开始符号，P是产生式的有限集合。3.1.2代换句型中最左边非终结符的推导，这样的推导叫做最左推导。最右推导，略。3.14二义性 一个文法如果存在某个句子有不止一颗分析树与之对应，那么称这个文法是二义的。3.2.5 消除二义性。二义文法： stmt if expr then stmt| if expr then stmt else stmt (3.5)| other 非二义文法：stmt matched _stmt | unmatched_stmtmatched_stmt if expr then matched_stmt else matched_stmt | other (3.7)unmatched_stmt if expr then stmt| if expr then matched_stmt else unmatched_stmt 3.2.6消除左递归 左递归产生式AAa |b，可以用非左递归的A b AA a A| e3.2.7 提左因子 如果A ab1 | ab2 原来的产生式成为：A a A A b1 | b2 3.3.2一个文法的符号串a的开始符号集合FIRST(a )是FIRST (a )=a | a * a, a VT 特别是，a * e时，规定e FIRST (a )。如果非终结符A的所有选择的开始符号集合两两不相交，即对A的任何两个不同的选择ai 和aj，有FIRST (ai ) FIRST (aj ) = f非终结符A的后继符号集合FOLLOW(A)是，所有在句型中可以直接出现在A后面的终结符的集合，也就是FOLLOW (A) = a | S * Aa，aVT此外，如果A是某个句型的最右符号，那么属于FOLLOW(A)。如果有产生式AaB或AaBb且b *e，那么FOLLOW(A)的一切元素都要加入FOLLOW(B)中。需要文法的任何两个产生式A a | b都满足下面两个条件：（1）FIRST(a ) FIRST(b ) = f；（2）若b * e ，那么FIRST(a ) FOLLOW( A ) = f。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。3.3.4 非递归的预测分析这个分析器的工作过程如下。预测分析程序根据当前的栈顶符号X和输入符号a决定分析器的动作，它有四种可能：（1）如果X = a =$, 分析器宣告分析完全成功而停机。（2）如果X = a $，分析器弹出栈顶符号X，并推进输入指针，指向下一个符号。（3）如果X是终结符但不是a，则分析器报告出错，调用错误恢复例程。（4）如果X是非终结符，程序访问分析表M，若MX, a是X的产生式，例如，MX, a = X UVW，那么分析器用WVU代替栈顶的X，并让U在栈顶。作为输出，我们假定分析器在这里打印出所用的产生式，当然也可以执行其它代码。如果MX, a指示出错，则分析器调用错误恢复例程。3.3.5算法3.2 构造预测分析表。输入 文法G。输出 分析表M。方法 （1）对文法的每个产生式A a ，执行（2）和（3）。（2）对FIRST (a )的每个终结符a，把A a 加入MA, a。（3）如果e在FIRST(a)中，对FOLLOW(A)的每个终结符b（包括$）, 把A a加入MA, b。3.4.4 它根据栈中所有的内容和下一个输入符号不能决定是移进呢还是归约（移进-归约冲突）, 或不能决定按哪一个产生式进行归约（归约-归约冲突）3.5.1算法3.3 LR分析算法。 输入 LR分析表和输入串w。 输出 若w是句子，得到w的自下而上分析，否则报错。方法 最初，初始状态s0在分析器的栈顶，w$在输入缓冲区，然后分析器执行图3.12的程序，直至碰到接受或出错动作。 让ip指向w$的第一个符号；repeat forever begin令s是栈顶的状态，a是ip指向的符号；if actions, a = 移进s then begin把a 和s依次压入栈；推进ip指向一下输入符号endelse if actions, a = 归约A b then begin栈顶退掉2 * |b | 个符号；令s是现在的栈顶状态；把A和gotos, A 压入栈；输出产生式A bendelse if actions, a = 接受 then returnelse error ( )end例3.29看下面文法：SV = E SE V * E Vid EV 可以把V和E想象成分别代表左值和右值，左值表示一个存储单元，右值是一个可存储的值。*表示“取单元内容”的算符