算符优先分析器设计

算符优先分析器设计

1实验目的

（1）掌握算符优先分析法—— 一种自底向上的语法分析方法的思想。 （2）能识别算符优先分析法中的可规约串——最左素短语。 （3）领会算符优先关系表转换成优先函数的方法。

2实验内容和实验要求

根据形式化算法，编制程序实现一个算符优先分析器，能对常见的算术表达式语句进行分析。

要求实现以下功能： 1) 组织算术表达式的输入；

2) 组织算符优先关系表或者优先函数的输入；

3) 若输入的符号串是一个算术表达式语句，则输出一个分析树骨架（既每一步规约用到的最左素短语），否则输出一个错误信息。

3 待分析的语法描述

E->E+T|T T->T*F|F F->(E)| I

4算法描述

4.1 算府分析法基本方法

实现算法，转化成某种高级语言程序，实现一个算符优先分析器。其中要用到分析栈和输入缓冲器，本实验采用的方法是一种自底向上的语法分析方法，所以是在词法分析的基础上进行的。

对于表达式结果的计算，要在算法中引入内部变量来保存结果，另外在分析过程中，除了移进、规约、接受、报错等动作外，还要引入计算的动作。

4.2实现方法

（1） 首先定义char precede（char a,char c），在这里规定算符（终结符之间）的优先规则，在分析文法的时候便于调用。

（2） 再定义 isn(char c)，判断是否为非终结符，返回值为1和0，用于循环调用。

（3）主函数，总控算法：

1．定义栈堆Stack中的变量，以及控制指针（用于存发归约或者待形成最左素短语的符号串）。

2．用string工作单元存放当前输入的字符，归约成功的标志是当读入的输入字符是句子的结束符号#号时，即栈中只是剩下#T的时候（栈Stack中只剩下开始标志# 和终结符号T的时候）

使用判断是否栈顶指针指向的是#，若不是，则继续顺序扫描子过程。 从输入符号串中依次读入字符到string中， 调用char precede（char a,char c）中进行分析是否要归约，还是要移进输入符，再栈S中形成最左素短语。

Loop：

当stack[j]与当前输入符s之间是.>关系时,重复寻找最左素短语，将stack[j+1]…stack[k]归约为某个终结符（ETF），这是即可输出当前的归约串，将最 左素短语进行归约。

当stack[j]与当前输入符s之间是<.或者时＝关系时, 再将字符读入到栈堆Stack中，即移进字符串。

若均不是，则转入出错处理，输出分析失败。 当最后分析到读入的字符串时#号时，分析成功。

4.3子过程分析

4.3.1优先函数的定义char precede（char a,char c）

根据给定的文法，分析终结符号之间的优先关系，+,*,(,)，#,总共32种优

先关系。

4.3.2出错管理（两类错误）

(1)如果分析栈顶的中继符号与下一个输入字符之间没有优先关系，即表明下一个输入的字符与已分析归约的文法符号串之间是不匹配的，即一个错误的基本语法成分。发现此类错误之后给出错误信息，同时结束输入符号串的进一步分析。 （2）当前句型中找到一个最左素短语，单不存在右部包含最左素短语的任意产生式。此时输出出错的信息，同时出错管理中确定最左该素断语于哪个产生式的右部

最相似，给出进一步的错误信息。

5 程序框架

开始 读入分析的句型 是 否

是否移进归约 有效？ 是 报错 （error） 解决移进，归约 指针后移 接收的字符串是否为# 还是T

退出程序

6程序清单和程序运行结果

程序清单见磁盘

程序运行结果如下：

1．显示所要分析的文法，并且输入所要分析的句型(以#号结束)：

2.输入所要分析的句型

（1）若所要分析的字符串不为该文法的句型，则有两种出错分析：

例1：若为i－ii#，则出错显示如下：

例2：若为i＋ii＋i#，则出错显示如下：

(2)若正确输入该文法的句型如：i＋i*i+i 则分析结果如下：

(3)选择是否要继续分析，若需要则选Y,若不需要，则选择N，则退出程序。

7实验感想

在完成自顶向下的语法分析之后，接着又开始接触到算符优先的分析法。算符优先的分析法实际上式仿照了算术表达式的运算过程而提出的一种自底而上的语法分析，而作为自底向上分析法的关键就是，在分析的过程中如何确定号句柄，从而判断如何进行移进和归约。

在判断的过程中同时要处理号如何解决出错的问题，这样就可以比较恰当的去了解相关的信息的内容。在做这个实验的过程中，为了检验的方便，首先规定好一个比较熟悉的文法，这样就可以熟练的进行算符优先的定义，同时将他们存放在一定的缓存单元。在解决好基本思想的问题之后，就是要解决界面的问题。因为在学习的过程中，做题都是用相应的表格进行分析处理的，所以这个也是需要进行表格处理的，在分析表格的过程中，栈中空格符的管理也是相当重要的。所以引入了与之相对应的循环队列，从而达到输入空格的控制，使界面友好化。

这个实验最大的收获，不仅仅使让我更进一步的了解到算符优先算法是一个省略了所有单非终结符产生式对应的归约步骤，其分析的效率是非常高的，同时也让我加深了对于表格管理这个语法分析的后端的了解和使用。

7实验感想

在完成自顶向下的语法分析之后，接着又开始接触到算符优先的分析法。算符优先的分析法实际上式仿照了算术表达式的运算过程而提出的一种自底而上的语法分析，而作为自底向上分析法的关键就是，在分析的过程中如何确定号句柄，从而判断如何进行移进和归约。

在判断的过程中同时要处理号如何解决出错的问题，这样就可以比较恰当的去了解相关的信息的内容。在做这个实验的过程中，为了检验的方便，首先规定好一个比较熟悉的文法，这样就可以熟练的进行算符优先的定义，同时将他们存放在一定的缓存单元。在解决好基本思想的问题之后，就是要解决界面的问题。因为在学习的过程中，做题都是用相应的表格进行分析处理的，所以这个也是需要进行表格处理的，在分析表格的过程中，栈中空格符的管理也是相当重要的。所以引入了与之相对应的循环队列，从而达到输入空格的控制，使界面友好化。

这个实验最大的收获，不仅仅使让我更进一步的了解到算符优先算法是一个省略了所有单非终结符产生式对应的归约步骤，其分析的效率是非常高的，同时也让我加深了对于表格管理这个语法分析的后端的了解和使用。

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