算符优先文法的编程实现_怎样将一个非算符优先文法改造成算符优先文法

实验三 算符优先文法的编程实现

一、实验目的

1. 通过本次实验，加深对移进规约分析法中算符优先法的理解；

2. 学习程序设计语言的语法分析器的手工编程方法。

 

二、实验内容

1. 对于任意给定的文法，判断其是否是算符优先文法。

2. 通过语法分析，生成抽象语法树，在此基础上设计并实现一个简单的计算器。

 

三、实验原理

1. 自底向上优先分析方法

也称移进-归约分析，粗略地说它的思想是对输入符号串自左向右进行扫描，并将输入符号逐个移入一个后进先出栈，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可归约串时，就将该产生式的左部非终极符代替相应的右边文法符号串。

2. 算符优先分析

依照算术表达式的四则运算过程来进行语法分析，即这种分析方法要预先规定运算符(确切地说是终结符)之间的优先关系和结合性质，然后借助于这种关系来比较相邻运算符的优先级，以确定句型的“可归约串”来进行归约。

因此，算符优先分析法不是一种规范归约，在整个归约过程中起决定性作用的是相继两个终结符的优先关系。

3. 算符优先文法

首先定义一个任何产生式的右部都不含两个相继(并列)的非终结符的文法为算符文法，即算符优先文法首先应是一个算符文法；其次，还要定义任何两个可能相继出现的终结符a与b (它们之间最多插有一个非终结符)的优先关系。

4. 终结符号间优先关系的确定，用FIRSTVT集和LASTVT集计算。

 FIRSTVT集:

(1) 若有产生式P→a…或P→Qa…，则a∈FIRSTVT(P);

(2) 若a∈FIRSTVT(Q)，且产生式P→Q…，则a∈FIRSTVT(P)。

LASTVT集：

(1)    若有产生式P→…a或P→…aQ，则a∈LASTVT(P)；

(2)    若a∈LASTVT(Q)，且P→…Q，则a∈LASTVT(P)。

 

四、算法思想

1.根据所输入文法规则，求文法中每个非终结符的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