语法分析程序

编译原理实验报告HUNANUNIVERSITY编译原理实验报告题目：语法分析器的实现学生姓名：杨玉茹学生学号：201508010325专业班级：计科1503上课老师：杨晓波编译原理实验报告1目录一、实验目的...............................................................错误!未定义书签。二、实验任务..............................................................................................2三、实验内容..............................................................................................2四、系统设计..............................................................................................2五、实验测试............................................................................................12六、实验体会............................................................................................13附录（源代码及注释）............................................................................14编译原理实验报告2一、实验目的（一）学习已有编译器的经典语法分析源程序。（二）通过本次实验，加深对语法分析的理解，学会编制语法分析器。二、实验任务（一）阅读已有编译器的经典语法分析源程序，并测试语法分析器的输出。（二）用C或JAVA语言编写一门语言的语法分析器。三、实验内容（一）学习经典的语法分析器（2学时）（1）选择一个编译器，如：TINY或PL/0，其它编译器也可（需自备源代码）。（2）通过将定义语言的语法规则的BNF文法改写成EBNF文法，以利于递归下降分析算法。（3）阅读语法分析源程序，加上你自己的理解。尤其要求对相关函数与重要变量的作用与功能进行稍微详细的描述。若能加上学习心得则更好。TINY语言请参考《编译原理及实践》第3.7节；PL/0语言请参考相关实现文档。对TINY语言要特别注意抽象语法树的定义与应用。对PL/0语言要特别注意各种符号表的处理。（4）测试语法分析器。对TINY语言要求输出测试程序的字符形式的抽象语法树。（手工或编程）画出图形形式的抽象语法树。对PL/0语言要求给出测试程序的各种符号表的内容。TINY语言：测试用例一：sample.tny。测试用例二：用TINY语言自编一个程序计算任意两个正整数的最大公约数与最大公倍数。PL/0语言：测试用例一~三：test.pls，test2.pls，a1.pls。（二）实现一门语言的语法分析器（6学时）（1）语言确定：C－语言，其定义在《编译原理及实践》附录A中。也可选择其它语言，不过要有该语言的详细定义（可仿照C－语言）。一旦选定，不能更改，因为要在以后继续实现编译器的其它部分。鼓励自己定义一门语言。（2）完成C－语言的BNF文法到EBNF文法的转换。通过这一转换，消除左递归，提取左公因子，将文法改写为LL（1）文法，以适用于自顶向下的语法分析。规划需要将哪些非终结符写成递归下降函数。（3）为每一个将要写成递归下降函数的非终结符，如：变量声明、函数声明、语句序列、语句、表达式等，定义其抽象语法子树的形式结构，然后定义C－语言的语法树的数据结构。（4）仿照前面学习的语法分析器，编写选定语言的语法分析器。（5）准备2~3个测试用例，测试并解释程序的运行结果。编译原理实验报告3四、系统设计（1）实验设计思路分析：思路：主函数里面的执行步骤：（由于我所使用的绘图软件不能导出图片，因此只能通过截屏）编译原理实验报告4（2）代码分析A．声明产生式Pronode：包括三部分，产生式左边、产生式的推导符号、产生式右边编译原理实验报告5B.每次声明一个产生式以后需要对产生式进行初始化；C.输入一个含有产生式的文件txt以后，需要对文件进行读取，因此这里使用了ReadPro函数进行读取；读取的方式主要是运用库函数fsanf以输入流的方式进行读取；分三段进行读取，产生式的左边、终结推介符号、右边；D．打印txt文件里面含有的产生式PrintPro；E.对产生式里面的终结符号和非终结符号分别用SetUnTerminate和SetTerminate进行存储到UnTerminate和Terminate两个数组当中去；用bool数flag对表里面的内容进行标记，如果已经含有了，就不需要再进行存储了；如果没有标记过，就加入表中去；编译原理实验报告6F．获得产生式的First集合以及Follow集合；First集合的求解方法：○1如果右边的第一个字符是一个终结符号，那么直接加入到First集合当中去；○2如果右边的第一个字符是非终结符号，若对于产生式右边的一切非终结符,均可推出ε，则将ε加进FIRST集，○3将产生式右边能推出空字符的非终结符的Frist集中不含ε的终结符加入到该非终结符的Fisrt集；○4产生式右边不能推出空字符的非终结符的Frist集加入到该非终结符的Fisrt集；变量说明：boolIsNull(charc)：非终结符能否产生空字符boolIsTerminate(charc)：判断是否为终结符号voidAddChar(charchArray[],charc)：将非终结符的所有first值加入First集voidAddCharToChar(charchArray[],charotherArray[])：将非终结符的所有first集加入First集voidAddCharToChar(charchArray[],charotherArray[])：将非终结符的所有first集加入First集voidAddFollow(charfollow[],charc);将非终结符的所有follow值加入Follow集编译原理实验报告7Follow集合的求解方法：○1将$放进Follow（S）集合当中去，其中S是开始符号；○2如果存在一个产生式A-aCB,那么FOLLOW(B)中除了$之外的所有符号都在FOOLOW（B）当中了；○3如果存在一个产生式A-aB，或者存在产生式A-aCB且FIRST（B）包含空，那么FOLLOW（A）中的所有的符号都在FOLLOW(B)中；编译原理实验报告8G．根据给出的First集合和Follow集合选择出对应的输入的符号对应的产生式SetSelect；步骤：○1扫描每一个产生式，求出Select集合○2如果产生式的右边第一字符为终结符，则将其加入select集○3如果产生式的右边字符为ε,则应将左边字符的follow集加入select集产生式右边的第一个字符为非终结符，则逐个分析：若α=X1X2…Xnα′，其中Xi∈VN,1≤i≤n；若ε∈FIRST(X1),则将FIRST(X2)中的一切非ε的终结符加进FIRST(α),FIRST(α)则应加入select集；以此类推○4处理像E-ABaβ的产生式的情况，若α=X1X2…Xnα′，其中Xi∈VN,1≤i≤n；若对于一切1≤i≤n,ε∈FIRST(Xi)，则将follow(α)加入select集合；相关代码（由于代码太长了，只截取了一部分的代码）：编译原理实验报告9H.构造分析表SetSheet，根据我们已经求出来的FIRST集合和FOLLOW集合，构造出预测分析表：I．输入我所需要分析的字符串voidInputSym()；编译原理实验报告10J.万事具备只欠东风，此时所有的事情已经准备好了，那么就只需要一一的进行分析；voidScan()函数就将字符串的分析过程体现出来了，当然这个分析过程包含了以下几个重要的部分：存储符号的栈：包括栈底和栈顶，以及栈的大小存储剩余符号的队列：队列里面包含了两个结构，一个是数据，一个是指向下一个数据的指针；预测分析表：也就是我们刚刚构造出来的分析表SetSheet；每一步操作所运用到的产生式PrintSheet(introw,intcol)：编译原理实验报告11F分析的过程：○1将#压入栈中，Push(SymStack,'#');○2开始符号入栈，Push(SymStack,UnTerminate[0]);○3读入第一个符号：a=GetSym(Remain);○4查看是否和输入符号的第一个符号对应，如果没有的话，就继续在栈中进行左递推；○5如果对应了就将此符号出队列，然后再进行左递推；编译原理实验报告12五、实验测试我的pro.txt文件里面的产生式为：打印出的产生式与我的产生式是一样的：得出的分析表：编译原理实验报告13对i*i进行预测分析时执行的步骤：六、实验心得a)实验问题：1)程序读不到我的pro.txt文件刚开始的时候，我写了一个读取txt文件里面的产生式的文件，可以每次我输入文件名以后，程序也不报任何的错误或者信息，也没有显示不能读取，我检查了半天我的程序，最后发现是我最后在txt文件里面末尾少写了一个#。b)实验心得：由于有了之前几次实验的基础，所以这次在理解题意的时候变得相对的简单一点了，不过这次实验明显比前几次都难，涉及到的步骤程序太多了，因此思绪很容易乱。不过由于之前我已经把LL的方法透彻的理解过了，所以相对要好一些，过程中遇到了不少的麻烦，所以部分的代码编译原理实验报告14借鉴了网上的。LL（1）分析器是自顶向下的一个最重要的分析，所以这是我们这学期该重点掌握的内容，所以做实验的过程也加强了我对这个算法的理解。七、附录（源代码及注释）代码附在文件夹里面编译原理实验报告15HUNANUNIVERSITY编译原理实验报告题目：LL（1）分析学生姓名：杨玉茹学生学号：201508010325专业班级：计科1503上课老师：杨晓波、陈浩编译原理实验报告16目录一、实验目的...............................................................错误!未定义书签。二、实验任务..............................................................................................2三、实验内容..............................................................................................2四、系统设计..............................................................................................2五、实验测试............................................................................................12六、实验体会............................................................................................13附录（源代码及注释）............................................................................14编译原理实验报告17二、实验目的学习和掌握LL（1）文法的判定