基于算符优先分析方法的语法制导翻译程序设计.doc

1、一、课程设计的目的与要求1 词法分析器设计的目的与要求11 词法分析器设计的目的本实验是为计算机科学与技术专业、网络工程专业、信息安全专业的学生在学习编译技术课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术设计出词法分析器，了解扫描器的组成结构，不同种类单词的识别方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。12 词法分析器设计的要求设计一个扫描器，该扫描器是一个子程序，其输入是源程序字符串，每调用一次识别并输出一个单词符号。为了避免超前搜索，提高运行效率，简化扫描器的设

2、计，假设该程序设计语言中，基本字（也称关键词）不能做一般标识符用，如果基本字、标识符和常数之间没有确定的运算符或界符作间隔，则用空白作间隔。单词符号及其内部表示如表1-1所示，单词符号中标识符由一个字母后跟多个字母、数字组成，常数由多个十进制数字组成。单词符号的内部表示，即单词的输出形式为二元式：（种别编码,单词的属性值）。表1-1单词符号及其内部表示单词符号种别编码单词的属性值BEGINIFTHENELSEEND标识符整型常数+*（）123456789101112在名字表中的地址十进制整数2 算符优先分析程序设计的目的与要求2.1 算符优先分析程序设计的目的本实验是为计算机科学与技术等专业的

3、学生在学习编译技术课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术, 设计、编写和调试算符优先分析程序，了解算符优先分析程序的组成结构，掌握实现通用算符优先分析算法的方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。2.2 算符优先分析程序设计的要求算符优先分析属于自下而上的分析方法，该语法分析程序的输入是终结符号串（即单词符号串，以一个“”结尾），如果输入串是句子则输出“YES”，否则输出“NO”和错误信息。算符优先分析过程与非终结符号无关，当由文法产生了优先关系之后文法也

4、就失去了作用,本题目给出文法的目的是为了便于对语法分析结果进行验证。(1)文法设算符优先文法为： 说明：i为整型常数或者为标识符表示整型变量；使用中用*表示。(2)优先关系表设优先关系表如表1-2所示。表1-2优先关系表+ * i ( ) # + * i ( ) # 3 基于算符优先分析方法的语法制导翻译程序的设计的目的和要求3.1 基于算符优先分析方法的语法制导翻译程序的设计的目的本实验是为计算机科学与技术等专业的学生在学习编译技术课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术, 通过设计、编写和调试语法制导翻译程序

5、，掌握从一种语句的语法和语义出发，构造相应的语义子程序，实现基于算符优先分析方法的语法制导翻译的方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。3.2 基于算符优先分析方法的语法制导翻译程序的设计的要求算符优先分析方法是通过反复把输入符号移进分析栈，使用优先关系表在分析栈顶寻找最左素短语，将其归约为一个非终结符号而实现的。这个分析过程与非终结符号无关，当由文法产生了优先关系之后文法也就失去了作用（所以本题目无需给出文法）。基于算符优先分析方法的语法制导翻译是在算符优先语法分析的基础上进行翻译工作（即语义分析），每当将一个最左素短语归约为一个非终结

6、符号时，就调用对应产生式的语义子程序，去完成相应的语义翻译工作，这步归约使用的产生式对非终结符号不加区分（即将所有的非终结符号用一个通用的非终结符号表示）。语法制导翻译程序的输入是终结符号串（即单词符号串，以一个“”结尾），如果输入符号串是句子,则按照其语义进行翻译,输出等价的四元式序列（作为练习应显示输出）。二、课程设计正文1 词法分析器设计1.1 程序的实现流程（1） 输出提示；（2） 读入源串；（3） 使用循环逐字符检测：如果该首字符是字母，则它是一个标识符或关键字，开始标记；如果首字符是数字，在后面没有字母，则它是数字，有字母则是标识符，开始标记；如果是空格或者运算符则终止这次标记；（

7、4） 每次终止标记前都要输出前面的关键字、标识符或数字，然后输出该运算符，都以二元式形式输出；（5） 检索完最后一个字符或者遇到非法输入则终止检索。1.2自行规定（1） 关键字：begin，if，then，else，end；（2） 标识符：以字母开头由字母或数字组成并且不属于关键字的单词；（3） 数字：完全由十进制数字组成；（4） 标识符：+，*，*，（，）。1.3在屏幕上显示begin：（1，-）if：（2，-）then：（3，-）else：（4，-）end：（5，-）标识符：（6，在名字表中的地址）整型常数：（7，十进制整数）+：（8，-）*：（9，-）*：（10，-）（：（11，-）：（

8、12，-）1.4程序流程图开始输入字符串取一个字符是*吗？是否指针A指向该字符是标识符的第一个字符吗？不是指针A指向该字符是a-z吗？ 是 是 是是数字的第一个字符？ 还在数字中 输出A到B字符串所对应的二元式是0-9？ 否 是 在标识符中是空格？ 否 是运算符吗？返回 否 是 数字中出现字母 是 否指针B指向该字符输入错误，存在非法字符输出A到B字符串所对应的二元式返回输出该运算符对应的二元式2 算符优先分析程序设计2.1自行规定可识别字符：i，+，*，（，），#，/。由于*识别起来有点儿麻烦，又限于时间上的问题，我暂时用/表示的。2.2优先级设计使用整形二维数组即邻接矩阵形式存放，其中1为

9、高于，0为等于，-1为低于，-2为不能比较。2.3程序流程这里用文字描述，具体流程图参考语法制导翻译。（1） 提示输入；（2） 输入字符串；（3） 错误检验：主要进行检测输入串中是否含有不能识别的字符，首字符必须是i或（，字符串内部（后面只能是i；（4） 输入串放到缓冲区中，栈中只放#；（5） 当栈中出现#N，缓冲区中出现#时退出；（6） 找到栈中第一个终结符，用top指向他；（7） 比较栈顶首终结符和缓冲区首字符的优先级：低于等于则入栈，高于就找到从栈顶数第二终结符准备归约，不能比较就输出错误并终止；（8） 归约时，如果栈顶首终结符和第二终结符优先级相等就把他们及之间的字符归约为N，如果栈顶

10、首终结符优先级高并且是栈顶字符则将该字符归约为N，如果栈顶首终结符优先级高并且栈顶字符是N则将该字符及其左右的N一起归约为N。3 基于算符优先分析方法的语法制导翻译程序的设计3.1在算符优先分析程序的基础上继续实现，可以输出四元式。3.2为了实现输出四元式，需要找到两个操作数，即通过运算符两边的N来找到被归约为N的两个操作数。我使用一个字符串数组来存放被归约为N的操作数，由于栈的特殊性质，每次归约时都是从栈顶的N开始，不论归约的字符串中有几个N都是从栈顶开始，所以我想了一个方法：因为输出四元式时都是归约运算符和他两边的N，所以从第一个N开始就记录该N所对应的字符串，以后每次归约时都要找到该字符

11、前面N的个数，将被归约的几个字符以字符串形式一起存入对应数组中，这样再去找N对应的归约字符串就是他的操作数。3.3程序流程图由于用电脑画程序流程图时一页总是会不够，所以我决定在纸上手工画。三、 课程设计总结或结论三个程序均为自己写的，使用Java语言，Eclipse集成开发环境实现。1词法分析器设计1.1为了实现字符串的增加与删除，我使用的是StringBuilder，他是继承字CharSequence，是一个16位字符数组，以至于在后面拿StringBuilder对象和String对象进行匹配时出现错误。因为一个是字符数组，一个是字符串，必须转化为相同形式才可以比较，我查阅JDK的帮助文档发

12、现String类中有一个将字符串转化为字符数组的方法toCharInt（），但是转化后并不是16位的，于是我自己尝试着写了一个转化函数toCharInt16（），结果发现还是不能匹配成功，通过调试发现两方都是16位字符数组但就是不能匹配成功，我尝试将equals（）换位=，还是不行。后面突然发现，我可以将这个StringBuilder对象转化为String对象，总类Object中有toString（），这个方法我经常用，但是一直想着将字符串转换，而忽略了其它。1.2实现技术需要分析的种类比较多：begin，if，then，else，end是关键字不是标识符需要单独考虑，同时他们属于字符串，可以

13、通过找到标识符后再判断是不是关键字；我使用了两个标志位来记录并判断标识符和数字，flagL判断是不是在标识符中，flagN判断是不是在数字中。如果该字符是标识符，flagL为false那么这个字符是接下来这个标识符的第一个字母，这时就可以用指针pointA指向他，并把flagL置为true，flagL为true那么直接去检测下一个字符；如果该字符是数字，flagL为false并且flagN为false说明他是数字的第一个字母，这时可以用pointA指向他，并把flagN置为true，flagL为false并且flagN为true说明这个字母仍然处于数字中，可以直接去检测下一个字符，flagL为

14、true并且flagN为false说明这个字母正处在一个标识符中，可以直接去检测下一个字符，其它情况即flagL为true并且flagN为true说明这个字母既在标识符中又在数字中，是不可能发生的。对于运算符来说，+，*，（，）都是一个字符，检测到是他们就可以置pointB的值，让从pointA开始到pointB-1的字符作为一个整体来说，为了区分他们是标识符还是数字，因为标志符和数字的属性值不同，这是可以检测他的第一个字符，这个字符是字母这个整体就是标识符或关键字，这个字符是数字这个整体就是数字，他们输出时有区别；我们还有一个运算符*，由于他有两个字符，需要区别对待，当检测到第一个*时要先检

15、测下一个字符是不是*，如果是说明检测到的是*，这样下一次循环检测就没有意义了，我又用了一个标志位isDoubleAsterisk，默认是false的，这时就可以将其置为true，每次循环时首先检测isDoubleAsterisk是否为true，为true就直接进入下一循环。将他们前面的整体输出为二元式后要将以上三个标志位置为false，然后还要将他们自己的二元式输出。检测到是空格就直接将前面整体的二元式输出。1.3存在不足由于时间上的关系，这个小程序存在一些bug，比如连续两个空格，就会输出两次前面的东西，虽然不同但是对整体结果有影响；输完最后一个字符后必须要输入个空格才能把最后这个输出。2

16、算符优先分析程序设计2.1使用一个StringBuilder对象stack作为栈，初始值为#；使用一个StringBuilder对象buffer作为缓冲区，初始值为输入的源串。2.2由于循环次数是不确定的，我使用一个do-while语句来不断循环，并设置一个标志位flag来判断是否可以再次执行。flag被置为false即不能再循环的情况有：开始时判断包含非法字符；存不合适的搭配，比如（之后必须是i；两个字符的优先级不能比较。2.3为了输出能够对齐，我使用了水平制表符即“t”。2.4使用了两个指针指向从栈顶数第一个终结符和第二个终结符，第一个为全局变量，第二个为局部变量。2.5规约时分了三种情况

17、：被归约的是栈顶的那个字符；被归约的是该字符和他两边的N；被归约的是该字符以及他前面的N还有他前面与他同优先级的字符。在程序中归约只是字符串的变换。2.6仍有不足，我将*换成了/，这样减小了难度。由于时间上的关系，没有想到解决的办法。3基于算符优先分析方法的语法制导翻译程序的设计3.1他是在第二个实验的基础上实现的，时间上本来可以减少的，但是出现了一个比较难解决的问题：如何通过N来找到这个N被归约之前是什么。因为程序中N就是一个字符，所有的N都一样，这就出现了难题。我想到的第一种方法是使用ArrayList创建两个动态数组，一个用来存放Nn，这时需要把栈中归约成的N变为有标记的Nn，然后用另一

18、个动态数组作为这个的映射，保存该N被归约前的东西。但是有两个问题：（1）栈中不再是N了，与我们所学的有些差距；（2）原来的N是一个字符，现在的Nn是两个，检测时肯定不容易。我果断放弃了这种方法。第二种方法是每一次归约时都去检测一下栈，从栈底开始找这个字符前面有几个N，这个整数作为索引，放将要被归约的东西的进一个字符串数组中。如果刚刚把四元式输出了，说明有了一个新的结果，使用Tn表示的，这里也应该要归约并且会将两个N归约掉，所以需要将这个Tn放到前一个N的数组中替换原来的内容。我其实对第二种方法没有多少信心，感觉也上可能对，但是经过试验后发现是对的。我就又回过头去想为什么这么做可以，发现因为在这

19、个栈中，被归约的都是从栈顶开始的N，不会只将中间的N和其它字符归约掉，这样就保证了归约的是栈顶首终结符。3.2另一个遇到的问题就相对来说简单了，就是在什么时候什么位置输出四元式。自己在纸上写了几个语句的四元式以及算符优先分析的过程，发现在归约运算符时会连带其两边的N一起归约，这两个N原来的值就是四元式的两个操作数。附录（设计流程图、程序、运行结果等）实验一源代码：import java.util.*;/* * author SXH * 说明 词法分析器 * */public class LexicalAnalysis /* * 存储源代码 * */static String sourceCod

20、e;/* * 两个指针 * */static int pointA = 0, pointB = 0;/* * 当前字符 * */static char presentChar;/* * 存放每次识别的单词 * */static StringBuilder temp = new StringBuilder();/* * 是否处于单词中 */static boolean flagL = false;/* * 是否处于数字中 * */static boolean flagN = false;/* * 是否是双星号即“*” * */static boolean isDoubleAsterisk = f

21、alse;/* * 词法分析 */public static void main(String args) System.out.println(单词符号tt种别编码tt单词属性);System.out.println(begintt 1tt -);System.out.println(iftt 2tt -);System.out.println(thentt 3tt -);System.out.println(elsett 4tt -);System.out.println(endtt 5tt -);System.out.println(标识符tt 6tt在名字表中的地址);System.o

22、ut.println(整型常数tt 7tt十进制整数);System.out.println(+tt 8tt -);System.out.println(*tt 9tt -);System.out.println(*tt 10tt -);System.out.println(tt 11tt -);System.out.println()tt 12tt -);System.out.println(*);System.out.println( 将以二元式形式输出：（种别编码，属性值）);Scanner s = new Scanner(System.in);System.out.print(请输入：

23、);sourceCode = s.nextLine();lexicalAnalysis(sourceCode);/* * 词法分析 * * param sourceCode * 需要分析的字符串 * */static void lexicalAnalysis(String sourceCode) for (int i = 0; i = a & sourceCode.charAt(i) = 0& sourceCode.charAt(i) = 0 & temp.charAt(0) = a & temp.charAt(0) = z) / 以字母开头是标识符或关键字if (temp.toString(

24、).equals(begin) System.out.println(1,-); else if (temp.toString().equals(if) System.out.println(2,-); else if (temp.toString().equals(then) System.out.println(3,-); else if (temp.toString().equals(else) System.out.println(4,-); else if (temp.toString().equals(end) System.out.println(5,-); else lette

25、r();/* * 本来打算写一个将字符串转化为16位字符数组的函数，结果还是不能匹配，没有使用 * */static char toCharArray16(String string) char array = new char16;for (int j = 0; j array.length; j+) if (j string.length()arrayj = string.charAt(j);else arrayj = ;return array;实验一运行结果：实验二源代码：import java.util.*;/* * author SXH * 说明 算符优先分析 * */public

26、 class OperatorPrecedence /* * 源串 * */static String resourceCode;/* * 判断是否可以继续执行 */static boolean flag = true;/* * 栈 * */static StringBuilder stack = new StringBuilder(#);/* * 输入缓冲区 * */static StringBuilder buffer = new StringBuilder();/* * 步骤 */static int step = 1;/* * 栈顶第一个终结符 */static int top;/*

27、* 字符顺序表 *暂时用/表示 */static String sequenceList = +*/i()#;/* * 优先关系表,其中1为高于，0为等于，-1为低于，-2为不能比 */static int relation = 1, -1, -1, -1, -1, 1, 1 , 1, 1, -1, -1, -1, 1, 1 , 1, 1, -1, -1, -1, 1, 1 , 1, 1, 1, -2, -2, 1, 1 , -1, -1, -1, -1, -1, 0, -2 , 1, 1, 1, -2, -2, 1, 1 , -1, -1, -1, -1, -1, -2, 0 ;/* * 主

28、程序 */public static void main(String args) System.out.print(请输入字符串：);Scanner s = new Scanner(System.in);resourceCode = s.nextLine();buffer.append(resourceCode);if (sequenceList.indexOf(buffer.charAt(0) = -1) / 要检测缓冲区字符flag = false;System.err.println(t由于包含非法字符，这不是句子！);return;if(buffer.charAt(0)!=i&buf

29、fer.charAt(0)!=()/不会出现第一个字符不是i和（的时候flag = false;System.err.println(t你的语法混乱，这不是句子！);return;for (int i = 1; i b,从栈顶找第二个终结符，准备归约int second;for (second = top - 1; stack.charAt(second) = N; second-) continue;i = sequenceList.indexOf(stack.charAt(top);j = sequenceList.indexOf(stack.charAt(second);if (rela

30、tionji = 0) / 栈顶首终结符和第二终结符优先级相等/ stack.delete(second, top);/ stack.append(N);stack.replace(second, top + 1, N);/ 从第二终结符到第一首终结符都除去,用N替换 else if (relationji = -1) / 栈顶首终结符优先级高if (stack.charAt(top - 1) = N) / 如果左边有N，则右边也有，和两边的N一起归约stack.delete(top, top + 2);/ 删除掉从start到end-1的字符 else / 只归约它自己,他处于栈顶stack.deleteCharAt(top);stack.append(N);System.out.println(step+ + tt + stack + tt + buffer);break;case 0:/ a=b,b入栈case -1:/