《编译技术》课程实验指导书
实验一 词法分析
一.实验目的
1、 学会针对DFA转换图实现相应的高级语言源程序。
2、 深刻领会状态转换图的含义,逐步理解有限自动机。
3、 掌握手工生成词法分析器的方法,了解词法分析器的内部工作原理。
二.实验内容
TINY计算机语言的编译程序的词法分析部分实现。
从左到右扫描每行该语言源程序的符号,拼成单词,换成统一的内部表示(token)送给语法分析程序。
为了简化程序的编写,有具体的要求如下:
(1) 数仅仅是整数。
(2) 空白符仅仅是空格、回车符、制表符。
(3) 代码是自由格式。
(4) 注释应放在花括号之内,并且不允许嵌套
TINY语言的单词
三.实验要求
要求实现编译器的以下功能:
(1) 按规则拼单词,并转换成二元式形式
(2) 删除注释行
(3) 删除空白符 (空格、回车符、制表符)
(4) 显示源程序,在每行的前面加上行号,并且打印出每行包含的记号的二元形式
(5) 发现并定位错误。
词法分析进行具体的要求:
(1) 记号的二元式形式中种类采用枚举方法定义;其中保留字和特殊字符是每个都一个种类,标示符自己是一类,数字是一类;单词的属性就是表示的字符串值。
(2) 词法分析的具体功能实现是一个函数GetToken(),每次调用都对剩余的字符串分析得到一个单词或记号识别其种类,收集该记号的符号串属性,当识别一个单词完毕,采用返回值的形式返回符号的种类,同时采用程序变量的形式提供当前识别出记号的属性值。
(3) 标识符和保留字的词法构成相同,为了更好的实现,把语言的保留字建立一个表格存储,这样可以把保留字的识别放在标示符之后,用识别出的标示符对比该表格,如果存在该表格中则是保留字,否则是一般标识符。
实验二 递归下降语法分析器设计
一、实验目的
(1)加深对递归下降分析法一种自顶向下的语法分析方法的理解。
(2)根据文法的产生式规则消除左递归,提取公共左因子构造出相应的递归下降分析器。
二、实验内容
根据课堂讲授的形式化算法,编制程序实现递归下降分析器,能对常见的语句进行分析。
三、实验要求
要求实现以下语法的递归下降分析:
示例:
四、实现方法
将要实现语言的上下文无关文法进行检查,消除左递归和左公共因子,从逻辑上检测避免死循环和低效率处理。 采用每个产生式的左边的文法符号对应一个函数或过程的形式,编写程序实现一个递归下降分析器。注意这里的语法分析,是在词法分析的基础上进行的。
实验三 算符优先分析器设计
一、实验目的
(1)掌握算符优先分析法—— 一种自底向上的语法分析方法的思想。
(2)能识别算符优先分析法中的可规约串——最左素短语。
(3)领会算符优先关系表转换成优先函数的方法。
二、实验内容
根据课堂讲授的形式化算法,编制程序实现一个算符优先分析器,能对常见的算术表达式语句进行分析。
已知算符文法G[E]: E→E+E|E-E|E*E|E/E|(E)|-E|id,其优先关系表如下:
三、实验要求
要求实现以下功能:
a) 组织算术表达式的输入;
b) 组织算符优先关系表或者优先函数的输入;
c) 若输入的符号串是一个算术表达式语句,则输出一个分析树骨架(既每一步规约用到的最左素短语),否则输出一个错误信息;
c) 选做:采取相应的技巧,把算术表达式的结果计算出来。
四、实现方法
实现算法,转化成某种高级语言程序,实现一个算符优先分析器。其中要用到分析栈和输入缓冲器,本实验采用的方法是一种自底向上的语法分析方法,所以是在词法分析的基础上进行的。
提示:对于表达式结果的计算,要在算法中引入内部变量来保存结果,另外在分析过程中,除了移进、规约、接受、报错等动作外,还要引入计算的动作。
实验四 LR(k)分析器设计
一、实验目的
(1)掌握下推机这一数学模型的结构和理论,并深刻理解下推自动机在LR分析法中的应用(即LR分析器)。
(2)掌握LR分析法的思想,学会特定分析表的构造方法,利用给出的分析表进行LR分析。
二、实验内容
根据课堂讲授的形式化算法,编制程序实现对实验二中语法进行自底向上语法分析的LR分析器,设计分析表,对任一个输入语句进行语法分析,判断是否符合相应的文法要求。
三、实验要求
要求实现以下功能:
a) 设计分析表和语句的输入;
b) 要实现通用的LR分析思想的源代码;
c) 输出对语句的语法分析判断结果,如果可能给出错误的信息提示。
四、实现方法
根据课本的LR分析器模型和LR分析算法,完成LR分析。对要求中的错误信息提示,指的是对应分析表中的空白处,每一个空白的地方都应该有对应的错误情况,因而有相应的错误信息。注意这里的语法分析,是在词法分析的基础上进行的。
实验五 中间代码生成器设计
一、实验目的
(1) 熟悉各种中间代码表示的方式,比较它们之间的优缺点;
(2) 掌握语法树到中间代码的转换线性处理方法;
(3) 设计符合源语言和目标语言得到综合平衡的中间语言;
(4) 属性文法和语法制导翻译法进行语义翻译。
二、实验内容
根据课堂讲授的形式化,编制程序实现一个中间代码生成器,该程序能够使用前面的词法分析器和语法分析器,完成语法树到中间代码的转换。
三、实验要求
要求实现以下功能:
a) 设计比较完善的中间语言;
b) 对说明语句,要求将说明的各符号记录到相应符号表中;
c) 赋值语句的翻译,布尔表达式的翻译,过程调用的处理;
d) 对可执行语句,应产生出四元式中间代码并填写到三地址码表中;
b) 采用较为合理的结构实现生成器,简单的可以采用语法制导翻译法来实现,最好能够实现语法树直接线性化的中间代码生成,这样能够简单移植来实现其他类型的中间语言处理;
c) 在转换的过程中要进行错误处理。
四、实现方法
本设计可以采用JAVA语言或者C、C++语言来实现,实现的方法可以选择,可以参考PL/0编译器的实现形式,也可以采用《编译原理与实践》中讲述的简单的中间代码生成器,采用遍历语言树的形式完成到中间语言的转换。也可以按照课堂上讲授的方法和模型来完成。关键的是分析源和目标语言设计一个合适的中间语言,为了便于执行代码的转换要注意设计中语义的恰当处理。为了检查中间代码生成的效果,可以编写一个虚拟机执行中间代码。在设计中关键是语法树到中间代码的转换,注重其效率。
第二篇:《 智能决策技术》课程实验指导书
《智能决策技术》
实验指导书
信息管理系
目 录
实验一 具有事前信息的决策树技术的操作应用... 3
实验二 应用层次分析法进行多目标决策... 5
实验三 成本预测决策支持系统的开发... 7
实验四 专家系统开发工具CLIPS………………………………………………………
实验五 专家系统的开发………………………………………………………………….
实验一 具有事前信息的决策树技术的操作应用
实验类型:验证性 实验学时:2
实验目的:掌握风险型决策中的贝叶斯决策,利用决策树进行决策的方法。
实验内容:
某石油公司的决策人,打算投资开发某油田。根据现有资料,预计这口油井有高产、低产两种不同状态,分别记为S1、S2。高产可获利润400万元,而低产时将净亏损200万元,已知这两种情况出现的概率分别为:P(S1)=0.6,P(S2)=0.4,一般来说,常见的地质结构有“好”、“中等”、“差”3种,分别记为C1、C2、C3,为判断该地区属于哪种结构,可作进一步勘测,勘测费用为10万元。已知在不同的油井状态下,勘测结果为不同地质结构的概率如下,P(C1/S1)=0.7,P(C2/S1)=0.2,P(C3/S1)=0.1,P(C1/S2)=0.3,P(C2/S2)=0.1,P(C3/S2)=0.6,问:应采取何种行动方案,才能获取最大收益?
(问题:是否要进一步勘测?若进一步勘测,那么在勘测后应采取何种方案)
重点利用全概率公式:
和贝叶斯公式:
求后验概率部分,得出各方案在不同状态下的概率P(Sj/Ck),以求出最大期望值。
要求实验操作过程中,学生自己输入已有数据,并基于已知数据求出后验概率,然后求出不同方案的期望值,进行剪枝决策,得出最优方案。
具体过程如下:
第一步:将已知数据输入excel中,如表1所示。
表1 输入已知数据
第二步:用贝叶斯公式计算各自然状态下的后验概率P(Sj│Ck),用概率论中的全概率公式计算勘测结果为Ck的概率P(Ck)。
由公式
计算在不同勘测结果下、油井状态为高产或低产的后验概率。
由公式 计算勘测结果为Ck 的概率P(Ck)
在相关的单元格中输入上述公式,其计算结果如表2所示:
表2 后验概率与全概率的计算结果
上表中相应的公式见下表3
表3 后验概率与全概率的计算公式
第三步:构造决策树。
本实验的决策树如下图1所示
图1 决策树
第四步:计算各方案的期望收益值,并进行决策。
决策树中各方案的期望收益计算是从右向左进行的,首先考虑第二级决策,当勘测结果是“结构好”时,如果采取“不开发”方案,则期望收益为0;如果采取“开发”方案,则当自然状态为“高产”(其修正后的后验概率为0.78)时,收益为400,当自然状态为“低产”,(其修正后的后验概率为0.22)时,收益为-200,所以,“开发”方案的期望收益=400*0。78+(-200)*0.22=268(万元)。该值可以单元格P19中输入=V17*T17+V21*T21获得.
比较两种方案的期望收益,选择“开发”方案。所以当勘测结果为“结构好”时,应选择“开发”方案,其期望收益为268万元(这里暂时未扣除勘测费用)。前去“不开发”这一方案分支,并在“结构好”的概率分支上标上期望收益为268万元。同理可得,当勘测结果为“结构中等”时,应采取“开发”方案,其期望收益为250万元;当勘测结果为“结构差”时,应采取“不开发”方案,其期望收益为0(这里暂时均未扣除勘测费用)。
比较三个方案的期望收益,取期望收益最大的方案作为最优方案,在单元格D16中输入=MAX(G10,G14,G30)
得到最大期望收益值为175万元,可见方案“先勘测”的期望收益最大,为最优方案。
因此,本实验的最优决策结果是:先勘测,当勘测结果为“结构好”或“结构中等”时开发,当勘测结果为“结果差”时,不开发,该决策的期望收益为175万元。
实验小结(要求手写):
实验中遇到的问题及解决办法、心得、体会等等...
实验思考题(要求手写):
1、 利用各种资源查询一个DSS的应用案例,说明它的应用环境、功能结构和所起的作用(注:此处主要说明案例的适应领域,是用来解决什么问题的,怎样解决问题的,采用哪些技术或手段,它的结构是怎样的?你觉得这个DSS如何?为什么?)。
实验二 应用层次分析法进行多目标决策
实验类型:验证性 实验学时:3
实验目的:熟悉并应用层次分析方法对多方案进行优劣排序,从而使学生掌握综合定性和定量两种方法解决问题的思维方式。。
实验内容:
某公司打算增添一台新设备,现有三种不同型号的设备,P1,P2,P3供选择,选择设备主要考虑的要素是功能、价格和维护,你将如何选择?
第一步,建立递阶层次结构模型。
图1 设备购买决策的递阶层次结构图
第二步,构造比较判断矩阵。
设比较判断矩阵A= (i.j=1,2,……,n)。比较判断矩阵中的元素a ij
是以上一层某要素(比如说要素A)为准则,对本层次的n个元素( 比如说,要素C1,C2……C n)进行两两比较来确定的。其形式如下:
A C1 C2 …… Cj …… Cn
C1 a11 a12 a1j a1n
C2 a21 a22 a2j a2n
…… …… …… …… ……
Ci ai1 ai2 aij ain
……
Cn an1 an2 anj ann
其中,比较判断矩阵中的元素aij表示对上一层要素A要素而言,本层要素Ci的相对重要程度。
本实验中,A为目标层,其下一层的相关要素有三个:功能C1,价格C2,维护C3。通过咨询,由专家对要素C1,C2,C3进行两两比较,得到如下结果:“功能(C1)”比“价格C2”明显重要,比“维护(C3)”稍微重要,“价格C2”比“功能(C1)”明显不重要,比“维护(C3)”稍微不重要。由此构造出比较出判断矩阵A-C如下:
1 5 3
A-C= 1/5 1 1/3
1/3 3 1
. 1 1/4 2
C1-p= 4 1 8
1/2 1/8 1
1 4 1/3
C2-p= 1/4 1 1/8
3 8 1
1 1 1/3
C3-p= 1 1 1/5
3 5 1
第三步,层次单排序。
首先,估算比较判断矩阵各列的列和Sj。
其次,将比较判断矩阵A中的各个要素除以该要素所在的列的列和Sj,得到一个归一化了的新矩阵Anorm,这里归一化矩阵是指每一列和等于1的矩阵,则有,
再次,计算新矩阵Anormk中每一行的均值Wi,它就是特征向量W,它就是A矩阵中各要素的层次单排序权值。
最后,由特征向量估算特征根
第四步,层次总排序
求出最低层(方案层)相对于最高层(目标层)的相对重要性排序权值,也就是层次总排序权值,最大的为最优方案。
即C层对于总目标A的层次总排序权值,是以上一层次B的层次总排序权值为权重、对C层的层次单排序权值进行加权和得出的,如下式所示:
第五步,一致性检验
定义一致性指标CI为
定义一致性比率CR为
其中,RI为平均随机一致性指标,它是与比较判断矩阵的阶数有关的指标,即RI可查表得出,当n=3时,RI=0.52。
计算出CR,当CR≤0.1时,比较判断矩阵具有满意的一致性。
本实验具体操作步骤如下:
(1)输入比较判断矩阵如表1所示:
(2)层次单排序和归一化矩阵如表2所示:
(3)一致性检验如表3所示
表1 比较判断矩阵 表2 层次单排序
表4 层次总排序
表3一致性检验
(4)层次总排序如表4所示:
决策结果p2最优。
实验小结:
实验中遇到的问题及解决办法、心得体会等
思考题:
除了AHP方法外,解决多目标决策问题还有哪些方法?简单介绍其中的一种方法是如何解决多目标问题的?
实验三 成本预测决策支持系统的开发
(必修,4学时)
一、实验目的
熟悉和掌握决策支持技术的运行机制,掌握基于规则推理的基本方法和智能决策过程。能熟练运用所学的风险决策法、期望值法、决策树等方法对多方案进行分析和选择,确定最优方案,以进一步理解智能决策支持和专家系统等相关理论。
二、预备知识
能熟练掌握并运用某一软件如Delphi、Access、Excel、Flash等进行智能决策专家系统的局部设计和实现,掌握专家系统与智能决策支持系统等相关理论,课题设计内容不限。
决策过程与决策技术应该由以下四个步骤:
(1) 情报活动:探查环境、寻求要求决策的条件;
(2) 设计活动:创造、制订和分析可能采取的行动方案;
(3) 抉择活动:从可资利用的方案中选出行动方案;
(4) 检查活动:对过去所做的抉择进行评价
三、实验要求
根据实验目的和自身能力,自行设计实验方案,选择实验工具,拟定实验操作程序加以实现并对实验结果进行分析处理。
该实验的设计性特点要求学生具有一定的主动性、探索性,实验工具和方法不限。
四、实验内容
1.学生应了解具体的决策过程:确定目标——拟定方案——分析方案——选择方案——实施方案,依据该过程设计自己的实验。
2.学生可以根据个人兴趣和能力设计小型专家系统(包括数据库、推理机制和人机界面),进行推理判断、决策。参考课题如下:成本预测决策支持系统开发,麦粒肿诊断专家系统开发,大学生心理素质测评专家系统,动物是识别专家系统,产品市场需求预测决策支持系统,产品销售优化决策支持,产品生产优化决策支持,材料存储优化决策支持,其它经营活动决策支持等。
六、实验结论
包括设计对象、实验方案论证、实验结果分析等,具体要写成实验报告.