编译原理课程设计

二、需求分析

本课程设计的题目为“FirstVT集和LastVT集生成算法模拟”，它是算符优先分析算法中判断三种优先关系的关键。算法优先分析法是一种不太规范的自下向上分析方法，分析速度快，特别适用于表达式的分析。而所谓的自底向上分析法是一种语言形式分析算法.是根据形式文法的重写规则，自叶开始逐级向上归约，直到构造出表示句子结构的整个推导树为止的一种语言形式分析算法。

-第 2 页 -

饶望：FirstVT集和LastVT集生成算法模拟

三、设计思路

Firstvt集：

找Firstvt的三条规则：如果要找A的Firstvt，A的候选式中出现： A->a.......，即以终结符开头，该终结符入Firstvt A->B.......，即以非终结符开头，该非终结符的Firstvt入A的Firstvt

A->Ba.....，即先以非终结符开头，紧跟终结符，则终结符入

为了计算方便，建立一个布尔数组F[m,n]（m为非终结字符的个数，n为终结字符的个数）和一个后进先出栈STACK。将所有的非终结符排序，用iA表示非终结符A的序号，再将所有的终结符排序，用ia表示终结符a的序号。算法的目的是要使数组的一个元素最终取值满足：F[iA,ja]的值为真，当且仅当a属于FirstVT（A）。至此，显然所有的非终结符的FirstVT集已完全确定。

步骤如下：

首先按规则①对每个数组元素附初值。观察这些初值，若F[iA,ia]的值是真，则将（A，a）推入栈中，直至对所有数组的初值都按此处理完。然后对栈做如下运算。

将栈顶项弹出，则令其变为真，且将（A，a）推进栈，如此重复直到栈弹空为止。 Lastvt集：

找Lastvt的三条规则：如果要找A的Lastvt，A的候选式中出现： A->.......a，即以终结符结尾，该终结符入Lastvt A->.......B，即以非终结符结尾，该非终结符的Lastvt入A的Lastvt

A->.....aB，即先以非终结符结尾，前面是终结符，则终结符入Firstvt 数据结构：

布尔数组F[P, a]：F[P, a]为真当且仅当a?LASTVT(P)。开始时，按上述规则(1)对每个数组元素F[P, a]赋初值。

栈STACK：把所有初值为真的数组元素F[P,a]的符号对(P, a)全都放入STACK中。

第 3 页

编译原理课程设计

计算过程：

如果栈STACK不空，就将顶项逐出，记此项为(Q,a)。 对于每个形如 P→Q?

的产生式，若F[P,a]为假，则改变其值为真且将(P,a)推进STACK栈。 上述过程必须一直重复，直至栈STACK拆空为止。

-第 4 页 -

饶望：FirstVT集和LastVT集生成算法模拟

四、详细设计

void main() //主函数 {

int i,j,k=0;

printf(\请输入文法规则数：\ scanf(\

printf(\请输入文法规则：\\n\ for(i=0;i

scanf(\存储文法规则，初始化FIRSTVT集和LASTVT集*/

first[i][0]=0; /*first[i][0]和last[i][0]分别表示st[i][0]非终极

符的FIRSTVT集和LASTVT集中元素的个数*/ last[i][0]=0; }

for(i=0;i

for(j=0;st[i][j]!='\\0';j++) {

if(st[i][0]<'A'||st[i][0]>'Z') {

printf(\不是算符文法!\\n\ exit(-1); }

if(st[i][j]>='A'&&st[i][j]<='Z') {

if(st[i][j+1]>='A'&&st[i][j+1]<='Z') {

printf(\不是算符文法!\\n\ exit(-1); } } } }

for(i=0;i

第 5 页

编译原理课程设计

for(j=0;st[i][j]!='\\0';j++) {

if((st[i][j]<'A'||st[i][j]>'Z')&&st[i][j]!='-'&&st[i][j]!='>'&&st[i][j]!='|')

lable[k++]=st[i][j]; } }

lable[k]='#';

lable[k+1]='\\0'; table();

printf(\每个非终结符的FIRSTVT集为：\\n\符的FIRSTVT集

for(i=0;i

printf(\ for(j=0;j

printf(\ }

printf(\ }

printf(\每个非终结符的LASTVT集为：\\n\的LASTVT集

for(i=0;i

printf(\ for(j=0;j

printf(\ }

printf(\ }

printf(\算符优先分析表如下:\\n\

for(i=0;lable[i]!='\\0';i++) printf(\

printf(\

-第 6 页 -

输出每个非终结输出每个非终结符