2022年语法分析器实验报告 .pdf

《2022年语法分析器实验报告 .pdf》由会员分享，可在线阅读，更多相关《2022年语法分析器实验报告 .pdf（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、语法分析器一 需求分析1.1 题目背景描述编译器实现技术是一大宝库，一方面以编译器的实现为背景可以实践几乎全部在数据结构与算法分析课程中学到的主要数据结构与算法；另一方面，编译器设计中使用的问题求解方法、 处理问题的思路被广泛地用于自动数据处理（转换）及其它一些新的研究领域。没有编译器的出现就没有现代数字计算机的发展。本次课设即以“语法规则的存储与显示”、“句子的生成”、“语法（分析）树的建立”等等这些编译器中的一些基本功能的实现为题，对高级程序设计语言在计算机中的表达和相关的处理有一个初步认识，提前领略“数据的自动转换与处理”这一计算机问题求解的核心技术。尽管这些功能的实现并不涉及较深入的编

2、译技术，但也需要带着问题预先学习、掌握有关形式语言、编译原理与技术的若干基本概念。1.2 课程设计任务给定若干描述某种高级程序设计语言组成部分的语法规则及测试用例：1、设计恰当的数据结构实现语法规则的计算机存储并加以显示；2、对于给定语法规则的句子，能动态显示“句子的生成”；3、对于给定语法规则的句子（或句型） ，完成该句子（句型）的“语法（分析）树的建立”，并用图形界面显示；1.3 输入形式本程序用到的输入形式有键盘、鼠标和文件。各输入说明及输入值范围说明如下：1.3.1 键盘输入可在“建立推导”窗口通过键盘输入任意句子建立推导，两符号间需要空格。1.3.2 鼠标输入可在“文法管理系统”界面

3、通过鼠标点击任意菜单选项，实现对应功能。当文法或推导过长时，点击对应文本域滚动滚轮可查看余下全文。1.3.3 文件输入可输入任意存储了正确文法的txt 文件，默认有 Pascal 风格的文法和 C语言风格的文法，格式如下：Pascal 风格：St:=Assign|IfS|WhS Assign:=id := E E:=E + E|E - E|E * E|E / E|( E )|id IfS:=if BE then St|if BE then St else St BE:=id id|id = id|id E|E = E|E = E|E != E|E = 0 & IDtargeti.equals(

4、stri); i-); return i = -1; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 36 页该函数参数为保存了目标句子的字符串数组，每次从后向前比较最左非终结符之前的字符串与推导句子的相同位置的字符串是否相等。若出现不相等的字符串，说明之前的推导已经出错，返回 false 。boolean next(Grammar g, int rule) int i; boolean found = false; for(i = 0; i pos; j-) strj + len = strj; for(int j = 0; j le

5、n + 1; j+) strpos + j = g.grammari.rightj; strlength += len; / 最左非终结符号for(; pos strlength; pos+) for(i = 0; i g.vn; i+) if(strpos.equals(g.VNi) found = true; break; if(found) break; return true; 该函数是整个推导算法的核心，参数g用于传递用户给定文法，整型变量rule 代表产生式规则的序号。函数功能是实现将当前步推导按照第rule 个产生式规则变换，由于传递进来的 rule 数值可能是错误的，所以先进行

6、判断，如果该rule 值没有对应正确的产生式规则便返回 false 。因为 pos记录了最左非终结符的位置，所以将该位置的非终结符变换，变换结束后找到新的最左非终结符，改变pos的值，用于实现下一次变换。接着建立 Derivation类用于保存全部推导步骤。在推导前需要将句子中的标识符替换为默认标识符“ id ”用于简化判断，原标识符保存在数组中建树，并且记录推导开始时间用于计算推导的总时间。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 36 页private void LeftDerivation(int i, boolean r

7、everse) for(int rule = 1; rule inputlength) continue; if(!derivationi.equaltoStart(IDtarget) /去掉方向错误的推导continue; if(derivationi.pos = inputlength) step = i + 1; finnish = true; return; LeftDerivation(i + 1, reverse); 整个推导类通过该递归函数实现全部推导过程，首先从将rule 赋值为 1，并拷贝上一步推导用于建立当前步骤的推导。该函数的大致原理是将当前步骤的推导按照每一个规则变换一

8、次，接着每一个变换出的推导再按照每一个规则变换一次，直至变换出的句子和目标句子完全一样位置。其中maxrule 表示用户给定文法中的非终结符最多有几个产生式，在Pascal风格的文法中，该值为 6。布尔型变量 reverse 用于判断二义性，当其为 true 时，当前步推导按从 1到6的规则变换，为 false 时，当前步推导则按从 6到1的规则变换，若这两种变换顺序产生了正确且不同的推导方式，说明目标句子是有二义性的。在一次变换完成时，需要进行三次判断，第一次是当推导出的句子长度超出目标句子时，略过这次变换，第二次是当推导出的句子“推导方向”已经出错时，略过这次变换，第三次是当推导出的句子和

9、目标句子完全相等时，整个递归函数开始停下来。其中要说明的是第二次判断和第三次判断的正确性。第二次判断调用了 DerivationNode 类中的函数，该函数用于比较最左非终结符之前的字符串是否推导正确，因为最左非终结符之前的字符不能再进行变换，所以如果有错，那么之后推导也不可能得出正确的结果，可以将该“错误方向”之后的推导全部“剪”掉。当最左非终结符之前的字符全部正确时，如果最左非终结符的值等于句子长度，说明该句子中已经没有非终结符，也就是推导已完成并且推导出的句子已经是完全正确的了。第一次判断和第三次判断都是两个整数的比较，而第二次判断由于前一步推导已经判断过了先前的非终结符都是正确的，所以

10、这次只需要比较很少几个字符串便可“剪”掉错误的结果，节省了许多时间。3.2.2 建树算法程序位置在 GrammarTree.java 里。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 36 页GrammarTreeNode 类表示树的结点， 该结点连接左子结点和右兄结点，以“左子 - 右兄”的方式保存语法数。public void toTree() root= new GrammarTreeNode(d.derivation0.str0); for(int i = 1; i d.step - 1; i+) count = 0; fi

11、nnish = false; Visit(root, i); if(finnish) count= 0; VisitID(root); /建立所有标识符结点 该函数的大致原理是，首先建立根节点，接着从第二步推导开始，对于每一次推导都调用递归函数遍历一遍已建立好的树，直至找到树中最左且为非终结符的叶子结点，记录其位置并将其与当前推导建立父子关系。private void Visit(GrammarTreeNode r, int i) if(!finnish & r != null) Visit(r.leftchild, i); if(!finnish & r.leftchild = null)

12、int head = 0, tail = 0; count+; if(r.inVN(d.g) head = count - 1; /该非终结符在上一步推导中正数的位置tail = d.derivationi - 1.strlength - 1 - head; /该非终结符在上一步推导中倒数的位置r.leftchild = new GrammarTreeNode(d.derivationi.strhead); / 建立父子关系r = r.leftchild; for(int j = head + 1; j d.derivationi.strlength - tail; j+) r.rightsi

13、bling = new GrammarTreeNode(d.derivationi.strj); r = r.rightsibling; /建立兄弟关系finnish = true; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 36 页Visit(r.rightsibling, i); 建树的难点是在当前步推导中判断哪部分是由上一步推导中的最左非终结符变换产生的，我的方法是在树中找到上一步推导中的最左非终结符之后，记录其正数的位置head并计算出其倒数的位置 tail，那么当前步推导的 head和tail之间的字符串序列就是变换产

14、生的了。3.2.2 文件读取程序位置在 GrammarMenu.java 里。File file; /建立文件JFileChooser chooser = new JFileChooser(); /建立文件选择器chooser.setAcceptAllFileFilterUsed(false); /取消选择任意格式文件的功能chooser.addChoosableFileFilter(new TFileFilter(.txt, txt文件); /过滤txt 文件int state = chooser.showOpenDialog(form); file = chooser.getSelecte

15、dFile(); if(file != null & state = JFileChooser.APPROVE_OPTION) FileReader read; try read = new FileReader(file.getPath(); /开始读取文件BufferedReader br = new BufferedReader(read); String temp = ; /建立字符串保存文件内容for(String s = br.readLine(); s != null; s = br.readLine() temp += (s + n); form.agrammar.setTex

16、t(temp); String input = temp.split(n); /将文件内容分割为字符串数组form.initGrammar(input); /将该字符串数组作为构造参数传递进文法类form.switchGra(); /右侧文本域显示存储后的文法read.close(); br.close(); catch (Exception e) 四 调试分析4.1 调试中遇到的问题及解决方法4.1.1 构造参数为空问题编程时系统经常会出现 java.lang.NullPointerException错误，这是由于构造参数为空引起的。比如点击“建立推导”菜单选项时，用户还没有给出文法，或者点

17、击“显示语法分析树”菜单选项时，用户还没有建立推导，这时由于推导类或者建树类参数为空，系统会报错。还有一种情况是当弹出文件选择器时不选择文件或弹出“建立推导”对话框时不输入句子，直接点击“取消”，此时的返回值为null 作为参数传递进了文法类或推导类的构造函数，也会报错。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 36 页该问题的解决方法，是规范程序的流程图，明确在执行某操作时的前提条件。在出错的地方增加判断函数，防止再有构造参数为空的情况。4.2.2 设置全局字体问题java 默认的“ Dialog ”字体在按钮和菜单上的显示并

18、不美观，为了将其换成“微软雅黑”字体，我使用了各个类自带的设置字体函数。这样可以更换菜单和菜单选项的字体，但不能更换文件选择器的字体，这是由于文件选择器中包含了按钮，文本框，下拉框等多种组件，自带的设置字体函数无法设置全部组件的字体。该问题的解决方法，是使用循环依次设置UIManager中的每一个组件的字体，这样便可以修改全部字体了。4.2.3 推导时间过长问题在写推导类时，推导函数可以很快显示长度较短的句子的生成，但稍微长的句子就要花上很长的时间。经过分析后得知，推导时间长的原因是由于每次按照产生式规则变换句子后，都要耗费大量的时间进行字符串的判断，以得出当前推导出的句子是否和目标句子相等。

19、并且如果一开始的推导是错误的，就又要耗费大量时间进行错误的推导直至推导出的句子长度大于目标句子为止。该问题的解决方法，是在每一步推导中建立一个整型变量记录其最左非终结符的位置。这样一来，每次按照产生式规则变换句子后，先从后向前判断最左非终结符前的推导是否正确，可以避免错误的推导。并且判断是否推导出句子不再需要大量的字符串比较，只要最左非终结符的值等于句子的长度即可，节省了大量的时间。4.2 改进设想4.2.1 美化界面由于本次课设的核心是对数据结构本身的操作和处理，所以我在做界面时，并没有使用太多复杂的组件，仅满功能完备的条件即可。在改进时，可以在该系统中增加“保存文法”的菜单选项和“编译”的

20、按钮以实现修改文法的功能。即点击“打开文法”时，左侧文本域输出文档中的内容， 用户可以直接在左侧文本域修改文法，只有点击“编译”按钮，右侧文本域才会输出存储后的文法。用户还可以点击“保存文法”，在文件选择器中选择路径保存新的文法。在点击“显示语法分析树”后，新窗口出现的树的图案不是十分美观，如果一个结点的子结点过多， 结点间的连线就会变得密集， 影响美观。可以通过优化画树算法进行改进。4.2.2 改进算法本次课设中的推导函数在推导的句子过长时会耗费大量时间，需要减少几个步骤的复杂程度以继续优化。比如当前步推导在按照规则变换时，需要浏览一遍全部规则，以找到当前非终结符的产生式。在改进时可以使用哈

21、希表存储文法，并记录下每个非终结符的产生式个数， 这样既易于找到当前非终结符的产生式，也可以减少递归时的循环次数。再者，当用户输入完句子时，系统可以通过对句子中终结符的判断暂时删去用不到的变换式，同样可以减少一些查找时间。然而该推导函数使用的算法是穷举法，即使使用了剪枝优化，其时间复杂度仍是按级数递增的。如果要彻底的改进，还可以学习编译原理中的消除左递归算法，以减少更多的时间。4.2.2 增加进度条本系统的推导函数推导时间过长时，界面的菜单选项会“定住”，影响用户的继续使用。改进时可以将推导函数作为一个线程，并增加一个进度条线程。推导进度的百分比可以用最左非终结符的位置除以推导句子的总长度算出

22、。4.2.3 增加数据检测本系统在打开文法时并没有检测文法的正确性，即使打开空的txt 文件依然可以正常精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 36 页读取。在美化界面的基础上，用户点击“编译”按钮后，系统会在一定程度上自动判断文法的正确性，比如句子格式应形如“E:=E + T|E T|T ”。然而和所有编译器一样，逻辑错误是不能判断出来的， 比如形如“E:=E+T|E T|T”的句子， 由于两符号间没有空格，系统会认为非终结符“ E”可以变换成“ E+T ”这个单词，而不是式子。若对此也进行改进，那么将会增加该系统的对文法的

23、限制，有利也有弊，我会在学习编译原理后想出更好的方法做出调整。4.3 经验、体会从起初拿到课设题目，到最终实现基本功能和部分扩展功能。在此过程中，我复习并掌握了 java 程序设计语言和数据结构课程中大量的知识与算法，比如对递归算法的应用和树的“左子 -右兄”存储方式，对从前学的理论知识有了更加深刻、更加正确的理解，很好地将理论与实践结合了起来。此外，通过浏览互联网、 借阅书籍等方式， 在从前所学知识的基础上进行扩充，对java图形界面及相关算法有了更加深入、广泛的了解。比如如何对UIManager进行设置修改字体和界面风格，还有如何添加菜单、菜单选项以及文件选择器等。尽管本次课程设计的过程显

24、得有些坎坷，花费了很多时间，但我从中收获了很多，兴趣、能力都得到了提高。数据结构课程的设计即将告一段落，然而本系统还存在许多不完善的地方，我会利用假期好好完善，争取做出一份更令人满意的作品。总之，我很珍惜这次课程设计的过程！非常感谢老师在过程中的监督与指导。五 用户使用说明打开“ GRAMMAR”工程并运行，弹出“文法管理系统”界面。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 36 页点击“输入文法”菜单中的“打开文法”，弹出文件选择器。打开“ Syntax.txt”。系统自动存储文法（该文法为Pascal 风格的文法）。点击“建

25、立推导”菜单中的“建立推导”，弹出对话框，用户在“请输入”下的文本框输入句子“ x := ( ( i * i + i ) * i + i ) + i”。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 36 页点击确定或按下回车后，右侧文本域输出推导过程。点击“构造语法分析树”菜单中的“显示语法分析树”。弹出新窗口显示推导对应的语法分析树。点击“建立推导”菜单中的“判断二义性”，系统弹出说明该句子有二义性的消息框并在右侧文本域输出新的推导过程。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第

26、17 页，共 36 页之后点击“构造语法分析树”菜单中的“显示语法分析树”。会弹出新窗口显示新的的语法分析树。用户可输入较复杂的循环嵌套语句如“while a b do if max = a then while b max do b := b + 1 else while a max do a := a + 1”。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 36 页该推导过长，点击右侧文本域滚动滚轮可查看余下全文。点击“帮助”菜单中的“说明”。会弹出新窗口显示说明。精选学习资料 - - - - - - - - - 名师归纳总结

27、- - - - - - -第 19 页，共 36 页六 测试结果6.1 输入数据检测系统只判断数据是否为空， 对于错误的数据， 系统依然可以读入， 并产生错误的转换。比如打开文法文件时不会考虑文法的正确性，输入句子时不会考虑该句子是否是一个符合文法风格的句子。有时在这种情况下依然可以推导出来，只是结果不符合用户的设想。6.2 健壮性与局限性6.2.1 健壮性若用户打开的 txt 文件没有存储正确的文法，那么系统依然会正常读取，但无法进行正确的文法存储和句子推导。若用户在“建立推导”对话框输入错误的句子（包括两符号间没有空格），只要该句子无法推导出来，“文法管理系统”右侧文本域就不会有任何输出。

28、此时系统不会报错。6.2.2 局限性当句子长度过长时，推导将耗费大量时间。如对于Pascal 风格的文法，若输入句子为“a := ( a + b ) * ( a b ) * ( a + b ) * ( a b ) ”。因推导过于复杂会导致系统无法响应，需要由用户关闭该进程。当用户想要更改文法时，只能在原txt 文件中更改并重新打开。判断二义性时，系统对于存在二义性的句子只能给出两种推导方式。即按产生式规则正序进行变换和按产生式规则逆序进行变换得出的推导方式。七 附录7.1 源程序/Form.javaimport java.awt.BorderLayout; import java.awt.Co

29、lor; import java.awt.Font; import java.awt.GridLayout; import java.util.Enumeration; import javax.swing.BorderFactory; import javax.swing.JFrame; import javax.swing.JPanel; import javax.swing.JScrollPane; import javax.swing.JTextArea; import javax.swing.UIManager; import javax.swing.plaf.FontUIResou

30、rce; SuppressWarnings( serial) class Form extends JFrame Grammar g; /文法类Derivation d; /推导类GrammarTree t ; /建树类精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 36 页JTextArea agrammar = new JTextArea(); /左侧文本域JTextArea atext = new JTextArea(); /右侧文本域JScrollPane scrollgrammar = new JScrollPane(agr

31、ammar); /左侧滚动条JScrollPane scrolltext = new JScrollPane(atext); /右侧滚动条JPanel p = new JPanel(); /新窗口public Form() /构造函数 setTitle( 文法管理系统 ); /设置全局字体initGlobalFontSetting( new Font( 微软雅黑 , 0, 12); GrammarMenu menubar = new GrammarMenu(this); setLayout(new BorderLayout(5, 5); add(menubar, BorderLayout.NO

32、RTH); add( p, BorderLayout.CENTER); p.setLayout(new GridLayout(1, 2, 20, 20); agrammar.setBorder(BorderFactory.createLineBorder(Color.BLACK , 1); agrammar.setLineWrap(true); /垂直滚动条自动出现scrollgrammar.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_AS_NEEDED); atext.setBorder(BorderFactory.cr

33、eateLineBorder(Color.BLACK, 1); atext.setEditable(false); atext.setLineWrap(true); scrolltext.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_AS_NEEDED); p.add(scrollgrammar); p.add(scrolltext); setSize(800, 600); setLocationRelativeTo(null); setVisible(true); setDefaultCloseOperation(JFra

34、me.EXIT_ON_CLOSE ); publicvoid initGrammar(String input) / “打开文法 ” 菜单选项调用 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 36 页g = new Grammar(input); switchGra(); publicvoid switchGra() / “显示文法 ” 菜单选项调用 if( g != null) atext.setText(g.getGrammar(); validate(); publicvoid switchDer() / “显示推导 ” 菜

35、单选项调用 if( d != null) atext.setText(d.getDerivation(); validate(); publicvoid showPaintTree() / “显示语法分析树” 菜单选项调用 if( t != null) new TreeForm(); publicvoid initDerivation(String input) / “建立推导 ” 菜单选项调用 if( g = null) return; d = new Derivation(g); d.leftDerivation(input); switchDer(); initTree(); publi

36、cvoid initTree() /建立语法分析树 if( d != null) t = new GrammarTree(d); t .toTree(); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 36 页 publicstaticvoid initGlobalFontSetting(Font font) /设置全局字体 FontUIResource fontRes = new FontUIResource(font); for(Enumeration keys = UIManager.getDefaults().keys();

37、 keys.hasMoreElements();) Object key = keys.nextElement(); Object value = UIManager.get (key); if(value instanceof FontUIResource) UIManager.put (key, fontRes); publicstaticvoid main(String args) new Form(); class TreeForm extends JFrame /新窗口显示语法分析树 TreeForm() add( new PaintTree(t . root); setSize(8

38、00, 600); setVisible(true); /Grammar.javaclass GrammarNode /文法产生式规则 String left; /:=左侧非终结符String right; /:=右侧产生式规则 class Grammar GrammarNode grammar = new GrammarNode100; /存储产生式规则String VN = new String50; /存储非终结符String VT = new String50; /存储终结符introw = 0, vn = 0, vt = 0, maxrule = 0; /产生式规则个数非终结符个数终

39、结符个精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 36 页数 最多产生式规则数public Grammar(String input) /构造函数存储文法 for( int i = 0; i maxrule ? tempright.length : maxrule; /添加新的 VNfor(count = 0; count vn ) VN vn + = temp0; for( int j = 0; j tempright.length; j+, row +) /添加新的 grammargrammar row = new Gramm

40、arNode(); grammar row .left = temp0; grammar row .right = temprightj.split( ); /添加新的 VTfor( int r = 0; r grammar row .right. length; r+) for(count = 0; count vt ) VT vt + = grammar row .rightr; /删除重复的 VTfor( int t = 0; t vt ; t+) for( int n = 0; n vn ; n+) if( VNn.equals(VTt) /VTt可能为 null for( int c

41、ount = t; count vt ; count+) VTcount = VTcount + 1; vt -; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页，共 36 页public String getGrammar() /输出文法 int i; String str = ; str += row ; for(i = 0; i row ; i+) str += (n + i + + grammari.left + :=); for( int j = 0; j grammar i.right. length; j+) str +=

42、(grammar i.rightj + ); str += (nn + vn + n); for(i = 0; i vn ; i+) str += (VNi + ); str += (nn + vt + n); for(i = 0; i vt ; i+) str += (VTi + ); return str; /Derivation.javaclass DerivationNode /推导 String str; /存储推导intstrlength, pos ; /推导符号个数最左非终结符号位置DerivationNode(String s, int l, int p) /用于构造 deri

43、vation0 strlength = l; pos = p; str = new String100; for( int i = 0; i strlength; i+) stri = si; DerivationNode(DerivationNode n) /拷贝构造函数 strlength = n.strlength; /pos记录最左非终结符号位置用于判断之前的推导是否有误以及之后判断的起始位置pos = n.pos ; str = new String100; for( int i = 0; i = 0 & IDtargeti.equals(stri); i-); return i =

44、 -1; boolean next(Grammar g, int rule) /根据产生式规则进行变换变换失败返回false int i; boolean found = false; for(i = 0; i pos ; j-) strj + len = strj; for( int j = 0; j len + 1; j+) str pos + j = g.grammari.rightj; strlength += len; /最左非终结符号for(; pos strlength; pos +) for(i = 0; i g.vn ; i+) if( str pos .equals(g.V

45、Ni) found = true; break; if(found) break; returntrue; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 26 页，共 36 页class Derivation Grammar g; /用户给定文法DerivationNode derivation; /存储推导过程String ID ; /标识符数组intinputlength, step, idcount; /句子长度推导步骤数记录标识符数组个数用于建树private String target, IDtarget; /输入句子规范化输入priv

46、atebooleanfinnish, reverse; /推导是否完成是否改变产生式规则的顺序privatelongstarttime; /推导开始时间privatelongendtime; /推导结束时间public Derivation(Grammar G) /构造函数 g = G; String Z = new String1; Z0 = g. grammar 0.left; /识别符号derivation = new DerivationNode100; derivation0 = new DerivationNode(Z, 1, 0); /识别符号 privateboolean is

47、ID(String temp) /判断是否为标识符 for( int n = 0; n g. vn ; n+) if(temp.equals(g. VNn) returnfalse; for( int t = 0; t g. vt ; t+) if(temp.equals(g. VTt) returnfalse; returntrue; publicvoid leftDerivation(String input) /最左推导 target = input.split( ); IDtarget = input.split( ); / 用于比较inputlength = target. leng

48、th; /记录长度ID = new Stringinputlength; idcount = 0; for( int i = 0; i target. length; i+) if(isID(targeti) IDtargeti = id; ID idcount+ = targeti; /保存标识符 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 27 页，共 36 页 /初始化step = 0; starttime = System.currentTimeMillis(); /获取开始时间reverse = finnish = false; Le

49、ftDerivation(1, reverse); if( finnish) derivation step+ = new DerivationNode(target, inputlength, inputlength); endtime = System.currentTimeMillis(); /获取结束时间 privatevoid LeftDerivation(int i, boolean reverse) /最左推导调用的递归函数 for( int rule = 1; rule inputlength) continue; if(! derivationi.equaltoStart(I

50、Dtarget) /去掉方向错误的推导continue; if( derivationi.pos = inputlength) step = i + 1; finnish = true; return; LeftDerivation(i + 1, reverse); public String getDerivation() /输出推导过程 String r = ; r += ( 推导用时： + (endtime - starttime) + msn + step + n); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 28 页，共 36 页f