实验二 算术表达式解释器于龙斌

实验二 算数表达式解释器的设计与实现

一. 实验目的

1、了解并掌握自顶向下语法分析的思想，熟悉递归下降子程序分析法。

2、了解并掌握语法制导翻译法，掌握采用递归子程序进行语义分析的方法。

二. 实验内容

用适当的程序设计语言编制一个算术表达式的解释器，并完成相应的调试，要求该程序能够读入一个算术表达式，运行后给出计算的结果。 1．算术表达式的解释过程（参考）

第一步：首先进行词法分析（即使用实验一编制的词法分析器），提取最终得到的结果——单词符号序列，将其作为语法和语义分析的输入；

第二步：调用算术表达式的语法分析器。本次实验要求采用递归下降子程序法编写语法分析器，并且此语法分析器中包含对语义的分析。

分析结束后，显示表达式的计算结果。 2．使用的文法

E –> TE’

E’ –> +TE’ |?|-TE’ T –> FT’

T’ –> *FT’|?|/TE’ F→i｜(E) 其中i可为整数(简单点的)，如果考虑周全的话，可取实数类型(需要看一下自己编制的词法分析器是否对实数进行了识别)。该文法的递归下降子程序参见课堂笔记(单纯语法分析部分在第四章介绍过, 结合语义分析的部分代码在第六章介绍过)。

3. 有能力的同学在完成加乘算术表达式的计算后，试扩充2 中定义的文法,增加识别减法和除法的规则，并修改对应的程序，使之能够识别并计算加减乘除四则运算式。

三. 实验要求

1. 程序完成后，由实验老师检查代码，验证程序的功能。如: 输入 (2+3)*10

对文法进行扩充的，输入 (12-8)*20/5+4 等等。

2. 实验二共4学时，实验完成后，提交一份实验报告，写清实验的目的、内容、思路、设计及实现的过程(包括关键的代码，不宜多)，以及实验的结果。实验类型为设计型实验。

四. 程序设计流程图

语法分析器遵循自上而下语法分析的基本算法。其核心思想是将每个非终结符组织成函数的形式，并在每个函数中依据相应的产生式右部的符号序列，对读进的符号串进行匹配。如果在产生式右部遇到终结符，那么新读进的符号必须与该终结符一致；如果遇到非终结符，那么则根据预测分析表，调用相应的非终结符对应的函数继续匹配。如果不能满足以上两点，

1

则认为源程序出现了语法错误。算法的流程图如下所示：

开始 打开文件 Y 读取字符 关闭文件 读一个符号 N M1=0 { Y I++ M1=i N M2=0 、 Y j++ M2=j N } M3=0 Y k++ M3=k N i、j、k值是否相邻 语法分析错误 N 读下一个字符 输出运算结果 结束 2

五. 实验步骤

1、定义一些全局变量和数组，其中数组用来存放词法分析的结果，定义布尔型变量 flag用来作为错误信息的提示标志。关键代码如下： string[,] str = new string[50,2];

2、 打开词法分析的结果：点击词法分析按钮，将保存在磁盘上的词法分析结果赋值给 textbox并将其显示在文本框中。

3、进行语法分析：在进行语法分析前，首先将textbox中的字符串进行分割，调用 tiQuZiFu()方法，在该方法中我们首先定义三个数组m1,m2,m3分别记录左括号、右括号和顿号的位置，如果遇到左括号（譬如“((、()“）则继续向下读取下一个，如果下一个还为左括号则记录上一个左括号的位置，如若下一个不为左括号则记录上一个左括号的位置并将此时的位置变量i进行减1进行变量值的恢复。如果遇到顿号，记录当前的位置于m3中，此时继续往下走，如果下一个字符为左括号或者右括号，此时什么也不做。否则的话将i值减1进行位置的恢复。遇到右括号的情况与左括号的情况相似。最后调用Substring方法进行字符串的截取。关键代码如下：

for (int i = 0; i < m1.Count; i++) //进行字符串的截取 {

str[i, 0] = str1.Substring(Convert.ToInt32(m1[i]) + 1, Convert.ToInt32(m2[i]) - Convert.ToInt32(m1[i]) - 1);

str[i, 1] = str1.Substring(Convert.ToInt32(m2[i]) + 1, Convert.ToInt32(m3[i]) - Convert.ToInt32(m2[i]) - 1) }

4、判断括号是否合法，调用checkSpace()方法。由于定义了静态的数组str来存放词法分析的结果，我们先定义全局变量m来存放数组的真实长度。在该方法中首先判断左右括号的个数是否匹配，接着判断左右括号是否匹配.判断左右括号是否匹配的主要思想是：若存放括号的arr数组的第一个字符是右括号，则提示括号不匹配的错误；如果第一个为左括号，则继续往下找，直到找到右括号为止，此时将这两个字符从数组中移除。接下来从头开始遍历数组，直到找到错误或者将数组遍历完为止。关键代码如下： if (a != b) //左右括号不相等时 {

MessageBox.Show(\表达式不正确！！！\flag = false; } else {

for (int j = 0; j < arr.Count;) {

if (arr[0].Equals(\数组的头部为“）”时 提示出错 {

MessageBox.Show(\表达式不正确！！！\flag = false; break; }

3

else {

if (arr[j].Equals(\如果为“（”则寻找相应的“）”并将他们从arr链表中移除 {

for (int m = j; m < arr.Count; m++) {

if (arr[m].Equals(\{

arr.RemoveAt(j); arr.RemoveAt(m-1); } } }

5、利用递归下降子程序法，进行加减乘除的运算。文法中每个非终结符对应一个函数，按照文法中非终结符的顺序进行函数的编写。其中F()函数是递归的出口，每个函数的返回值类型定义为整形，如果句子符合文法的规定，则返回表达式的值。其中在E1()、T()函数中进行了异常的判断（譬如a+2，此时由于+号左右的种别码不同则提示表达式不正确的错误信息提示）。在加减运算中，将返回值k的初值赋值为0，在乘除运算中，将返回值k的初值赋值为1。核心代码如下： public int T1() {

int k = 1; if (flag) {

if (i < m) {

if (str[i, 1].Equals(\{ i++; if (i < m) {

if (!str[i, 1].Equals(str[i - 2, 1]) && !(str[i, 1].Equals(\&& !(str[i-2,1].Equals(\{

MessageBox.Show(\表达式不正确！！！\flag = false; } else {

k = F() * T1(); } } else {

4

MessageBox.Show(\表达式不正确！！！\flag = false; } }

else if (str[i, 1].Equals(\{

return(1/(F() * T1())); else { k = 1; }

return k;

六. 实验结果

只有当输入符合该文法要求的表达式才能在最后显示出结果，倘若输入任何一个不符合语法规范的句子都会提示表达式不正确的信息。然后弹出对话框咨询用户是否重新输入，若点击确定，则光标有移到文本框，让用户重新输入。

七. 实验心得与体会

在刚开始的时候，自己脑袋一片空白，始终不明白词法分析和语法分析之间的联系。后来询问老师，老师告诉我说，最初可以不考虑词法分析与语法分析的关联，自己先定义一个二维数组存放一个固定的值来作为语法分析的输入。后来自己按照老师说的定义了静态的二位数组str并在里面存放了一个句子。然后按照老师上课给的伪代码进行语法分析程序在C#中的编写。起初，我只是完成了对正确句子的语法分析，后来自己又在其基础上进行了包括括号在内的异常信息的捕获。最后困扰我的就是词法与文法的关联。刚开始我想把词法与文法放在同一个程序里，但由于自己定义的一些变量与词法分析中的变量产生了冲突，只好放弃这种想法。后来自己想出了利用substring函数来对保存起来的词法分析结果进行截取，动态的给str数组赋值。在进行截取的时候，主要的问题还是数组越界，后来自己通过单步调试解决了这个问题。

语法分析是编译器的重要阶段之一，根据一定得规则构成语言的各种结构，即语法规则：根据语法规则识别入序列中的语言结构，即语法分析，同词法分析比较，语法分析的不是记号，而是组成语言的句子，从结构上讲不是线性的而是层次的。对于规模比较小的语言，递归下降子程序方法是很有效的方法，它简单灵活，容易构造，其缺点是程序与文法直接相关，对文法的任何改变均需对程序进行相应的修改。

通过这次实验，我对编译原理这门专业必修课有了进一步的深层次了解，把理论知识应用于实践中，也让我们重新熟悉了才C#语言的相关内容，加深了对C#语言的深化和用途的了解，相信在以后的毕业设计以及读研自己做项目时可以更大的提升。

5

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