文档库 最新最全的文档下载
当前位置:文档库 › 编译原理 算符优先分析实验报告

编译原理 算符优先分析实验报告

编译原理 算符优先分析实验报告
编译原理 算符优先分析实验报告

实验四、算符优先分析算法

姓名:

学号:

班级:

指导老师:

时间:

计算机与信息技术学院

程序功能描述

实现算符优先分析算法,完成以下描述算术表达式的算符优先文法的算符优先分析过程。

G[E]:E→E+T∣E-T∣T

T→T*F∣T/F∣F

F→(E)∣i

说明:终结符号i 为用户定义的简单变量,即标识符的定义。

(1)构造该算符优先文法的优先关系矩阵或优先函数;(2)输入串应是词法分析的输出二元式序列,即某算术表达式“实验项目一”的输出结果,输出为输入串是否为该文法定义的算术表达式的判断结果;(3)算符优先分析过程应能发现输入串出错。(4)设计两个测试用例(尽可能完备,正确和出错),并给出测试结果。

备注:程序中判断该输入串是否为该文法定义的算术表达式的结果,若是则输出“accept”,若不是则输出“error”。该二元式序列要以“#”为结尾。

主要数据结构描述

程序结构描述

程序测试:

测试1:(i+i*i)

输出:

输入二:i+i*ii

输出:

学习总结

算符优先文法关键点就在于判断各个终结符号的优先级,构造算符优先矩阵是个难点,程序里面没有实现,而是直接定义了优先矩阵,这是需要完善的地方,试试能不能在程序中动态地构造优先矩阵。另外对于算符优先文法,失败的条件是比较两个非终结符的优先关系,若优先关系表中为空,就返回error.

算符优先分析器设计实验报告--宁剑

编译原理实验报告 题目: 算符优先分析法分析器 学 院 计算机科学与技术 专 业 xxxxxxxxxxxxxxxx 学 号 xxxxxxxxxxxx 姓 名 宁剑 指导教师 xxxx 2015年xx 月xx 日 算符优先分析法分析器 装 订 线

一、实验目的 1.理解自底向上优先分析,比较和自顶向下优先分析的不同。 2.理解算符优先分析的特点,体会其和简单优先分析方法的不同。 3.加深对编译器语法分析的理解。 二、实验原理 1.自底向上优先分析方法,也称移进-归约分析,粗略地说它的思想是对输入符号串自左向右进行扫描,并将输入符号逐个移入一个后进先出栈,边移入边分析,一旦栈顶符号串形成某个句型的句柄或可归约串时,就将该产生式的左部非终极符代替相应的右边文法符号串。 2.算符优先分析法的基本思想 首先确定算符(确切地说是终结符)之间的优先关系和结合性质,然后借助这种关系,比较相邻算符之间的优先级来确定句型的可归约串,并进行归约。 注意:算符优先分析过程是自下而上的归约过程,但它的可归约串未必是句柄,也就是说,算符优先分析过程不是一种规归约。 3.终结符号间优先关系的确定,用FIRSTVT和LASTVT计算。 4.最左素短语 所谓素短语是指这样一个短语,它至少含有一个终结符,并且除它自身之外不再含有其它素短语。最左素短语是指处于句型最左边的那个素短语。最左素短语是算符优先分析算法的可归约串。 5.计算得到所给文法的算符优先矩阵

6.算符优先分析的基本过程 三、实验要求 使用算符优先分析算法分析下面的文法: E’→#E# E→E+T|T T→T*F|F F→P^F|P

编译原理课程设计报告_算符优先分析法

编译原理课程设计报告_算符优先分析法 编译原理课程设计报告 选题名称: 算符优先分析法 系(院): 计算机工程学院 专业: 计算机科学与技术 班级: 姓名: 学号: 指导教师: 学年学期: 7>2012 ~ 2013 学年第 1 学期 2012年 12 月 04 日 设计任务书 课题名称算符优先分析法 设计 目的 通过一周的课程设计,对算符优先分析法有深刻的理解,达到巩固理论知识、锻炼实践能力、构建合理知识结构的目的。实验环境Windows2000以上操作系统,Visual C++6.0编译环境 任务要求 1.判断文法是否为算符优先文法,对相应文法字符串进行算符优先分析; 2.编写代码,实现算符优先文法判断和相应文法字符串的算符优先分析; 3.撰写课程设计报告; 4提交报告。工作进度计划序号起止日期工作内容 1 理论辅导,搜集资料 2 ~编写代码,上机调试

3 撰写课程设计报告 4 提交报告 指导教师(签章): 年月日 摘要: 编译原理是计算机专业重要的一门专业基础课程,内容庞大,涉及面广,知识点多。本次课程设计的目的正是基于此,力求为学生提供一个理论联系实际的机会,通过布置一定难度的课题,要求学生独立完成。我们这次课程设计的主要任务是编程实现对输入合法的算符优先文法的相应的字符串进行算符优先分析,并输出算符优先分析的过程。算符优先分析法特别有利于表达式的处理,宜于手工实现。算符优先分析过程是自下而上的归约过程,但这种归约未必是严格的规范归约。而在整个归约过程中,起决定作用的是相继连个终结符之间的优先关系。因此,所谓算符优先分析法就是定义算符之间的某种优先关系,并借助这种关系寻找句型的最左素短语进行归约。通过实践,建立系统设计的整体思想,锻炼编写程序、调试程序的能力,学习文档编写规范,培养独立学习、吸取他人经验、探索前言知识的习惯,树立团队协作精神。同时,课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷。 关键字:编译原理;归约;算符优先分析;最左素短语; 目录 1 课题综述 1 1.1 课题来源 1 1.2课题意义 1 1.3 预期目标 1 1.4 面对的问题 1 2 系统分析 2

数据结构实验二——算术表达式求值实验报告

《数据结构与数据库》 实验报告 实验题目 算术表达式求值 学院:化学与材料科学学院 专业班级:09级材料科学与工程系PB0920603 姓名:李维谷 学号:PB09206285 邮箱:liwg@https://www.wendangku.net/doc/8b1575007.html, 指导教师:贾伯琪 实验时间:2010年10月10日 一、需要分析 问题描述:

表达式计算是实现程序设计语言的基本问题之一,它的实现是栈的应用的一个典型例子。设计一个程序,演示通过将数学表达式字符串转化为后缀表达式,并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析: 在计算机中,算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级,又要考虑括号,因此,算术表达式的求值不可能严格地从左到右进行。因而在程序设计时,借助栈实现。 设置运算符栈(字符型)和运算数栈(浮点型)辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理,然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果,输入表达式后演示在求值中运算数栈内的栈顶数据变化过程,最后得到运算结果。 算法规定: 输入形式:一个算术表达式,由常量、变量、运算符和括号组成(以字符串形式输入)。为使实验更完善,允许操作数为实数,操作符为(、)、.(表示小数点)、+、-、*、/、^(表示乘方),用#表示结束。 输出形式:演示表达式运算的中间结果和整个表达式的最终结果,以浮点型输出。 程序功能:对实数内的加减乘除乘方运算能正确的运算出结果,并能正确对错误输入和无定义的运算报错,能连续测试多组数据。 测试数据:正确输入:12*(3.6/3+4^2-1)# 输出结果:194.4

实验4 算符优先分析法.

实验名称: 实验任务: 对下述描述算符表达式的算符优先文法G[E],给出算符优先分析的实验结果。 实验容: 有上下无关文法如下: E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 说明:优先关系矩阵的构造过程: (1) = 关系由产生式 F->(E) 知‘(’=‘)’ FIRSTVT集及LASTVT集 FIRSTVT(E)={ +,-,*,/,(,i } FIRSTVT(F)={ (,i } FIRSTVT(T)={ *,/,(,i } LASTVT(E)={ +,-,*,/,),i } LASTVT(F)={ ),i } LASTVT(T)={ *,/,),i } (2) < 关系 +T 则有:+ < FIRSTVT(T) -T 则有:- < FIRSTVT(T) *F 则有:* < FIRSTVT(F)

/F 则有:/ < FIRSTVT(F) (E 则有:( < FIRSTVT(E) (3) > 关系 E+ 则有: LASTVT(E) > + E- 则有: LASTVT(E) > - T* 则有: LASTVT(T) > * T/ 则有: LASTVT(T) > / E) 则有: LASTVT(E) > ) (4)请大家画出优先关系矩阵 终结符之间的优先关系是唯一的,所以该文法是算符优先文法。程序的功能描述:程序由文件读入字符串(以#结束),然后进行算符优先分析,分析过程中如有错误,则终止程序并报告错误位置,最终向屏幕输出移近——规约过程。

(5)依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。算法描述如下: for 每个形如 P->X1X2…Xn的产生式 do for i =1 to n-1 do begin if Xi和Xi+1都是终结符 then Xi = Xi+1 if i<= n-2, Xi和Xi+2 是终结符, 但Xi+1 为非终结符 then Xi = Xi+2 if Xi为终结符, Xi+1为非终结符 then for FirstVT 中的每个元素 a do Xi < a if Xi为非终结符, Xi+1为终结符 then for LastVT 中的每个元素 a do a > Xi+1 end (6)构造总控程序 算法描述如下: stack S; k = 1; //符号栈S的使用深度

编译原理 实验3 算符优先分析

编译原理实验3 算符优先分析 一、实验目的 通过设计编制调试构造FIRSTVT集、LASTVT集和构造算符优先表、对给定符号串进行分析的程序,了解构造算符优先分析表的步骤,对文法的要求,生成算符优先关系表的算法,对给定的符号串进行分析的方法。 二、实验内容 1. 给定一文法G,输出G的每个非终结符的FIRSTVT集和LASTVT集。 2. 构造算符优先表。 3. 对给定的符号串进行分析,包含符号栈,符号栈栈顶符号和输入串当前符号的优先级,最左素短语和使用的产生式和采取的动作。 三、程序思路 在文法框内输入待判断文法产生式,格式E->a|S,注意左部和右部之间是“->”,每个产生式一行,ENTER键换行。文法结束再输入一行G->#E# 1. 先做文法判断,即可判断文法情况。 2. 若是算符优先文法,则在优先表栏显示优先表。 3. 写入要分析的句子,按回车即可。 4. 在分析过程栏,可以看到整个归约过程情况 四、实验结果 FunctorFirst.h #include #include #include #include usingnamespace std;

#define rightlength 20 #define product_num 20 // 产生式最多个数 #define num_noterminal 26 // 非终结符最多个数 #define num_terminal 26 // 终结符最多个数 struct Production { char Left; char Right[rightlength]; int num; }; struct VT { bool vt[num_noterminal][num_terminal]; }; struct Stack { char P; char a; }; class CMyDlg { public:CMyDlg(); void InputRule(); CString showLastVT(); CString showFirstVT(); CString shownoTerminal(char G[]); CString showTerminal(char g[]); CString showLeftS(char S[], int j, int k); void InitAll(); CString showSentence(CString sen, int start); CString showStack(char S[], int n); void Initarry(char arry[], int n); CString ProdtoCStr(Production prod); int selectProd(int i, int j, char S[]); void preFunctor(CString sen); void insertFirstVT(Stack S[], int&sp, char P, char a); void insertLastVT(Stack S[], int&sp, char P, char a); void ShowPreTable(); void createPreTable();

编译原理实验报告

编译原理实验报告 班级 姓名: 学号: 自我评定:

实验一词法分析程序实现 一、实验目的与要求 通过编写和调试一个词法分析程序,掌握在对程序设计语言的源程序进行扫描的过程中,将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。 二、实验内容 根据教学要求并结合学生自己的兴趣和具体情况,从具有代表性的高级程序设计语言的各类典型单词中,选取一个适当大小的子集。例如,可以完成无符号常数这一类典型单词的识别后,再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的扫描器的设计和实现。 输入:由符合或不符合所规定的单词类别结构的各类单词组成的源程序。 输出:把单词的字符形式的表示翻译成编译器的内部表示,即确定单词串的输出形式。例如,所输出的每一单词均按形如(CLASS,VALUE)的二元式编码。对于变量和常数,CLASS字段为相应的类别码;VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号(要求在变量名表登记项中存放该标识符的字符串;常数表登记项中则存放该常数的二进制形式)。对于关键字和运算符,采用一词一类的编码形式;由于采用一词一类的编码方式,所以仅需在二元式的CLASS字段上放置相应的单词的类别码,VALUE字段则为“空”。另外,为便于查看由词法分析程序所输出的单词串,要求在CLASS字段上放置单词类别的助记符。 三、实现方法与环境 词法分析是编译程序的第一个处理阶段,可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义(如BNF),用手工的方式(例如可用C语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应的状态矩阵,该状态矩阵同控制程序便组成了编译器的词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成,即首先用正规式对语言中的各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程序所应进行的语义处理工作,然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。 总的来说,开发一种新语言时,由于它的单词符号在不停地修改,采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了,则采用手工编写词法分析程序效率更高。 四、实验设计 1)题目1:试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。 语言中具有的单词包括五个有代表性的关键字begin、end、if、then、else;标识符;整型常数;六种关系运算符;一个赋值符和四个算术运算符。参考实现方法简述如下。 单词的分类:构造上述语言中的各类单词符号及其分类码表。 表I 语言中的各类单词符号及其分类码表 单词符号类别编码类别码的助记符单词值

编译原理实验报告5-语法分析程序的设计(2)

实验5 语法分析程序的设计(2) 一、实验目的 通过设计、编制、调试一个典型的语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,进一步掌握常用的语法分析中算法优先分析方法。 二、实验内容 设计一个文法的算法优先分析程序,判断特定表达式的正确性。 三、实验要求 1、给出文法如下: G[E] E->T|E+T; T->F|T*F; F->i|(E); + * ( ) i + * ( ) i 2、计算机中表示上述优先关系,优先关系的机内存放方式有两种1)直接存放,2)为 优先关系建立优先函数,这里由学生自己选择一种方式; 1、给出算符优先分析算法如下: k:=1; S[k]:=‘#’; REPEAT 把下一个输入符号读进a中; IF S[k]∈V T THEN j:=k ELSE j:=k-1; WHILE S[j] a DO BEGIN REPEAT Q:=S[j]; IF S[j-1]∈V T THEN j:=j-1 ELSE j:=j-2 UNTIL S[j] Q 把S[j+1]…S[k]归约为某个N; k:=j+1;

S[k]:=N; END OF WHILE; IF S[j] a OR S[j] a THEN BEGIN k:=k+1;S[k]:=a END ELSE ERROR UNTIL a=‘#’ 1、 根据给出算法,利用适当的数据结构实现算符优先分析程序; 2、 利用算符优先分析程序完成下列功能: 1) 手工将测试的表达式写入文本文件,每个表达式写一行,用“;”表示结束; 2) 读入文本文件中的表达式; 3) 调用实验2中的词法分析程序搜索单词; 4) 把单词送入算法优先分析程序,判断表达式是否正确(是否是给出文法的语 言),若错误,应给出错误信息; 5) 完成上述功能,有余力的同学可以对正确的表达式计算出结果。 四、实验环境 PC 微机 DOS 操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、 分析文法中终结符号的优先关系; 2、 存放优先关系或构造优先函数; 3、利用算符优先分析的算法编写分析程序; 4、写测试程序,包括表达式的读入和结果的输出; 5、程序运行效果,测试数据可以参考下列给出的数据。 六、测试数据 输入数据: 编辑一个文本文文件expression.txt ,在文件中输入 如下内容: 正确 结果: (1)10; 输出:正确 (2)1+2; 输出:正确 (3)(1+2)*3+(5+6*7); 输出:正确 (4)((1+2)*3+4 10; 1+2; (1+2)*3+(5+6*7); ((1+2)*3+4; 1+2+3+(*4+5); (a+b)*(c+d); ((ab3+de4)**5)+1;

编译原理实验4算符优先算法

一、实验目的与任务 算术表达式和赋值语句的文法可以是(你可以根据需要适当改变): S→i=E E→E+E|E-E|E*E|E/E|(E)|i 根据算符优先分析法,将赋值语句进行语法分析,翻译成等价的一组基本操作,每一基本操作用四元式表示。 二、实验涉及的相关知识点 算符的优先顺序。 三、实验内容与过程 如参考C语言的运算符。输入如下表达式(以分号为结束):(1)a = 10; (2)b = a + 20; 注:此例可以进行优化后输出(不作要求):(+,b,a,20) (3)c=(1+2)/3+4-(5+6/7); 四、实验结果及分析 (1)输出:(=, a,10,-) (2)输出:(=,r1,20,-)

(+,r2,a,r1) (=,b,r2,-) (3)输出:(+,r1,1,2) (/,r2,r1,3) (/,r3,6,7) (+,r4,5,r3,) (+,r5,r2,4) (-,r6,r5,r4) (=,c,r6,-) 五、实验有关附件(如程序、附图、参考资料,等) ... ... h == '#') o][Peek(n0).No]; if(r == '<') h == 'E'&& Peek(1).ch == '#' && Token[ipToken].ch == '#') return TRUE; else return FALSE; } h) { k = TRUE; h == 'E') { n ++; } return n; } 词结束(遇到“#”号),无法移进,需要规约,返回:1 词没有结束,需判断是否可以移进 栈单词<=单词:移进后返回:2 栈单词>单词:不能移进,需要规约,返回:1 单词没有优先关系:出错,返回:-1 int MoveIn() { SToken s,t; h = '#';

编译原理实验报告

学生学号0120810680316 实验课成绩 武汉理工大学 学生实验报告书 实验课程名称《编译原理》 开课学院计算机科学与技术学院 指导老师姓名何九周 学生姓名刘洋 学生专业班级软件工程0803 2010 —2011 学年第二学期

实验课程名称:编译原理 实验项目名称单词的词法分析程序设计实验成绩实验者刘洋专业班级软件0803 组别 同组者实验日期 2011 年 5 月 17日 第一部分:实验分析与设计(可加页) 一、实验内容描述(问题域描述) 实验目的: 设计,编制并调试一个词法分析程序,加深对词法分析原理的理解。 实验要求: 在上机前应认真做好各种准备工作,熟悉机器的操作系统和语言的集成环境,独立完成算法编制和程序代码的编写;上机时应随带有关的高级语言教材或参考书;要学会程序调试与纠错;每次实验后要交实验报告。 实验题目: 对于给定的源程序(如C语言或Pascal等),要求从组成源程序的字符行中寻找出单词,并给出它们的种别和属性——输出二元组序列。以便提供给语法分析的时候使用。要求能识别所有的关键字,标志符等,并且能够对出先的一些词法规则的错误进行必要的处理。 二、实验基本原理与设计(包括实验方案设计,实验手段的确定,试验步骤等,用硬件逻辑或 者算法描述) 实验原理: 由于这是一个用高级语言编写一个词法分析器,使之能识别输入串,并把分析结果(单词符号,标识符,关键字等等)输出.输入源程序,输入单词符号,本词法分析器可以辨别关键字,标识符,常数,运算符号和某些界符,运用了文件读入来获取源程序代码,再对该源程序代码进行词法分析,这就是词法分析器的基本功能.当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后,分析器就从此缓冲区中逐一识别单词符号.当缓冲区里的字符串被处理完之后,它又调用预处理子程序来处理新串. 编写的时候,使用了文件的输入和输出,以便于词法分析的通用型,同时在文件输出时,并保存在输出文件output文件中。 从左到右扫描程序,通过初始化:1为关键字;2为标志符; 3为常数;4为运算符或界符。 三、主要仪器设备及耗材 计算机

编译原理作业集-第五章-修订(精选.)

第五章语法分析—自下而上分析 本章要点 1. 自下而上语法分析法的基本概念: 2. 算符优先分析法; 3. LR分析法分析过程; 4. 语法分析器自动产生工具Y ACC; 5. LR分析过程中的出错处理。 本章目标 掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。 本章重点 1.自下而上语法分析的基本概念:归约、句柄、最左素短语; 2.算符优先分析方法:FirstVT, LastVT集的计算,算符优先表的构造,工作原理;3.LR分析器: (1)LR(0)项目集族,LR(1)项目集簇; (2)LR(0)、SLR、LR(1)和LALR(1)分析表的构造; (3)LR分析的基本原理,分析过程; 4.LR方法如何用于二义文法; 本章难点 1. 句柄的概念; 2. 算符优先分析法; 3. LR分析器基本; 作业题 一、单项选择题: 1. LR语法分析栈中存放的状态是识别________的DFA状态。 a. 前缀; b. 可归前缀; c. 项目; d. 句柄; 2. 算符优先分析法每次都是对________进行归约: (a)句柄(b)最左素短语(c)素短语(d)简单短语

3. 有文法G=({S},{a},{S→SaS,S→ε},S),该文法是________。 a. LL(1)文法; b.二义性文法; c.算符优先文法; d.SLR(1)文法; 4. 在编译程序中,语法分析分为自顶向下分析和自底向上分析两类,和LL(1)分析法属于自顶向下分析; a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法 5. 自底向上语法分析采用分析法,常用的是自底向上语法分析有算符优先分析法和LR分析法。 a. 递归 b. 回溯 c. 枚举 d. 移进-归约 6. 一个LR(k)文法,无论k取多大,。 a. 都是无二义性的; b. 都是二义性的; c. 一部分是二义性的; d. 无法判定二义性; 7. 在编译程序中,语法分析分为自顶向下分析和自底向上分析两类,和LR分析法属于自底向上分析。 a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法 8. 在编译程序中,语法分析分为自顶向下分析和自底向上分析两类,自顶向下分析试图为输入符号串构造一个; a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导 9. 在编译程序中,语法分析分为自顶向下分析和自底向上分析两类,自底向上分析试图为输入符号串构造一个。 a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导 10. 采用自顶向下分析方法时,要求文法中不含有。 a. 右递归 b. 左递归 c. 直接右递归 d. 直接左递归 11. LR分析是寻找右句型的;而算符优先分析是寻找右句型的。 a. 短语; b. 素短语; c. 最左素短语; d. 句柄 12. LR分析法中分析能力最强的是;分析能力最弱的是。 a. SLR(1); b. LR(0); c. LR(1); d. LALR(1) 13. 设有文法G: T->T*F | F F->F↑P | P P->(T) | a 该文法句型T*P↑(T*F)的最左直接短语是下列符号串________。 a. (T*F), b. T*F, c. P, d. P↑(T*F) 14. 在通常的语法分析方法中,()特别适用于表达式的分析。 a.算符优先分析法b.LR分析法c.递归下降分析法d.LL(1)分析法 15. .运算符的优先数之间有几种关系。 a.3种 b. 2种 c. 4种 d. 1种 16. 算符优先法属于() a.自上而下分析法 b.LR分析法 c.SLR分析法 d.自下而上分析法 17. 在LR分析法中,分析栈中存放的状态是识别规范句型的DFA状态。 a.句柄 b. 前缀 c. 活前缀 d. LR(0)项目 一.答案: 1. b; 2. b; 3. b; 4. d; 5. d; 6. a; 7. c; 8. c; 9. d;10. b;11. d,c;12. c,b;13. a;14. a 15. a;16. d;17. c;

实验三算符优先分析算法设计与实现

实验三算符优先分析算法的设计与实现 (8学时) 一、实验目的 根据算符优先分析法,对表达式进行语法分析,使其能够判断一个表达式是否正确。通过算符优先分析方法的实现,加深对自下而上语法分析方法的理解。 二、实验要求 1、输入文法。可以是如下算术表达式的文法(你可以根据需要适当改变): E→E+T|E-T|T T→T*F|T/F|F F→(E)|i 2、对给定表达式进行分析,输出表达式正确与否的判断。 程序输入/输出示例: 输入:1+2; 输出:正确 输入:(1+2)/3+4-(5+6/7); 输出:正确 输入:((1-2)/3+4 输出:错误 输入:1+2-3+(*4/5) 输出:错误 三、实验步骤 1、参考数据结构 char *VN=0,*VT=0;//非终结符和终结符数组 char firstvt[N][N],lastvt[N][N],table[N][N]; typedef struct //符号对(P,a) { char Vn; char Vt; } VN_VT; typedef struct //栈 { VN_VT *top; VN_VT *bollow; int size; }stack; 2、根据文法求FIRSTVT集和LASTVT集 给定一个上下文无关文法,根据算法设计一个程序,求文法中每个非终结符的FirstVT 集和LastVT 集。

算符描述如下: /*求 FirstVT 集的算法*/ PROCEDURE insert(P,a); IF not F[P,a] then begin F[P,a] = true; //(P,a)进栈 end; Procedure FirstVT; Begin for 对每个非终结符 P和终结符 a do F[P,a] = false for 对每个形如 P a…或 P→Qa…的产生式 do Insert(P,a) while stack 非空 begin 栈顶项出栈,记为(Q,a) for 对每条形如 P→Q…的产生式 do insert(P,a) end; end. 同理,可构造计算LASTVT的算法。 3、构造算符优先分析表 依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。 算法描述如下: for 每个形如 P->X1X2…X n的产生式 do for i =1 to n-1 do begin if X i和X i+1都是终结符 then X i = X i+1 if i<= n-2, X i和X i+2 是终结符, 但X i+1 为非终结符 then X i = X i+2 if X i为终结符, X i+1为非终结符 then for FirstVT 中的每个元素 a do X i < a ; if X i为非终结符, X i+1为终结符 then for LastVT 中的每个元素 a do a > X i+1 ; end 4、构造总控程序 算法描述如下: stack S; k = 1; //符号栈S的使用深度 S[k] = ‘#’ REPEAT

编译原理实验报告总结

学年第学期《编译原理》实验报告 学院(系):计算机科学与工程学院 班级:11303070A 学号:11303070*** 姓名:无名氏 指导教师:保密式 时间:2016 年7 月

目录 1.实验目的 (1) 2.实验内容及要求 (1) 3.实验方案设计 (1) 3.1 编译系统原理介绍 (1) 3.1.1 编译程序介绍 (2) 3.1.2 对所写编译程序的源语言的描述 (2) 3.2 词法分析程序的设计 (3) 3.3 语法分析程序设计 (4) 3.4 语义分析和中间代码生成程序的设计 (4) 4. 结果及测试分析 (4) 4.1软件运行环境及限制 (4) 4.2测试数据说明 (5) 4.3运行结果及功能说明 (5) 5.总结及心得体会 (7)

1.实验目的 根据Sample语言或者自定义的某种语言,设计该语言的编译前端。包括词法分析,语法分析、语义分析及中间代码生成部分。 2.实验内容及要求 (1)词法分析器 输入源程序,输出对应的token表,符号表和词法错误信息。按规则拼单词,并转换成二元形式;滤掉空白符,跳过注释、换行符及一些无用的符号;进行行列计数,用于指出出错的行列号,并复制出错部分;列表打印源程序;发现并定位词法错误; (2)语法分析器 输入token串,通过语法分析,寻找其中的语法错误。要求能实现Sample 语言或自定义语言中几种最常见的、基本的语法单位的分析:算术表达式、布尔表达式、赋值语句、if语句、for语句、while语句、do while语句等。 (3)语义分析和中间代码生成 输入token串,进行语义分析,修改符号表,寻找其中的语义错误,并生 成中间代码。要求能实现Sample语言或自定义语言中几种最常见的、基本的语法单位的分析:算术表达式、布尔表达式、赋值语句、if语句、for语句、while 语句、do while语句等。 实验要求:功能相对完善,有输入、输出描述,有测试数据,并介绍不足。3.实验方案设计 3.1 编译系统原理介绍 编译器逐行扫描高级语言程序源程序,编译的过程如下: (1).词法分析 识别关键字、字面量、标识符(变量名、数据名)、运算符、注释行(给人看的,一般不处理)、特殊符号(续行、语句结束、数组)等六类符号,分别归类等待处理。 (2).语法分析 一个语句看作一串记号(Token)流,由语法分析器进行处理。按照语言的文法检查判定是否是合乎语法的句子。如果是合法句子就以内部格式保存,否则报错。直至检查完整个程序。 (3).语义分析 语义分析器对各句子的语法做检查:运算符两边类型是否相兼容;该做哪些类型转换(例如,实数向整数赋值要"取整");控制转移是否到不该去的地方;是

编译原理_实验报告实验二__语法分析(算符优先) 2

华北水利水电学院编译原理实验报告 一、实验题目:语法分析(算符优先分析程序) (1)选择最有代表性的语法分析方法算符优先法; (2)选择对各种常见程序语言都用的语法结构,如赋值语句(尤指表达式)作为分析对象,并且与所选语法分析方法要比较贴切。 二、实验内容 (1)根据给定文法,先求出FirstVt和LastVt集合,构造算符优先关系表(要求算符优先关系表输出到屏幕或者输出到文件); (2)根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式(要求输出归约过程) (3)给定表达式文法为: G(E’): E’→#E# E→E+T | T T→T*F |F F→(E)|i (4) 分析的句子为: (i+i)*i和i+i)*i 三、程序源代 #include #include #include #include #define SIZE 128 char priority[6][6]; //算符优先关系表数组 char input[SIZE]; //存放输入的要进行分析的句子 char remain[SIZE]; //存放剩余串 char AnalyseStack[SIZE]; //分析栈 void analyse(); int testchar(char x); //判断字符X在算符优先关系表中的位置 void remainString(); //移进时处理剩余字符串,即去掉剩余字符串第一个字符 int k; void init()//构造算符优先关系表,并将其存入数组中 {

编 译 原 理 实 验 报 告

编译原理实验报告 课程:编译原理 系别:计算机系 班级:11网络 姓名:王佳明 学号:110912049 教师:刘老师 实验小组:第二组 1

实验一熟悉C程序开发环境、进行简单程序的调试 实验目的: 1、初步了解vc++6.0环境; 2、熟悉掌握调试c程序的步骤: 实验内容: 1、输入下列程序,练习Turbo C 程序的编辑、编译、运行。 #include main() { printf(“Programming is fun.\n”); } 2、分析程序,预测其运行结果,并上机检测你的预测。 #include main() { printf(“*\n”); printf(“* * *\n”); printf(“* * * * *\n”); printf(“* * * * * * *\n”); } 3、下面是一个加法程序,程序运行时等待用户从键盘输入两个整数,然后求出它们的和并输出。观察运行结果(程序输出),上机验证该程序。 #include main() { int a,b,c; printf(“Please input a,b:”); scanf(“%d,%d”,&a,&b); c=a+b; printf(“%d+%d=%d\n”,a,b,c); } 2

实验二词法分析器 一、实验目的: 设计、编制、调试一个词法分析子程序-识别单词,加深对词法分析原理的理解。 二、实验要求: 1.对给定的程序通过词法分析器弄够识别一个个单词符号,并以二元式(单词种别码,单词符号的属性值)显示。而本程序则是通过对给定路径的文件的分析后以单词符号和文字提示显示。 2.本程序自行规定: (1)关键字"begin","end","if","then","else","while","write","read", "do", "call","const","char","until","procedure","repeat" (2)运算符:"+","-","*","/","=" (3)界符:"{","}","[","]",";",",",".","(",")",":" (4)其他标记如字符串,表示以字母开头的标识符。 (5)空格、回车、换行符跳过。 在屏幕上显示如下: ( 1 , 无符号整数) ( begin , 关键字) ( if , 关键字) ( +, 运算符) ( ;, 界符) ( a , 普通标识符) 三、使用环境: Windows下的visual c++6.0; 四、调试程序: 1.举例说明文件位置:f:、、11.txt目标程序如下: begin x:=9 if x>0 then x:=x+1; while a:=0 do 3

c语言实现算符优先语法分析

#include char prog[100],zhongjian[100],shu[500]; char ch,zh; int syn,p,q,a,b,c,d; //p指向prog,q指向zhongjian int table[8][8]={ {1,1,-1,-1,-1,1,-1,1}, {1,1,-1,-1,-1,1,-1,1}, {1,1,1,1,-1,1,-1,1}, {1,1,1,1,-1,1,-1,1}, {-1,-1,-1,-1,-1,-1,-1,0}, {1,1,1,1,0,1,0,1}, {1,1,1,1,0,1,0,1}, {-1,-1,-1,-1,-1,0,-1,-1}}; //存储算符优先关系表,大于为1,小于或等于为-1,其它为0表示出错char zhan[100];//数组栈 int z,j;//z为栈顶指针,j为zhongjian数组指针 void push(char ch)//入栈 { zhan[z++]=ch; } void pop()//出栈 { z--; } void putzhan()//打印栈内字符 { for(int i=0;i

编译原理 六章 算符优先分析法

第六章算符优先分析法 课前索引 【课前思考】 ◇什么是自下而上语法分析的策略? ◇什么是移进-归约分析? ◇移进-归约过程和自顶向下最右推导有何关系? ◇自下而上语法分析成功的标志是什么? ◇什么是可归约串? ◇移进-归约过程的关键问题是什么? ◇如何确定可归约串? ◇如何决定什么时候移进,什么时候归约? ◇什么是算符文法?什么是算符优先文法? ◇算符优先分析是如何识别可归约串的? ◇算符优先分析法的优缺点和局限性有哪些? 【学习目标】 算符优先分析法是自下而上(自底向上)语法分析的一种,尤其适应于表达式的语法分析,由于它的算法简单直观易于理解,因此,也是学习其它自下而上语法分析的基础。通过本章学习学员应掌握: ◇对给定的文法能够判断该文法是否是算符文法 ◇对给定的算符文法能够判断该文法是否是算符优先文法 ◇对给定的算符文法能构造算符优先关系表,并能利用算符优先关系表判断该文法是否是算符优先文法。 ◇能应用算符优先分析算法对给定的输入串进行移进-归约分析,在分析的每一步能确定当前应移进还是归约,并能判断所给的输入串是否是该文法的句子。 ◇了解算符优先分析法的优缺点和实际应用中的局限性。 【学习指南】 算符优先分析法是自下而上语法分析的一种,它的算法简单、直观、易于理解,所以通常作为学习其它自下而上语法分析的基础。为学好本章内容,学员应复习有关语法分析的知识,如:什么是语言、文法、句子、句型、短语、简单短语、句柄、最右推导、规范归约基本概念。 【难重点】 ◇通过本章学习后,学员应该能知道算符文法的形式。 ◇对一个给定的算符文法能构造算符优先关系分析表,并能判别所给文法是否为算符优先文法。 ◇分清规范句型的句柄和最左素短语的区别,进而分清算符优先归约和规范归约的区别。 ◇算符优先分析的可归约串是句型的最左素短语,在分析过程中如何寻找可归约串是算符优先分析的关键问题。对一个给定的输入串能应用算符优先关系分析表给出分析(归约)步骤,并最终判断所给输入串是否为该文法的句子。 ◇深入理解算符优先分析法的优缺点和实际应用中的局限性。 【知识点】

编译原理算符优先算法语法分析实验报告

数学与计算机学院编译原理实验报告 年级专业学号姓名成绩 实验题目算符优先分析法分析器的设计实验日期 一、实验目的: 设计一个算符优先分析器,理解优先分析方法的原理。 二、实验要求: 设计一个算符优先分析器 三、实验内容: 使用算符优先分析算法分析下面的文法: E’→#E# E →E+T | T T →T*F | F F →P^F | P P →(E) | i 其中i可以看作是一个终结符,无需作词法分析。具体要求如下: 1、如果输入符号串为正确句子,显示分析步骤,包括分析栈中的内容、优先关系、输入符号串的变化情况; 2、如果输入符号串不是正确句子,则指示出错位置。 四、实验结果及主要代码: 1.主要代码 void operatorp()

{ char s[100]; char a,Q; int k,j,i,l; string input,temp; cin>>input; cout<<"步骤"<<'\t'<<"栈"<<'\t'<<"优先关系"<<'\t'<<"当前符号"<<'\t'<<"剩余输入串"<<'\t'<<"移进或归约"<') { cout<<'('<

for(l=1;l'<<'\t'<

编译原理实验报告一

实验一词法分析程序实现 一、实验目得与要求 通过编写与调试一个词法分析程序,掌握在对程序设计语言得源程序进行扫描得过程中,将字符流形式得源程序转化为一个由各类单词符号组成得流得词法分析方法 二、实验内容 基本实验题目:若某一程序设计语言中得单词包括五个关键字begin、end、if、then、else;标识符;无符号常数;六种关系运算符;一个赋值符与四个算术运算符,试构造能识别这些单词得词法分析程序(各类单词得分类码参见表I)。 表I语言中得各类单词符号及其分类码表 输入:由符合与不符合所规定得单词类别结构得各类单词组成得源程序文件。 输出:把所识别出得每一单词均按形如(CLASS,VALUE)得二元式形式输出,并将结果放到某个文件中。对于标识符与无符号常数,CLASS字段为相应得类别码得助记符;V AL UE字段则就是该标识符、常数得具体值;对于关键字与运算符,采用一词一类得编码形式,仅需在二元式得CLASS字段上放置相应单词得类别码得助记符,V ALUE字段则为“空". 三、实现方法与环境 词法分析就是编译程序得第一个处理阶段,可以通过两种途径来构造词法分析程序.其一就是根据对语言中各类单词得某种描述或定义(如BNF),用手工得方式(例如可用C语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应得状态矩阵,该状态矩阵连同控制程序一起便组成了编译器得词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序得另外一种途径就是所谓得词法分析程序得自动生成,即首先用正规式对语言中得各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程

相关文档
相关文档 最新文档