从lex&yacc说到编译器 [转]

作者:tangl_99 
QQ:8664220 
msn:tangl_99@hotmail.com 
email:tangl_99@sohu.com 

从lex&yacc说到编译器

一、正则表达式

学过编译原理的朋友肯定都接触过LEX这个小型的词法扫描工具. 但是却很少有人真正把LEX用在自己的程序里. 在构造专业的编译器的时候,常常需要使用到lex和yacc. 正是因为这两个工具,使得我们编写编译器,解释器等工具的时候工作变得非常简单.不过话说回来,会使用lex和yacc的人也确实不简单. Lex和yacc里面牵涉到一系列的编译原理的理论知识,不是简单地看看书就能搞懂的. 本文只是简单地介绍一下lex和yacc的使用方法.相关编译理请查看本科教材. 

国内大学教材里面对于lex和yacc的介绍很少,有些根本就没有,不过在国外的编译原理教材介绍了很多. 按照学科的分类,国内大学本科里面开的<<编译原理>>教程只是讲解编译的原理,并不讲解实践. 而对于实践方面则是另外一门学科<<编译技术>>. 关于编译技术的书籍在国内是少之又少. 前不久, 听说上海交大的计科内部出版过编译技术的教材.可惜我们这些人就无法得见了. 还好,机械工业出版社引进了美国 Kenneth C.Louden所著的经典著作<<编译原理及实践>>中,比较详细地介绍lex和yacc的使用. 

Lex属于GNU内部的工具,它通常都是gcc的附带工具. 如果你使用的Linux操作系统,那么肯定系统本身就有lex和yacc,不过yacc的名字变成了bison. 如果你使用的Windows操作系统,那么可以到cygwin或者GNUPro里面找得到. 网上也有windows版本lex和yacc,大家可以自己去找一找. 

本文一共有两篇,一篇是介绍lex,另一篇是介绍yacc. Lex和yacc搭配使用, 我们构造自己的编译器或者解释器就如同儿戏. 所以我把本文的名字叫做黄金组合. 

本文以flex( Fase Lex)为例,两讲解如何构造扫描程序. 
Flex可以通过一个输入文件,然后生成扫描器的C源代码. 

其实扫描程序并不只用于编译器 .比如编写游戏的脚本引擎的时候,我看到很多开发者都是自己写的扫描器,其算法相当落后(完全没有DFA的概念化), 甚至很多脚本引擎开发者的词法扫描器都没有编写,而是在运行过程中寻找token(单词). 在现代的计算机速度确实可以上小型的脚本引擎在运行中进行词法扫描, 但是作为一个合格的程序员, 或者说一个合格的计算机本科毕业生而来说, 能够运用编译原理与技术实践,应该是个基本要求. 

如果要说到词法分析的扫描器源代码编写, 其实也很简单, 会C语言的人都会写. 可是Kenneth Louden在<<编译原理及技术>里面,花了50多页,原因就是从理论角度,介绍标准的,可扩展的,高效的词法扫描器的编写. 里面从正则表达式介绍到DFA(有穷自动机),再到NFA(非确定性有穷自动机),最后才到代码的编写. 以自动机原理编译扫描器的方法基本上就是现在词法扫描器的标准方法, 也就是Lex使用的方法. 在Lex中,我们甚至不需要自己构造词法的DFA, 我们只需要把相应的正则表达式输入, 然后lex能够为我们自己生成DFA,然后生成源代码,可谓方便之极. 

本文不讲DFA, lex的输入是正则表达式, 我们直接先看看正则表达式方面知识就可以了. 

1.正则表达式(regular expression): 

对于学过编译原理的朋友来说,这一节完全可以不看.不过有些东西还是得注意一下,因为在flex中的正则表达式的使用有些具体的问题是在我们的课本上没有说明的. 
先看看例子: 
例1.1 
name Tangl_99 
这就是定义了name这个正则表达式,它就等于字符串Tangl_99.所以,如果你的源程序中出现了Tangl_99这个字符传,那么它就等于出现一次name正则表达式. 

例1.2 
digit 0|1|2|3|4|5|6|7|8|9 
这个表达式就是说,正则表达式digit就是0,1,2,…,9中的某一个字母.所以无论是0,2,或者是9…都是属于digit这个正则表达式的. 
“|”符号表示”或者”的意思. 
那么定义正则表达式 name Tangl_99|Running,同样的,如果你的源程序中出现了Tangl_99或者Running,那么就等于出现了一次name正则表达式. 

例1.3 
one 1* 
“*”符号表示”零到无限次重复” 
那么one所表示的字符串就可以是空串(什么字符都没有), 1, 11, 111, 11111, 11111111111, 11111111…等等.总之,one就是由0个或者N个1所组成(N可以为任意自然数). 
与”*”相同的有个”+”符号.请看下面的例子1.4 

例1.4 
realone 1+ 
“+”符号表示”1到无限次重复” 
那么realone和one不同的唯一一点就是,realone不包含空串,因为”+”表示至少一次重复,那么realone至少有一个1.所以realone所表达的字符串就是1,11,111, 1111, 11111…,等等. 

例1.5 
digit [0-9] 
letter [a-zA-Z] 
这里的digit等于例1.2中的digit,也就是说,a|b|c就相当于[a-c]. 
同理,letter也就是相当于 a|b|c|d|e|f|…|y|z|A|B|C|D…|Z 不过注意的一点就是,你不能把letter写成[A-z],而必须大写和小写都应该各自写出来. 

例1.6 
notA [^A] 
“^”表示非,也就是除了这个字符以外的所有字符 
所以notA表示的就是除了A以外的所有字符. 
下面让我们来看看一些一般高级程序语言中常用的综合例子. 
digit [0-9] 
number {digit}+ 
letter [a-zA-Z_] 
digit前面多次提起过,就是0-9的阿拉伯数字.number就是所有的数字组合,也就是整数. 
Letter前面也提起过,唯一不同的就是多了一个下划线.因为一般我们的C语言中容许有下划线来表示定义的变量名,所以我也把下划线当成英语字母来处理了. 
这里number中使用上面定义的digit正则表达式.在lex中,用{digit}就是表示正则表达式digit. 

newline [\n] 
whitespace [ \t]+ 
newline就是提行的意思.这里我们使用的是\n这个符号,它和C语言中表示提行号一致.问题是大家可能要问到为什么要使用[]符号.因为在lex中,如果你使用[],那么里面表示的肯定就是单个字符号,而不会被理解成”\”和”n”两个字符. 
Whitespace就是空格符号的意思.一般的高级程序语言中有两种,一种就是简单的空格,还有一种就是\t制表符.使用了”+”符号,就表示了这些空白符号的无限组合. 


二、flex的使用

看了第一篇的关于正则表达式的说明后,下面我们就来通过它,使用flex这个词法分析工具来构造我们的编译器的词法分析器. 

关于lex的教程应该是很多,这里我就简单地介绍一下,然后着重后面的lex和yacc的配合使用以及其技巧.所以,如果你不看了后还是不太明白lex或者yacc的使用,请你自己上网去查查,这方面的教程是很多的.我知道的一篇常见的就是 

Yacc 与 Lex 快速入门 
Lex 与 Yacc 介绍 

它的作者就是Ashish Bansal. 



Flex就是fast lex的意思.而lex就是Lexical Analyzar的意思.flex可以在cygwin或者gnupro中找到.它是unix的一个工具,属于GNU组织产品.网上也可以找到单独可以在windows下用的版本. 

我们一般把我们的词法扫描程序要扫描的一些单词(token)用正则表达式写好,然后作为lex的输入文件,输入命令flex xxx.l(xxx.l就是输入文件),lex经过处理后,就能得到一个名字叫lex.yy.c的C源代码.这个C源代码文件,就是我们的词法扫描程序.通常lex为我们生成的词法分析器的C源代码都是十分复杂而且庞大的,我们一般根本不会去查看里面的代码(放心好了,flex这个东西不会出错的) 

下面让我们看看几个我已经使用过的几个lex输入文件. 

这是一个前段时间我为GBA上的一个RPG游戏写的脚本引擎所使用的lex输入文件(部分) 

例2.1 

%{ 

/* need this for the call to atof() below */ 

#include 

#include 

#include 

#include "globals.h" 

%} 

digit [0-9] 

number ("-"|"+"?{digit}+ 

hexnumber "0x"({digit}|[a-fA-F])+ 

letter [a-zA-Z] 

identifier ({letter}|_)({number}|{letter}|_)* 

newline [\n] 

whitespace [ \t]+ 

string \"[^"]*\" 

comment "#"[^#]*"#" 

%% 

{string} { return VM_STRING; } 

"Logo" { return VMIN_LOGO; } 

"FaceIn" { return VMIN_FACEIN; } 

"FaceOut" { return VMIN_FACEOUT; } 

"LoadTile" { return VMIN_LOAD_TILE; } 

"CreateRole" { return VMIN_CREATE_ROLE; } 

"ReleaseRole" { return VMIN_RELEASE_ROLE;} 

"CreateMap" { return VMIN_CREATE_MAP; } 

"ReleaseMAP" { return VMIN_RELEASE_MAP;} 

"ShowBitmap" { return VMIN_SHOWBITMAP; } 

"CreateDialog" { return VMIN_CREATE_DIALOG; } 

"ReleaseDialog" { return VMIN_RELEASE_DIALOG;} 

"Fight" { return VMIN_FIGHT; } 

"Delay" { return VMIN_DELAY; } 

"PressA" { return VMIN_PRESS_A; } 

"PressB" { return VMIN_PRESS_B; } 

"PressR" { return VMIN_PRESS_R; } 

"PressL" { return VMIN_PRESS_L; } 

"PressStart" { return VMIN_PRESS_START; } 

"PressSelect" { return VMIN_PRESS_SELECT;} 

{number} { return VM_NUMBER; } 

{whitespace} { /* skip whitespace */ } 

{identifier} { return VM_ID; } 

{newline} ; 

. ; 

%% 

int yywrap() 

{ 

return 1; 

} 

这里的lex输入文件一共有三个部分,用%%分开.第一部分中的%{和}%中的内容就是直接放在lex输出C代码中的顶部.我们通过它可以来定义一些所需要的宏,函数和include一些头文件等等.我的这个lex输入文件中也没什么特别的东西,就是常规的C源文件的include头文件 

%{ 

/* need this for the call to atof() below */ 

#include 

#include 

#include 

#include "globals.h" 

%} 

第一部分中,除了前面的%{和}%包含的部分,下面的就是正则表达式的定义. 

看了第一篇的正则表达式,这样你就能够在这里派上用场了. 

让我们来看看我这里定义的正则表达式: 

digit [0-9] 

number ("-"|"+"?{digit}+ 

hexnumber "0x"({digit}|[a-fA-F])+ 

letter [a-zA-Z] 

identifier ({letter}|_)({number}|{letter}|_)* 

newline [\n] 

whitespace [ \t]+ 

string \"[^"]*\" 

comment "#"[^#]*"#" 

digit就不用说了,就是0-9的阿拉伯数字定义,第一篇文章中也举了这个例子.number就是digit的1到无限次的重复,再在其前面加上”+”和”-“符号. 

注意: 

“a”: 即使a是元字符,它仍是字符a 

\a: 当a是元字符时候,为字符a 

a?: 一个可选的a,也就是说可以是a,也可以没有a 

a|b: a或b 

(a): a本身 

[abc]: 字符a,b或c中的任一个 

[a-d]: a,b,d或者d中的任一个 

[^ab]: 除了a或b外的任何一个字符 

.: 除了新行之外的任一个字符 

{xxx}: 名字xxx表示的正则表达式 

这里需要特别说明的就是 

newline [\n] 

newline就是新行,这里我使用了[]把\n换行号括起来.因为如果我直接用\n表示的话,那么按照上面的规则,那就会看成\和n两个字符,所以我使用了[\n].有些时候newline也被写成[\n]|[\r\n].因为在文本文件中,一般换行一次,那么就是一个\n(0xA),可是在二进制文件中,换行有时候又是\r\n(0xD,0xA)一共两个字符号. 

第二部分就是定义扫描到正则表达式的动作. 

这些动作其实就是C代码,它们将会被镶嵌在lex输出的C文件中的yylex()函数中. 

上面的例子的动作其实十分平常,就是返回一个值. 

我们在外部使用这个lex为我们生成C代码的时候,只需要使用它的int yylex()函数.当我们使用一次yylex(),那么就会自动去扫描一个匹配的正则表达式,然后完成它相应的动作.这里的动作都是返回一值,那么yylex就会返回这个值.通常默认yylex返回0时候,表示文件扫描结束,所以你的动作中最好不要返回0,以免发生冲突.当然,动作中也可以不返回一值,那么yylex就会完成这个动作后自动扫描下一个可以被匹配的字符串,一直到扫描到文件结束. 

当扫描到一个可以被匹配的字符串,那么这个时候,全局变量yytext就等于这个字符串 

请大家一定记住这些正则表达式的顺序. 

如果出现一个字符串,可以同时匹配多个正则表达式,那么它将会被定义在前面的正则表达式匹配.所以我一般把字符串string定义在最前面. 

如果文件中的字符没有被lex输入文件中任何一个字符匹配,那么它会自动地被标准输出.所以大家一定要记住在每个正则表达式处理完毕后,一定要加上{newline}和.这两个正则表达式的动作. 

好,让我们看看lex为我们输出C文件中提供一些常量 

Lex 变量 

yyin 
FILE* 类型。 它指向 lexer 正在解析的当前文件。 

yyout 
FILE* 类型。 它指向记录 lexer 输出的位置。 缺省情况下，yyin 和 yyout 都指向标准输入和输出。 

yytext 
匹配模式的文本存储在这一变量中（char*）。 

yyleng 
给出匹配模式的长度。 

yylineno 
提供当前的行数信息。（lexer不一定支持。） 

例2.2 

这是<<编译原理与实践>>书中配套的源代码的lex输入文件.大家可以参考一下,作者为它自己定义的一个Tiny C编译所做的词法扫描器. 

/****************************************************/ 

/* File: tiny.l */ 

/* Lex specification for TINY */ 

/* Compiler Construction: Principles and Practice */ 

/* Kenneth C. Louden */ 

/****************************************************/ 



%{ 

#include "globals.h" 

#include "util.h" 

#include "scan.h" 

/* lexeme of identifier or reserved word */ 

char tokenString[MAXTOKENLEN+1]; 

%} 



digit [0-9] 

number {digit}+ 

letter [a-zA-Z] 

identifier {letter}+ 

newline \n 

whitespace [ \t]+ 



%% 



"if" {return IF;} 

"then" {return THEN;} 

"else" {return ELSE;} 

"end" {return END;} 

"repeat" {return REPEAT;} 

"until" {return UNTIL;} 

"read" {return READ;} 

"write" {return WRITE;} 

":=" {return ASSIGN;} 

"=" {return EQ;} 

"<" {return LT;} 

"+" {return PLUS;} 

"-" {return MINUS;} 

"*" {return TIMES;} 

"/" {return OVER;} 

"(" {return LPAREN;} 

"" {return RPAREN;} 

";" {return SEMI;} 

{number} {return NUM;} 

{identifier} {return ID;} 

{newline} {lineno++;} 

{whitespace} {/* skip whitespace */} 

"{" { char c; 

do 

{ c = input(); 

if (c == EOF) break; 

if (c == '\n') lineno++; 

} while (c != '}'); 

} 

. {return ERROR;} 



%% 



TokenType getToken(void) 

{ static int firstTime = TRUE; 

TokenType currentToken; 

if (firstTime) 

{ firstTime = FALSE; 

lineno++; 

yyin = source; 

yyout = listing; 

} 

currentToken = yylex(); 

strncpy(tokenString,yytext,MAXTOKENLEN); 

if (TraceScan) { 

fprintf(listing,"\t%d: ",lineno); 

printToken(currentToken,tokenString); 

} 

return currentToken; 

} 



这里有点不同的就是,作者用了另外一个getToken函数来代替yylex作为外部输出函数.其中getToken里面也使用了lex默认的输出函数yylex(),同时还做了一些其它的事情.不过我建议大家不要像作者那样另外写自己的结果输出函数,因为在后面,需要和yacc搭配工作的时候,yacc生成的语法分析程序只认名字叫yylex()的词法结果输出函数. 

if (firstTime) 

{ firstTime = FALSE; 

lineno++; 

yyin = source; 

yyout = listing; 

} 

其中的yyin,yyout,source,listing都是FILE*类型.yyin就是要lex生成的词法扫描程序要扫描的文件,yyout就是基本输出文件(其实我们通常都不用yyout,即使要生成一些输出信息,我们都是自己通过fprintf来输出). 

"{" { char c; 

do 

{ c = input(); 

if (c == EOF) break; 

if (c == '\n') lineno++; 

} while (c != '}'); 

} 

其中,作者的这个Tiny C是以{}来包括注释信息.作者并没有写出注释信息的正则表达式,但是它可以通过检索“{”,然后用lex内部函数input()一一检查 { 后面的字符是不是 } 来跳过注释文字.(C语言的/* */注释文字正则表达式十分难写,所以很多时候我们都用这种方法直接把它的DFA(扫描自动机)写出来). 

本文就是通过简单地举出两个比较实际的例子来讲解flex输入文件的.再次说明,如果你是第一次接触lex,那么请看看前面我推荐的文章,你可以在IBM的开发者网上查到.下一篇关于yacc于BNF文法的说明也是如此.请大家先参考一下其它标准的教程. 


三、范式文法

从这一节开始,我们就算进入编译器构造的正题了.不得不说,前面的词法扫描器在整个编译器部分只是个很小很小的组成,而这两节讲述的语言构造器才能真正为我们的编译工作起到重要的作用.这些东西相信大家在大学的编译原理的课程已经学了不少,那么本文我也只是大致地带过,让大家回忆起大学的知识,重要的yacc使用技巧等等,我将在后面的内容讲出. 

例3.1 
exp -> exp op exp | (exp) | number 
op -> + | - | * 

这里就是一个定义的带有加法,减法,乘法的简单整数算术表达式的文法.其中粗体表示的是终结符号,也就是不能有产生式生成的符号.而exp,op就是非终结符,它们都是由一个”->”符号来产生的. 
比如100 + 222 *123123 -(888+11)就是符合上述文法的具体的表达式. 
注意,在文法定义中,是可以递归的.所以exp产生式右边的式子中可以再次出现exp. 
这里的|和正则表达式一样,表示的选择的意思,也就是说,exp可以是exp op exp或者(exp)再或者number. 

下面让我们看看<<编译原理及实践>>书中的一个关于BNF文法的介绍. 
比如说我们有个数学表达式(34-3)*42,然后我们来看看上面的exp文法怎么来推导识别它. 

(1) exp => exp op exp [exp ->exp op exp] 
(2) => exp op number [exp ->number ] 
(3) => exp * number [op -> * ] 
(4) => (exp) * number [exp ->(exp) ] 
(5) => (exp op exp) * number [exp ->exp op exp] 
(6) => (exp op number)* number [exp -> number ] 
(7) => (exp - number) * number [op -> - ] 
(8) => (number-number)* number [exp -> number ] 

最终,exp里面全部的非终结符号全部变成了终结符号.那么推导完成. 
这种推导十分像我们在离散数学中讲到的命题推理.其实形式语言的推导的数学基础就是我们离散数学的命题推理. 

在推导过程中,其实就是把原来的文法中的递归展开.那么我们在推导的过程,也就很容易实现分析树的生成.而分析树就是我们编译程序中十分重要的信息源.我们之所以前面又做词法分析,又做语法分析的目标就是为了生成分析树.有了它,我们编译程序在后面的代码生成过程中将变得容易百倍. 

请看: 

例3.2 
同样是<<编译原理及实践>>书上的例子. 
设E -> E+a | a 表示的文法为G,那么考虑它生成的表达L(G) 
如果由标准的数学定义,那么我们用公式L(G)={s | exp =>* s }表示一种文法G. 
s代表记号符号的任意数组串,也就是我们的终结符号.而exp代表非终结符号,=>*表示一系列的从非终结符到终结符号的推导过程.这里*有点像我们在讲述正则表达式中的*符号一样,它表示0到无限次的重复.所以=>*就是表示0次到无限次的推导过程. 

L(G) = {a,a+a,a+a+a,a+a+a+a,…} 
E => E+a => E+a+a => E+a+a+a 

同时,在我们的编译课本上,又经常讲述另一种数学表达方式来阐述文法的定义. 
G=(T,N,P,S) 
注意,这里的T,N,P,S都是集合. 
T表示终结符号(terminal),也就是这里{a,+} 
N表示非终结符号(nonterminal),也就是这里{E},但是N不能与T相交. 
P表示产生式(production)或者文法规则(grammar rule)的集合,这里它只有一个元素: E -> E+a 
S表示集合N的开始符号(start symbol).关于S,本人也搞不清楚它的用处,所以很抱歉! 

例3.3 
这是我们C程序语言中经常使用if else文法 
statement -> if-stmt | other 
if-stmt -> if (exp) statement | if (exp) statement else statement 
exp -> 0|1 

statement就是我们C语言中使用语句,它的产生式包括了两种可能,一是if-stmt语句,二是other.然后我们又另外定义if-stmt语句的产生式.这里有两种情况,一是没有else的,另外就是有else的.里面我们又使用了递归.if-stmt本来是包含在statement里面的,可是我们又在if-stmt的产生式中使用statement.正是因为文法中允许递归,所以它比起我们前面讲的正则表达式有更广泛的表示能力,但同时,文法的推导识别也更加法复杂.按照编译原理的书籍,一般讲完BNF文法后,就要重点讲解文法的推导算法.一共有两种,一是LL算法,自顶向下的算法,二是LR算法,自底向上的算法.LL算法比较简单,其中还有一种特殊的情况,就是我们下一节要讲的递归下降的算法.由于C语言中的函数本来就可以递归,那么实现这中递归下降的算法是十分简单的,而且对于我们一般的程序设计语言来说,虽然它的算法能力很弱,但是已经是足够用了.而关于LR的算法,那么就是一个大难题了.它的算法能力最强,但是实现起来十分困难,还好,已经有科学家为我们提供了yacc(或者叫bison)这个工具,可以来自动生成LR的文法推导算法.这就是我们一直在提到的yacc工具了. 

回过头来,我们看看下面的程序 
if(0) other else other 
的分析树 

思考: 为什么要把文法最终分析成树结构? 
因为文法本身是递归的,而表示的递归的最好数据结构就是树,所以我们把文法弄成树结构后,后面在处理代码生成等问题上,也可以用递归来很容易地完成. 

例3.4 
这里我给出microsoft在msdn中对于C语言的statement的文法 
注意,这里用:符号替代了我们前面产生式的-> 

statement : 
labeled-statement 
compound-statement 
expression-statement 
selection-statement 
iteration-statement 
jump-statement 
try-except-statement /* Microsoft Specific */ 
try-finally-statement /* Microsoft Specific */ 
jump-statement : 
goto identifier ; 
continue; 
break; 
return expression opt ; 
compound-statement : 
{ declaration-list opt statement-list opt } 
declaration-list : 
declaration 
declaration-list declaration 
statement-list : 
statement 
statement-list statement 
expression-statement : 
expression opt ; 
iteration-statement : 
while ( expression  statement 
do statement while ( expression ; 
for ( expression opt ; expression opt ; expression opt  statement 
selection-statement : 
if ( expression  statement 
if ( expression  statement else statement 
switch ( expression  statement 
labeled-statement : 
identifier : statement 
case constant-expression : statement 
default : statement 
try-except-statement : /* Microsoft Specific */ 
__try compound-statement 
__except ( expression  compound-statement 
try-finally-statement : /* Microsoft Specific */ 
__try compound-statement 
__finally compound-statement 


四、文法识别(一)

没想到这一系列文件能得到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语言中,由于函数本身是可以递归的,所以实现这种算法就只需要写简单的几个函数的递归过程就是了. 
为什么叫自顶向下呢?因为在分析过程中,我们是从语法树的树顶逐步向树底分析的,所以叫自顶向下的算法. 

为了方便说明自顶向下算法的简单性,我们来看一下<>中的一个例子.(本系列文章经常要引用国外经典著作的范例,希望大家不要告我抄袭,我实在找不到比大师的范例更经典的范例了) 

例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的代码就是镶嵌在这些纯的语法分析代码中.


 五、实用javacc

前言 

本系列的文章的宗旨是让大家能够写出自己的编译器,解释器或者脚本引擎,所以每到理论介绍到一个程度后,我都会来讨论实践问题.理论方面,编译原理的教材已经是够多了,而实践的问题却很少讨论. 

前几节文章只讨论到了词法分析和LL文法分析,关键的LR文法分析这里却还没有讲,我们先不要管复杂的LR文法和算法,让我们使用LL算法来实际做一些东西后再说.本文将介绍一个在JAVA上广泛使用的LL算法分析工具Javacc.(这是我唯一能找到的使用LL算法的语法分析器构造工具).这一节的文章并非只针对JAVA开发者,如果你是C/C++开发者,那么也请你来看看这个JAVA下的优秀工具,或许你将来也用得着它. 

Lex和yacc这两个工具是经典的词法分析和语法分析工具,但是它们都是基于C语言下面的工具,而使用JAVA的朋友们就用不上了.但是JAVA下已经有了lex和yacc的替代品javacc(Java Compiler Compiler .同时javacc也是使用LL算法的工具,我们也可以实践一下前面学的LL算法. 

首先声明我不是一个JAVA专家,我也是刚刚才接触JAVA.Java里面或许有很多类似javacc一样的工具,但是据我所知,javacc还是最广泛,最标准的JAVA下的词法语法分析器. 

Javacc的获取 
同lex和yacc一样,javacc也是一个免费可以获取的通用工具,它可以在很多JAVA相关的工具下载网站下载,当然,javacc所占的磁盘空间比起lex和yacc更大一些,里面有标准的文档和examples.相对lex和yacc来说,javacc做得更人性化,更容易一些.如果你实在找不到javacc,还是可以联系我,我这里有.现在最新的就是javacc 3.2版本. 

Javacc的原理 

Javacc可以同时完成对text的词法分析和语法分析的工作,使用起来相当方便.同样,它和lex和yacc一样,先输入一个按照它规定的格式的文件,然后javacc根据你输入的文件来生成相应的词法分析于语法分析程序.同时,新版本的Javacc除了常规的词法分析和语法分析以外,还提供JJTree等工具来帮助我们建立语法树.总之,Javacc在很多地方做得都比lex和yacc要人性化,这个在后面的输入文件格式中也能体现出来. 

Javacc的输入文件 

Javacc的输入文件格式做得比较简单.每个非终结符产生式对应一个Class中的函数,函数中可以嵌入相应的识别出该终结符文法时候的处理代码(也叫动作).这个与YACC中是一致的. 

Javacc的输入文件中,有一系列的系统参数,比如其中lookahead可以设置成大于1的整数,那么就是说,它可以为我们生成LL(k)算法(k>=1),而不是简单的递归下降那样的LL(1)算法了.要知道,LL(2)文法比起前面讨论的LL(1)文法判断每个非终结符时候需要看前面两个记号而不是一个,那么对于文法形式的限制就更少.不过LL(2)的算法当然也比LL(1)算法慢了不少.作为一般的计算机程序设计语言,LL(1)算法已经是足够了.就算不是LL(1)算法,我们也可以通过前面讲的左提公因式把它变成一个LL(1)文法来处理.不过既然javacc都把lookahead选择做出来了,那么在某些特定的情况下,我们可以直接调整一个lookahead的参数就可以,而不必纠正我们的文法. 


下面我们来看看Javacc中自带的example中的例子. 

例5.1 

这个例子可以在javacc-3.2/doc/examples/SimpleExamples/Simple1.jj看到 

PARSER_BEGIN(Simple1) 

public class Simple1 { 

public static void main(String args[]) throws ParseException { 

Simple1 parser = new Simple1(System.in); 

parser.Input(); 

} 

} 

PARSER_END(Simple1) 

void Input() : 

{} 

{ 

MatchedBraces() ("\n"|"\r"* 

} 

void MatchedBraces() : 

{} 

{ 

"{" [ MatchedBraces() ] "}" 

} 



设置好javacc的bin目录后,在命令提示符下输入 

javacc Simple1.jj 

然后javacc就会为你生成下面几个java源代码文件 

Simple1.java 

Simple1TokenManager.java 

Simple1Constants.java 

SimpleCharStream.java 

Token.java 

TokenMgrError.java 



其中Simple1就是你的语法分析器的对象,它的构造函数参数就是要分析的输入流,这里的是System.in. 

class Simple1就定义在标记PARSER_BEGIN(Simple1) 

PARSER_END(Simple1)之间. 

但是必须清楚的是,PARSER_BEGIN和PARSER_END中的名字必须是词法分析器的名字(这里是Simple1). 

PARSER_END下面的定义就是文法非终结符号的定义了. 

Simple1的文法基本就是: 

Input -> MatchedBraces ("\n"|"\r"* 

MatchedBraces -> “{“ MatchedBraces “}” 

从它的定义我们可以看到,每个非终结符号对于一个过程. 

比如Input的过程 

void Input() : 

{} 

{ 

MatchedBraces() ("\n"|"\r"* 

} 


在定义void Input后面记住需要加上一个冒号”:”,然后接下来是两个块{}的定义. 

第一个{}中的代码是定义数据,初试化数据的代码.第二个{}中的部分就是真正定义Input的产生式了. 

每个产生式之间用”|”符号连接. 

注意: 这里的产生式并非需要严格BNF范式文法,它的文法既可以是BNF,同时还可以是混合了正则表达式中的定义方法.比如上面的 

Input -> MatchedBraces ("\n"|"\r"* 

中(“\n”|”\r”)* 就是个正则表达式,表示的是\n或者\r的0个到无限个的重复的记号. 

而是javacc系统定义的记号(TOKEN),表示文件结束符号. 

除了,无论是系统定义的TOKEN,还是自定义的TOKEN, 里面的TOKEN都是以的方式表示. 

每个非终结符号(Input和MatchedBraces)都会在javacc生成的Simple1.java中形成Class Simple1的成员函数.当你在外部调用Simple1的Input,那么语法分析器就会开始进行语法分析了. 

例5.2 

在javacc提供的example里面没有.javacc提供的example里面提供的例子中SimpleExamples过于简单,而其它例子又过于庞大.下面我以我们最常见的数学四则混合运算的文法来构造一个javacc的文法识别器.这个例子是我自己写的,十分简单,.其中还包括了文法识别同时嵌入的构建语法树Parse-Tree的代码.不过由于篇幅的原因,我并没有给出全部的代码,这里只给了javacc输入部分相关的代码.而Parse-tree就是一个普通的4叉树,3个child,1个next(平行结点),相信大家在学习数据结构的时候应该都是学过的.所以这里就省略过去了. 

在大家看这些输入代码之前,我先给出它所使用的文法定义,好让大家有个清楚的框架. 

Expression -> Term { Addop Term } 
Addop -> "+" | "-" 
Term -> Factor { Mulop Factor } 
Mulop -> "*" | "/" 
Factor -> ID | NUM | "(" Expression "" 

这里的文法可能和BNF范式有点不同.{}的意思就是0次到无限次重复,它跟我们在学习正则表达式的时候的”*”符号相同,所以，在Javacc中的文法表示的时候，{…}部分的就是用(…)*来表示. 

为了让词法分析做得更简单,我们通常都不会在文法分析的时候,使用”(”,”)“等字符号串来表示终结符号,而需要转而使用LPAREN, RPAREN这样的整型符号来表示. 

PARSER_BEGIN(Grammar) 

public class Grammar implements NodeType { 

public ParseTreeNode GetParseTree(InputStream in) throws ParseException 

{ 

Grammar parser =new Grammar(in); 

return parser.Expression(); 

} 


} 

PARSER_END(Grammar) 

SKIP : 

{ 

" " | "\t" | "\n" | "\r" 

} 

TOKEN : 

{ 

< ID: ["a"-"z","A"-"Z","_"] ( ["a"-"z","A"-"Z","_","0"-"9"] * > 

| < NUM: ( ["0"-"9"] + > 

| < PLUS: "+" > 

| < MINUS: "-" > 

| < TIMERS: "*" > 

| < OVER: "/" > 

| < LPAREN: "(" > 

| < RPAREN: "" > 

} 


ParseTreeNode Expression() : 

{ 

ParseTreeNode ParseTree = null; 

ParseTreeNode node; 

} 

{ 

( node=Simple_Expression() 

{ 

if(ParseTree == null) 

ParseTree =node; 

else 

{ 

ParseTreeNode t; 

t= ParseTree; 

while(t.next != null) 

t=t.next; 

t.next = node; 

} 

} 

)* 

{ return ParseTree;} 

} 

ParseTreeNode Simple_Expression() : 

{ 

ParseTreeNode node; 

ParseTreeNode t; 

int op; 

} 

{ 

node=Term(){} 

( 

op=addop() t=Term() 

{ 

ParseTreeNode newNode = new ParseTreeNode(); 

newNode.nodetype = op; 

newNode.child[0] = node; 

newNode.child[1] = t; 

switch(op) 

{ 

case PlusOP: 

newNode.name = "Operator: +"; 

break; 

case MinusOP: 

newNode.name = "Operator: -"; 

break; 

} 

node = newNode; 

} 

)* 

{ return node; } 

} 

int addop() : {} 

{ 

{ return PlusOP; } 

| { return MinusOP; } 

} 

ParseTreeNode Term() : 

{ 

ParseTreeNode node; 

ParseTreeNode t; 

int op; 

} 

{ 

node=Factor(){} 

( 

op=mulop() t=Factor() 

{ 

ParseTreeNode newNode = new ParseTreeNode(); 

newNode.nodetype = op; 

newNode.child[0] = node; 

newNode.child[1] = t; 

switch(op) 

{ 

case TimersOP: 

newNode.name = "Operator: *"; 

break; 

case OverOP: 

newNode.name = "Operator: /"; 

break; 

} 

node = newNode; 

} 

)* 

{ 

return node; 

} 

} 

int mulop() :{} 

{ 

{ return TimersOP; } 

| { return OverOP; } 

} 

ParseTreeNode Factor() : 

{ 

ParseTreeNode node; 

Token t; 

} 

{ 

t= 

{ 

node=new ParseTreeNode(); 

node.nodetype= IDstmt; 

node.name = t.image; 

return node; 

} 

| 

t= 

{ 

node=new ParseTreeNode(); 

node.nodetype= NUMstmt; 

node.name = t.image; 

node.value= Integer.parseInt(t.image); 

return node; 

} 

| 

node=Simple_Expression() 

{ 

return node; 

} 

} 



其中SKIP 中的定义就是在进行词法分析的同时,忽略掉的记号.TOKEN中的,就是需要在做词法分析的时候,识别的词法记号.当然,这一切都是以正则表达式来表示的. 

这个例子就有多个非终结符号,可以看出,我们需要为每个非终结符号写出一个过程.不同的非终结符号的识别过程中可以互相调用. 

以Simple_Expression()过程为例,它的产生式是Expression -> Term { addop Term },而在javacc的输入文件格式是，它的识别是这样写的node=Term(){} ( op=addop() t=Term(){ … })* 前面说过，这里的”*”符号和正则表达式是一样的，就是0次到无限次的重复.那么Simple_Expression等于文法Term Addop Term Addop Term Addop Term … 而Addop也就相当于PLUS和MINUS两个运算符号.这里我们在写Expression的文法的时候，同时还使用了赋值表达式，因为这个和Yacc不同的时候，Javacc把文法识别完全地做到了函数过程中，那么如果我们要识别Simple_Expression的文法，就相当于按顺序识别Term和Addop两个文法,而识别那个文法，就相当于调用那两个非终结符的识别函数.正是这一点，我觉得Javacc的文法识别处理上就很接近程序的操作过程,我们不需要像YACC那样使用严格的文法表示格式，复杂的系统参数了. 

关于Yacc的使用，其实比Javacc要复杂，还需要考虑到和词法分析器接口的问题，这个我会在以后细细讲到. 

至于其它的文法操作解释我就不再多说了,如果要说,就是再写上十篇这样的文章也写不完.本文只能给读者们一个方向,至于深入的研究,还是请大家看javacc提供的官方文档资料. 

最后 

由于国外使用JAVA做项目的程序员比国内多,那么讨论JAVA技术的人员也比较多.可能来这里读我的文章的人都是C/C++程序员,但是关注其它领域同方向的技术也是可以让我们的知识领域更加宽广.关于JavaCC的讨论主要是在国际新闻组comp.compilers.tools.javacc如果大家在使用JavaCC做实际问题的时候遇到什么问题,不妨上去找找专家. 

2003-11-16 

成都,四川大学,计算机学院