语法、语义分析实验报告

1、河海大学物联网工程学院 编译原理课程实践学年学期 2015-2016第二学期 实验名称 语法分析、语义分析 作 者 1362810225 刘云瞻 组 员 刘云瞻 华路 授课班号 6282506 专 业 计算机科学与技术13级 指导教师 金永霞 2016年6月目录1引言- 2 -1.1 实验目的- 2 -1.2 实践内容- 3 -2.算法设计- 3 -2.1 语法分析- 4 -2.1.1 生成（非）终结符表- 4 -2.1.2 构造FirstVT集和LastVT集- 4 -2.1.4 算符优先分析- 7 -2.2 语义分析- 10 -2.2.1 算术表达式和简单赋值语句的翻译- 10 -3. 运

2、行结果与测试- 11 -3.1 运行结果- 11 -3.2 错误测试- 13 -4.心得体会- 14 -1引言1.1 实验目的通过使用高级语言实现部分算法加强对编译技术和理论的理解。设计的题目要求具有一定的规模，应涵盖本课程内容和实际应用相关的主要技术。1.2 实践内容本实验通过“算符优先分析法”来解决实验任务中的“语法分析”与“语义分析”这两个任务点。其中，“语法分析”是根据输入串和根据文法规则得出的优先关系表，完成一系列移进、归约的过程，“语义分析”在本实验中是通过对归约串进行的解释以及中间代码的生成。具体来说，这里我通过Java 编程语言完成整个实验的设计，根据文法规则求得FirstVT

3、集和LastVT集，然后生成算符优先关系表，最终实现算符优先分析总控程序，输出识别过程及结论；此处，在归约时候根据赋值语句的语法致导定义，为输入的赋值语句生成四元式序列。2. 算法设计本实验的算法设计主要分为“语法分析”和“语义分析”两部分。其中，“语法分析”由生成（非）终结符表、构造FirstVT集和LastVT集、生成算符优先关系表和算符优先分析四个部分组成；“语义分析”是对实现“算术表达式和简单赋值语句的翻译”，找到归约采用文法、输出赋值过程及四元式序列。这里，我使用的文法规则为：A->#S#S->d=EE->E+TE->TT->T*FT->FF-&g

4、t;-PF->PP->(E)P->i输入串为：d=i+i*i#赋值 i=62.1 语法分析2.1.1 生成（非）终结符表根据算符文法的定义简单判断文法是否合法，具体通过BaseUtil.isLegal(grammars)来实现，主要是不存在两个连续相继的非终结符。终结符：文法规则的左部非终结符：文法规则的右部中除了终结符以外都是非终结符2.1.2 构造FirstVT集和LastVT集求这两个集合主要是根据定义来求得，定义形式为：FirstVT：<1>产生式P->a或者P->Qa，则a属于FirstVT(P)<2>产生式P->Q，则Fi

5、rstVT(Q)属于FirstVT(P)LastVT：<1>产生式P->a或者P->aQ，则a属于FirstVT(P)<2>产生式P->Q，则LastVT(Q)属于LastVT(P) 2.1.3 生成算符优先关系表public static char getFirstVt(String wfs, char vt, char C) String firstVtStr = ""for (int i = 0; i < wfs.length; i+) if (C = wfsi.charAt(0) char c = wfsi.toCha

6、rArray();int j = 3;/ A->. 0 1 2 下标从3开始/ A->a.if (isVt(cj, vt) firstVtStr += cj; else / A->B.if (c.length = 4) firstVtStr += String.valueOf(getFirstVt(wfs, vt, cj);/ 求该非终结符的头符 else / A->Ba.firstVtStr += cj + 1;return removeRepeat(firstVtStr);public static char getLastVt(String wfs, char v

7、t, char C) String lastVtStr = ""for (int i = 0; i < wfs.length; i+) if (C = wfsi.charAt(0) char c = wfsi.toCharArray();int j = c.length - 1;/ A->.aif (isVt(cj, vt) lastVtStr += cj; else / A->.Bif (c.length = 4) lastVtStr += String.valueOf(getLastVt(wfs, vt, cj);/ 求该非终结符的尾符 else /

8、A->.aBlastVtStr += cj - 1;lastVtStr += String.valueOf(getLastVt(wfs, vt, cj);/ 求该非终结符的尾符return removeRepeat(lastVtStr);根据FIrstVT、LastVT求出优先关系表<1>产生式右部aQ，则a<FirstVT(Q)<2>产生式右部Qa，则LastVT(Q)>a注：文法中右部含有ab或aQb时，a=b #d()i*+=-#=<d=(<=<<<><)>>>>>i>

9、>>>>*><><>>><+><><><><=><<><<<-><><>>>算符优先关系表public static void setTable(String wfs, char vt, char table) int wfLen = wfs.length;for (int i = 0; i < wfLen; i+) char c = wfsi.toCharArray();for (in

10、t j = 3; j < c.length; j+) / A abif (j + 1 < c.length) && isVt(cj, vt) && isVt(cj + 1, vt) setOperator(cj, cj + 1, table, '=');/ A aBbif (j + 2 < c.length) && isVt(cj, vt) && isVt(cj + 2, vt) && !isVt(cj + 1, vt) setOperator(cj, cj + 2, table,

11、 '=');/ AaB，则a<FirstVT(B)if (j + 1 < c.length) && isVt(cj, vt) && !isVt(cj + 1, vt) char first = getFirstVt(wfs, vt, cj + 1);for (int k = 0; k < first.length; k+) setOperator(cj, firstk, table, '<');/ ABb，则LastVT(B)>aif (j + 1 < c.length) &&

12、!isVt(cj, vt) && isVt(cj + 1, vt) char last = getLastVt(wfs, vt, cj);for (int k = 0; k < last.length; k+) setOperator(lastk, cj + 1, table, '>');2.1.4 算符优先分析（1）移进归约的过程如下图所示。程序图（2）对于程序图具体说明：Str：输入串Array：当前栈a：输入串中当前的读入字符串归约方法：（找2个大于） （1） 栈中第一个终结符>输入符号 （2） 自顶向下扫描符号栈，找到某个i，满足Arr

13、ayi<栈中第一个终结符移进方法： 栈中第一个终结符<=输入符号public static void dealProcess(char input, char vts, char table, String wfs) System.out.println("分析过程：");System.out.println("t" + "栈内容" + "tt" + "输入" + "t" + "剩余串" + "tt" + "优先关

14、系说明" + "tt" + "动作");/ 初始化char stack = ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ;/ 栈int step = 1;/ 步骤int top = 0; / 栈顶stacktop = '#'int j; / 栈顶终结符下标int i = 0;/ 输入串下标char a = inputi

15、;char Q = 0;char s_top = 0;while (i < input.length) if (BaseUtil.isVt(stacktop, vts) j = top; else j = top - 1;/ 移进（比较第一个终结符与输入字符）if ('<' = BaseUtil.getOperator(stackj, a, table) | '=' = BaseUtil.getOperator(stackj, a, table) formatPrint(step, i, stack, input, a,stackj + "

16、" + BaseUtil.getOperator(stackj, a, table) + "" + a + "", "移进");step+;top+;stacktop = a;i+;a = inputi;/ 归约（找出第一个比栈顶终结符小的）else if ('>' = BaseUtil.getOperator(stackj, a, table) Q = stackj;s_top = stackj;/ 输出用if (BaseUtil.isVt(stackj - 1, vts) j = j - 1; el

17、se j = j - 2;String record4print = ""/ 输出用while ('=' = BaseUtil.getOperator(stackj, Q, table) record4print = '=' + "" + Q + "" + record4print;/ 输出用Q = stackj;if (BaseUtil.isVt(stackj - 1, vts) j = j - 1; else j = j - 2;formatPrint(step, i, stack, input,

18、a, stackj + "" + BaseUtil.getOperator(stackj, Q, table) + "" + Q+ "" + record4print + BaseUtil.getOperator(s_top, a, table) + "" + a + "", "归约");step+;String temp = ""/ 查找规约的字符串for (int m = j + 1; m <= top; m+) temp += stackm;S

19、ystem.out.println("当前规约串： " + temp);int pos = CommonUtil.Operate(temp, wfs);if (pos != -1) System.out.println("使用文法为: " + wfspos);/ 语义分析int place = CommonUtil.ChooseFun(pos, top, j + 1, stack);for (int m = j + 1; m <= top; m+) stackm = ' 'top = j + 1;/ System.out.print

20、ln("数组空间：" + place);char str = wfspos.toCharArray()0;CommonUtil.ValueArrInteger.valueOf(str) = CommonUtil.ValueArrplace;System.out.println("规约字符" + str + "的Value值: " + CommonUtil.ValueArrInteger.valueOf(str).getValue();stacktop = wfspos.toCharArray()0; else System.out.p

21、rintln("规约出错!");break;/ stacktop = 'N' else formatPrint(step, i, stack, input, a,stackj + "" + BaseUtil.getOperator(stackj, a, table) + "" + a + "", "错误");System.out.println("This inputStr has an error!");break;/ #N 时，停止归约if (a = &#

22、39;#' && top = 1) formatPrint(step, i, stack, input, a, "#=#", "接受");System.out.println("最终运算结果d的值为：" + CommonUtil.ValueArrInteger.valueOf('d').getValue();break;2.2 语义分析2.2.1 算术表达式和简单赋值语句的翻译（1）使用的数据结构/ 对象存储：存储i、P、E等的Value值public static ChaPara ValueArr = new ChaPara520;（2）赋值过程实现结果：<对于归约串来说> （1）输出当前归约串 （2）归约所使用的文法 （3）归约成结果的Value值 （4）四元式表示运算过程 （5）显示输入串最终结果 3. 运行结果与测试3.1 运行结果（1）具体输出结果如