第2章 PL0编译程序的实现 完整课后习题答案+吕映芝编

5.1 考虑以下的文法：S→S;T|TT→a（1）为这个文法构造LR(0)的项目集规范族。

（2）这个文法是不是LR(0)文法？如果是，则构造LR(0)分析表。

（3）对输入串“a;a”进行分析。

解：（1）拓广文法G[S’]：0：S’→S1：S→S;T2：S→T3：T→a构造LR(0)项目集规范族（2）该文法不存在“归约－归约”和“归约－移进”冲突，因此是LR(0)文法。

LR(0)分析表如下：（3）对输入串“a;a”进行分析如下：5.2 证明下面文法是SLR(1)文法，但不是LR(0)文法。

S→AA→Ab|bBaB→aAc|a|aAb解：文法G[S]：0：S→A1：A→Ab2：A→bBa3：B→aAc4：B→a5：B→aAb状态5存在“归约－移进”冲突，状态9存在“归约－归约”冲突，因此该文法不是LR(0)文法。

状态5：FOLLOW(B)＝｛a｝，因此，FOLLOW(B)∩｛b｝＝Φ状态9：FOLLOW(B)＝｛a｝，FOLLOW(A)＝｛#，b，c｝，因此FOLLOW(B)∩FOLLOW(A)＝Φ该SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(0)文法。

5.3 证明下面文法是LR(1)文法，但不是SLR(1)文法。

S→AaAb|BbBaA→εB→ε解：拓广文法G[S’]：0：S’→S1：S→AaAb2：S→BbBa3：A→ε4：B→ε＝｛a,b｝，即FOLLOW(A)∩FOLLOW(B)＝｛a,b｝≠Φ，所以该文法不是SLR(1)文法。

构造LR(1)项目集规范族：分析表无重定义，说明该文法是LR(1)文法，不是SLR(1)文法。

5.4 考虑以下的文法：E→EE＋E→EE*E→a（1）为这个文法构造LR(1)项目集规范族。

（2）构造LR(1)分析表。

（3）为这个文法构造LALR(1)项目集规范族。

（4）构造LALR(1)分析表。

（5）对输入符号串“aa*a+”进行LR(1)和LALR(1)分析。

编译原理第二版课后习答案《编译原理》课后习题答案第一章第 1 章引论第 1 题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第 2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

汇编语言程序设计第四版【课后习题答案】--囮裑為檤第2章8086的指令系统〔习题2.1〕已知DS＝2000H、BX＝0100H、SI＝0002H，存储单元[20100H]～[20103H]依次存放12 34 56 78H，[21200H]～[21203H]依次存放2A 4C B7 65H，说明下列每条指令执行完后AX寄存器的内容。

（1）mov ax,1200h（2）mov ax,bx（3）mov ax,[1200h]（4）mov ax,[bx]（5）mov ax,[bx+1100h]（6）mov ax,[bx+si]（7）mov ax,[bx][si+1100h]〔解答〕（1）AX＝1200H（2）AX＝0100H（3）AX＝4C2AH ;偏移地址=bx=0100h（4）AX＝3412H ;偏移地址=bx=0100h（5）AX＝4C2AH ;偏移地址=bx+1100h=1200h（6）AX＝7856H ;偏移地址=bx+si=0100h+0002h=0102h（7）AX＝65B7H ;偏移地址=bx+si+1100h=0100h+0002h+1100h=1202h〔习题2.2〕指出下列指令的错误（1）mov cx,dl（2）mov ip,ax（3）mov es,1234h（4）mov es,ds（5）mov al,300（6）mov [sp],ax（7）mov ax,bx+di（8）mov 20h,ah〔解答〕（1）两操作数类型不匹配（2）IP指令指针禁止用户访问（3）立即数不允许传给段寄存器（4）段寄存器之间不允许传送（5）两操作数类型不匹配（6）目的操作数应为[ SI ]（7）源操作数应为[BX+DI]（8）立即数不能作目的操作数〔习题2.3〕已知数字0 ~ 9对应的格雷码依次为：18H、34H、05H、06H、09H、0AH、0CH、11H、12H、14H，它存在于以table为首地址（设为200H）的连续区域中。

编译原理第二版课后习答案编译原理是计算机科学领域中的一门重要学科，它主要研究程序的自动翻译技术，将高级语言编写的程序转换为机器能够执行的低级语言。

编译原理的基本概念和技术是计算机专业学生必须学会的知识之一，而编译原理第二版课后习题则是帮助学生更好地理解课程内容和提高编译器开发能力的重要资源。

本篇文章将对编译原理第二版课后习题进行分析和总结，并提供一些参考答案和解决问题的思路。

一、词法分析词法分析是编译器的第一步，它主要将输入的字符流转换为有意义的词法单元，例如关键字、标识符、常量和运算符等。

在词法分析过程中，我们需要编写一个词法分析程序来处理输入的字符流。

以下是几道词法分析相关的习题：1. 如何使用正则表达式来表示浮点数？答案：[+|-]?(\d+\.\d+|\d+\.|\.\d+)([e|E][+|-]?\d+)?这个正则表达式可以匹配所有的浮点数，包括正负小数、整数和指数形式的浮点数。

2. 什么是语素？举例说明。

答案：语素是构成单词的最小承载语义的单位，例如单词“man”，它由两个语素“ma”和“n”组成。

“ma”表示男性，“n”表示名词。

3. 采用有限状态自动机(Finite State Automata)实现词法分析的优点是什么？答案：采用有限状态自动机(Finite State Automata)实现词法分析的优点是运行速度快，消耗内存小，易于编写和调试，具有可读性。

二、语法分析语法分析是编译器的第二步，它主要检查词法分析生成的词法单元是否符合语法规则。

在语法分析过程中，我们需要编写一个语法分析器来处理词法单元序列。

以下是几道语法分析相关的习题：1. 什么是上下文无关文法？答案：上下文无关文法(Context-Free Grammar, CFG)是一种形式语言，它的语法规则不依赖于上下文，只考虑规则左边的非终结符号。

EBNF是一种常见的上下文无关文法。

2. LR分析表有什么作用？答案：LR分析表是一种自动机，它的作用是给定一个输入符号串，判断其是否符合某个文法规则，并生成语法树。

第二章PL/0编译程序的实现【课前思考】复习第1章介绍的一个高级程序设计语言编译程序的功能和实现的步骤。

编译程序就是一个语言的翻译程序，通常是把一种高级程序设计语言（称源语言）书写的程序翻译成另一种等价功能语言（称目标语言）的程序。

换句话说，编译是指把一种用源语言表示的算法转换到另一种等价的用目标语言表示的算法。

编译程序实现的必要步骤有词法、语法、语义分析和代码生成。

此外必需有符号表管理程序和出错处理程序。

本章介绍的PL/0编译程序的实现是用PASCAL语言书写的【学习目标】本章目的：以PL/0语言编译程序为实例,学习编译程序实现的基本步骤和相关技术，对编译程序的构造和实现得到一些感性认识和建立起整体概念，为后面的原理学习打下基础。

◇了解并掌握用语法图和扩充的巴科斯-瑙尔范式(EBNF)对PL/0语言的形式描述。

◇了解并掌握PL/0语言编译程序构造和实现的基本技术和步骤。

◇了解并掌握PL/0语言编译程序的目标程序在运行时数据空间的组织管理。

【学习指南】◇要求读者阅读PL/0语言编译程序文本，了解一个编译程序构造的必要步骤和实现技术。

一个编译程序的实现比较复杂，读懂一个典型的程序从设计思想到实现技术也有一定难度，特别是入门开始需要耐心。

一但读懂，不仅了解编译程序的实现方法和技术，还可学到许多编程技巧和好的编程风格。

◇阅读PL/0语言编译程序文本时，应从整体结构开始逐步细化，弄清楚每个过程的功能和实现方法及过程之间的相互关系。

◇建议用一个PL/0源程序的例子为导引作为阅读PL/0语言编译程序文本的入门，然后再逐步全面读懂。

◇通过对PL/0语言编译程序某些指定功能的扩充，加深对编译程序构造步骤和实现技术的理解，并能在实践中应用。

【难重点】重点：◇弄清源语言(PL/0)、目标语言(类pcode)与实现语言（C）这3个语言之间的关系和作用。

◇掌握用语法图和扩充的巴科斯-瑙尔范式(EBNF)对一个高级程序设计语言的形式描述。

第一章编译程序概述1.1什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多 数计算机系统都含有不止一个高级语言的编译程序。

对有些高 级语言甚至配置了几个不同性能的编译程序。

1.2编译过程概述和编译程序的结构编译程序完成从源程序到目标程序的翻译工作，是一个复 杂的整体的过程。

从概念上来讲，一个编译程序的整个工作过 程是划分成阶段进行的，每个阶段将源程序的一种表示形式转 换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连 接在一起的。

一般一个编译过程划分成词法分析、语法分析、 语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。

事实上，某些阶段可能组合在一起， 这些阶段间的源程序的中间表示形式就没必要构造岀来了。

我 们将分别介绍各阶段的任务。

另外两个重要的工作：表格管理 和岀错处理与上述六个阶段都有联系。

编译过程中源程序的各 种信息被保留在种种不同的表格里，编译各阶段的工作都涉及 到构造、查找或更新有关的表格，因此需要有表格管理的工作； 如果编译过程中发现源程序有错误，编译程序应报告错误的性 质和错误发生的地点，并且将错误所造成的影响限制在尽可能 小的范围内，使得源程序的其余部分能继续被编译下去，有些 编译程序还能自动校正错误， 这些工作称之为岀错处理。

图1.3表示了编译的各个阶段。

图1.3编译的各个阶段它不生成目标代码，它每遇到一个语句，就要对这个语句进行 分析以决定语句的含义，执行相应的动作。

右面的图示意了它 的工作机理第二章：PL/O 编译程序问答第1题 PL/0语言允许过程嵌套定义和递归调用，试问 它的编译程序如何解决运行时的存储管理。

答：PL/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。

(数组CODE 存放的只读目 标程序，它在运行时不改变。

)运行时的数据区S 是由解释程序 定义的一维整型数组，解释执行时对数据空间S 的管理遵循后进先岀规则，当每个过程(包括主程序)被调用时，才分配数据 空间，退出过程时，则所分配的数据空间被释放。

第2章 PL/0编译程序的实现第1题PL/0语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管理。

答案：PL/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。

（数组CODE存放的只读目标程序，它在运行时不改变。

）运行时的数据区S是由解释程序定义的一维整型数组，解释执行时对数据空间S的管理遵循后进先出规则，当每个过程(包括主程序)被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。

应用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题。

第2题若PL/0编译程序运行时的存储分配策略采用栈式动态分配，并用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题，试写出下列程序执行到赋值语句b∶=10时运行栈的布局示意图。

var x,y;procedure p;var a;procedure q;var b;begin (q)b∶=10;end (q);procedure s;var c,d;procedure r;var e,f;begin (r)call q;end (r);begin (s)call r;end (s);begin (p)call s;end (p);begin (main)call p;end (main).答案：程序执行到赋值语句b∶=10时运行栈的布局示意图为：第3题写出题2中当程序编译到r的过程体时的名字表table的内容。

size name kind level/val adr答案：题2中当程序编译到r的过程体时的名字表table的内容为：name kind level/val adr sizex variable 0 dxy variable 0 dx+1p procedure 0 过程p的入口（待填） 5a variable 1 dxq procedure 1 过程q的入口 4 s procedure 1 过程s的入口（待填） 5c variable 2 dxd variable 2 dxr procedure 2 过程r的入口 5e variable 3 dxf variable 3 dx+1注意：q和s是并列的过程，所以q定义的变量b被覆盖。