基于ＶＣ＋＋平台的ＬＬ（１）语法分析器的设计

崔　蕊　徐安凤

摘要:文章讨论了LL(1)语法分析器的工作原理和过程,以具体实例说明语法定义、造表和总控程序的实现过程。

关键词:编译原理;自上而下语法分析;预测分析

中图分类号:TP314文献标识码:A

文章编号:1674-1145(2009)23-0133-01

编译程序能够将软件语言书写的各种程序处理成可在计算机上执行的程序,是重要的系统软件。在编译系统中,语法分析阶段是整个编译过程中继词法分析后的第二个阶段。按照建立语法分析树的方法,语法分析分为两类:自上而下分析和自下而上分析。本文讨论的预测分析法属于自上而下的方法。

一、语法规则的表示

语法规则是由上下文无关文法进行定义的。例如一个语言可用一系列的产生式定义:<程序>-> begin <语句串> end <语句串> -> <语句><;<语句串>> 等等,为了方便问题描述,把实际含义用符号进行抽象,本文讨论的例子就是抽象后的符号表示的。本文所讨论的预测分析自上而下语法分析式由初始符号出发,利用产生式不断推导,实际就是从左到右扫描符号串,模拟句子推导的过程。因此文法必必须为满足推导条件的LL(1)文法。LL(1)文法的条件是:(1)文法不含左递归;(2)每个非终结符号的各个产生式的候选首字符集两两不相交;(3)每个非终结符号的候选首字符集包含空,则首字符集和跟随字符集的交集为空。具体可查看LL(1)文法的相关知识。本文的文法如下(是LL(1)文法):E->T EE->+TE|ε T->FTT->*FT|εF->(E)|I

其中大写字母为非终极符号,E为初始符,其他为终结符号。

二、构造文法中个非终结符号的FIRST集和FOLLOW集

FIRSTFOLLOW

E->T E (i ) #

E->+TE + ) #

ε ε

T->FT (i +)#

T->*FT * +)#

ε ε

F->(E) ( *+)#

i i

三、构造预测分析表

造表规则为:(1)若A->ri|…|rma∈FIRST(ri) M[A,a]=A->ri;(2)rj->εa∈FLLOW(A) 则M[A,a]=A->rj;(3)除(1)(2)外出错。

四、LL(1)语法分析器实现

1.语法分析器的逻辑结构

2.工作流程:从左到右,模拟推导过程

(1)#开始符号进栈

(2)设当前状态为

(3)Xm与ai对话

情况1:Xm=ai!= #Xm出栈,输入串的指针右移一位。

情况2:Xm∈VN,查表M[Xm,ai]= Xm->UVW,Xm退栈,按WVU顺序进栈(最左侧在栈顶)输入串指针不变。

情况3:Xm=ai= # 成功。

其他情况出错。

3.总控程序算法

开始符号压栈

While(栈顶符!=# &&下一个输入符!=#)

{If(栈顶符号==下一个输入符)

{ 栈内弹出栈顶符;

读下一个字符;

}

else if(栈顶符号是非终结符A&&下一个a)

{ 查表M[A,a]->X1X2…Xn;

栈顶元素出栈;

Xn…X2X1进栈;

}

else error;

}

If(栈顶符==# &&下一个输入符==#)

Accept;

Else error;

参考文献

[1]陈火旺,刘春林,谭庆平,等.程序设计语言编译原理[M].国防工业出版社,2002.

[2]陈意云,张昱.编译原理[M].北京:高等教育出版社,2003.