西南交大-编译原理课程设计二-赋值语句的解释程序设计

1、编译原理课程设计赋值语句的解释程序设计姓名：汤朋学号：2014112217班级：软件四班时间：2017/6/13学期：2016-2017第一学期1. 设计题目：赋值语句的解释程序设计2. 设计内容：用算符优先分析方法设计一个分析解释程序，对输入的赋值语句、输出语句、清除语句进行词法分析、语法分析、表达式求值并存储于指定变量中：若存在错误，提示错误相关信息。3. 设计目的：a) 了解掌握算符优先分析的基本方法、内容b) 学会科学思考并解决问题，提高程序设计能力4. 实现环境Ø 电脑：l Windows10家庭中文版l 型号：雷神l 处理器：Intel(R) Core(TM) i7-67

2、00HQ CPU 2.60GHz l RAM：16.0GB(15.9GB可用)l 系统类型：64位操作系统，基于x64的处理器Ø 实现语言及环境：Java，JDK 1.8IDE：Ecplise neon.15. 概要设计文法表示：Sà v=E|E?|clearEàE+T|E-T|TTàT*F|T/F|FFà(E)|v|c归约规则：Nà v=N| N?|clearN à N + N | N - N | NN à N * N | N / N | NN à( N)|v|c种别码设计：单词符号种别码=1？2+3-

3、4*5/6(7)8v9c10clear11#12N13优先关系表123456789101112=?+-*/()vcclear#1=<<<<<<<>2?>3+>>><<<><<>4->>><<<><<>5*>>>>><><<>6/>>>>><><<>7(<<<<<=<&l

4、t;>8)>>>>>>>9v=>>>>>>>10c>>>>>>>11clear>12#<<<<<<<<<<<=程序流程图6. 详细设计单词符号二元组使用下面的类来表示：public class WordSymbol public static final int TYPE_NULL = 0; /无值public static final int TYPE_INT = 1; /整数public

5、static final int TYPE_STRING = 2; /字符串int code;/种别码int type;/单词符号值类型Object value;/单词符号的属性值public WordSymbol() super();public WordSymbol(int code, int type, Object value) super();this.code = code;this.type = type;this.value = value;public int getCode() return code;public void setCode(int code) this.c

6、ode = code;public int getType() return type;public void setType(int type) this.type = type;public Object getValue() return value;public void setValue(Object value) this.value = value;Overridepublic String toString() return "WordSymbol code=" + code + ", type=" + type + ", va

7、lue=" + value + ""归约栈：用Java中的栈对象 Stack<WordSymbol> 来表示单词串：用链表对象List<WordSymbol>来存放单词串变量表：使用Map<String,Integer>对象来充当变量表，其以键值对的方式存放变量，键可以设为变量名，值存放变量值变量名值KeyValue可归约串语义解释：变量归约：N àv，在变量表中查找该变量，若不存在则报错：变量未定义，否则修改非终结符N的属性值为变量v的值，并设N的种别码为13常量归约：N àc，修改非终结符N的属性值为常量

8、c的值，并设N的种别码为13运算归约：设运算的操作数为N1，N2；将N1，N2进行相应运算并将运算结果设为N3的属性值，将N3的种别码设为13括号归约：将(N)归约为N赋值归约：在变量表中查找被赋值的变量v，若不存在，则先在变量表中创建该变量，然后再将N的属性值赋值给v，最后将 v = N归约为N输出语句：先输出表达式N的属性值，然后将N?归约为N清除语句：将变量表中的所以变量清空，然后clear归约为N运算符之间的关系使用对象Relation来描述，其结构如下public class Relation public static final int REL_LESS = -1; / 小于pu

9、blic static final int REL_EQUAL = 0; / 等于public static final int REL_GREATER = 1; / 大于public static final int REL_NULL = 2; / 无关系int codeLeft, codeRight;int relation;public Relation() super();public Relation(int codeLeft, int codeRight, int relation) super();this.codeLeft = codeLeft;this.codeRight =

10、 codeRight;this.relation = relation;public int getCodeLeft() return codeLeft;public void setCodeLeft(int codeLeft) this.codeLeft = codeLeft;public int getCodeRight() return codeRight;public void setCodeRight(int codeRight) this.codeRight = codeRight;public int getRelation() return relation;public vo

11、id setRelation(int relation) this.relation = relation;Overridepublic String toString() String str = ""switch (relation) case -1:str = " < "break;case 1:str = " > "break;case 0:str = " = "break;case 2:str = " 无关系 "break;return "Relation：&qu

12、ot; + codeLeft + str + codeRight;同时，使用Relation二维数组来存放优先符关系表7. 程序清单package tp;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Stack;public class AssignmentExplain / 单词符号private String words = "=", "?", "+",

13、"-", "*", "/", "(", ")", "v", "c", "clear", "#", "N" ;private Stack<WordSymbol> stack = new Stack<>(); / 归约栈private List<WordSymbol> wordSymbols = new ArrayList<>(); / 单词符号priv

14、ate Map<String, Integer> variables = new HashMap<>(); / 变量表private Relation relations; / 优先关系表private int index = 0;public static void main(String args) String str = "a=3;(a+17)/3?"AssignmentExplain assignmentExplain = new AssignmentExplain();try String sentence = str.split(&qu

15、ot;");for (String inputStr : sentence) assignmentExplain.getDoubleGroup(inputStr);System.out.println("n单词符号串：");System.out.println(assignmentExplain.wordSymbols + "n");assignmentExplain.startExplain(inputStr);System.out.println("n变量表：");for (String key : assignment

16、Explain.variables.keySet() System.out.println(key + ":" + assignmentExplain.variables.get(key); catch (Exception e) e.printStackTrace();public void initRelation() relations = new Relation1212;for (int i = 0; i < 12; i+) for (int j = 0; j < 12; j+) Relation relation = new Relation();r

17、elation.setCodeLeft(i + 1);relation.setCodeRight(j + 1);switch (i + 1) case 1:switch (j + 1) case 1:case 2:case 8:case 11:relation.setRelation(Relation.REL_NULL);break;case 3:case 4:case 5:case 6:case 7:case 9:case 10:relation.setRelation(Relation.REL_LESS);break;case 12:relation.setRelation(Relatio

18、n.REL_GREATER);break;break;case 2:switch (j + 1) case 12:relation.setRelation(Relation.REL_GREATER);break;default:relation.setRelation(Relation.REL_NULL);break;break;case 3:case 4:switch (j + 1) case 1:case 11:relation.setRelation(Relation.REL_NULL);break;case 2:case 3:case 4:case 8:case 12:relation

19、.setRelation(Relation.REL_GREATER);break;default:relation.setRelation(Relation.REL_LESS);break;break;case 5:case 6:switch (j + 1) case 1:case 11:relation.setRelation(Relation.REL_NULL);break;case 7:case 9:case 10:relation.setRelation(Relation.REL_LESS);break;default:relation.setRelation(Relation.REL

20、_GREATER);break;break;case 7:switch (j + 1) case 1:case 2:case 11:relation.setRelation(Relation.REL_NULL);break;case 8:relation.setRelation(Relation.REL_EQUAL);break;case 12:relation.setRelation(Relation.REL_GREATER);break;default:relation.setRelation(Relation.REL_LESS);break;break;case 8:switch (j

21、+ 1) case 1:case 7:case 9:case 10:case 11:relation.setRelation(Relation.REL_NULL);break;default:relation.setRelation(Relation.REL_GREATER);break;break;case 9:switch (j + 1) case 1:relation.setRelation(Relation.REL_EQUAL);break;case 7:case 9:case 10:case 11:relation.setRelation(Relation.REL_NULL);bre

22、ak;default:relation.setRelation(Relation.REL_GREATER);break;break;case 10:switch (j + 1) case 1:case 7:case 9:case 10:case 11:relation.setRelation(Relation.REL_NULL);break;default:relation.setRelation(Relation.REL_GREATER);break;break;case 11:switch (j + 1) case 12:relation.setRelation(Relation.REL_

23、GREATER);break;default:relation.setRelation(Relation.REL_NULL);break;break;case 12:switch (j + 1) case 12:relation.setRelation(Relation.REL_EQUAL);break;default:relation.setRelation(Relation.REL_LESS);break;break;relationsij = relation;/ 扫描缓冲区，求得二元组public void getDoubleGroup(String inputStr) throws

24、Exception wordSymbols.clear();inputStr = "#" + inputStr + "#"index = 0;while (index < inputStr.length() String ch = ""while (ch = inputStr.substring(index, index + 1).equals(" ") index+;if (index >= inputStr.length()break;if (ch.equals(" ") ind

25、ex+;continue;if (Character.isLetter(ch.charAt(0) if (!recognizeIdentifier(inputStr) new Exception("不能识别的标识符");index+; else if (Character.isDigit(ch.charAt(0) if (!recognizeInteger(inputStr) new Exception("不能识别的整数");index+; else int code = -1;switch (ch) case "=":code =

26、codeOfWord("=");if (code = -1)System.out.println("找不到该单词符号的种别码");else WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_NULL, "-");wordSymbols.add(symbol);break;case "?":code = codeOfWord("?");if (code = -1)System.out.println("找不到该单词符号的种别

27、码");else WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_NULL, "-");wordSymbols.add(symbol);break;case "+":code = codeOfWord("+");if (code = -1)System.out.println("找不到该单词符号的种别码");else WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_NULL,

28、 "-");wordSymbols.add(symbol);break;case "-":code = codeOfWord("-");if (code = -1)System.out.println("找不到该单词符号的种别码");else WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_NULL, "-");wordSymbols.add(symbol);break;case "*":code = code

29、OfWord("*");if (code = -1)System.out.println("找不到该单词符号的种别码");else WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_NULL, "-");wordSymbols.add(symbol);break;case "/":code = codeOfWord("/");if (code = -1)System.out.println("找不到该单词符号的种别码&qu

30、ot;);else WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_NULL, "-");wordSymbols.add(symbol);break;case "(":code = codeOfWord("(");if (code = -1)System.out.println("找不到该单词符号的种别码");else WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_NULL, &qu

31、ot;-");wordSymbols.add(symbol);break;case ")":code = codeOfWord(")");if (code = -1)System.out.println("找不到该单词符号的种别码");else WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_NULL, "-");wordSymbols.add(symbol);break;case "clear":code = code

32、OfWord("clear");if (code = -1)System.out.println("找不到该单词符号的种别码");else WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_NULL, "-");wordSymbols.add(symbol);break;case "#":code = codeOfWord("#");if (code = -1)System.out.println("找不到该单词符号的种别

33、码");else WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_NULL, "-");wordSymbols.add(symbol);break;case "N":code = codeOfWord("N");if (code = -1)System.out.println("找不到该单词符号的种别码");else WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_NULL,

34、 "-");wordSymbols.add(symbol);break;default:throw new Exception("无法识别的字符");System.out.println("识别出界符/运算符：" + ch);index+;/ 识别标识符的子程序public boolean recognizeIdentifier(String inputStr) int state = 0;String strToken = ""String ch = ""while (index < i

35、nputStr.length() ch = inputStr.substring(index, index + 1);switch (state) case 0:if (Character.isLetter(ch.charAt(0) state = 1;strToken += ch;index+; else return false;break;case 1:if (Character.isLetter(ch.charAt(0) | Character.isDigit(ch.charAt(0) strToken += ch;index+; else state = 2;index-;break

36、;case 2:int code = codeOfWord("v");if (code = -1)System.out.println("找不到该单词符号的种别码");else if (strToken.equals("clear")code = 11;WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_STRING, strToken);wordSymbols.add(symbol);return true;return false;/ 识别常整数的子程序public b

37、oolean recognizeInteger(String inputStr) int state = 0;String strToken = ""String ch = ""while (index < inputStr.length() ch = inputStr.substring(index, index + 1);switch (state) case 0:if (Character.isDigit(ch.charAt(0) state = 1;strToken += ch;index+; else return false;break

38、;case 1:if (Character.isDigit(ch.charAt(0) strToken += ch;index+; else state = 2;break;case 2:index-;int code = codeOfWord("c");if (code = -1)System.out.println("找不到该单词符号的种别码");else WordSymbol symbol = new WordSymbol(code, WordSymbol.TYPE_INT, Integer.valueOf(strToken);wordSymbol

39、s.add(symbol);return true;return false;/ 返回单词符号的种别码public int codeOfWord(String word) for (int i = 0; i < words.length; i+) if (wordsi.equals(word)return i + 1;return -1;public void startExplain(String inputStr) throws Exception / 开始归约initRelation();stack.clear();int pointer = 0;WordSymbol topWor

40、d = wordSymbols.get(pointer);pointer+;WordSymbol rightWord;stack.add(topWord);while (pointer < wordSymbols.size() int stackSize = stack.size();while (-stackSize >= 0) if (stack.get(stackSize).getCode() != 13) topWord = stack.get(stackSize);break;rightWord = wordSymbols.get(pointer);System.out.

41、println("栈：" + stack);/ System.out.println("rightWord:" + rightWord);Relation temp = relationstopWord.getCode() - 1rightWord.getCode() - 1;int relation = temp.getRelation();String strTemp = ""switch (relation) case -1:strTemp = "<"break;case 0:strTemp = &qu

42、ot;="break;case 1:strTemp = ">"break;System.out.println("优先关系:(" + temp.getCodeLeft() + "," + temp.getCodeRight() + "," + strTemp + ")");if (relation <= 0) stack.add(rightWord);if (rightWord.getCode() = 11) variables.clear();WordSymbol top

43、 = stack.pop();top.setCode(13);top.setValue("-");stack.push(top);pointer+; else if (relation = 2) String str = rightWord.getValue().toString();str = inputStr.substring(pointer, pointer + 1);/ int index = inputStr.indexOf(str);/ if(index = -1)System.out.println("输入串在" + str + &quo

44、t;附近有语法错误！");stack.clear();variables.clear();throw new Exception("输入串在" + str + "附近有语法错误！"); else int leftPos, rightPos = stack.size() - 1;leftPos = rightPos - 1;while (stack.get(rightPos).getCode() = 13) rightPos-;leftPos-;while (stack.get(leftPos).getCode() = 13) leftPos-;

45、while (relationsstack.get(leftPos).getCode() - 1stack.get(rightPos).getCode() - 1.getRelation() = 0) rightPos = leftPos;leftPos-;while (stack.get(leftPos).getCode() = 13) leftPos-;/ System.out.println("终结符：left：" + leftPos + ",right:" +/ rightPos);leftPos+;if (leftPos = stack.siz

46、e() - 1) if (stack.get(leftPos).getCode() = 11) variables.clear(); else if (stack.get(leftPos).getCode() = 9) String key = stack.get(leftPos).getValue().toString();Integer integer = variables.get(key);if (integer = null) throw new Exception("变量：" + key + "未定义！"); else WordSymbol

47、symbol = stack.pop();symbol.setCode(13);symbol.setValue(integer);stack.push(symbol); else WordSymbol symbol = stack.pop();symbol.setCode(13);stack.push(symbol); else if (stack.size() - leftPos = 2) System.out.println("输出语句：" + stack.get(leftPos).getValue();stack.pop(); else if (stack.size(

48、) - leftPos = 3) if (stack.get(leftPos).getCode() = 9) String key = stack.get(leftPos).getValue().toString();Integer integer = variables.get(key);if (integer = null) WordSymbol N = stack.pop();stack.pop();stack.pop();variables.put(key, (Integer) N.getValue();stack.push(N); else WordSymbol symbol = stack.pop();variables.put(key, (Integer) symbol.getValue();stack.pop();stack.pop();stack.push(symbol); else if (stack.get(leftPos).getCode() = 7) stack.pop();WordSymbol N = stack.pop();stack.pop();stack.push(N); else WordSymbol operator1