算符优先分析法设计与实现

算符优先分析法设计与实现

一、实验目的

加深对语法分析器工作过程的理解；加强对算符优先分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。

二、实验内容

在实验1的基础上，用算符优先分析法编制语法分析程序，语法分析程序的实现可以采用任何一种编程语言和工具。

三、实验要求：

1. 对语法规则有明确的定义；

2. 编写的分析程序能够对实验一的结果进行正确的语法分析；

3. 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；

四、实验步骤

1. 定义目标语言的语法规则；

2. 求解预测分析方法需要的符号集和分析表；

3. 依次读入实验一的分析结果，根据预测分析的方法进行语法分析，直到源程序结束；

4. 对遇到的语法错误做出错误处理。

五、实验报告要求

详细说明你的程序的设计思路和实现过程。实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作过程，说明错误处理的实现。

算符优先分析器（综合性实验）

一、实验目的

掌握 FirstVT和 LastVT集的算法，算符优先分析表的构造算法及其分析过程，并掌握中间代码产生过程。

二、实验内容

算术表达式和赋值语句的文法可以是（可以根据需要适当改变）：

S→i=E

E→E+T

E→E-T

E→T

T→T*F

T→T/F

T→F

F→(E)

F→i

根据算符优先分析法，将赋值语句进行语法语义分析，翻译成等价的一组基本操作，每一基本操作用四元式表示。

三、实验过程和指导

1、构造FirstVT和LastVT集合

给定一个上下文无关文法，根据算法设计一个程序，求文法中每个非终结符的 FirstVT 集和LastVT 集。

算符描述如下：

/*求 FirstVT 集的算法*/

PROCEDURE insert(P,a);

IF not F[P,a] then

begin

f[p,a] = true; (P,a)进栈

end;

Procedure FirstVT;

Begin

for 对每个非终结符 P和终结符 a do

F[P,a] = false

for 对每个形如 P→a…或 P→Qa…的产生式 do

Insert(P,a)

while stack 非空

begin

栈顶项出栈，记为(Q,a)

for 对每条形如 P→Q…的产生式 do

insert(P,a)

end;

end.

2、构造算符优先分析表

依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。

算法描述如下：

for 每个形如 P->X1X2…Xn的产生式 do

for i =1 to n-1 do

begin

if Xi和 Xi+1都是终结符 then

Xi = Xi+1

if i<= n-2, Xi和 Xi+2 是终结符, 但 Xi+1 为非终结符 then

Xi = Xi+2

if Xi为终结符, Xi+1为非终结符 then

for FirstVT 中的每个元素 a do

Xi < a ;

if Xi为非终结符, Xi+1为终结符 then

for LastVT 中的每个元素 a do

a > Xi+1 ;

end;

3、构造算符优先分析和中间代码产生过程。

四、输入数据和输出数据

若输入文法：

E->E+T | T

T->T*F | F

F-> (E) | i

将得到如下所示的 FirstVT 集和LastVT数组。

输出的优先关系表如下：

若输入的语句是

a:=b+c*(e-a)

则输出：

(-，e,a,T1)

(*,c,T1,T2)

(+,b,T2,T3)

(:=,T3,_,a)

算符优先文法处理

一、实验目的

掌握算符优先分析法的原理，利用算符优先分析法将赋值语句进行语法分析，翻译成等价的四元式表示。

二、实验内容：

1.算术表达式的文法可以是（你可以根据需要适当改变）：

E→E+E|E-E|E*E|E/E|（E）|i

2.根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确。

3.将赋值语句进行语法分析，翻译成等价的一组基本操作，每一基本操作用四元式表示。

三、实验预习提示

1.实验原理

我们要分析的表达式满足下面的算符优先矩阵

θ2\\θ1 + - * / ( ) ε

+ > > < < < > >

- > > < < < > >

* > > > > < > >

/ > > > > < > >

( < < < < < =

) > > > > > >

ε < < < < < =

为实现算符优先算法，可以使用两个工作栈。一个叫做OPTR，用以寄存运算符，一个叫OPND,用以寄存操作数或结果。算法描述如下：

[1]首先置操作数栈为空栈，将表达式起始符;作为运算符栈的栈底元素。

[2]依次读入表达式中每个单词，若是操作数则进OPND栈，若是运算符则转[3]。

[3]将此运算符θ1与OPTR栈顶元素θ2进行比较，即查上表，若 θ1＞θ2，则：θ1进栈，转[2]

若 θ1＝θ2 ,如θ1为；，则分析成功，否则OPTR栈顶元素出栈，并转[2]

若 θ1<θ2,则出栈OPND栈顶元素至b，又出栈其栈顶元素至a，出栈OPTR栈顶元素至t，进行运算r=a t b(t 为运算符)，并将结果r存入栈OPND后转[3]。

若θ1和θ2之间无优先关系，则报错。

四、实验步骤

（一)准备：

1. 阅读课本有关章节，花一周时间确定算术表达式的文法，设计出算符优先关系表；

2.考虑好设计方案；

3. 设计出模块结构、测试数据，初步编制好程序。

(二)上课上机：上机调试，发现错误，分析错误，再修改完善。教师根据学生的设计方案与学生进行探讨，以修改方案和代码。

(三）程序要求：

程序思路（仅供参考）：

1.借用实验一的结果，可将其中的取字符函数几乎原封不动地移植过来，其中的分割和分析单词的方法可借用过来分割现在这个实验的运算符、常量和变量。

2.模块结构：（1）初始化：设立算符优先关系表（或优先函数）、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（2）控制部分：将一个表达式从文件中读出；（3）词法分析：将表达式分割成单词序列；（4）利用算符优先文法进行表达式处理：根据算符优先关系表（或优先函数）对表达式单词序列进行堆栈（或其他）操作，得到并保存四元组，如果遇到错误则显示错误信息；（5）输出四元组。

3.程序输入/输出示例：

如参考C语言的运算符。输入如下表达式（以分号为结束）和输出结果：

（1）10;

输出：正确

（2）1+2;

输出：正确

（3）(1+2)/3+4-(5+6/7);

输出：正确

（4）((1-2)/3+4

输出：错误

（5）1+2-3+(*4/5)

输出：错误

注意：1.为降低难度，表达式中不含变量（只含无符号整数）；

2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；

3.测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；

4.对学有余力的同学，可增加功能：当判断一个表达式正确时，输出计算结果，计算过程用浮点表示，但要注意不要被0除。