1 编写一个递归算法将输入的任意一个正整数n以相反的顺序输出。例如：输入12345则输出54321。
解析：1）本题考查对函数的定义和调用的掌握情况
2）为了使算法简单，采用递归方法进行程序设计，
程序流程图
2编写程序，要求从键盘任意输入一个3*3的矩阵，利用二维数组的结构将输入存储，并计算该矩阵的对角线之和，并将结果显示出来。
解析：1）采用二维矩阵存储输入的数据
2）利用二重循环控制输入顺序
3）对数组对角线元素的判断是行数等于列数
程序流程
3将从键盘输入一串英文字符中的大写字符转换成小写字符，并输出转换后的字符串，要求使用指针来操作。
显示结果为:Please input char:
asf A KFJewrtrOPKs
ASFAKFJEWRTROPKS
解析：1）小写字母比大写字母的ASCII码在数值上大32，这是小写转大写的途经2）对输入的字符串采用指针依次读取每一个字符
3）对每个字符判断，若为小写不变，为大写+32转换为小写，若不是字母，显示错误并退出
4）对字符串的输入调用系统函数gets（）
程序流程
4 运用数据链表，建立一个学生数据库，包括学生的姓名，学号，年龄，性别，成绩信息。程序提供两个功能，当输入n时，表示输入新的记录，输入l时表示将所有学生数据输出。输入此外的字符则程序终止。
解析：
1在主函数的外部先定义两个指针变量myhead,mythis,mynew用它们来处理链表节点的联系，并在主函数中给head赋值NULL,即链表开始是空的
2如果输入的是n就执行输入新数据，用new_record()函数实现，将一个新节点插入链表中，首先要开辟新节点，就要调用malloc函数，用sizeof(struct stud_type) 来测出每个节点的长度，用new指向开辟的新节点,将新节点链接到表中，再对节点赋值。
3输入l时，将所有的数据输出，用listall()函数实现，从表头开始，依次遍历链表，到表尾时终止
编译原理实验报告 实验名称 _____________ 消除文法的左递归__________________________ 实验时间 _____________________________________________ 院系 _________________________________________ 班级 ______________________________________________ 学号 ____________________________________________ 姓名
1. 试验目的 ?掌握和理解消除左递归(包括直接左递归和间接左递归)在构建 LL(1)文法的作用和目的 ?掌握消除左递归(包括直接左递归和间接左递归)的方法和步骤。 ?写出对于输入任意的上下文无关文法可以输出消除了左递归的等 价文法。 2. 实验原理 ?直接左递归的消除 消除产生式中的直接左递归是比较容易的。例如假设非终结符 P的规则为 P—P a/ B 其中，B是不以P开头的符号串。那么，我们可以把P的规则改写为 如下的非直接左递归形式：P—尸’ P'—P'￡ 考虑更一般的情况，假定关于非终结符P的规则为 P—P a / P o2 / …/ P a n / [31 / [32 / …/ p m 其中，a (I = 1, 2,…，n)都不为￡而每个p j (j = 1, 2,…，m) 都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归： P— p l P'/ 32 P'/…/p m P' P' — 01P' / a P'/…/ a n P'/￡
《计算方法》上机实验报告 班级：XXXXXX 小组成员：XXXXXXX XXXXXXX XXXXXXX XXXXXXX 任课教师：XXX 二〇一八年五月二十五日
前言 通过进行多次的上机实验，我们结合课本上的内容以及老师对我们的指导，能够较为熟练地掌握Newton 迭代法、Jacobi 迭代法、Gauss-Seidel 迭代法、Newton 插值法、Lagrange 插值法和Gauss 求积公式等六种算法的原理和使用方法，并参考课本例题进行了MATLAB 程序的编写。 以下为本次上机实验报告，按照实验内容共分为六部分。 实验一： 一、实验名称及题目： Newton 迭代法 例2.7(P38):应用Newton 迭代法求 在 附近的数值解 ，并使其满足 . 二、解题思路： 设'x 是0)(=x f 的根,选取0x 作为'x 初始近似值,过点())(,00x f x 做曲线)(x f y =的切线L ,L 的方程为))((')(000x x x f x f y -+=,求出L 与x 轴交点的横坐标) (') (0001x f x f x x - =,称1x 为'x 的一次近似值,过点))(,(11x f x 做曲线)(x f y =的切线,求该切线与x 轴的横坐标) (') (1112x f x f x x - =称2x 为'x
的二次近似值,重复以上过程,得'x 的近似值序列{}n x ,把 ) (') (1n n n n x f x f x x - =+称为'x 的1+n 次近似值，这种求解方法就是牛顿迭代法。 三、Matlab 程序代码： function newton_iteration(x0,tol) syms z %定义自变量 format long %定义精度 f=z*z*z-z-1; f1=diff(f);%求导 y=subs(f,z,x0); y1=subs(f1,z,x0);%向函数中代值 x1=x0-y/y1; k=1; while abs(x1-x0)>=tol x0=x1; y=subs(f,z,x0); y1=subs(f1,z,x0); x1=x0-y/y1;k=k+1; end x=double(x1) K 四、运行结果： 实验二：
一、教学目标 1、知识与技能 (1)．认识递归现象。 (2)．使用递归算法解决问题往往能使算法的描述乘法而易于表达 (3)．理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4)．认识递归算法往往不是高效的算法。 (5)．了解递归现象的规律。 (6)．能够设计递归程序解决适用于递归解决的问题。 (7)．能够根据算法写出递归程序。 (8)．了解生活中的递归现象，领悟递归现象的既有重复，又有变化的 特点，并 且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 （1）了解递归现象和递归算法的特点。
（2）能够根据问题设计出恰当的递归程序。 2、教学难点 (1)递归过程思路的建立。 (2)判断问题是否适于递归解法。 (3)正确写出递归程序。 三、教学环境 1、教材处理 教材选自《广东省普通高中信息技术选修一：算法与程序设计》第四章第五节，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远，但方法和答案却都是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 教学方法采用讲解、探究、任务驱动和学生自主学习相结合 2、预备知识 学生已掌握了用计算机解决问题的过程，掌握了程序设计基础，掌握了解析法、穷举法、查找法、排序法设计程序的技巧。 3、硬件要求 建议本节课在多媒体电脑教室中完成，最好有广播教学系统或投影仪，为拓展学习，学生机应允许上互联网。 4、所需软件 学生机要安装VB6.0或以上版本。 5、所需课时 2课时（90分钟）
递归与分治实验报告 班级：计科1102 姓名：赵春晓学号：2011310200631 实验目的：进一步掌握递归与分治算法的设计思想，通过实际问题来应用递归与分治设计算法。 实际问题：1集合划分问题，2输油管道问题，3邮局选址问题，4整数因子分解问题，5众数问题。 问题1：集合划分 算法思想：对于n个元素的集合，可以划分为由m个子集构成的集合，例如{{1,2}{3,4}}就是由2个子集构成的非空子集。假设f（n，m）表示将n个元素划分成由m个子集构成的集合的个数。那么1）若m == 1 ，则f（n，m）= 1 ；2）若n == m ，则f（n，m）= 1 ；3）若不是上面两种情况则有下面两种情况构成：3.1）向n-1个元素划分成的m个集合里面添加一个新的元素，则有m*f(n-1,m)种方法；3.2）向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合，则有f(n-1,m-1)种方法。 实验代码： #include
学号107 成绩 编译原理上机报告 名称：编写递归下降语法分析器 学院：信息与控制工程学院 专业：计算机科学与技术 班级：计算机1401班 姓名：叶达成 2016年10月31日
一、上机目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、基本原理和上机步骤 递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的产生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于任一非终结符号U的产生式右部x1|x2|…|x n，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P?+ P的推导），也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。 三、上机结果 测试数据： (1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (2)输出结果：i+i*i#为合法符号串 (3)输入一符号串如i+i*#,要求输出为“非法的符号串”。 程序清单： #include
递归算法与递归程序 岳西中学：崔世义一、教学目标 1知识与技能 (1) ?认识递归现象。 (2) ?使用递归算法解决冋题往往能使算法的描述乘法而易于表达 (3) ?理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4) ?认识递归算法往往不是咼效的算法。 (5) ? 了解递归现象的规律。 (6) ?能够设计递归程序解决适用于递归解决的问题。 (7) ?能够根据算法写出递归程序。 (8) ? 了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1) 了解递归现象和递归算法的特点。 (2) 能够根据问题设计出恰当的递归程序。 2、教学难点 (1) 递归过程思路的建立。 (2) 判断冋题是否适于递归解法。 (3) 正确写出递归程序。 三、教学环境 1、教材处理 教材选自《浙江省普通高中信息技术选修：算法与程序设计》第五章，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自 定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习⑵ 和练习
共享知识分享快乐 编译原理实验报告 实验名称消除文法左递归 实验时间2014年12月12日 院系软件工程 ______________ 班级软件工程（2）班 学号E01214215 __________ 姓名刘翼________________
实验目的： 输入：任意的上下文无关文法。输出：消除了左递归的等价文法。 实验原理： 1．直接左递归的消除 消除产生式中的直接左递归是比较容易的。例如假设非终结符P 的规则为 P—P a / B 其中，B是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式：P —B P' P'—a P' / ￡ 这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。 设有简单表达式文法G[E] ： E —E+T/ T T —T*F/ F F —（E）/ I 经消除直接左递归后得到如下文法： E —TE' E ' —+TE' / ￡ T —FT' T' —*FT' / ￡ F —（E）/ I 考虑更一般的情况，假定关于非终结符P的规则为 P—P a 1 / P a 2 / …/ P a n / B 1 / B 2 / …/ B m 其中，a i （I = 1，2，…，n）都不为￡，而每个B j （j = 1，2，…，m都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归： P—B 1 P' / B 2 P' / …/ B m P' P' —a 1P' / a 2 P' / …/ a n P' / ￡ 2．间接左递归的消除 直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设有文法G[S] ： S—Qc/ c Q—Rb/ b R—Sa/ a 虽不具有左递归，但S、Q R都是左递归的，因为经过若干次推导有 S Qc Rbc Sabc Q Rb Sab Qcab R Sa Qca Rbca
实验报告名称 班级：学号：姓名：成绩： 1实验目的 1）通过对二分法与牛顿迭代法作编程练习与上级运算，进一步体会二分法与牛顿迭代法的不同特点。 2）编写割线迭代法的程序，求非线性迭代法的解，并与牛顿迭代法。 2 实验内容 用牛顿法和割线法求下列方程的根 x^2-e^x=0; x*e^x-1=0; lgx+x-2=0; 3实验步骤 1)根据二分法和牛顿迭代法，割线法的算法编写相应的求根函数； 2)将题中所给参数带入二分法函数，确定大致区间； 3)用牛顿迭代法和割线法分别对方程进行求解； 3 程序设计 牛顿迭代法x0=1.0; N=100; k=0; eps=5e-6; delta=1e-6; while(1) x1=x0-fc1(x0)/fc2(x0); k=k+1; if k>N disp('Newmethod failed')
break end if(abs(x1-x0) 实验三递归下降分析法 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 程序比较复杂，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调 用的方法。 二、实验要求 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 三、实验内容 程序输入/输出示例： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E-TG （2）G-+TG|—TG （3）G-ε （4）T-FS （5）S-*FS|/FS （6）S-ε （7）F-(E) （8）F-i 输出的格式如下： (1)递归下降分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 引用也要改变）。 注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.对学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。 四、实验学时 4学时 五、实验步骤 （一）准备： 1.阅读课本有关章节， 2.考虑好设计方案； 3.设计出模块结构、测试数据，初步编制好程序。 （二）上课上机： 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。 （三）程序思路（仅供参考）： 0.定义部分：定义常量、变量、数据结构。 1.初始化：从文件将输入符号串输入到字符缓冲区中。 2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 六、实验预习提示 1、递归下降分析法的功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2、递归下降分析法的前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法， 3、递归下降分析法实验设计思想及算法 为G的每个非终结符号U构造一个递归过程,不妨命名为U。 U的产生式的右边指出这个过程的代码结构： (1)若是终结符号，则和向前看符号对照， 若匹配则向前进一个符号；否则出错。 (2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。 具体为： （1）对于每个非终结符号U-u1|u2|…|un处理的方法如下： U( ) { ch=当前符号; if(ch可能是u1字的开头) 处理u1的程序部分; else if(ch可能是u2字的开头)处理u2的程序部分; … else error() } （2）对于每个右部u1-x1x2…xn的处理架构如下： 处理x1的程序； 处理x2的程序； … 处理xn的程序； （3）如果右部为空，则不处理。 递归算法向非递归算法转换 递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。 将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。 1. 直接转换法 直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。 尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法： long fact(int n) { if (n==0) return 1; else return n*fact(n-1); } 当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法： long fact(int n) { int s=0; for (int i=1; i<=n;i++) s=s*i; //用s保存中间结果 return s; } 单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下： int f(int n) { 集美大学计算机工程学院实验报告 课程名称：编译原理 指导教师：付永钢 实验成绩： 实验编号： 实验二 实验名称：递归下降分析程序构造 班级：计算12 姓名： 学号： 上机实践日期：2014.11 上机实践时间： 4学时 一、实验目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： (1) 掌握从源程序文件中读取有效字符的方法和产生源程序内部表示文件的方法； (2)掌握语法分析的实现方法； (3)上机调试编出的语法分析程序。 二、实验环境 Windows7 x64、VC6.0 三、实验原理 递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，可根据输入串的当前符号以及各产生式右部首符，选择某非终结符的产生式，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。即：假设A 的全部产生式为A →α1|α2|……|αn ，则必须满足如下条件才能保证可以唯一的选择合适的产生式 First(A →αi )∩First (A →αj )=Φ,当i≠j. 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于人以非中介符号U 的产生式右部n x x x |...||21，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P P +?的推导），也不含以ε为右部的产生式，那么可以通过执行消除左递归的算法消除文法的一切左递归。 四、实验内容 完成以下描述算术表达式的LL(1)文法的递归下降分析程序构造 G[E]: E →TE ′ E ′→+TE ′|ε T →FT ′ 数值分析上机实验报告 《数值分析》上机实验报告 1.用Newton 法求方程 X 7-X 4+14=0 在（0.1，1.9）中的近似根（初始近似值取为区间端点，迭代6次或误差小于0.00001）。 1.1 理论依据： 设函数在有限区间[a ，b]上二阶导数存在，且满足条件 {}α?上的惟一解在区间平方收敛于方程所生的迭代序列 迭代过程由则对任意初始近似值达到的一个中使是其中上不变号 在区间],[0)(3,2,1,0,) (') ()(],,[x |))(),((|,|,)(||)(|.4;0)(.3],[)(.20 )()(.110......b a x f x k x f x f x x x Newton b a b f a f mir b a c x f a b c f x f b a x f b f x f k k k k k k ==- ==∈≤-≠>+ 令 )9.1()9.1(0)8(4233642)(0)16(71127)(0)9.1(,0)1.0(,1428)(3 2 2 5 333647>?''<-=-=''<-=-='<>+-=f f x x x x x f x x x x x f f f x x x f 故以1.9为起点 ?? ?? ? ='- =+9.1)()(01x x f x f x x k k k k 如此一次一次的迭代，逼近x 的真实根。当前后两个的差<=ε时，就认为求出了近似的根。本程序用Newton 法求代数方程(最高次数不大于10)在（a,b ）区间的根。 1.2 C语言程序原代码： #include 魏陈强 23020092204168 实验3 递归下降法的语法分析器 一、实验目的 学习用递归下降法构造语法分析器的原理，掌握递归下降法的编程方法。 二、实验内容 用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。 这里只要求实现部分产生式，文法的开始符号为program。（完整的源语言的文法定义见教材附录 A.1，p394） program→ block block→{stmts } stmts→stmt stmts | stmt→id=expr; | if(bool)stmt | if( bool)stmt else stmt | while(bool)stmt | do stmt while(bool ) ; | break ; | block bool →expr < expr | expr <= expr | expr > expr | expr >= expr | expr expr→ expr + term | expr - term | term term→ term * factor | term / factor | factor factor→ ( e xpr ) | id| num 三、实验要求 １．个人完成，提交实验报告。 ２．实验报告中给出采用测试源代码片断，及其对应的最左推导过程（形式可以自行考虑）。 测试程序片断： { i = 2; while (i <=100) { sum = sum + i; i = i + 2; } } 对应的推导过程为： program?block ?{stmts } ?{stmt stmts} ?{id=expr;stmts } ?{id=num;stmts } ?{id=num;stmt stmts } ?{id=num;while(bool)stmt stmts } ?{id=num;while(e xpr<= expr)stmt stmts } ?{id=num;while(id<= expr)stmt stmts } ?{id=num;while(id<= num)stmt stmts } ?{id=num;while(id<= num)block stmts } ?{id=num;while(id<= num){stmts }stmts } ?．．．．．．． 四、实验思路 之前编写的词法分析器，能够将语句中的每一个词素都识别出来，因此，在此基础上，定义一个二维字符串数组finaltable[100][20]，用于存放由词法分析器提取出来的每个词素，比如，i=2，则finaltable[0]=”id”， 计算方法实验报告 班级： 学号： 姓名： 成绩： 1 舍入误差及稳定性 一、实验目的 （1）通过上机编程，复习巩固以前所学程序设计语言及上机操作指令； （2）通过上机计算，了解舍入误差所引起的数值不稳定性 二、实验内容 1、用两种不同的顺序计算10000 21n n -=∑，分析其误差的变化 2、已知连分数() 1 01223//(.../)n n a f b b a b a a b =+ +++，利用下面的算法计算f ： 1 1 ,i n n i i i a d b d b d ++==+ (1,2,...,0 i n n =-- 0f d = 写一程序，读入011,,,...,,,...,,n n n b b b a a 计算并打印f 3、给出一个有效的算法和一个无效的算法计算积分 1 041 n n x y dx x =+? (0,1,...,1 n = 4、设2 2 11N N j S j == -∑ ，已知其精确值为1311221N N ?? -- ?+?? （1）编制按从大到小的顺序计算N S 的程序 （2）编制按从小到大的顺序计算N S 的程序 （3）按两种顺序分别计算10001000030000,,,S S S 并指出有效位数 三、实验步骤、程序设计、实验结果及分析 1、用两种不同的顺序计算10000 2 1n n -=∑，分析其误差的变化 （1）实验步骤： 分别从1~10000和从10000~1两种顺序进行计算，应包含的头文件有stdio.h 和math.h （2）程序设计： a.顺序计算 #include 编译方法实验报告实验名称：简单的语法分析程序设计 实验要求 1.功能：对简单的赋值语句进行语法分析 随机输入赋值语句，输出所输入的赋值语句与相应的四元式 2.采用递归下降分析程序完成（自上而下的分析） 3.确定各个子程序的功能并画出流程图 4.文法如下： 5.编码、调试通过 采用标准输入输出方式。输入输出的样例如下： 【样例输入】 x:=a+b*c/d-(e+f) 【样例输出】(说明，语句和四元式之间用5个空格隔开) T1:=b*c (*,b,c,T1) T2:=T1/d (/,T1,d,T2) T3:=a+T2 (+,a,T2,T3) T4:=e+f (+,e,f,T4) T5:=T3-T4 (-,T3,T4,T5) x:=T5 (:=,T5,-,x) 【样例说明】程序除能够正确输出四元式外，当输入的表达式错误时，还应能检测出语法错误，给出相应错误提示。 6.设计3-5个赋值语句测试实例，检验程序能否输出正确的四元式；当输入错误的句子时， 检验程序能够给出语法错误的相应提示信息。 7.报告容包括： 递归程序的调用过程，各子程序的流程图和总控流程图，详细设计，3-5个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等。 目录 1.语法分析递归下降分析算法 (5) 1.1背景知识 (5) 1.2消除左递归 (6) 2.详细设计及流程图 (6) 2.1 函数void V( ) // V -> a|b|c|d|e...|z . (6) 2.2 函数void A( ) // A -> V:=E (7) 2.3 函数void E() //E -> TE' (7) 2.4函数void T( ) // T -> FT' (8) 2.5函数void E1( ) //E'-> +TE'|-TE'|null (8) 2.6函数void T1() // T'-> *FT'|/FT'|null (9) 3.测试用例及截图 (9) 3.1测试用例1及截图 (9) 3.2测试用例2及截图 (10) 3.3测试用例3及截图 (11) 代码清单 (11) 递归算法的实现 【基本信息】 【课标要求】 （三）算法与问题解决例举 1. 内容标准 递归法与问题解决 （1）了解使用递归法设计算法的基本过程。 （2）能够根据具体问题的要求，使用递归法设计算法、编写递归函数、编写程序、求解问题。 【教材分析】 “算法的程序实现”是《算法与程序设计》选修模块第三单元的内容，本节课是“递归算法的程序实现”，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序以及本节的前一小节知识点“什么是自定义函数”的学习，在学习自定义函数的基础上，学习递归算法的程序实现是自定义函数的具体应用，培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。 『递归算法在算法的学习过程中是一个难点，在PASCAL和C语言等程序语言的学习过程中，往往是将其放在“函数与过程”这一章节中来讲解的。递归算法的实现也是用函数或是过程的自我调用来实现的。从这一点上来讲，作者对教材的分析与把握是准确的，思路是清晰的，目标是明确的。』 【学情分析】 教学对象是高中二年级学生，前面学习了程序设计的各种结构，在学习程序设计各种结构的应用过程中培养了用计算机编程解决现实中问题的能力，特别是在学习循环语句的过程中，应用了大量的“递推”算法。前一节课学习了如何自定义函数，在此基础上学习深入学习和体会自定义函数的应用。以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。 『递归算法的本质是递推，而递推的实现正是通过循环语句来完成的。作者准确把握了学生前面的学习情况，对递归算法的本质与特征也分析的很透彻，可以说作者对教学任务的分析是很成功的，接来就要看，在成功分析的基础上作者是如何通过设计教学来解决教学难点的了。』 【教学目标】 院系：计算机科学学院 专业、年级： 07计科2大班 课程名称：编译原理 学号姓名： 指导教师： 2010 年11月17 日 组员学号姓名 实验 名称 实验一：词法分析实验室9205 实验目的或要求 通过设计一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 具体要求：输入为某语言源代码，达到以下功能： 程序输入/输出示例：如源程序为C语言。输入如下一段： main() { int a,b; a=10; b=a+20; } 要求输出如下（并以文件形式输出或以界面的形式输出以下结果）。 （2，”main”） （5，”（“） （5，”）“） （5，”{“} （1，”int”） （2，”a”） （5，”,”） （2，”b”） （5，”;”） （2，”a”） （4，”=”） （3，”10”） （5，”;”） （2，”b”） （4，”=”） （2，”a”） （4，”+”） （3，”20”） （5，”;”） （5，”}“） 要求： 识别保留字：if、int、for、while、do、return、break、continue等等，单词种别码为1。 其他的标识符，单词种别码为2。常数为无符号数，单词种别码为3。 运算符包括：+、-、*、/、=、>、<等；可以考虑更复杂情况>=、<=、!= ；单词种别码为4。分隔符包括：“，”“；”“（”“）”“{”“}”等等，单词种别码为5。 编译原理课程实验报告 班级学号：姓名： 实验名称：递归下降分析法 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验要求： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下： (1)递归下降分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 注意： 1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 三、实验过程： 程序设计： 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 程序编写： 1.定义部分：定义常量、变量、数据结构。 2.初始化：从文件将输入符号串输入到字符缓冲区中。 3.利用递归下降分析法，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 四、实验结果 （1）程序流程图 主函数main( )流程图 E( )过程流程图 T( )过程流程图 G( )过程流程图 F( )过程流程图 递 归 冯文科 一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引 用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及n a 与前面临近几项之间的关系。 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： ???>==-1 ,1,11n na n a n n 如果需要写一个函数来求n a 的值，那么可以很容易地写成这样： 这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一 些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为 特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。 以上面求阶乘数列的函数)(n f 为例。如在求)3(f 时，由于3不是特殊值，因此需要计 算)2(*3f ，但)2(f 是对它自己的调用，于是再计算)2(f ，2也不是特殊值，需要计算 )1(*2f ，需要知道)1(f 的值，再计算)1(f ，1是特殊值，于是直接得出1)1(=f ，返回上 一步，得2)1(*2)2(==f f ，再返回上一步，得62*3)2(*3)3(===f f ，从而得最终解。 用图解来说明，就是 下面再看一个稍复杂点的例子。 【例1】数列}{n a 的前几项为 学生学号0120810680316 实验课成绩 武汉理工大学 学生实验报告书 实验课程名称《编译原理》 开课学院计算机科学与技术学院 指导老师姓名何九周 学生姓名刘洋 学生专业班级软件工程0803 2010 —2011 学年第二学期 实验课程名称：编译原理 实验项目名称单词的词法分析程序设计实验成绩实验者刘洋专业班级软件0803 组别 同组者实验日期 2011 年 5 月 17日 第一部分：实验分析与设计（可加页） 一、实验内容描述（问题域描述） 实验目的： 设计，编制并调试一个词法分析程序，加深对词法分析原理的理解。 实验要求： 在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写；上机时应随带有关的高级语言教材或参考书；要学会程序调试与纠错；每次实验后要交实验报告。 实验题目： 对于给定的源程序（如C语言或Pascal等），要求从组成源程序的字符行中寻找出单词，并给出它们的种别和属性——输出二元组序列。以便提供给语法分析的时候使用。要求能识别所有的关键字，标志符等，并且能够对出先的一些词法规则的错误进行必要的处理。 二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或 者算法描述） 实验原理： 由于这是一个用高级语言编写一个词法分析器,使之能识别输入串,并把分析结果(单词符号,标识符,关键字等等)输出.输入源程序,输入单词符号,本词法分析器可以辨别关键字,标识符,常数,运算符号和某些界符,运用了文件读入来获取源程序代码,再对该源程序代码进行词法分析,这就是词法分析器的基本功能.当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后,分析器就从此缓冲区中逐一识别单词符号.当缓冲区里的字符串被处理完之后,它又调用预处理子程序来处理新串. 编写的时候，使用了文件的输入和输出，以便于词法分析的通用型，同时在文件输出时，并保存在输出文件output文件中。 从左到右扫描程序，通过初始化：1为关键字；2为标志符； 3为常数；4为运算符或界符。 三、主要仪器设备及耗材 计算机实验三 递归下降分析程序实现
递归算法和非递归算法的区别和转换
编译原理-实验二-递归下降分析程序构造
数值分析上机实验报告
实验三_递归下降法的语法分析器
计算方法上机实习题大作业(实验报告).
递归下降语法分析程序的设计说明
高中信息技术 算法与程序设计-递归算法的实现教案 教科版
编译原理实验报告
递归下降分析法
递归算法详解
编译原理实验报告
相关主题
文本预览