《编译原理基础——习题与上机题解答 教学课件 ppt 作者 刘坚 第6-10章 第7章》由会员分享，可在线阅读，更多相关《编译原理基础——习题与上机题解答 教学课件 ppt 作者 刘坚 第6-10章 第7章（42页珍藏版）》请在金锄头文库上搜索。
1、,第7章上机题,编译原理是一门理论与实践并重的课程，上机实践是学习编译原理的一个重要环节。通过自己动手编写一个小的编译器，可以帮助学习者将所学的理论知识与具体的应用结合起来，并加深对编译技术的理解和掌握。 在编译器的分析综合模式中，编译器被划分为前端和后端。前端对源程序进行语法和语义分析，生成某种中间表示；后端根据中间表示和不同的硬件环境，生成目标代码。由于程序设计语言编译器的构造是一件十分庞杂的事情，而且除了少量的计算机语言需要生成目标代码之外，绝大多数的软件系统需要用到的仅是编译器的前端，即语言的分析(也称为语言的识别)。,由于上机时数的限制，我们设计的上机题目仅侧重于前端的构造技术，包括
2、词法分析、语法分析和语义分析。题目是一个简单的函数绘图语言的解释器，它接受用户编写的绘图语句序列(不妨称为源程序)，对语句进行分析和处理，最终将源程序所规定的图形显示在终端上。,希望读者通过上机实习至少达到下述目的： (1) 会用正规式和产生式设计简单语言的语法； (2) 会用递归下降子程序编写编译器或解释器； (3) 会写上机报告(简单的技术文档)。 基于这一目的，我们给出了一个递归下降子程序的解决方案，并紧密结合教材内容给出了重要步骤的详细解释和完整的函数绘图语言解释器的源程序清单。为了照顾不同程度的读者，我们还简单介绍了利用词法和语法分析器编写工具LEX/YACC编写解释器的基本方法，并
3、给出了源程序清单。,7.1 简单的函数绘图语言 本上机题中，要求设计一个最简单的函数绘图语言，该语言提供一条循环绘图语句，将用此语句规定的函数轨迹以直角坐标系的形式逐点显示在计算机显示屏上(或窗口中)。该语言还提供图形变换的语句，可以进行图形的平移、旋转和纵横比例的改变。如果源程序中不提供图形变换语句，则系统的默认值是：不平移(原点坐标为(0, 0)、不旋转(旋转角度为0)、坐标的纵横比例为11。语言中还提供注释语句，以使用户书写的源程序更清晰易懂。,显示屏的直角坐标系一般以显示屏(或显示窗口)左上角为原点，X轴的正方向是自左向右，Y的正方向是自顶向下，这与一般的直角坐标系的Y轴正方向正好相反
4、。因此，如果希望所绘图形的Y方向是向上增长的，则要求绘图语句中的Y坐标取其负值。 【例7.1】 首先通过函数绘图语言的例子建立对该语言的感性认识。下述源程序将绘图原点的位置平移到坐标(100, 300)处，横坐标和纵坐标的比例设置为11，然后在所建立的坐标系中用绘图语句绘制三条直线。,- 函数f(t)=t的图形 origin is (100, 300); - 设置原点的偏移量 rot is 0; - 设置旋转角度(不旋转) scale is (1, 1); - 设置横坐标和纵坐标的比例 for T from 0 to 200 step 1 draw (t, 0); - 横坐标的轨迹(纵坐标为0
5、),for T from 0 to 150 step 1 draw (0, t); - 纵坐标的轨迹(横坐标为0) for T from 0 to 120 step 1 draw (t, t); - 函数f(t)=t的轨迹 源程序所绘制的图形如图7.1所示。,图7.1,7.1.1 语句的语法和语义 函数绘图语言的源程序由五种类型的语句构成：循环绘图(FOR-DRAW)、比例设置(SCALE)、角度旋转(ROT)、坐标平移(ORIGIN)和注释，它们在例7.1中均已出现过。 这些语句满足下述基本原则： (1) 各类语句可以按任意次序书写，且语句以分号结尾。源程序中的语句以它们出现的先后顺序处理。
6、 (2) ORIGIN、ROT和SCALE 语句只影响其后的绘图语句，且遵循最后出现的语句有效的原则。例如，若有下述ROT语句序列：,ROT IS 0.7 ； ROT IS 1.57 ； 则随后的绘图语句将按1.57而不是0.7弧度旋转。 (3) 无论ORIGIN、ROT和SCALE语句的出现顺序如何，图形的变换顺序总是：比例变换旋转变换平移变换。 (4) 语言对大小写不敏感，例如for、For、FOR等，均被认为是同一个保留字。 (5) 语句中表达式的值均为双精度类型，旋转角度单位为弧度且为逆时针旋转，平移单位为点。,1循环绘图(FOR-DRAW )语句 绘图语句是绘图语言的核心，主要完成函
7、数图形的绘制工作。它的语法如下： FOR T FROM 起点 TO 终点 STEP 步长 DRAW(横坐标，纵坐标)； 语句的起点、终点、步长、横坐标、纵坐标均为表达式。语句的作用是在闭区间起点，终点上，以每次一个步长的增量绘制点(横坐标，纵坐标)的轨迹。横坐标和纵坐标分别是T的函数，T每变化一个增量，就绘制一个点，因此T在绘图语句中起着一支笔的作用。,由于函数绘图语言中仅有这唯一的绘图语句且所有语句顺序执行(即一支笔顺序画所有的图形)，故整个绘图语言只需要一个变量并将此变量固定命名为T。,图7.2,对于下述语句： FOR T FROM 0 TO 2*PI STEP PI/50 DRAW (c
8、os(T)，sin(T); 它的作用是，令T从0到2*PI、步长为 PI/50，绘制出各个点的坐标(cos(T)，sin(T)。表7.1列出了参数T取不同值时对应的部分点坐标。 在坐标系上画出各个点即得到图7.2所示的单位圆(比例设置前仅能看到一个点)。,表 7.1,2比例设置语句(SCALE 语句) 比例设置语句是将绘图语句画出的图形进行比例缩放。它的语法如下： SCALE IS (横坐标比例因子，纵坐标比例因子) ； 其作用是对绘图语句中的横、纵坐标值按该语句指定的比例因子缩放。 对于下述的源程序： SCALE IS (100, 100/3)； FOR T FROM 0 TO 2*PI S
9、TEP PI/50 DRAW (cos(T)，sin(T)；,它的作用是令绘图语句中点的横坐标放大100倍，纵坐标放大100/3倍。于是得到图7.3所示的椭圆。,图7.3,3角度旋转语句(ROT 语句) 角度旋转语句的语法如下： ROT IS 弧度值； 它的作用是令紧随其后的绘图语句所绘制的图形按ROT语句指定的弧度绕原点逆时针旋转。将图形绕原点旋转角度，实际上就是将图形上的每个点分别绕原点旋转角度。下面给出点坐标的旋转变换公式：,图7.4,旋转后X = 旋转前X * COS(弧度值) + 旋转前Y * SIN(弧度值) 旋转后Y = 旋转前Y * COS(弧度值) 旋转前X * SIN(弧度
10、值) 旋转变换公式的推导如下(参见图7.4)： m=* cos n=* sin a=* cos() b=* sin() a=*coscos+*sinsin b=*sincos*cossin,a = m*cos+n*sin b = n*cosm*sin 例如，执行下述的源程序将得到图7.5所示结果。 ROT IS PI/2； / 将图7.3中椭圆逆时针旋转PI/2 SCALE IS (100, 100/3)； FOR T FROM 0 TO 2*PI STEP PI/50 DRAW (cos(T)，sin(T)；,图7.5,4. 坐标平移语句(ORIGIN 语句) 平移语句的语法如下： ORIG
11、IN IS(横坐标偏移量，纵坐标偏移量) ； 它的作用是对已得到的图形的坐标进行整体平移。平移后图形各点坐标计算公式如下： 平移后X = 平移前X + 横坐标偏移量 平移后Y = 平移前Y + 纵坐标偏移量 如果我们希望对图7.5中的椭圆向右平移360个单位，向下平移240个单位，则程序为：,ORIGIN IS (360, 240) ； ROT IS PI/2 ； SCALE IS (100, 100/3) ； FOR T FROM 0 TO 2*PI STEP PI/50 DRAW (cos(T)，sin(T) ； 其输出结果如图7.6所示。,图7.6,5注释语句 源程序中的任何位置均可以接
12、收C+形式(/引导直到当前行结束)和Ada形式(-引导直到当前行结束)的注释，具体如下： / This is a comment line 或 - 此行是注释 两种形式注释的语义是一致的，注释内容均是从注释引导符(“/”或“-”)开始，直到此行结束。,这种形式注释的优点是随着一行的结束注释自动结束，可以避免因少写注释结束符而使得注释内容无法结束造成程序错误的问题。它的缺点是当需要书写一大段注释时，每行的开始均需注释引导符引导。有兴趣的读者可以加入C的注释形式，即/* */，从而避免上述每行都要写注释引导符的麻烦。,7.1.2 记号的语法和语义 绘图语言中有这样几类记号：常数、参数、保留字、函数
13、、运算符和分隔符等。它们的语法和作用分别表述如下： (1) 常数：我们将常数字面量和标识符形式的常量名均称为常数。字面量的形式为普通的数值，如果没有小数部分，则可以省略小数点。例如2、2.、2.0都是合法的常数。标识符PI、E也是常数，它们分别代表圆周率和自然对数的底。常数不能有符号位，如1和+2不是常数而是(一元运算的)表达式。,(2) 参数：本作图语言中唯一的、已经被定义好的变量名T被称为参数，它也是一个表达式。由于作图语言中并没有其它的变量，因此作图语言中没有变量或参数的声明和定义语句。 (3) 函数：为简单起见，当前的函数仅支持正弦函数sin，余弦函数cos，正切函数tan，算术平方根
14、函数sqrt以及指数函数exp和对数函数ln。有兴趣的读者可以再加入其他函数 (4) 保留字：语句中具有固定含义的标识符，如FOR、DRAW、SCALE等。,(5) 运算符：运算符包括 +、*、/和*，分别代表加、减、乘、除和乘方运算。乘方是右结合的，其它运算均为左结合。运算符的优先级从高到低依次为：乘方、一元加减、乘除、二元加减。 (6) 分隔符：最重要的分隔符是括号。括号具有最高优先级，因此可以用括号来改变运算的优先级和结合性。如果我们希望算术表达式1+2*3中的“+”先运算，则可以写为(1+2)*3。分隔符还包括逗号和分号，分别用于分隔坐标的横、纵分量和句子。,上机作业的题目是：为简单的
15、函数绘图语言编写一个解释器。该解释器接受用绘图语言编写的源程序，经过语法和语义分析之后，直接将源程序所规定的图形显示在显示屏(或显示窗口)中。作业的目的是：通过自己动手编写解释器，掌握语言翻译，特别是语言识别的基本方法。,7.2 题 目 与 要 求,对于修“编译原理基础”课程的本科生，我们对上机作业做以下要求，包括解释器的实现方法、上机环境的选择，以及最终上机报告的书写等。,7.2.1 解释器的实现方法 读者可以采用两种方法编写解释器： 用某种程序设计语言(如C/C+、Pascal、Java等)和递归下降子程序的方法编写完整的解释器，由于环境限制，本书统一采用C/C+程序设计语言； 利用编译器编写工具LEX/YACC提供的方式规定绘图语言的词法和语法，用C/C+语言编写解释器的语义。两种方法的语义部分基本相同，主要区别在于词法和语法分析器的构造是手工完成还是借助于工具完成的。,两种方法的实现过程和解释器的工作过程可以用图7.7简单说明。两者的主要区别在于，递归下降子程序方法需要编写C/C+源程序形式的词法分析器和语法分析器(见图7.7(a)，而LEX/YACC方法中，只需要编写LEX和YACC源程序(见图7.7(b), 其中LEX的源程序主要是规定构词规则的正规式，YACC的源程序主要是规定语言结构的产生式)，分别由LEX和YACC编译器将它们编译
