从lex&yacc说到编译器(4.文法识别(一))
作者:tangl_99
QQ:8664220
email:tangl_99@sohu.com
没想到这一系列文件能得到csdn和大家的这么看好,首先要感谢大家的赏识和csdn的推荐.那么我就更没有理由不写好这下面的几篇文章了.本来我的计划是简单把lex和yacc介绍完后就直接进入编译器的构造的技术细节问题讨论,但是最近看了一些国外经典教材后,发现文法的识别问题在编译原理和技术中是个绝不能忽视的问题.即使现在有了yacc工具来帮助我来识别文法,但是有些时候还是需要我们自己来写简单的语法分析器.
1.什么是文法识别(语法分析)
首先要告诉大家的是,这里的文法识别是指的上下文无关的文法,也就是上一节我们一直在讨论的那些 BNF式.
比如说,我写了一句
if (a>6+5) printf(“OK!”); else printf(“No!”);
那么它匹配的文法也就是
if-stmt -> if expr stmt
| if expr stmt else stmt
我们通常要为一个程序语言写出很多BNF式的文法,怎么知道这句话是匹配的哪个文法,这就是语法分析器(或者叫文法分析器要做的工作).知道了是那句文法后,我们才能对这句话做出正确的解释,所以文法识别是个不可忽视的工作.下面我来看看我们常使用的文法识别的算法.
2.自顶向下的算法(LL算法)
自顶向下的语法分析算法是十分简单的.自顶向下的算法也叫LL算法.LL(k)就是向前预测k个符号的自顶向下的算法.不过无论是我们国内的编译教程还是国外的经典教程都是只讨论了LL(1)算法.因为一般的程序语言,只使用LL(1)算法就已经足够了.这里我们同样也只是讨论LL(1)算法.
其中有种特殊的算法叫做递归下降的算法,在C语言中,由于函数本身是可以递归的,所以实现这种算法就只需要写简单的几个函数的递归过程就是了.
为什么叫自顶向下呢?因为在分析过程中,我们是从语法树的树顶逐步向树底分析的,所以叫自顶向下的算法.
为了方便说明自顶向下算法的简单性,我们来看一下<<Compilers Principles,Techniques,and Tools>>中的一个例子.(本系列文章经常要引用国外经典著作的范例,希望大家不要告我抄袭,我实在找不到比大师的范例更经典的范例了)
例4.1
考虑一个Pascal中定义变量的文法.
特别说明,这里的dotdot表示”..”
type -> simple | id | array [ simple ] of type
simple -> integer | char | num dotdot num
在为array[ num dotdot num] of integer构造一个分析数的时候,该算法就是从根结点开始.
下面我们通过其中主要的三个步骤来看看算法的实现原理.
第一步分析:
__________________________________________________________________________________
首先分析的是输入的字符串第一个串”array”,判断出它属于type的First集合.所以在图中的分析树部分,我们的当前分析就是树根结点type.(图中标上箭头,就表示是当前正在分析的部分).
这里遇到一个新名词:First集合.在大学里的编译课程肯定是讲过First集合的吧.不过我还是要在这里重复一次了.
名词解释First集合:
在对文法产生式进行判断的时候,每个产生式都是由好几个终结符和非终结符构成.比如
本例中的文法
type -> simple
| id
| array [ simple ] of type
simple -> integer
| char
| num dotdot num
判断type的产生式的时候,如果我们把每个产生式里面的simple,id,array, [ ,simple ,] , of , type这些终结符和非终结符都进行判断的话,那么就会涉及到”试验和错误”的问题.当一个文法产生式分析到最后,发现并不匹配,就必然会产生回溯的问题,就要回到头,从新开始对第二个产生式逐步进行判断分析.我们知道,回溯的算法效率肯定是十分低效率的.但是实际上我们完全可以避免这种回溯算法,而完成同样工作的文法分析.这就产生了计算First集合的理论和以及后面的左提公因式的问题.
First集合简单地说,就是一个非终结符的最开头的字符串(终结符号)的集合.比如说.
First(simple) = { integer, char, num }
First(type) = First(simple) U { id, array }
这里的type的一个产生式中有个simple非终结符在其开头,那么simple的开头字符串同时也可以是simple,所以First(simple)也是First(type)的一部分.
为什么我们只计算每个非终结符的最开头的终结符? 因为我们这里是考虑的LL(1)算法,LL(1)算法只向前预测一个字符号,所以我们只考虑一个First集合就可以判断出是哪个文法产生式了.
这里听起来似乎有些不太可能,一个产生式有那么千百万化,如果单单只看第一个非终结符号,如果就能说明一个输入串到底是哪个产生式呢? 如果有两个产生式的最开头一样怎么办,比如像if语句,那怎么办? 但其实我们几乎所有的程序语言的文法都可以通过LL(1)来分析出来.原因是我们可以通过左提公因式来把最开头的相同的产生式的公共终结符号提取出来,留下两个子产生式,而他们的最开头的非终结符号不相同.
左提公因式:
例4.2
考虑文法
A -> ab
|ac
这里,A的两个产生式中最开头的终结符号都是’a’,那么就无法通过这个最开头的终结符号来判断一个输入串到底该是哪个产生式了.那么我们可以修改文法成
A -> aA’
A’-> b | c
这样一来,一个文法变成两个,但是无论A还是A’,它们的每个产生式的First集合都是不相交的.所以,他们能够只通过最开头的终结符号来判断是哪个产生式.
这个变化过程有点想我们的代数里面的 ab + ac = a(b+c),所以叫它左提公因式.
这只是个简单的左提公因式的例子,实际当中还会遇到一些复杂的问题.但是无论是哪个编译教材,都会给出针对一切文法的左提公因式的算法.同样,计算First集合的算法也在教材中详细讲解了.我就不在这里再描述了.
第二步分析:
__________________________________________________________________________________
经过第一步的考察输入串中的第一个串为”array”属于非终结符号type第三个产生式的First集合,那么就可以确定这个串确实为type文法第三个产生式的串.所以在第二步中,展开出type的第三个产生式出来. type -> array [ simple ] of integer
那么接下来就是继续分析构造出来的type -> array[ simple] of integer产生式中的每个结点.
所以箭头又放到了分析树中type的第一个孩结点array上.因为array是终结符号,如果它和输入中的当前箭头所指的终结符号相同,那么箭头都往下移动一结点到’[‘符号.同样地,由于分析树中的’[‘是终结符号,那么只要看输入中的串是否是’[‘就可以了.如果是,那么继续往下分析.分析到分析数中的simple的时候,由于simple是非终结符号,那么就需要考虑simple的产生式了.
第三步分析:
__________________________________________________________________________________
在第二步中,分析到分析数中的simple子结点的时候,由于simple是非终结符号,那么就需要考虑simple的产生式.simple一共有三个产生式.通过输入串当前的串是”num”,是属于simple产生式中第3个产生式的First集合,所以simple在分析数中就按第三个产生式simple -> num dotdot num 来展开.那么分析箭头同样,也自动移动到simple的第一个子结点num上继续分析.
总体说来,这中自顶向下的分析原理就基本上是上面的过程.通过计算产生式的First集合,来逐步产生非终结符的产生式.最后的分析树都会划归到终结符来进行判断(非终结符号是无法进行直接判断的,一定要展开过后才行).
看了原理,我们再看实现的伪代码.代码很简单.
________________________________________________________________________
void match(char token)
{
if lookahead == token)
lookahead = token;
else
error(0);
}
void type()
{
if( lookahead == integer || lookeahead == char || lookahead == num)
simple();
else if( lookahead == id)
match(id);
else if( lookahead == array)
{
match(array); match(')'); simple(); match(')'); match(of); type();
}
else
error(0);
}
void simple()
{
if( lookahead == integar) match(integer);
else if( lookahead == char) match(char);
else if( lookahead == num)
{
match(num); match(dotdot); match(num);
}
else
error(0);
}
_________________________________________________________________________
注意:这里的代码都是纯的语法分析代码,实际执行过程中并没有什么用处,但是我们构造语法树parse-tree的代码就是镶嵌在这些纯的语法分析代码中.
2003-10-23
成都,四川大学
