2024-2025(1)编译原理实验指导

编译原理试验指导书合肥学院计算机科学与技术系试验一词法分析程序 一、试验目的通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并驾驭在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 二、试验内容 1.编制一个读单词词法分析程序即扫描器;从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类；其中包括名字、类型、安排的内存空间； 2.并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分接着显示）3.处理各常量说明，计算每个常量的值和类型。 三、试验预习提示 1、词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号经常表示成以下的二元式(单词种别码，单词符号的属性值)。本试验中，采纳的是一类符号一种别码的方式。 2、单词的BNF表示- -| | - -| -+ - - -= 3、“超前搜寻”方法 词法分析时，经常会用到超前搜寻方法。如当前待分析字符串为“a+”,当前字符为，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？明显，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符+，这时可知应将说明为大于运算符。但此时，超前读了一个字符+，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似状况。 4、模块结构四、试验步骤 (一）打算： 1.阅读课本有关章节，明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。 2.初步编制好程序。 3.打算好多组测试数据。 (二）上机： 将源代码拷贝到机上调试，发觉错误，再修改完善。上机调试通过。 (三)写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 (四)程序要求：程序输入/输出示例： 如源程序为C语言。输入如下一段： main() inta,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。 运算符包括：+、-、*、/、=、=、u1|u2|un处理的方法如下：U() ch=当前符号; if(ch可能是u1字的开头)处理u1的程序部分; elseif(ch可能是u2字的开头)处理u2的程序部分; elseerror() （2） 对于每个右部u1-x1x2xn的处理架构如下： 处理x1的程序； 处理x2的程序； 处理xn的程序；（3）假如右部为空，则不处理。 （4）对于右部中的每个符号xi 假如xi为终结符号： if(xi=当前的符号) NextChar()； return; else 出错处理 假如xi为非终结符号，干脆调用相应的过程xi() 说明：NextChar为前进一个字符函数。 四、试验步骤： （一）打算： 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.对学有余力的同学，可以具体的输出推导的过程，即具体列出每一步运用的产生式。试验三LL（1）分析方法 一、试验目的依据某一文法编制调试LL（1）分析程序，以便对随意输入的符号串进行分析。加深对预料分析LL（1）分析法的理解。二、试验内容1.定义部分：定义常量、变量、数据结构。 2.初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； 3.限制部分：从键盘输入一个表达式符号串； 4.利用LL(1)分析算法进行表达式处理：依据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，假如遇到错误则显示错误信息。三、试验预习提示 1.LL（1）分析法的功能LL（1）分析法的功能是利用LL（1）限制程序依据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。2.LL（1）分析法的前提 改造文法：消退二义性、消退左递归、提取左因子，推断是否为LL（1）文法， 3.LL（1）分析法试验设计思想及算法 四、试验步骤： （一）打算： 1.阅读课本有关章节， 2.考虑好设计方案； 3.设计出模块结构、测试数据，初步编制好程序。 （二）上课上机： 将源代码拷贝到机上调试，发觉错误，再修改完善。其次次上机调试通过。 （三）程序要求： 程序输入/输出示例： 对下列文法，用LL（1）分析法对随意输入的符号串进行分析： （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)LL（1）分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+*/（）i#)：在此位置输入符号串 (3)输出过程如下： 步骤分析栈剩余输入串 所用产生式 1 E i+i*i# E-TG (4)输入符号串为非法符号串(或者为合法符号串) 备注：(1)在“所用产生式”一列中假如对应有推导则写出所用产生式；假如为匹配终结符则写明匹配的终结符；如分析异样出错则写为“分析出错”；若胜利结束则写为“分析胜利”。(2)在此位置输入符号串为用户自行输入的符号串。(3)上述描述的输出过程只是其中一部分的。 留意：1.表达式中允许运用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.假如遇到错误的表达式，应输出错误提示信息（该信息越具体越好）； 3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行比照；试验四算符优先文法处理 一、试验目的驾驭算符优先分析法的原理，利用算符优先分析法将赋值语句进行语法分析，翻译成等价的四元式表示。二、试验内容： 1.算术表达式的文法可以是（你可以依据须要适当变更）： EE+E|E-E|E*E|E/E|（E）|i 2.依据算符优先分析法，将表达式进行语法分析，推断一个表达式是否正确。 3.将赋值语句进行语法分析，翻译成等价的一组基本操作，每一基本操作用四元式表示。 三、试验预习提示1.试验原理 我们要分析的表达式满意下面的算符优先矩阵 21+ - * / ( ) + - * / ( =为实现算符优先算法，可以运用两个工作栈。一个叫做OPTR，用以寄存运算符，一个叫OPND,用以寄存操作数或结果。算法描述如下： 1首先置操作数栈为空栈，将表达式起始符;作为运算符栈的栈底元素。2依次读入表达式中每个单词，若是操作数则进OPND栈，若是运算符则转3。 3将此运算符1与OPTR栈顶元素2进行比较，即查上表，若12，则：1进栈，转2 若12,如1为；，则分析胜利，否则OPTR栈顶元素出栈，并转2 若1B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTOi,A移进状态栈，其中i为修改指针后的栈顶状态。 (3) 接受acc: 当归约到文法符号栈中只剩文法的起先符号S时，并且输入符号串已结束即当前输入符是#，则为分析胜利。 (4) 报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。 3、LL（1）分析法试验设计思想及算法 四、试验步骤（一）打算： 1.阅读课本有关章节， 2.考虑好设计方案； 3.设计出模块结构、测试数据，初步编制好程序。 （二）上课上机： 将源代码拷贝到机上调试，发觉错误，再修改完善。 （三）程序要求： 程序输入/输出示例： 对下列文法，用LR（1）分析法对随意输入的符号串进行分析： （1）E-E+T （2）E-ET （3）T-T*F （4）T-T/F （5）F-(E) （6）F-i 输出的格式如下： (1)LR（1）分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+*/（）i#)：在此位置输入符号串 (3)输出过程如下： 步骤状态栈符号栈剩余输入串动作10 # i+i*i# 移进 (4)输入符号串为非法符号串(或者为合法符号串)备注：(1)在“所用产生式”一列中假如对应有推导则写出所用产生式；假如为匹配终结符则写明匹配的终结符；如分析异样出错则写为“分析出错”；若胜利结束则写为“分析胜利”。 (2)在此位置输入符号串为用户自行输入的符号串。 留意：1.表达式中允许运用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.假如遇到错误的表达式，应输出错误提示信息（该信息越具体越好）； 3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行比照；试验六逆波兰式的产生及计算一、试验目的将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。 二、试验内容1.定义部分：定义常量、变量、数据结构。 2.初始化：设立算符优先分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； 3.限制部分：从键盘输入一个表达式符号串； 4.利用算符优先分析算法进行表达式处理：依据算符优先分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，假如遇到错误则显示错误信息。 5.对生成的逆波兰式进行计算。 三、试验预习提示1、逆波兰式定义 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象依次不变，运算符号位置反映运算依次。采纳逆波兰式可以很好的表示简洁算术表达式，其优点在于易于计算机处理表达式。2、产生逆波兰式的前提中缀算术表达式 3、逆波兰式生成的试验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简洁算术表达式，为便利起见,设该简洁算术表达式的右端多加上了优先级最低的特别符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符起先推断，假如该字符是数字，则分析到该数字串的结束并将该数字串干脆输出。(4)假如不是数字，该字符则是运算符，此时需比较优先关系。做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。假如，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘如不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简洁算术表达式，确定全部字符都得到正确处理，我们便可以将中缀式表示的简洁算术表达式转化为逆波兰表示的简洁算术表达式。3、逆波兰式计算的试验设计思想及算法 (1)构造一个栈，存放运算对象。 (2)读入一个用逆波兰式表示的简洁算术表达式。 (3)自左至右扫描该简洁算术表达式并推断该字符，假如该字符是运算对象，则将该字符入栈。若是运算符，假如此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。假如该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。 (4)重复上述操作直至扫描完整个简洁算术表达式的逆波兰式，确定全部字符都得到正确处理，我们便可以求出该简洁算术表达式的值。四、试验步骤（一）打算： 1.阅读课本有关章节， 2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。 （二）上课上机：将源代码拷贝到机上调试，发觉错误，再修改完善。其次次上机调试通过。 （三）程序要求： 程序输入/输出示例： 输出的格式如下：(1)逆波兰式的生成及计算程序，编制人：姓名，学号，班级 (2)输入一以#结束的中缀表达式(包括+*/（）数字#)：在此位置输入符号串如(28+68)*2#(3)逆波兰式为：28&68+2* (4)逆波兰式28&68+2*计算结果为192 备注：(1)在生成的逆波兰式中假如两个数相连则用&分隔，如28和68，中间用&分隔； (2)在此位置输入符号串为用户自行输入的符号串。留意：1.表达式中允许运用运算符（+-*/）、分割符（括号）、数字，结束符#；2.假如遇到错误的表达式，应输出错误提示信息（该信息越具体越好）； 3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行比照试验七课程设计 一、试验目的综合运用各章的学问，完成小型编译系统，初步驾驭编译系统开发的基本方法；提高学生的应用程序设计实力，提高分析问题、解决问题的实力。 二、试验内容 1.利用需求分析、设计说明写出程序结构框架，阐明设计思路、用到的原理和方法。 2.程序规模适中，着重于内核功能，对界面无要求。3.充分利用试验一、二、三模块和结论。4.课程试验具有词法分析、语法分析、语义分析，目标代码生成等基本功能。 三、试验步骤（一）选题：通过平常积累，找到适合于自己的应用或某种软件功能，该应用能利用编译原理中的某些理论。题目大小适中。请在一周前选好题目。参考题目如下： 1.表达式计算器：这是一款算术表达式计算程序，可干脆利用试验四的成果，用户通过输入表达式达到计算的目的，可代替目前普遍运用的计算器。设计难度一般。 2.字符串搜寻程序：用户输入要查找的字符串的正则表达式，软件可在大量文本中找到符合描述的字符串。这个设计可参考微软.NET的正则表达式的功能。 3.逻辑运算分析：可对关系表达式进行分析，并得出结果。这个设计结果可变更后用于电路分析、谓词演算等。 4.小型编译器设计：设计具有词法分析器、语法分析器、中间代码产生器和说明执行代码的说明器的编译器。5.其他：在网上发布。 （二）分析：选好题目后，分析该题目的应用性，可用到编译原理的哪些理论？对它们进行简洁阐述。同时对软件进行需求分析，通过回答下面问题得到： 软件供应哪些功能？软件有什么用？界面怎样？怎样运用该软件？对输入数据的格式有什么要求？用什么语言开发？怎样测试该软件？该软件开发的进度如何支配？ 写出以上问题的答案，然后自问：你的分析材料别人能特别清晰地看懂吗？假如回答是确定的，就可以搞设计了。 （三）设计： 对软件划分功能模块，将模块细化，设计出数据存放格式，写出各模块（函数）的功能、传递参数的格式和返回值的类型，画出模块结构图。最终画出程序流程图。（四）上机（修改设计/编码/调试/测试）： 第一次上机：依据流程图编制并输入代码，老师查看学生的设计，对设计提出修改看法。 第一次上机后：修改设计，接着完成输入代码，并作初步调试。 其次次上机：调试，老师帮助解决学生设计和调试中出现的难题。其次次上机后：修改设计中的缺陷，完善程序。 第三次上机：演示软件，老师依据实际状况提出测试用例，学生作最终的修改和完善，老师评分。 第三次上机后：接着完善程序，并完成设计说明书，上交成果。 （五）留意事项： 测试数据的设计：每组测试数据包括输入数据、预期的输出结果、实际的输出结果和预期的是否相吻合（假如不吻合，实际输出什么？可能错误的缘由？检查源代码或设计进行查错，纪录结果。（六）上交： 1.程序源代码（打包上传，文件名中包含姓名）； 2.一组较完备的测试数据（存在一个文本文件中上传）；附试验报告范例试验名称：词法分析 一、试验目的和要求 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。 二、试验内容和步骤：试验内容 对于这个试验，我总共用了四个函数，即主函数、扫描函数、建立缓冲区、取单词。主要完成的功能是从缓冲区中识别出一个个单词，并能够区分所取的单词是什么类型。 试验步骤 1、基于试验的内容，构造程序所需的模块 2、依据已建构的模块，写出各个模块的相应程序代码 3、在主函数中调用模块来完成所要得到的效果 在此，我想先介绍一下我的三个子模块，第一个是扫描函数。扫描函数scanner()，其实大家都比较熟识了，就是我们上次试验内容，可以原封不动的拿来用。它的功能是调用一次就从缓冲区中取一个字符出来。这为我们的取字符供应了基础，因此假如这个程序不会设计的话，那么这个试验就没法设计了。至于建立其次个模块，就是从文件中把一个个字符读到缓冲区，比较简洁，我在这里就不想说了。接下来，我想比较地说一下第三个模块，也就是本试验的主要要求。这个模块的函数程序代码如下： chargetsym()/从缓冲区中取一个单词 boolflag=false;/用来表示取出的单词是否为关键词，假如是则flag的值为true,否则为false intk=-1;/表示取出的字符放在单词数组的指针 CType=0;/预先定义的取出的单词的类型Lasttype=0;/初始化从前的类型，此变量为推断正负数用 while(ch0)/去掉不能显示的字符Fbuffer=scanner(); if(ch=a&ch=A&ch=Z)/取出标识符或者是关键词 k=-1; while(true)/取出的单词长度不超过WMaxlen，假如超过，则其后的字符无效 if(+k)=a&ch=A&ch=0&ch=9) break; Word+k=0;/以0标识取出单词的结束，以便利后面的推断此单词是标识符还是关键词 for(inti=0;i=0&ch=0&ch=9) Word+k=ch;Fbuffer=scanner(); elseCType=3;break;/不是数字则跳出循环/假如以字母开头，且长度不超过WMaxlen，且下面跟有字母，则此整数非法，输出类型为8，在主程序中输出出错信息 if(k=a&ch=A&ch=a&ch=A&ch=0&ch=9|Fbuffer=-1) if(kWMaxlen)/假如长度大于取出单词定义的最大长度，则返回类型为8，在主程序中打出出错信息 CType=Longtype; elseCType=Errtype;/否则返回类型7，在主程序出错，并明确写出此单词的具体内容 Word+k=0; elseif(ch=+|ch=-|ch=*|ch=/)/取出是运算符号的单词 Word+k=ch; if(ch=+|ch=-)/假如是+号或者是-号，则还要推断是不是正负数if(Lasttype=6)/推断其取出的当前字母的前一个单词是6号类型的，即是、=、=、=时则可推断现在取出的是整数 Fbuffer=scanner(); while(ch=0&ch|ch=|ch=|ch=!)/取出运算符的另几类，即、=、=、=、!= Word+k=ch;Fbuffer=scanner(); if(ch=)/推断是不是=、=、!= Word+k=ch; Fbuffer=scanner(); Word+k=0; for(inti=0;iSign_No;i+)/推断取出的单词是不是运算符 if(strcmp(Signi,Word)=0) flag=true; break; if(flag)CType=4; Lasttype=6; elseif(ch=,|ch=;|ch=|ch=|ch=(|ch=)/推断当前取出的单词是不是界符，假如是界符，则定义其类型为5 CType=5; Word+k=ch; Word+k=0; Fbuffer=scanner(); return(CType); 此函数返回一个识别出来的单词的类型，其实还返回一个值，那就是识别出来的单词。这样为主程序的输出供应便利。在此函数中调用了扫描程序，调用一次就判别是否当前在取的单词已经结束。所以这样子的话，在取另一个单词时，已经从缓冲区取出了一个字符，这为单词的选取以及主程序判别程序是否结束供应了便利。其实这也是主程序在起先调用这个函数之前这前就先在缓冲区中取了一个字符的缘由。 这几个函数中，主函数调用了三个函数，getsym调用了source函数 四、试验过程记录1、出现致命错误， 缘由分析：原来把定义取出单词的最大长度放在缓冲区中的最大长度上了。 解决：把缓冲区的长度重新定义一下。 2、答案错0误，老是在输出的答案中多出一个0字符缘由分析：定义存放在单词字符串中的指针初始值为1，结果在while（true）以后做赋值操作，这样就多出一个字符while(true)if(k)WMaxlen) k+; Wordk=ch; 解决：改为如下即可while(true) if(+k)WMaxlen) k+; Wordk=ch; 3、在字母后老是多一个数字2 缘由分析：定义的标识符有关系，可能与前一个相冲突了 解决：把WType改为CType 4、有些输出的类型不相匹配 缘由分析，在类型赋值时，由于考虑的条件比较多，没有考虑到在同一种状况下的另一个分支类别是不同的。 解决：用return(type)语句使得在已经知道确定的类型后，让程序即时返回。免得其类型在后面又被赋值。 5、程序不能结束 缘由分析：在截掉多出的字符后，没让程序把缓冲区中的字符读完，导致程序又起先读同一个单词后的几个字母 解决：截取后，让其在分程序中读完此单词并设立标记使其结束 五、试验总结 共花时五个小时，半个小时思索。其它的都是在电脑上调程序，我一般来说比较喜爱哪里出错了以后，采纳单步调试来解决。假如有些东西忘了，可以多翻翻以前的c语言这本书。 此程序还有很多没有考虑到，比如说不能区分出浮点数。所以假如以后想到的话，还想好好地来修改一下。最大的收获是在提出一个难题以后，假如能比较顺手的解决的话，那是一件比较快乐的事。只是有些时候越想问题就会越多，也越难解决，那就得渐渐调试，渐渐推导了。信任只要想得出，就能调得出，当然耐性是很重要的，花在上面的时间也是要多一点的。