语法分析器实验报告

实验三语法分析器一、实验目的：理解和掌握LL(1)语法分析方法的基本原理；根据给出的LL(1)文法，掌握LL(1)分析表的构造及分析过程的实现，掌握语法分析方法和程序设计方法。二、实验要求：对每个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与。产生式结构几乎是一致的，通过设计、编程、调试出一个具体语法分析程序。三、实验原理：语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器的工作本质上是按文法的产生式，识别输入串是否是一个句子。自上而下分析法的主旨是，对任何输入串，试图用一切可能的方法，从文法开始符号出发，自上而下地为输入串建立一棵语法树。这种方法本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。对于一个文法满足以下三个条件，则称该文法为LL(1)文法。文法不含有左递归。对于文法中的每一个非终结符A的各个产生式的侯选首符集两两不相交。即，若A->Q1|Q2|…|Qn则FIRST(Qi)^FIRST(Qj)=null(i!=j)对文法中的每个非终结符号A，若他存在某个侯选首符集包含空串，则FIRST(A)^FOLLOW(A)=null对于一个文法满足LL(1)条件时，我们就可以对其输入串进行有效的无回溯的自上而下分析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符号。四、实验步骤：1、功能描述：根据给定的文法，由程序生成项集族和语法分析表，对输入的源程序进行词法分析，得到语法分析的输入串，经过语法分析后得到三个栈，它们分别是状态栈，字符栈，输入栈，从而分析出输入的源程序是否有语法错误。2、构造自己设计的小语言的语法分析器：(1)语言的语法描述(语法规则)的设计即文法的设计；(2)把文法形式符号中所隐含的信息内容挖掘出来并用LL或LR的资料形式(分析表)表示出来；(3)语法分析的数据输入形式和输出形式的确定；(4)语法分析程序各个模块的设计与调试。3、主程序流程图：开始开始定义各个数据结构定义find()，first()，closure()，mygoto()，sign(),items()，reloatoken()函数main()函数开始从“in_gram.txt”文件中读入文法；计算产生式的个数调用sign（）提取文法符号序列调用item（）分析项集簇输出各状态自动机，即项集簇输出语法分析表首行根据anatab[i][j]的数值填写分析表从“in_code.txt”读入待分析代码调用reload（）进行词法分析把词法分析的结果写入“in_out.txt”从“in_out.txt”读入词法分析结果语法分析，把分析过程栈的状态输出结束五、程序的设计与实现：1、主要函数说明：1)find(state&unclosure,intn)函数：功能：判断是否已包含某一产生式。在求闭包closure()函数中对其进行调用；参数说明：unclosure还没有求闭包的状态；n表示第几个产生式；2)first(chartmp)函数：求各文法符号的first集，确定搜索符时使用到。在求闭包的函数中队其进行调用；参数说明：tmp为需要求first集的文法符号；3)sign()函数：功能：提取文法符号序列，将所有的文法符号+’$’都存放在一个一维数组中，该数组在输出分析表及语法分析中对栈进行处理时是需要使用；4)reloadtoken()函数：功能：词法分析的结果。从文件中读入字符到buff中，将得到的单词定义成相应的运算符、分隔符，关键字k，标识符i，实数f'，整数n；写入到out_in.txt文件中，该文件为词法分析的输出，语法分析的输入；5)voiditems(coll&head)函数：功能：求LR(1)项目集族；6)voidclosure(state&unclosure)函数：功能：求LR(1)项目集族的闭包；7)statemygoto(conststate&cur,intk,inttmp)函数：功能：写分析表anatab[][]，使用数字，空白用0，S移入为负数，r规约为正数，-32767表示acc接受。六、实验结果（1）输入一个文法（2）输入一个符号串七、实验结果分析：本次实验借助语法分析，设计一个表达式的判断分析器，从键盘上输入算术表达式，分析器对该表达式的正确与否进行分析。若是正确的算术表达式，则符合文法，输出正确；若是错误的算术表达式，则表达式不符合文法，输出其错误之处并显示异常。该程序执行过程无误，输出结果正常。但由于我们的疏忽，该程序未能完全满足实验要求，并不能够构造其LR分析表，并不是由该分析表驱动的语法分析器程序，这是本次实验的一个缺陷。八、实验总结：此次实验，让我对编译原理的基本知识有了深入的了解，加强