编译原理课后答案——第九章_小型编译程序介绍课件.pptVIP

第九章 小型编译程序介绍;9.1 小型编译程序结构; 第二阶段为语法分析。语法分析的任务是在词法分析的基础上，根据语言的语法规则(文法规则)把单词符号串分解成各类语法单位(语法范畴)，如“短语”、“子句”、“句子”、“程序段”和“程序”。通过语法分析确定整个输入串是否构成一个语法上正确的“程序”。 第三阶段为中间代码产生。按语言的语义将语法分析出来的语法单位翻译成中间代码。一般而言，中间代码是一种独立于具体硬件的记号系统，但它与计算机的指令形式有某种程度的接近，或者能够比较容易地把它变换成计算机的机器指令。常用的中间代码有四元式、三元式、间接三元式和逆波兰记号等。;图9-1 编译程序结构示意; 第四阶段为优化。优化的任务在于对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效(节省时间和空间)的目标代码。 第五阶段为目标代码生成。这一阶段的任务是把中间代码(或经优化处理之后)变换成特定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码。这一阶段实现了最后的翻译，它的工作有赖于硬件系统结构和机器指令含义。; 上述编译过程的五个阶段是编译程序工作时的动态特征，编译程序的结构可以按照这五个阶段的任务分模块进行设计。编译程序的结构示意如图9-1所示。 我们设计的小型编译程序包含除优化以外的其余各阶段。 ;9.2 小型编译程序关于高级语言的规定 ; S→if B then S else S ︱while B do S ︱begin L end︱A L→S;L︱S A→i:=E B→B∧B︱B∨B︱??B︱(B) ︱i rop i︱i E→E+E︱E*E︱(E) ︱i ; 其中，各非终结符的含义如下： S——语句； L——语句串； A——赋值句； B——布尔表达式； E——算术表达式。 ; 各终结符的含义如下： i?——整型变量或常数，布尔变量或常数； rop?——六种关系运算符的代表； ;?——起语句分隔符作用； :=?——赋值符号； ??——逻辑非运算符“not”； ∧?——逻辑与运算符“and”；; ∨?——逻辑或运算符“or”； +?——算术加运算符； *?——算术乘运算符； (?——左括号； )?——右括号。 注意，六种关系运算符分别为 ：小于 =：小于等于 ：不等于 ：大于 =：大于等于 =：等于; 关于表达式的运算，我们规定由高到低优先顺序为算术运算、关系运算、布尔运算；并且服丛左结合规则。算术运算符优先级的顺序依次为“( )”﹑“*” ﹑“+” ；布尔运算符优先级的顺序依次为“??”﹑“∧”﹑“∨”；六个关系运算符优先级相同。 我们规定的程序是由一条语句或由begin和end嵌套起来的复合语句组成的，并且规定在语句末要加上“#~”表示程序结束。下面给出的是符合规定的程序示例： begin A:=A+B*C; C:=A+2;; while AC and BD do while AB do if M=N then C:=D else while A=D do A:=D end#~ ;9.3 小型编译程序关于单词的内部定义 ;表9-1 关于单词的内部定义 ;9.4 小型编译程序的LR分析表;表9-2 算术表达式的SLR(1)分析表 ; 2． 布尔表达式的LR分析表 布尔表达式的文法如下： B-B∧B︱B∨B︱??B︱i rop i︱I 为了便于语法分析时的加工处理，我们将上述文法改写为文法G[S]： B→BAB︱BOB︱??B︱(B)︱i rop i︱i BA→ B∧ BO→ B∨; 将文法G[S]拓广为文法G[S′]：(0) S′→B ???(1) B→I ??(2) B→i rop i ?? ? (3) B→(B) ??? (4) B→NOT B ??? (5) A→B AND ? ??(6) B→AB ?? ?(7) O→B OR ?? ?(8) B→OB 由此得到布尔表达式的SLR(1)分析表如表9