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

《编译原理》

课程设计

赋值语句的解释程序设计

姓名：汤朋

学号：2014112217

班级：软件四班

时间：2017/6/13

学期：2016-2017第一学期

1

1. 设计题目：

赋值语句的解释程序设计 2. 设计内容：

用算符优先分析方法设计一个分析解释程序，对输入的赋值语句、输出语句、清除语句进行词法分析、语法分析、表达式求值并存储于指定变量中：若存在错误，提示错误相关信息。 3. 设计目的：

a) 了解掌握算符优先分析的基本方法、内容 b) 学会科学思考并解决问题，提高程序设计能力 4. 实现环境 ? 电脑：

? Windows10家庭中文版 ? 型号：雷神

? 处理器：Intel(R) Core(TM) i7-6700HQ CPU @2.60GHz ? RAM：16.0GB(15.9GB可用)

? 系统类型：64位操作系统，基于x64的处理器

?

实现语言及环境： Java，JDK 1.8 IDE：Ecpliseneon.1

5. 概要设计 文法表示： S? v=E|E?|clear

2

E?E+T|E-T|T T?T*F|T/F|F F?(E)|v|c

归约规则： N? v=N|N?|clear N?N +N |N -N |N N?N *N |N /N |N N?(N)|v|c

种别码设计：

单词符号 = ？ + - * / ( ) v c 3

种别码 1 2 3 4 5 6 7 8 9 10 clear # N

优先关系表

1 2 3 4 5 6 7 8 9 10 11 12

4

11 12 13 = ? + - * / ( ) v c 1 = = 2 ? > > > > > > > < 3 + < > > > > < > > > < 4 - < > > > > < > > > < 5 * < < < > > < > > > < 6 / < < < > > < > > > < 7 ( < < < < < < < 8 ) > > > > = > > > < 9 v < < < < < < < 10 11 c < < < < < < < 12 clear # < > > > > > > > > > > > = clear # < 开始输入单词符号串初始化栈stack;设指针 pointer = 0;将串的第一个单词符号#二元组压入stack；pointer++Stack.size() == 3 && stack.pop().getCode() == 12 NPointer < stack.size()?YNstack.pop().getCode() == 13&& stack.pop().getCode() == 12 N栈顶终结符优先级小于等于pointer所指终结符？Y将pointer所指终结符的单词符号入栈；pointer++N栈顶终结符优先级大于pointer所指终结符？YrightPos = leftPos = pointer-1;leftPos--;NStack.get(rightPos).getCode == 13?rightPos--;leftPos--;输出表达式错误输出在input.charAt(pointer)附近语法错误YNNStack.get(leftPos).getCode == 13?YleftPos--;YN清空stack和变量表Stack.get(leftPos) euqals stack.get(rightPos)?YrightPos = leftPos;NleftPos++;leftPos == pointer-1?结束YStack.get(leftPos).getCode()==11?N报错：变量stack.get(leftPos).getValue()未定义变量stack.get(leftPos).getValue()存在变量表中？Y修改栈顶元素的种别码为13，设其值为该变量的值Stack.get(leftPos).getCode()==9?NPointer-leftPos-1==2?Y输出stack.get(leftPos).getValue();stack.pop();N清空变量表YPointer-leftPos-1==3?Y报错：表达式有错！结束N变量Stack.get(leftPos).getValue是否存在？NYStack.get(leftPos).getCode()==9?YY更新变量表中的值NN修改栈顶元素的种别码为13，设其值为该常量的值N在变量表中创建变量并赋值弹出栈顶三个元素；重新压入第二个元素YStack.get(leftPos).getCode()==7?NStack.get(leftPos+1).getCode()==3?NY弹出栈顶三元素；计算首尾两元素之和并放到变量表中的临时变量中弹出栈顶三元素；计算首尾两元素之积并放到变量表中的临时变量中YStack.get(leftPos+1).getCode()==5?NStack.get(leftPos+1).getCode()==4?Y弹出栈顶三元素；计算首尾两元素之差并放到变量表中的临时变量中压入（13，1，计算结果）到栈N压入（13，1，计算结果）到栈弹出栈顶三元素；计算首尾两元素之商并放到变量表中的临时变量中YStack.get(leftPos+1).getCode()==6?N 程序流程图 5 报错：不能识别字符Stack.get(leftPos+1).getValue()

6. 详细设计

单词符号二元组使用下面的类来表示：

publicclass WordSymbol {

@Override

public String toString() {

6

publicstaticfinalintTYPE_NULL = 0; //无值 publicstaticfinalintTYPE_INT = 1; //整数 publicstaticfinalintTYPE_STRING = 2; //字符串

intcode; inttype;

public WordSymbol() { }

public WordSymbol(intcode, inttype, Object value) { }

publicint getCode() { }

publicvoid setCode(intcode) { }

publicint getType() { }

publicvoid setType(inttype) { }

public Object getValue() { }

publicvoid setValue(Object value) { }

this.value = value; returnvalue; this.type = type; returntype; this.code = code; returncode; super();

this.code = code; this.type = type; this.value = value; super();

//种别码

//单词符号值类型

Object value; //单词符号的属性值

}

}

return\[code=\ + code + \type=\ + type + \value=\ + value

+ \;

归约栈：用Java中的栈对象Stack来表示 单词串：用链表对象List来存放单词串 变量表：

使用Map对象来充当变量表，其以键值对的方式存放变量，键可以设为变量名，值存放变量值

变量名 Key 可归约串语义解释：

变量归约：N?v，在变量表中查找该变量，若不存在则报错：变量未定义，否则修改非终结符N的属性值为变量v的值，并设N的种别码为13

常量归约：N?c，修改非终结符N的属性值为常量c的值，并设N的种别码为13

运算归约：设运算的操作数为N1，N2；将N1，N2进行相应运算并将运算结果设为N3的属性值，将N3的种别码设为13 括号归约：将(N)归约为N

赋值归约：在变量表中查找被赋值的变量v，若不存在，则先在变量表中创建该变量，然后再将N的属性值赋值给v，最后将 v = N归约为N

输出语句：先输出表达式N的属性值，然后将N?归约为N

7

值 Value 清除语句：将变量表中的所以变量清空，然后clear归约为N 运算符之间的关系使用对象Relation来描述，其结构如下

publicclass Relation {

publicvoid setRelation(intrelation) {

8

publicstaticfinalintREL_LESS = -1; // 小于 publicstaticfinalintREL_EQUAL = 0; // 等于 publicstaticfinalintREL_GREATER = 1; // 大于 publicstaticfinalintREL_NULL = 2; // 无关系 intcodeLeft, codeRight; intrelation; public Relation() { }

public Relation(intcodeLeft, intcodeRight, intrelation) { }

publicint getCodeLeft() { }

publicvoid setCodeLeft(intcodeLeft) { }

publicint getCodeRight() { }

publicvoid setCodeRight(intcodeRight) { }

publicint getRelation() { }

returnrelation;

this.codeRight = codeRight; returncodeRight;

this.codeLeft = codeLeft; returncodeLeft; super();

this.codeLeft = codeLeft; this.codeRight = codeRight; this.relation = relation; super();

}

this.relation = relation;

@Override

public String toString() { } }

String str = \; switch (relation) { case -1: }

return\：\ + codeLeft + str + codeRight;

str = \; break; str = \; break; str = \; break;

str = \无关系 \; break;

case 1:

case 0:

case 2:

同时，使用Relation[][]二维数组来存放优先符关系表

7. 程序清单

package tp;

import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Stack;

publicclass AssignmentExplain {

// 单词符号

private String[] words = { \, \, \, \, \, \, \, \, \, \, private Stackstack = new Stack<>(); // 归约栈

private ListwordSymbols = new ArrayList<>(); // 单词符号 private Mapvariables = new HashMap<>(); // 变量表

9

\, \, \ };

private Relation[][] relations; // 优先关系表 privateintindex = 0;

publicstaticvoid main(String[] args) { }

publicvoid initRelation() {

relations = new Relation[12][12]; for (inti = 0; i< 12; i++) {

for (intj = 0; j< 12; j++) {

Relation relation = new Relation(); relation.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;

String str = \;

AssignmentExplain assignmentExplain = new AssignmentExplain(); try { }

String[] sentence = str.split(\); for (String inputStr : sentence) { }

e.printStackTrace();

assignmentExplain.getDoubleGroup(inputStr); System.out.println(\单词符号串：\);

System.out.println(assignmentExplain.wordSymbols + \); assignmentExplain.startExplain(inputStr); System.out.println(\变量表：\);

for (String key : assignmentExplain.variables.keySet()) { }

System.out.println(key + \ +

assignmentExplain.variables.get(key));

} catch (Exception e) {

case 3: case 4: case 5: case 6:

10

case 7: case 9: case 10: } break;

switch (j + 1) { case 12: } break;

relation.setRelation(Relation.REL_GREATER); break;

relation.setRelation(Relation.REL_NULL); break;

relation.setRelation(Relation.REL_LESS); break;

relation.setRelation(Relation.REL_GREATER); break;

case 12:

case 2:

default:

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: } break;

relation.setRelation(Relation.REL_GREATER); break;

relation.setRelation(Relation.REL_LESS); break;

default:

case 5: case 6:

switch (j + 1) { case 1: case 11:

11

relation.setRelation(Relation.REL_NULL); break;

case 7: case 9: case 10: } break;

switch (j + 1) { case 1: case 2: case 11: } break;

switch (j + 1) { case 1: case 7: case 9: case 10: case 11: } break;

12

relation.setRelation(Relation.REL_LESS); break;

relation.setRelation(Relation.REL_GREATER); break;

default:

case 7:

relation.setRelation(Relation.REL_NULL); break;

relation.setRelation(Relation.REL_EQUAL); break;

relation.setRelation(Relation.REL_GREATER); break;

relation.setRelation(Relation.REL_LESS); break;

case 8:

case 12:

default:

case 8:

relation.setRelation(Relation.REL_NULL); break;

relation.setRelation(Relation.REL_GREATER); break;

default:

case 9:

switch (j + 1) { case 1:

relation.setRelation(Relation.REL_EQUAL); break;

case 7: case 9: case 10: case 11: } break;

switch (j + 1) { case 1: case 7: case 9: case 10: case 11: } break;

switch (j + 1) { case 12: } break;

switch (j + 1) { case 12:

relation.setRelation(Relation.REL_EQUAL);

13

relation.setRelation(Relation.REL_NULL); break;

relation.setRelation(Relation.REL_GREATER); break;

default:

case 10:

relation.setRelation(Relation.REL_NULL); break;

relation.setRelation(Relation.REL_GREATER); break;

default:

case 11:

relation.setRelation(Relation.REL_GREATER); break;

relation.setRelation(Relation.REL_NULL); break;

default:

case 12:

{

}

}

}

}

}

break;

relation.setRelation(Relation.REL_LESS); break;

default:

break;

relations[i][j] = relation;

// 扫描缓冲区，求得二元组

publicvoid getDoubleGroup(String inputStr) throws Exception {

wordSymbols.clear();

inputStr = \ + inputStr + \; index = 0;

while (index

{

String ch = \;

while ((ch = inputStr.substring(index, index + 1)).equals(\\)) }

if (ch.equals(\)) { }

if (Character.isLetter(ch.charAt(0))) {

if (!recognizeIdentifier(inputStr)) { } index++;

if (!recognizeInteger(inputStr)) { } index++; intcode = -1; switch (ch) { case\:

14

index++;

if (index>= inputStr.length())

break;

index++; continue;

new Exception(\不能识别的标识符\);

} elseif (Character.isDigit(ch.charAt(0))) {

new Exception(\不能识别的整数\);

} else {

code = codeOfWord(\); if (code == -1) } break;

code = codeOfWord(\); if (code == -1) } break;

code = codeOfWord(\); if (code == -1) } break;

code = codeOfWord(\); if (code == -1) } break;

code = codeOfWord(\); if (code == -1)

System.out.println(\找不到该单词符号的种别码\); else {

15

System.out.println(\找不到该单词符号的种别码\); WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol);

else {

WordSymbol.TYPE_NULL, \);

case\:

System.out.println(\找不到该单词符号的种别码\); WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol);

else {

WordSymbol.TYPE_NULL, \);

case\:

System.out.println(\找不到该单词符号的种别码\); WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol);

else {

WordSymbol.TYPE_NULL, \);

case\:

System.out.println(\找不到该单词符号的种别码\); WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol);

else {

WordSymbol.TYPE_NULL, \);

case\:

}

WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol);

WordSymbol.TYPE_NULL, \);

break;

code = codeOfWord(\); if (code == -1) } break;

code = codeOfWord(\); if (code == -1) } break;

code = codeOfWord(\); if (code == -1) } break;

code = codeOfWord(\); if (code == -1) }

16

case\:

System.out.println(\找不到该单词符号的种别码\); WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol);

else {

WordSymbol.TYPE_NULL, \);

case\:

System.out.println(\找不到该单词符号的种别码\); WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol);

else {

WordSymbol.TYPE_NULL, \);

case\:

System.out.println(\找不到该单词符号的种别码\); WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol);

else {

WordSymbol.TYPE_NULL, \);

case\:

System.out.println(\找不到该单词符号的种别码\); WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol);

else {

WordSymbol.TYPE_NULL, \);

}

}

}

}

}

break;

code = codeOfWord(\); if (code == -1) } break;

code = codeOfWord(\); if (code == -1) } break;

thrownew Exception(\无法识别的字符\);

System.out.println(\找不到该单词符号的种别码\); WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol); else {

System.out.println(\找不到该单词符号的种别码\); WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol); else {

case\:

WordSymbol.TYPE_NULL, \);

case\:

WordSymbol.TYPE_NULL, \);

default:

System.out.println(\识别出界符/运算符：\ + ch); index++;

// 识别标识符的子程序

publicboolean recognizeIdentifier(String inputStr) {

intstate = 0;

String strToken = \; String ch = \;

while (index

ch = inputStr.substring(index, index + 1); switch (state) { case 0:

if (Character.isLetter(ch.charAt(0))) {

state = 1; strToken += ch; index++;

17

}

}

}

} else { } break;

if (Character.isLetter(ch.charAt(0)) || } break;

intcode = codeOfWord(\); if (code == -1) }

returntrue;

System.out.println(\找不到该单词符号的种别码\); if (strToken.equals(\))

code = 11;

WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol); else {

strToken += ch; index++; state = 2; index--; returnfalse;

case 1:

Character.isDigit(ch.charAt(0))) {

} else {

case 2:

WordSymbol.TYPE_STRING, strToken);

returnfalse;

// 识别常整数的子程序

publicboolean recognizeInteger(String inputStr) {

intstate = 0;

String strToken = \; String ch = \;

while (index

ch = inputStr.substring(index, index + 1); switch (state) { case 0:

if (Character.isDigit(ch.charAt(0))) {

state = 1; strToken += ch; index++;

18

}

}

}

} else { } break;

if (Character.isDigit(ch.charAt(0))) { } break; index--;

intcode = codeOfWord(\); if (code == -1) }

returntrue;

System.out.println(\找不到该单词符号的种别码\); WordSymbol symbol = new WordSymbol(code, wordSymbols.add(symbol); else {

strToken += ch; index++; state = 2; returnfalse;

case 1:

} else {

case 2:

WordSymbol.TYPE_INT, Integer.valueOf(strToken));

returnfalse;

// 返回单词符号的种别码

publicint codeOfWord(String word) { }

publicvoid startExplain(String inputStr) throws Exception {// 开始归约

initRelation(); stack.clear(); intpointer = 0;

WordSymbol topWord = wordSymbols.get(pointer); pointer++;

WordSymbol rightWord;

19

for (inti = 0; i

return -1;

if (words[i].equals(word))

returni + 1;

stack.add(topWord);

while (pointer

intstackSize = stack.size(); while (--stackSize>= 0) { }

rightWord = wordSymbols.get(pointer); System.out.println(\栈：\ + stack);

// System.out.println(\ Relation temp = relations[topWord.getCode() - intrelation = temp.getRelation(); String strTemp = \; switch (relation) { case -1: }

System.out.println(\优先关系:(\ + temp.getCodeLeft() + \ + if (relation<= 0) {

stack.add(rightWord);

if (rightWord.getCode() == 11) { }

pointer++;

String str = rightWord.getValue().toString(); str = inputStr.substring(pointer, pointer + 1); // int index = inputStr.indexOf(str); // if(index == -1)

20

if (stack.get(stackSize).getCode() != 13) { }

topWord = stack.get(stackSize); break;

1][rightWord.getCode() - 1];

strTemp = \; break;

strTemp = \; break;

strTemp = \; break;

case 0:

case 1:

temp.getCodeRight() + \ + strTemp + \);

variables.clear();

WordSymbol top = stack.pop(); top.setCode(13); top.setValue(\); stack.push(top);

} elseif (relation == 2) {

栈：[(12,0,-)] 优先关系:(12,9,<) 栈：[(12,0,-), (9,2,b)] 优先关系:(9,2,>)

栈：[(12,0,-), (13,2,15)] 优先关系:(12,2,<)

栈：[(12,0,-), (13,2,15), (2,0,-)] 优先关系:(2,12,>) 输出语句：15

栈：[(12,0,-), (13,2,15)] 优先关系:(12,12,=)

栈：[(12,0,-), (13,2,15), (12,0,-)]

变量表： a:5 b:15

识别出界符/运算符：# 识别出界符/运算符：+ 识别出界符/运算符：* 识别出界符/运算符：? 识别出界符/运算符：#

单词符号串：

[(12,0,-), (9,2,b), (3,0,-), (9,2,a), (5,0,-), (9,2,a), (2,0,-), (12,0,-)]

栈：[(12,0,-)] 优先关系:(12,9,<) 栈：[(12,0,-), (9,2,b)] 优先关系:(9,3,>)

栈：[(12,0,-), (13,2,15)] 优先关系:(12,3,<)

栈：[(12,0,-), (13,2,15), (3,0,-)] 优先关系:(3,9,<)

栈：[(12,0,-), (13,2,15), (3,0,-), (9,2,a)] 优先关系:(9,5,>)

栈：[(12,0,-), (13,2,15), (3,0,-), (13,2,5)] 优先关系:(3,5,<)

栈：[(12,0,-), (13,2,15), (3,0,-), (13,2,5), (5,0,-)] 优先关系:(5,9,<)

栈：[(12,0,-), (13,2,15), (3,0,-), (13,2,5), (5,0,-), (9,2,a)] 优先关系:(9,2,>)

栈：[(12,0,-), (13,2,15), (3,0,-), (13,2,5), (5,0,-), (13,2,5)] 优先关系:(5,2,>)

26

栈：[(12,0,-), (13,2,15), (3,0,-), (13,2,25)] 优先关系:(3,2,>)

栈：[(12,0,-), (13,2,40)] 优先关系:(12,2,<)

栈：[(12,0,-), (13,2,40), (2,0,-)] 优先关系:(2,12,>)

输出语句：40 --此处为输出语句

栈：[(12,0,-), (13,2,40)] 优先关系:(12,12,=)

栈：[(12,0,-), (13,2,40), (12,0,-)]

变量表： a:5 b:15

识别出界符/运算符：# 识别出界符/运算符：= 识别出界符/运算符：+ 识别出界符/运算符：#

单词符号串：

[(12,0,-), (9,2,a), (1,0,-), (9,2,a), (3,0,-), (9,2,b), (12,0,-)]

栈：[(12,0,-)] 优先关系:(12,9,<) 栈：[(12,0,-), (9,2,a)] 优先关系:(9,1,=)

栈：[(12,0,-), (9,2,a), (1,0,-)] 优先关系:(1,9,<)

栈：[(12,0,-), (9,2,a), (1,0,-), (9,2,a)] 优先关系:(9,3,>)

栈：[(12,0,-), (9,2,a), (1,0,-), (13,2,5)] 优先关系:(1,3,<)

栈：[(12,0,-), (9,2,a), (1,0,-), (13,2,5), (3,0,-)] 优先关系:(3,9,<)

栈：[(12,0,-), (9,2,a), (1,0,-), (13,2,5), (3,0,-), (9,2,b)] 优先关系:(9,12,>)

栈：[(12,0,-), (9,2,a), (1,0,-), (13,2,5), (3,0,-), (13,2,15)] 优先关系:(3,12,>)

栈：[(12,0,-), (9,2,a), (1,0,-), (13,2,20)] 优先关系:(1,12,>)

栈：[(12,0,-), (13,2,20)] 优先关系:(12,12,=)

栈：[(12,0,-), (13,2,20), (12,0,-)]

27

变量表： a:20 b:15

执行错误语句的运行结果： 语句：b=a+10

错误：在使用变量a之前没有定义，故报错变量a未定义

语句：b=10;b?*?

错误：在第二条语句中不符合表达式定义，错误在字符‘？’处

语句：a=10;clear;b=a+1

28

错误：第一条语句定义了变量a，第二条语句清空了变量表，故a就不存在了，第三条语句引用a，此时就会报错：变量a未定义。同时变量表也为空

29

括号测试语句：a=3;(a+17)/3? 控制台输出：

识别出界符/运算符：# 识别出界符/运算符：= 识别出界符/运算符：#

单词符号串：

[(12,0,-), (9,2,a), (1,0,-), (10,1,3), (12,0,-)]

栈：[(12,0,-)] 优先关系:(12,9,<) 栈：[(12,0,-), (9,2,a)] 优先关系:(9,1,=)

30

本文来源：https://www.bwwdw.com/article/wila.html