编译原理实验报告3-LL(1)文法构造 联系客服

发布时间 : 星期四 文章编译原理实验报告3-LL(1)文法构造更新完毕开始阅读

数带来的弊端。

7、 实验总结。

实验本身是比较麻烦的,好在关键的remove_left_recursion()和remove_left_gene()两个子函数提供了算法再加上本身理论课提供的大量额外知识,很容易有思路。主要就在于实现这两个子函数的具体过程。而这两个函数的实现过程将与文法的数据结构关系密切,如果能首先在设计数据结构上下工夫,能够设计得到一个好的数据结构,绝对能事半功倍!所以以后对于相对复杂的问题,要首先设计好数据结构,其次慢慢完成算法。完成算法及其代码的编写后,就是调试了。要高效完成这项工作,需要了解IDE关于调试的各种功能,这样借助软件的这些功能,调试会更加容易,当然其中免不了会发现错误,需要修改程序的时候,我觉得特别要注意修改,这就像是一个状态转换的过程,你在修改前程序在一个过程,修改后是另一个过程,但到达的过程究竟是是否是你要的,就在于你的修改,修改时要特别将需要修改的部分用软件本身的自动将相同变量调亮的功能进行标记,免得漏改,一旦漏改,很容易进入思维误区,觉得刚才的修改方法出错,但其实不过是漏改了,这点错误在变量达到十几二十个时很容易犯,所以调试时要重点关注修改!

八、思考题

1、 是不是所有的文法都可以通过上述程序构造LL(1)文法?

答:不是;文法本身要能够被转换,在经过转换前要不含回路,不含以空字为右部的产生式,转换时,在提取公共左因子时还存在某些文法不能在有限步骤内提取完左公因子。 例如:

S->Ap|Bq A->aAp|d B->aBq|e

那么在转换后还要在经过判断才能最终确认是否是LL(1)文法。 2、 LL(1)文法在整个语法分析中的作用?

答:语法分析包括两类:一类是自上而下分析法,一类是自下而上分析法

自上而下的主旨是,对任何输入串,试图用一切可能的办法,从文法开始符号出发,自上而下的为输入串建立一棵语法树。或者说,为输入串寻找一个最左推倒,这种分析过程的本质是一种试探过程,是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。而在自上而下的分析法中,主要是研究LL(1)分析法。 3、 实验1中设计的文法数据结构对本实验的影响?

答:使用数据结构本身是能够简化问题,可以使具体算法的思路有倾向性,也可以使得程序处理过程更加有条理,另外实验1的数据结构,完整的将开始符号,终结

符,非终结符及所有产生式存储,对于消除左递归和提取左因子,可以对非终结符和产生式有进行更加有效的处理,较之没有使用数据结构或没有存储非终结符而言可以在迭代时单个处理,而不需要再所有步骤完成后才进行统一处理。 4、 如何更好地组合实验1和实验3,使之具有更高的效率?

答:使用结构体来定义文法,包括文法的四个部分,终结符和非终结符用string类,以便于可以调用string类的成员函数处理问题,产生式用C++类来定义,在存储文法时得到其左部的非终结符和右部的所有候选,并将候选按ASCII码排好序再存储,其数据有非终结符,所有候选,以及候选的个数,成员函数要能够查看,增加,修改,删除所有的成员,如果可以候选最好能使用链表,这样增加,替换,删除将更加简单,高效。在实验1中还要将有回路的和右部有空字的产生式进行判断,提示输入的文法不合理,另外再将由实验3定义的一些规定转接到实验1,这样文法的结构定义,文法的完整输入以及对可转换的非LL(1)文法的判断,以及其它输入的提示及出错检测全部集中在原来实验1要完成的部分,原来实验3的部分只关注将文法进行转换和输出,即消除左递归、提取左因子和输出到文本文件中。