简单优先分析法编译原理课程设计

1、学 号： 课 程 设 计题 目简单优先分析程序的设计学 院计算机科学与技术学院专 业软件工程专业班 级软件工程1002班姓 名指导教师何九周2013年1月12日课程设计任务书学生姓名： 专业班级： 软件工程1002班 指导教师： 何九周 工作单位： 计算机科学与技术学院 题 目:简单优先分析程序的设计初始条件：程序设计语言:主要使用C语言的开发工具，或者采用LEX、YACC等工具，也可利用其他熟悉的开发工具。算法：可以根据编译原理课程所讲授的算法进行设计。要求完成的主要任务:（包括课程设计工作量及其技术要求，说明书撰写等具体要求）1.明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程

2、设计指导书的要求，学会设计的基本方法与步骤，学会如何运用前修知识与收集、归纳相关资料解决具体问题的方法。严格要求自己，要独立思考，按时、独立完成课程设计任务。2. 主要功能包括：对教材P104中的上下文无关文法，实现它的简单优先分析程序，给出符号串b(aa)b的分析过程。（参考教材P103106）3.进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用出错处理程序。4. 设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字数不少于0.3万字。包含内容：课程设计的题目。目录。正文：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法分析方法及中间代码形式的

3、描述、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。结束语。参考文献。附录：软件清单（或者附盘）。时间安排：消化资料、系统调查、形式描述1天系统分析、总体设计、实施计划3天撰写课程设计报告书1天指导教师签名： 2013年 1月 12日系主任（或责任教师）签名： 2013年 1月 12日 目录1引言- 3 -2需求分析- 3 -3总体设计- 3 -3.1简单优先关系的定义- 4 -3.2简单优先分析法的基本思想- 4 -3.3简单优先关系矩阵流程图- 5 -3.4简单优先分析法流程图- 6 -3.5分析器

4、构造- 7 -4开发工具的选择- 7 -5详细的算法设计- 7 -5.1简单优先关系矩阵输出算法- 7 -5.2字符串读入- 8 -5.3字符串分析算法- 8 -5.4优先关系判断算法- 9 -5.5移近-规约算法- 9 -5.6分析结果判断- 11 -6软件调试- 11 -7软件的测试方法和结果- 12 -8有关技术的讨论- 13 -9收获与体会- 14 -10结束语- 14 -11 参考文献- 15 -12 附录- 15 -简单优先分析程序的设计1 引言上下文无关文法是形式语言理论中一种重要的变换文法，用来描述上下文无关语言，在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上

5、下文无关文法，因此应用十分广泛。简单优先分析法是预先在文法的各种符号 (终结符号和非终结符号)之间建立所谓优先关系，而在分析一个句型 (指规范句型，下同)时，从左到右依次扫视其中的符号，且每扫视一个符号都检查它和后继符号间的优先关系，以期找到句柄之尾，然后再从此尾符号处回头，进行反向扫描，且每扫视一个符号都检查它和其前的符号间的优先关系，直到找到句柄之头为止。本文将采用简单优先分析法对一个上下文无关文法进行分析，给出文法的简单关系优先矩阵，并对测试用例进行分析。2 需求分析本课程设计的目的是为了实现给定上下文无关文法的简单优先分析程序，并给出字符串的分析过程。上下文无关文法GS：S:=bAbA

6、:=(B|aB:=Aa)测试字符串：b(aa)b3 总体设计本文采用简单优先分析法实现指定上下文无关文法的分析程序，对于任意字符串给出其分析过程。3.1 简单优先关系的定义设G=(VN，VT,P,S)是一已化简的文法，V=VNVT，并设Si和Sj是V中的任意两个符号，若G中存在这样的规范句型 =SiSj 则此相邻的两个符号Si，Sj和的句柄之间的关系必然是下述情况之一： (1) 若Si在句柄中，而Sj不在句柄中 (如图42(a)所示)，则Si显然为句柄的尾符号，故G中必有形如ASi的产生式，使Si先于Sj被归约。此时，我们就说符号Si优于Sj，且记为Si>· Sj。此外，由于S

7、j出现在规范句型的句柄之右，故可知Sj必为终结符号。 (2) 若Si与Sj同时处于的句柄之中 (如图42(b)所示)，则G中必有形如ASiSj的产生式，使Si和Sj同时被归约。此时，我们就说Si和Sj有相同的优先关系，且记为Si=·Sj。 (3) 若Sj在句柄中，而Si不在句柄之中 (如图42(c)所示)，则Sj显然为句柄的头符号，故G中必有形如ASj的产生式，使Sj先于Si被归约。此时就Si和Sj的优先关系而言，我们说Si低于Sj且记为Si<·Sj。 (4) 若Si和Sj均不在句型的句柄之中，由于Si和Sj已相邻地在中出现，则必有G的另一规范句型，使Si和Sj在中相

8、邻地出现，且与的句柄的关系有上述三种情况之一。然而，也可能有这样的情况，对G中的某些符号序偶(Sr,St)而言，G中并不存在任何使Sr和St相邻出现的句型，此时我们就说Sr和St间不存在任何优先关系。3.2 简单优先分析法的基本思想根据优先关系的定义，将简单优先文法中各文法符号之间的这种关系用一个矩阵表示，称作简单优先矩阵。PDA读入一个单词后，比较栈顶符号和该单词的优先级，若栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入。直到最后栈内只剩下开始符号，输入串读到“”为止。此时识别正确。可分点描述如下:（1）、对句型中相邻的文法符号

9、规定优先关系，以寻找句型中的句柄; （2）、规定句柄内各相邻符号之间具有相同的优先级;（3）、规定句柄两端符号优先级要比位于句柄之外而又和句柄相邻的符号的优先级高，以先归约句柄; （4）、对于文法中所有符号，只要它们可能在某个句型中相邻，就要为它们规定相应的优先关系，若某两个符号永远不可能相邻，则它们之间就无关系。3.3 简单优先关系矩阵流程图输入欲分析文法判定是否是简单优先文法分析等于关系分析小于关系分析大于关系构造矩阵关系表NY3.4 简单优先分析法流程图S1<-#,i,j<-1MSi,TRj=error?开始结束Si>TRj?K<-iSk-1<sk?a=Sk

10、SK+1Sia是句柄，用它来查产生式表a与一产生式右部相同？Si=#且TRj=#？errori<-k Si<-U U是该产生式左部符号K<-k-1errori<-i+1Si<-TRij<j+1YNYNYYNYNN3.5 分析器构造分析栈 输入流 ST语法分析程序优先关系矩阵产生式表4 开发工具的选择开发环境：Windows8环境下的eclipse JDK1.7开发语言：Java5 详细的算法设计5.1 简单优先关系矩阵输出算法for(int i=1;i<9;i+)a0i=tokeni-1; for(int j=1;j<9;j+) aj0=toke

11、nj-1; for(int i=1;i<9;i+) for(int j=1;j<9;j+) aij=relationi-1j-1; for(int i=0;i<9;i+) for(int j=0;j<9;j+) System.out.print(aij+" "); System.out.print("n"); 5.2 字符串读入Scanner scanner = new Scanner(System.in); String testStr = scanner.nextLine(); char c= testStr.toCharAr

12、ray();5.3 字符串分析算法while(!s.isEmpty()char pre = s.pop();if(compare(pre,ci)/移进s.push(pre);s.push(ci);System.out.println("移进"+ci);else/规约s.push(pre);System.out.println("规约");i-;statute();i+;5.4 优先关系判断算法private static boolean compare(char pre, char d) throws Exception / TODO Auto-gene

13、rated method stubint i = map.get(pre);int j = map.get(d);char rel = relationij;if(rel = ' ')System.out.println("错误关系");throw new Exception();if(rel='>')return false;if(rel='='|rel='<')return true;return false;5.5 移近-规约算法switch (c)case 'S':/结束if

14、(s.pop()='#')return;throw new Exception();case 'b':/Sif(s.pop()='A')if(s.pop()='b')s.push('S');return;throw new Exception();case 'B':/Aif(s.pop()='(')s.push('A');return;throw new Exception();case 'a':/As.push('A');return

15、;case ')':/Bif(s.pop()='a')if(s.pop()='A')s.push('B');return;throw new Exception();default:throw new Exception();5.6 分析结果判断if(s.isEmpty()System.out.println("分析成功");elseSystem.out.println("分析失败");catch(Exception e)System.out.println("分析失败"

16、);6 软件调试使用eclipse自带的功能对源代码进行了调试，直至没有语法错误和语义错误。7 软件的测试方法和结果1.程序界面:2.给定测试字符串:b(aa)b#3.测试任意字符串:8 有关技术的讨论简单优先分析法简单易行，已有一套构造简单优先矩阵的形式化算法，从设计分析程序到具体地进行语法分析都可机械地进行。似乎是一种可靠和有效的方法，其实并非如此。这主要表现在对文法有较强的要求,例如本课程设计分析的文法为上下文无关文法。因为对通常的文法而言，它的某些符号对之间的优先关系往往会多于一种，也就是说，所给的文法常常并非简单优先文法。特别是当文法具有左递归时，就往往会导致这种情况的发生。所以,在

17、实际使用过程中,简单优先分析法存在很大局限性。9 收获与体会在本课程设计的过程中，我学习到了好多书本上学不到的东西，真正体会到了编译原理的强大。也同时为自己能够编写出这样一个强大的程序而感到欣慰。通过本次课程设计很好的复习了数据结构中所学的相关知识，尤其是对栈的运用有了更深的理解。同时也对本学期所学Java语言程序设计有了更深层次的理解，并将其在实践中得以运用。本次设计最深的感触是简单优先文法是一个非常准确，规范但分析效率很低的一种文法。此次课程设计，也让我对简单优先分析法有了比较全面的了解，并且通过上机操作等更好的理解了相关理论知识，增强了自己的动手能力。在课程设计过程中，我也发现了自己存在

18、的问题。例如，对数据结构相关知识的掌握不够牢固，对栈的使用存在错误；Java语言的运用不够娴熟，对方法的调用存在误区等。这些问题都在后来的调试过程中通过查阅相关材料得以解决。总之，这次课程设计让我受益匪浅。不仅加深了我对编译原理、数据结构和Java语言程序设计等课程的了解，而且也通过查阅资料和实践弥补了自己的不足之处。在今后的学习中，我会加强自己的动手能力，让理论和实践相结合，并且加强在专业课方面的学习。10 结束语编译原理一般认为是较难的一门课.不过我认为这门课其实并不是特别难，只要课前提前做好预习工作，课后认真做习题，学好这门课并非难事。经过这次课程设计,也让我深刻的认识到实践操作的重要性

19、。书本只能教给我们基础知识,只有通过实践才能将那些知识真正吸收,转化为自己的智慧。编译原理是一门实用性很强,对我们的专业很有帮助的科目,虽然已经结课,但是在以后的生活和学习中我将会继续努力,不断增加自己的知识面,深入的理解和运用编译原理，使自己成为一名合格的IT人才。 11参考文献1编译原理 主编：胡伦俊 徐兰芳 骆婷 出版社：电子工业出版社2Java语言程序设计主编：吕凤翥 马皓 出版社：清华大学出版社3编译原理（第二版） 主编：张素琴 吕映芝 出版社：清华大学出版社4数据结构（C语言版） 主编：严蔚敏 吴伟民 出版社：清华大学出版社12附录程序源代码：import java.util.Ha

20、shMap;import java.util.Stack;import ;import java.util.Scanner;import java.io.*;public class test public static char token='S','b','A','(','B','a',')','#'public static Stack<Character> s=new Stack<Character>();public static H

21、ashMap<Character,Integer> map= new HashMap<Character,Integer>();public static char relation = new chartoken.lengthtoken.length;static for(int i=0;i<token.length;i+)map.put(tokeni, i);for(int i=0;i<token.length;i+)for(int j=0;j<token.length;j+)relationij=' 'relation07=

22、9;>'relation12='='relation13='<'relation15='<'relation17='>'relation21='='relation25='='relation32='<'relation33='<'relation34='='relation35='<'relation41='>'relation45='>'r

23、elation51='>'relation55='>'relation56='='relation61='>'relation65='>'relation70='<'relation71='<'relation77='='public test()/* * param args */public static void main(String args) char a=new char99;System.out.println(&q

24、uot;文法GS:");System.out.println("S:=bAb");System.out.println("A:=(B|a");System.out.println("B:=Aa)");System.out.println("简单优先关系矩阵:");for(int i=1;i<9;i+)a0i=tokeni-1; for(int j=1;j<9;j+) aj0=tokenj-1; for(int i=1;i<9;i+) for(int j=1;j<9;j+) aij=

25、relationi-1j-1; for(int i=0;i<9;i+) for(int j=0;j<9;j+) System.out.print(aij+" "); System.out.print("n"); System.out.println("请输入测试用例（以“#”结束）：");/shiyan4 s4= new shiyan4();Scanner scanner = new Scanner(System.in); String testStr = scanner.nextLine(); char c= testS

26、tr.toCharArray(); s.push('#');tryint i=0;while(!s.isEmpty()char pre = s.pop();if(compare(pre,ci)/移进s.push(pre);s.push(ci);System.out.println("移进"+ci);else/规约s.push(pre);System.out.println("规约");i-;statute();i+;if(s.isEmpty()System.out.println("分析成功");elseSystem.

27、out.println("分析失败");catch(Exception e)System.out.println("分析失败");/* * 对栈中符号规约 * return false 规约失败 * throws Exception */private static void statute() throws Exception char c = s.pop();switch (c)case 'S':/结束if(s.pop()='#')return;throw new Exception();case 'b':/Sif(s.pop()='A')if(s.pop()='b')s.push('S');return;throw new Exception();case &#