实现一个脚本引擎

Part III:语法分析器

序言

前一部分的执行可以作一件很好的工作:把程序转换成记号.所有的关键词,操作符,分隔符,标识符和常量都被立即识别和报告.然而,你可以输入:

{ this ) = "pointless" + ;

然后程序将只是接受它,并且高高兴兴的产生一个记号的列表.因为它不清楚我们想要允许什么东西(我不知道上面的"语句"要做什么).我们必须能够识别输入程序的语法结构(或者它的缺点).

我们借助语法分析器来作这件事,语法分析器用来找出程序的结构并且检查所有的语法错误.

一点语言理论

我们怎么告诉语法分析器我们的语言是什么样呢?我们可以使用一个叫作BNF范式(Backus-Naur Form )的东西来描述语法(syntax或grammar).这种描述方法使用组成程序的基本概念.举例说明,表达式可以是在其他任何东西之中,标识符或者字符串常量(expressions can be, among other things, identifiers or string constants).在BNF范式中,它可以写成下面的形式:

expression: identifier | string;

一个打印语句或者输入语句:

statement
: PRINT expression END_STMT
| INPUT identifier END_STMT
;

(记住PRINT,INPUT和END_STMT都是词法分析器返回的记号)

现在,一个程序可以被表示成下面这种语句列表的方式:

program: | program statement;

上式说明一个程序可以是空或者由程序加上一个语句构成,这里说的语句是一个递归定义,它可以是一串语句(燕良注:这个文法是左递归的).

那么,我们已经用BNF范式定义的语言包含下面的语句:

print a;
(燕良注:这个语句可以使用下面的推导过程:
program: program statement;
program: program statement;(应用产生式  program: 空)
program: PRINT expression END_STMT;(应用产生式 expression: identifier)
program: PRINT identifier END_STMT;
经过词法分析后上面的语句形成的记号流与此式匹配;
以上是最左推导;下面是最右推导
program: program statement;
program: program PRINT expression END_STMT;
program: program PRINT identifier END_STMT;
program: PRINT identifier END_STMT;
根据上述推导可以画出语法树,对于无二义性的文法,所有的推导画出的语法树都是一样的.)
print "Hello";
input name;

Not legal is:

input "Hello";

通过我们的定义,input语句(燕良注:指产生式statement:INPUT identifier END_STMT;)只能作用于一个标识符,而不能是字符串常量.

我们可以使用BNF范式正规的描述我们的语言的整个语法.注意这些现在还不包含语义,于是这条语句:

a = (b == c);

纵使它没有意义它也将被语法分析器接受(我们正在试图把一个布尔值赋给一个字符串变量).语义将在下一阶段作检查.

太好了,我们现在知道的语言描述法足够来建立我们语法分析器.

看上去很熟悉!

语法分析器也可以用一个外部程序来产生.这个叫作Yacc(一个标准的UNIX工具,就像是LEX);我们将使用一个叫作Bison的改良版(get it?).Bison的手册有又可以在这里(http://www.monmouth.com/~wstreett/lex-yacc/lex-yacc.html)找到.Yacc文件(extension .y) 的分段实际上与LEX文件十分的相似.

<说明部分>包括记号的定义,类型信息,还有在前一部分我们看到的yylval共用体.那就是为什么我们使用一个共用体:Yacc使用同一共用体来在两个不同的"语言概念"之间传递信息,例如表达式,语句,程序.根据这些定义,Yacc为我们产生lexsymb.h(实际上它建立的是parse.cpp.h文件,不过parser.bat把它改名了).

就象LEX文件一样,在这部分同样可以在标记"%{"和"%}"之间包含一些初始化代码.在这部分的教程中没有用到这个功能,但还是可以增加一些你需要的附加的代码.

规则是特定的一些BNF范式,用来解释前一部分.

Yacc有一个恶劣的陷阱,那就是你的语言必须使用LR(1)文法描述...这究竟是什么意思在龙之书中有详细的解释(第4.5,关于自下向上分析),LR(1)文法基本的意思是语法分析器还必须能够在查看当前语法记号或者最多预读一个符号就能说出使用什么样的语法规则.下面的语法规则会产生一个移进/归约冲突(shift/reduce conflict).(关于更多的文法理论可以参见最后我加的附注)

A:
| B C
| B C D
| D E F

冲突产生在当你从输入文件中读了一个'B',而预读符号是'C'时,因为他们可以被组合(这两种产生式最终都将产生一个文法符号);问题是第2个产生式以'D'为结尾,而且第3个以它我起始:当语法分析器读取到了'C',而且预读的是'D'时,它不能决定是否归类为A2或A1后面跟着一个A3(燕良注:请注意我们只预读一个文法符号)!尽管这个完整的文法定义可能根本就没有二义性,但是对于语法分析器它却是有的,因为语法分析器只能预读一个文法符号.Yacc把这种不确定性称为移进/归约冲突或归约/归约冲突.

呵呵,别让这些吓着你.看一下这些规则.最重要的一条可能就是这条语句规则了:

你能看到,这里定义了我们的语言所有的语句类型,后面的代码是告诉语法分析器当发现了每个产生式时应该作什么.我认为这条规则是十分漂亮的.有一件事:"Errorstatement"告诉Yacc当分析一条语句时如果它遇到了一个语法错误后应该作什么(例如一个非法的记号或者一个不合时宜的记号).在这种情况下它会查找下一个END_STMT记号,然后继续分析后面的东西.语法错误会始终报告到在main.cpp中定义的yyerror()函数,所以我们的编译器会使用一个恰当的方法来处理它.如果在你的.y文件中没有提供任何一个错误规则,那么你的语法分析器遇到语法错误就会定下来,这可不是很好.

也许你在奇怪为什么会有这么多的表达式规则呢:expression, equal_expression, assign_expression, concat_expression 和 simple_expression.这是为了描述操作符的优先级.如果语法分析器看到了这个:

if (a == b + c)

它应该知道它不应该先计算a==b然后试着把这个布尔值计算结果与一个字符串变量c相加(燕良注:这里的侧重点不是数据类型,而是算符的优先级).这些不同的表达式规则确定了唯一的语句的语法分析方法.花点时间好好看看它;它能够工作.

另外一个问题是当分析下面的语句时:

if (a == b) if (c == d) e = f; else g = h;

语法分析器不知道else属于那个if语句(内层的还是外层的);它可以认为你的意思是:

if (a == b) {if (c == d) e = f;} else g = h;

但是作为一个所有语言都遵循的惯例,else与内层的if匹配.

因为没有办法通过改变我们的规则来解决这个问题,Yacc将会报告一个移进/归约冲突.这个冲突可以简单的在说明部分加上这行来禁止:

%expect 1

这意味这Yacc应该预期冲突1(Yacc should expect 1 conflict).Yacc将把else与最近的if配对,正象我们想要的那样.这就是它发现任何冲突的默认的解决方法.

一旦你理解了BNF范式,Yacc文件是非常的不解自明的.如果你还有什么不清楚的地方,你可以给我来mail或者在messageboard上提出问题.

Yacc的源文件可以使用这条命令来编译:

bison --defines --verbose -o parse.cpp

如果你得出了什么冲突,看一下输出的parse.cpp文件,那里包含冲动的细节(即使没有错误,那仍然是一个有趣的文件).如果你陷入了任何不能解决的冲突,可能把你的.y文件发给我,我会看一下的.

如果每件事都OK了(在样例代码中应该是这样的),那你在parse.cpp中就得到了一个可工作的语法分析器.我们的主程序要做的就是调用yyparse()函数,这个输入文件就会按我们的要求处理了.

再试试example.str文件,然后看一下它产生的错误.错误?是的,没错,我在第13行最后忘了一个';'.呵呵,它很棒吧?

Whew!

今天我们作了很多事.我们学习了一些形式语言理论,如何使用Yacc,为什么Yacc对它支持的文法如此的挑剔,如何描述操作符的优先级.在最后,我们制作了一个可以工作的语法分析器.

好吧,我想最难的部分就在后面.如果你理解了这些,休息一下吧.然而,我在LR(1)文法上忽略了很多.给我来信或者发到messageboard让我来澄清那些问题.欢迎任何的问题和评论,让我知道有人在读这些东西.

下面是什么呢?下次我们大概要写两个新的组件:符号表和语法树.到那之后,你有一周来试验这些代码.提示:试着找到一个接受C风格的while语句的编译器.

Quote!

"The major problem is quite simply one of grammar, and the main work to consult in this matter is Dr Dan Streetmentioner's Time Traveller's Handbook of 1001 Tense Formations. It will tell you for instance how to describe something that was about to happen to you in the past before you avoided it by time-jumping forward two days in order to avoid it. The event will be described differently according to whether you are talking about it from the standpoint of your own natural time, from a time in the further future, or a time in the further past and is further complicated by the possibility of conducting conversations whilst you are actually travelling from one time to another with the intention of becoming your own father or mother."

HHG 2:18

Downloads

Download the tutorial code (tut3.zip) (5k)

燕良的附注:说明一下文中的几个名词

• 关于BNF范式
  文中的
  expression: identifier | string;
  可以读作expression定义为identifier或string.
  这个式子包括两个产生式.
• 关于LR(1)分析原文中提到的不多,所以在这里补充一下.但是完整的语法分析理论恐怕您还是要找本书来看.不过,如果只是想使用工具的话我想看了原文和这里的补充应该差不多了.
  LR(1)分析是自下向上分析的一种,自下向上的分析实际上是最右推导的逆过程,名字中的'L'表示自左向右读入记号,'R'表示最后推导,'1'表示预读一个记号.
  实际上LR(1)分析也好,LL(1)等等各种分析也好,其最终目的都是得出一个状态矩阵.通过这个矩阵程序才能知道下一步该怎么作,动作主要有两种,一是移进,即读入下一记号,二是归约,就是用产生式的左部来代替产生式的右部,其中如果是规约,还要说明用那个产生式归约.
  验证文法的LR(1)性是一件比较复杂的事.本文只讲实现不讲设计,其实设计出好的文法我觉得很有挑战性.:P
• 这篇文章还是挺不错的,语法中的两个难点:操作符优先级和if-else问题都提到了.这是应该注意的地方.