从lex&yacc说到编译器(页 1) - 编程开发 & Rational - LoveUnix 最强AIX小机技术论坛,UNIX,Linux,存储,数据库,中间件,开发,管理

2004-4-9 20:53 sky-walker

作者:tangl_99 QQ:8664220 msn:tangl_99@hotmail.com email:tangl_99@sohu.com ------------------------------------------------------------- (1.正则表达式) 学过编译原理的朋友肯定都接触过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制表符.使用了”+”符号,就表示了这些空白符号的无限组合.

2004-4-9 20:56 sky-walker

(2.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 <div class='codetop'>CODE</div><div class='codemain'> %{ /* need this for the call to atof() below */ #include <stdio.h> #include <stdlib.h> #include <math.h> #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; } </div> 这里的lex输入文件一共有三个部分,用%%分开.第一部分中的%{和}%中的内容就是直接放在lex输出C代码中的顶部.我们通过它可以来定义一些所需要的宏,函数和include一些头文件等等.我的这个lex输入文件中也没什么特别的东西,就是常规的C源文件的include头文件 <div class='codetop'>CODE</div><div class='codemain'> %{ /* need this for the call to atof() below */ #include <stdio.h> #include <stdlib.h> #include <math.h> #include "globals.h" %} </div> 第一部分中,除了前面的%{和}%包含的部分,下面的就是正则表达式的定义. 看了第一篇的正则表达式,这样你就能够在这里派上用场了. 让我们来看看我这里定义的正则表达式: 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文件中提供一些常量 <div class='codetop'>CODE</div><div class='codemain'> Lex 变量 yyin FILE* 类型。它指向 lexer 正在解析的当前文件。 yyout FILE* 类型。它指向记录 lexer 输出的位置。缺省情况下，yyin 和 yyout 都指向标准输入和输出。 yytext 匹配模式的文本存储在这一变量中（char*）。 yyleng 给出匹配模式的长度。 yylineno 提供当前的行数信息。（lexer不一定支持。） </div> 例2.2 这是<<编译原理与实践>>书中配套的源代码的lex输入文件.大家可以参考一下,作者为它自己定义的一个Tiny C编译所做的词法扫描器. <div class='codetop'>CODE</div><div class='codemain'> /****************************************************/ /* 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; } </div> 这里有点不同的就是,作者用了另外一个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文法的说明也是如此.请大家先参考一下其它标准的教程.

2004-4-9 21:01 sky-walker

解决通讯录问题（1） 前言 一般的编译原理教材上关于使用lex和yacc构造词法分析的好例子并不多.很多教程都只是在讲解词法分析和语法分析的时候简单地提到了一下lex和yacc这两个工具，甚至有很多国内的大学教材对lex和yacc只字不提。其实lex和Yacc并非只是为了构造编译系统而开发的。本节通过一个提取通讯记录的信息的简单问题，来讲解一下lex和yacc的使用. 提取通讯录的信息 前几天收到朋友询问一下如何通过词法，语言分析，把一个通讯录中的人物姓名和电话号码的信息提取出来。我把问题改了一下，大致如下： 我有个记事本，里面的信息都是电话机生成的通讯记录信息。以文本格式保存在record.txt文件里面。里面的信息是以下面的方式组成的。 ---------2004.1.10---------- 姓名：jeclee 电话：05513606124 ---------2004.1.11---------- 姓名：wangan 电话：075528979205 … 现在我要建立一个数据库系统，需要把跟我同过电话的人的姓名和电话号码都输入进去。那么我需要考虑从这种电话机生成的记录格式文件中提取有用的信息。当然，解决的办法多不胜数，但是本节，我们将探讨使用lex和yacc两个工具，十分方便的构造语法分析器，来里面的信息。 寻找lex和yacc两个工具 或许你觉得动用编译原理来解决这种问题太麻烦了，但是当我们有了lex和yacc后，复杂的处理将被简化。Lex和yacc这两个东西本来是unix下的两个工具，一般大家使用windows操作系统就需要在网上去寻找。我使用的是cygwin中的flex.exe和bison.exe。bison.exe就是yacc.而cygwin就是一个在windows平台上模拟unix的工具。大家可以去下一个cygwin就可以用了。 词法分析器的输入文件 关于正则表达式的问题，我在本系列前面的文章中已经提到过，其详细的讲解请大家参考编译原理教材。 这里我先给出一些基本的词法的正则表达式，它们都是几乎在每个词法输入文件里面都会出现的。 digit [0-9] number {digit}+ letter [a-zA-Z_] identifier ({letter}|_)({number}|{letter}|_)* newline [\n]|[\r][\n] whitespace [ \t]+ 在电话机中的记录文件中另外还有标记头”---------2004.1.10----------“我们没有考虑。标记头的正则表达式十分简单，就是”-“和数字和点的组合而已，那么可以很容易地写下它的正则表达式。 Begin [-]+({number}[.])+[-]+ 这里的[-]表示的”-“符号,而number前面已经给出,为任意一个整数.而逗号”.”也是以[.]表示出来.那么({number}[.])+就表示记录头里面的日期信息，可是这里我们并不需要知道日期信息，所以就没有必要把它单独提取出来，而完全可以埋藏在一个简单的正则表达式里面。 好了，把这些正则表达式整理到一个名字为record.l的flex输入文件里面就可以了。 整个电话机记录都使用一种固定的文法形式，那么文法输入文件的编写就相对简单，完成词法分析后，我们的工作差不多就完成了一半了。

2004-4-9 21:07 sky-walker

(4.文法识别(一)) 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构造一个分析数的时候,该算法就是从根结点开始. 下面我们通过其中主要的三个步骤来看看算法的实现原理. 第一步分析: <img src='http://www.csdn.net/Develop/ArticleImages/21/21722/CSDN_Dev_Image_2003-10-231448120.jpg' border='0' alt='user posted image' /> 首先分析的是输入的字符串第一个串”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集合的算法也在教材中详细讲解了.我就不在这里再描述了. 第二步分析: <img src='http://www.csdn.net/Develop/ArticleImages/21/21722/CSDN_Dev_Image_2003-10-231448122.jpg' border='0' alt='user posted image' /> 经过第一步的考察输入串中的第一个串为”array”属于非终结符号type第三个产生式的First集合,那么就可以确定这个串确实为type文法第三个产生式的串.所以在第二步中,展开出type的第三个产生式出来. type -> array [ simple ] of integer 那么接下来就是继续分析构造出来的type -> array[ simple] of integer产生式中的每个结点. 所以箭头又放到了分析树中type的第一个孩结点array上.因为array是终结符号,如果它和输入中的当前箭头所指的终结符号相同,那么箭头都往下移动一结点到’[‘符号.同样地,由于分析树中的’[‘是终结符号,那么只要看输入中的串是否是’[‘就可以了.如果是,那么继续往下分析.分析到分析数中的simple的时候,由于simple是非终结符号,那么就需要考虑simple的产生式了. 第三步分析: <img src='http://www.csdn.net/Develop/ArticleImages/21/21722/CSDN_Dev_Image_2003-10-231448124.jpg' border='0' alt='user posted image' /> 在第二步中,分析到分析数中的simple子结点的时候,由于simple是非终结符号,那么就需要考虑simple的产生式.simple一共有三个产生式.通过输入串当前的串是”num”,是属于simple产生式中第3个产生式的First集合,所以simple在分析数中就按第三个产生式simple -> num dotdot num 来展开.那么分析箭头同样,也自动移动到simple的第一个子结点num上继续分析. 总体说来,这中自顶向下的分析原理就基本上是上面的过程.通过计算产生式的First集合,来逐步产生非终结符的产生式.最后的分析树都会划归到终结符来进行判断(非终结符号是无法进行直接判断的,一定要展开过后才行). 看了原理,我们再看实现的伪代码.代码很简单. <div class='codetop'>CODE</div><div class='codemain'> 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); }</div> 注意:这里的代码都是纯的语法分析代码,实际执行过程中并没有什么用处,但是我们构造语法树parse-tree的代码就是镶嵌在这些纯的语法分析代码中.

2004-4-9 21:09 sky-walker

(5.实用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看到 <div class='codetop'>CODE</div><div class='codemain'> 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")* <EOF> } void MatchedBraces() : {} { "{" [ MatchedBraces() ] "}" } 设置好javacc的bin目录后,在命令提示符下输入 javacc Simple1.jj 然后javacc就会为你生成下面几个java源代码文件 Simple1.java Simple1TokenManager.java Simple1Constants.java SimpleCharStream.java Token.java TokenMgrError.java </div> 其中Simple1就是你的语法分析器的对象,它的构造函数参数就是要分析的输入流,这里的是System.in. class Simple1就定义在标记PARSER_BEGIN(Simple1) PARSER_END(Simple1)之间. 但是必须清楚的是,PARSER_BEGIN和PARSER_END中的名字必须是词法分析器的名字(这里是Simple1). PARSER_END下面的定义就是文法非终结符号的定义了. Simple1的文法基本就是: Input -> MatchedBraces ("\n"|"\r")* <EOF> MatchedBraces -> “{“ MatchedBraces “}” 从它的定义我们可以看到,每个非终结符号对于一个过程. 比如Input的过程 void Input() : {} { MatchedBraces() ("\n"|"\r")* <EOF> } 在定义void Input后面记住需要加上一个冒号”:”,然后接下来是两个块{}的定义. 第一个{}中的代码是定义数据,初试化数据的代码.第二个{}中的部分就是真正定义Input的产生式了. 每个产生式之间用”|”符号连接. 注意: 这里的产生式并非需要严格BNF范式文法,它的文法既可以是BNF,同时还可以是混合了正则表达式中的定义方法.比如上面的 Input -> MatchedBraces ("\n"|"\r")* <EOF> 中(“\n”|”\r”)* 就是个正则表达式,表示的是\n或者\r的0个到无限个的重复的记号. 而<EOF>是javacc系统定义的记号(TOKEN),表示文件结束符号. 除了<EOF>,无论是系统定义的TOKEN,还是自定义的TOKEN, 里面的TOKEN都是以<token’s name>的方式表示. 每个非终结符号(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这样的整型符号来表示. <div class='codetop'>CODE</div><div class='codemain'> 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;}  <EOF> } 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() : {} {         <PLUS> { return PlusOP; } |   <MINUS> { 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() :{} {         <TIMERS> { return TimersOP; }         | <OVER> { return OverOP;   } } ParseTreeNode Factor() : {         ParseTreeNode node;         Token t; } {  t=<ID> {           node=new ParseTreeNode();           node.nodetype= IDstmt;           node.name = t.image;           return node;         }  |  t=<NUM>  {      node=new ParseTreeNode();           node.nodetype= NUMstmt;           node.name = t.image;           node.value= Integer.parseInt(t.image);           return node;    }  |  <LPAREN> node=Simple_Expression() <RPAREN>  {         return node;  } } </div> 其中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做实际问题的时候遇到什么问题,不妨上去找找专家.

2004-4-9 21:15 sky-walker

(6.数学表达式) 前言 文法分析中最重要算法是LL自顶向下和LR自底向上算法.前面几篇文章主要讲解的是LL算法的理论和一个LL算法的文法分析器javacc.本文以LL(1)算法中最简单的一种形式递归下降算法来分析常规算法问题中的数学表达式问题.同时,本文也介绍手工构造EBNF文法的分析器代码普遍方法.希望本文的实践能对大家实现自己的语法分析器带来帮助. 数学表达式问题 在学习算法的时候,四则混合运算的表达式处理是个很经典的算法问题. 比如这里有个数学表达式”122+2*(11-1)/(3-(2-0))”.我们需要根据这个字符串的描述,然后计算出其结果. Input: 122+2*(11-1)/(3-(2-0)) Output: 142 四则混合运算中还需要考虑到括号,乘除号与加减号的优先运算问题,通常的解决办法就是使用堆栈.那种常规的算法和LL算法有异曲同工之处,更或者说,那么的算法其实是一样的. 传统数学表达式处理算法简介 这个传统算法其实不知不觉地使用LL(1)算法的精髓.它就是主要依靠栈式的数据结构分别保存数和符号,然后根据运算符号的优先级别进行数学计算,并将结果保存在栈里面. 传统算法中使用了两个栈.一个是保存数值,暂时就叫值栈. 另一个是保存符号的,叫符号栈.我们规定一个记号#,来表示栈底.下面我们就来看看如何计算一个简单的表达式11+2-8*(5-3). 为了显示整个计算过程,我们以下面这个栈的变化图来表示. <img src='http://www.csdn.net/Develop/ArticleImages/22/22590/CSDN_Dev_Image_2003-12-7134320.png' border='0' alt='user posted image' /> 符号栈和值栈的变化是根据输入串来进行的.基本上栈的操作可以简单用下面几句话来说. Start: 1. 如果当前输入串中得到的是数字,则直接压入值栈.然后转到Start. 2. 如果当前输入串中得到的是符号,那么对符号进行判断. 1)如果符号是’+’或者’-‘,则依次弹出符号栈的符号,计算栈中数值,直到弹出的符号不是*,/,+,-. 2)如果符号是’*’或者’/’,则压入符号栈 3)如果符号是’(‘,则直接压’(‘入符号栈 4)如果符号是’)’,则依照符号栈的顺序弹出符号,计算栈中数值,把结果压入值栈,直到符号栈顶是’(‘,最后再弹出’(‘ . 最后转到Start. 3. 如果当前输入串得到的是EOF(字符串结束符号),则计算栈中数值,知道符号栈没有符号. 语法分析数学表达式 或者可能你以前运用过自己的办法来解决过这个程序问题,不过下面我们将通过编译原理建立的一套文法分析理论,来十分精彩地解决这个算法问题. 首先是建立数学表达式的文法EBNF.EBNF文法可以更灵活地表示BNF,是BNF范式文法的一种扩展.下面是上一篇javacc的介绍中使用到的计算表达式的文法. Expression -> Term { Addop Term } Addop -> "+" | "-" Term -> Factor { Mulop Factor } Mulop -> "*" | "/" Factor -> ID | NUM | "(" Expression ")" 我们来看看如何根据这个EBNF文法实现一个递归下降的分析程序.大致上来说要分那么几步来实现.(注意,下面的几个步骤不光是针对本节的数学表达式问题,而是包含所有通常的递归下降文法分析器的实现) 语法分析实现 1. Step 建立词法分析 本系列文章开篇第一节就是讲的词法分析相关问题.因为词法分析是语法分析的前提,那么我们在实现递归下降算法的时候,同样应该把词法分析的实现考虑进去. 本文要处理只是个数学表达式的问题,那么通过上面的文法,可以看到需要识别的词法无非就是2个ID,NUM和4个运算符号’+’’-‘‘*’’/’以及2个括号’(‘‘(‘.本文没有对词法分析的自动机原理进行讲解,这部分内容应该在编译原理中讲得比较透彻.所谓自动机,就是按一定步骤识别每个字符的算法.可以用下面的几个图来表示ID和NUM的识别自动机(识别步骤或算法) NUM: <img src='http://www.csdn.net/Develop/ArticleImages/22/22590/CSDN_Dev_Image_2003-12-7134322.gif' border='0' alt='user posted image' /> 基本算法就是,如果输入的字符是digit(‘0’-‘9’),那么进入check循环,如果输入还是digit,那么再跳回循环查看,如果输入是other(不是’0’-‘9’),那么就直接accept,接收这个串为NUM类型的TOKEN. ID: <img src='http://www.csdn.net/Develop/ArticleImages/22/22590/CSDN_Dev_Image_2003-12-7134324.gif' border='0' alt='user posted image' /> 同NUM一样,当输入的是letter,那么进入ID的有限自动机.只是在进入check循环后,有两种可能都继续留在循环,那就是digit和letter(‘a’-‘Z’).当输入既不是digit,也不是letter的时候,就跳出check循环,进入accept,把接收到的字符归结成ID类型的TOKEN. 通过这个有限自动机的图示,我们就很容易写出词法分析程序. 不过在此之前,我们得写出识别letter和digit的代码.我们建立两个函数IsLetter和IsDigit来完成这个功能. <div class='codetop'>CODE</div><div class='codemain'> int IsLetter(char ch) {    if(ch >= 'A' && ch <= 'Z')        return 1;    if(ch >='a' && ch <='z')        return 1;    return 0; } int IsDigit(char ch) {    if(ch >= '0' && ch <='9')        return 1;    return 0; } </div> 有个这两个辅助函数,那么接下来,我们就直接写gettoken词法分析函数,它的功能就是从输入中分析,得到一个一个的token.我们首先定义token的类型. <div class='codetop'>CODE</div><div class='codemain'> #define ID  1 #define NUM 2 #define PLUS   3 // ‘+’ #define MINUS  4 // ‘-‘ #define TIMERS 5 // ‘*’ #define OVER   6 // ‘/’ #define LPAREN 7 // ‘(‘ #define RPAREN 8 // ‘)’ #define ERROR 255 </div> 上面注释已经说符号token代表的意思,我也不再多说.不过需要注意的是,这里我们定义了个ERROR的常量,但是我们这里并没有ERROR的token,它只是为我们后面处理结果时候的一个错误处理信息的定义. <div class='codetop'>CODE</div><div class='codemain'> char token[10]; char *nextchar; const char g_strCalculate[]="122+2*(11-1)/(3-(2-0))"; </div> 我们需要定义token记号和一个指到输入串的指针.token记录的就是当前gettoken()得到的token的text(字符串).nextchar是当前指到输入串的指针.最后,我们随便定义一个要分析的数学表达式的输入串g_strCalculate. <div class='codetop'>CODE</div><div class='codemain'> int gettoken() {    char *ptoken =token;    while(*nextchar == ' ' || *nextchar=='\n' || *nextchar=='\t')        nextchar++;    switch(*nextchar)    {    case '+': nextchar++; return PLUS;    case '-': nextchar++; return MINUS;    case '*': nextchar++; return TIMERS;    case '/': nextchar++; return OVER;    case '(': nextchar++; return LPAREN;    case ')': nextchar++; return RPAREN;    default: break;    }    // ID的词法识别分析    if(IsLetter(*nextchar))    {         while(IsLetter(*nextchar) || IsDigit(*nextchar))         {                  *ptoken = *nextchar;                  nextchar++;                  ptoken++;         }         *ptoken ='\0';         printf("gettoken: token = %s\n",token);         return ID; } // NUM的词法识别分析    if(IsDigit(*nextchar))    {        while(IsDigit(*nextchar))        {               *ptoken = *nextchar;               nextchar++;               ptoken++;        }        *ptoken ='\0';        printf("gettoken: token = %s\n",token);        return NUM;    }    return ERROR; } </div> 代码很简单,我没有写多少任何注释.函数中,首先使用了char *ptoken记录token的首地址,它为后面的字符串复制(构造token)所用.同时,在处理代码的第一部分是过滤掉空格,制表符和换行符.然后是计算符号的词法分析.计算符号就是一个固定的字符号,所以它的识别很简单,直接用switch来判断*nextchar.而后面的ID,NUM的识别就是完全按照前面的有限自动机表示图表来进行编写的.以ID的图表来说,ID的自动机首先是要识别出第一个字符是letter,那么我就写了第一行if(IsLetter(*nextchar)),如果满足,则进入check循环,也就是while(IsLetter(*nextchar) || IsDigit(*nextchar))循环.循环中我们记录了*nextchar到token符号中.最后跳出check循环,进入accept,在代码中return ID.对于NUM的词法识别也是如此的,我就不多说了. 2. 根据EBNF文法建立文法识别函数 首先看到第一条非终结产生式 Expression -> Term { Addop Term } Expression也是我们总的输入结果函数.我们先定义函数int Expression(),其返回值就是我们要处理的表达式的值.右边的产生式中,第一个是Term,我们就直接调用Term函数完成.然后是0到无限次的Addop Term,那么用一个循环即可.文法中使用非终结符号Addop.程序代码中我没有特别为此非终结符号创建函数.我们直接在代码以’+’ || ‘-‘代替Addop. 代码如下. <div class='codetop'>CODE</div><div class='codemain'> int expression() {    int temp = term(); // 对应文法中的第一个Term int tokentype;    while(*nextchar == '+' || *nextchar == '-') // 对应文法中的{ Addop Term }    {        tokentype = gettoken();        switch(tokentype)        {        case PLUS:                temp +=term();                break;        case MINUS:                temp -=term();                break;        default:                break;        }    }    return temp; } </div> 然后是第二条文法.同样,我也没有特别为Mulop特别写一个文法函数,而是直接以’*’|| ‘\’代替. Term -> Factor { Mulop Factor } 同理,建立如下函数 <div class='codetop'>CODE</div><div class='codemain'> int term() {    int temp;    int tokentype;    temp = factor(); // 对应文法中的Factor    while(*nextchar == '*' || *nextchar == '\\') // 对应文法中的 {Mulop Factor}    {        tokentype =gettoken();        switch(tokentype)        {        case TIMERS:          temp *= factor();          break;        case OVER:          temp /= factor();          break;        default:          break;        }    }    return temp; } </div> 最后是Factor文法 Factor -> ID | NUM | "(" Expression ")" 这个文法涉及到文法中的产生式的选择.由LL(1)文法的理论我们可以知道,这完全可以是通过ID,NUM, “(“Expression”)”三个产生式的第一个终结符的不同来判断的.ID的第一个字符号肯定是letter.而NUM第一个字符号肯定是digit. "(" Expression ")"第一个字符号肯定是”(“.而ID,NUM的判断我们已经在词法分析的时候做好了(int gettoken()函数中).下面列出Factor文法函数的代码. <div class='codetop'>CODE</div><div class='codemain'> int factor() {    int number;    switch(gettoken())    {    case ID: break;    case NUM:        number = atoi(token);        break;    case LPAREN:        number = expression();        if(gettoken() != RPAREN)         printf("lost ')' in the expression \n");        break;    default:        break;    }    return number; } </div> 好了,把上面出现的函数都写到程序文件中,加上个main函数,就可以编译运行了. <div class='codetop'>CODE</div><div class='codemain'> int main(int argc, char *argv[]) {  nextchar = g_strCalculate;  printf("result = %d\n",expression());  system("PAUSE");  return 0; } </div> 整个数学表达式的源程序大家可以在这里下载. <a href='http://member.netease.com/~qinj/tangl_99/my' target='_blank'>http://member.netease.com/~qinj/tangl_99/my</a> doc/calculate/main.c 3. 总结 从上面三个EBNF文法实现我们可以容易得出一些机械性规律出来. 1. 对于EBNF文法中的非终结符都可以写成了一个单独的文法函数出来,比如前面Expression(),Term(),Factor(). 2. 文法中的产生式的选择可以根据第一个字符号来进行识别,这就是LL(1)算法中提到的First集合.比如上面的Factor是直接通过gettoken得到下一个token的类型,然后根据类型的不同的token来switch处理不同产生式的代码. 3. 文法中的{}(0到无限次循环),比如{Addop Term},{ Mulop Factor}可以直接通过循环语句完成.不过循环的条件还是需要判断下一token是不是Addop或者Mulop的First集合的元素.比如上面的代码中,Addop就是’+’和’-‘,Mulop无非就是’*’和’/’,所以判断很容易,直接通过*nextchar也可以判断.如果下一个token不是Addop或者Mulop的First集合元素,那么就应该跳出循环.返回文法函数. 虽然EBNF文法构造递归下降文法分析器代码是如此的简单,但是正如<<编译原理及实践>>书上提到的,它有它的特殊性.很多时候,仅仅是把BNF文法转换成EBNF文法本身就是一件十分困难的事情.这就需要我们前面提到的LL(1)文法的消除左递归和提取左因式的问题. 与传统算法的比较 当我们明白了EBNF文法和递归下降的分析后,构造的数学表达式处理代码比传统算法要简单,要容易.原因前面也提到过,首先种东西的EBNF文法十分容易写,其次,从EBNF文法到代码的创建也十分机械化,也十分容易,最后,递归下降算法没有接触到栈的操作,利用了程序语言本身的递归本身特性,让程序语言去处理栈的操作(并不是说递归下降的算法一点都没有接触到栈,可以说数据结构中递归处理就等于栈处理). 递归下降的算法也和容易扩展表达式的计算操作.比如说,我们想把函数(如sin,cos)加进去,而且是加到所有运算的最高级别.那么我们修改Factor文法即可 Factor -> ID | NUM | "(" Expression ")" | “sin””(“ Expression “)” | “cos””)” Expression “)” 至于代码的实现,我们也只需要在int Factor函数中的switch中增加几个case语句就可以了.

2004-4-9 21:25 sky-walker

如果有人感兴趣,推荐几本书啊 1.《现代编译程序设计》，讲了很多现在的技术，人民邮电出版社 2.《编译原理与实践》，这就不要多说了吧 3.《编译原理及技术》，呵呵，和上面一样，同样是Kenneth C.Louden的著作 相关工具 FLex，BYacc，Bison <a href='http://sourceforge.net/projects/gnuwin32上有' target='_blank'>http://sourceforge.net/projects/gnuwin32上有</a> 此外Lex和yacc在cygwin下都有的.

2004-4-9 21:29 纳兰婷

呵呵，大哥和我用的东西都差不多啊！ 我以前常用 yacc，后来是 flex 和 bison。

2004-4-10 15:33 wingc

这篇文章太棒了，哈哈 以前实践编译原理的时候，词法分析是自己写的，没有用lex，后来帮人家写了个SQL的简单解释，词法分析还是改的自己的，语法分析用的一个和yacc类似的工具lemon，现在看这篇文章，有些理论的东西还是忘了，好累的说~~

2004-4-12 12:20 无双

写的很不错偶以前看到BNF也不知道是什么东东 现在总算明白了一点

2004-4-27 10:16 sky-walker

编译原理学习导论 大学课程为什么要开设编译原理呢？这门课程关注的是编译器方面的产生原理和技术问题，似乎和计算机的基础领域不沾边，可是编译原理却一直作为大学本科的必修课程，同时也成为了研究生入学考试的必考内容。编译原理及技术从本质上来讲就是一个算法问题而已，当然由于这个问题十分复杂，其解决算法也相对复杂。我们学的数据结构与算法分析也是讲算法的，不过讲的基础算法，换句话说讲的是算法导论，而编译原理这门课程讲的就是比较专注解决一种的算法了。在20世纪50年代，编译器的编写一直被认为是十分困难的事情，第一Fortran的编译器据说花了18年的时间才完成。在人们尝试编写编译器的同时，诞生了许多跟编译相关的理论和技术，而这些理论和技术比一个实际的编译器本身价值更大。就犹如数学家们在解决著名的哥德巴赫猜想一样，虽然没有最终解决问题，但是其间诞生不少名著的相关数论。 推荐参考书 虽然编译理论发展到今天，已经有了比较成熟的部分，但是作为一个大学生来说，要自己写出一个像Turboc C,Java那样的编译器来说还是太难了。不仅写编译器困难，学习编译原理这门课程也比较困难。 正是因为编译原理学习相对困难，那么就要求有好的教师和好的教材。教师方面不是我们能自己更改的，而在教材方面我们却可以按自己的意愿来阅读。我下面推荐几本好的编译原理的教材。我推荐的书籍都是国外的经典教材，因为在国内的教材中，确实还没发现什么让人满意的。 第一本书的原名叫《Compilers Principles,Techniques,and Tools》,另外一个响亮的名字就是龙书。原因是这本书的封面上有条红色的龙，也因为獗臼樵诒嘁朐?砘?×煊蛉肥堤?忻???所以很多国外的学者都直接取名为龙书。最近机械工业出版社已经出版了此书的中文版，名字就叫《编译原理》。该书出的比较早，大概是在85或86年编写完成的，作者之一还是著名的贝尔实验室的科学家。里面讲解的核心编译原理至今都没有变过，所以一直到今天，它的价值都非凡。这本书最大的特点就是一开始就通过一个实际的小例子，把编译原理的大致内容罗列出来，让很多编译原理的初学者很快心里有了个底,也知道为什么会有这些理论，怎么运用这些理论。而这一点是我感觉国内的教材缺乏的东西，所以国内的教材都不是写给愿意自学的读者，总之让人看了半天，却不知道里面的东西有什么用。 第二本书的原名叫《Modern Compiler Design》,中文名字叫做《现代编译程序设计》。该书由人民邮电出版社所出。此书比较关注的是编译原理的实践，书中给出了不少的实际程序代码，还有很多实际的编译技术问题等等。此书另外一个特点就是其“现代”而字。在传统的编译原理教材中，你是不可能看到如同Java中的“垃圾回收”等算法的。因为Java这样的解释执行语言是在近几年才流行起来的东西。如果你想深入学习编译原理的理论知识，那么你肯定得看前面那本龙书，如果你想自己动手做一个先进的编译器，那么你得看这本《现代编译程序设计》。 第三本书就是很多国内的编译原理学者都推荐的那本《编译原理及实践》。或许是这本书引入国内比较早吧，我记得我是在高中就买了这本书，不过也是在前段时间才把整本书看完。此书作为入门教程也的确是个不错的选择。书中给出的编译原理讲解也相当细致，虽然不如前面的龙书那么深入，但是很多地方都是点到为止，作为大学本科教学已经是十分深入了。该书的特点就是注重实践，不过感觉还不如前面那本《现代编译程序设计》的实践味道更重。此书的重点还是在原理上的实践，而非前面那本那样的技术实践。《编译原理及实践》在讲解编译原理的各个部分的同时，也在逐步实践一个现代的编译器Tiny C.等你把整本书看完，差不多自己也可以写一个Tiny C了。作者还对Lex和Yacc这两个常用的编译相关的工具进行了很详细的说明，这一点也是很难在国内的教材中看到的。 推荐了这三本教材，都有英文版和中文版的。很多英文好的同学只喜欢看原版的书，不我的感觉是这三本书的翻译都很不错，没有必要特别去买英文版的。理解理论的实质比理解表面的文字更为重要。 编译原理的实质 前面已经说过，学习编译原理其实也就是学习算法而已，没什么特别的。只不过这些算法的产生已经形成了一套理论。下面我来看看编译原理里面到底有什么高深的理论吧。 几乎每本编译原理的教材都是分成词法分析，语法分析（LL算法，递归下降算法，LR算法），语义分析，运行时环境，中间代码，代码生成，代码优化这些部分。其实现在很多编译原理的教材都是按照85,86出版的那本龙书来安排教学内容的，所以那本龙书的内容格式几乎成了现在编译原理教材的定式，包括国内的教材也是如此。一般来说，大学里面的本科教学是不可能把上面的所有部分都认真讲完的，而是比较偏重于前面几个部分。像代码优化那部分东西，就像个无底洞一样，如果要认真讲，就是单独开一个学期的课也不可能讲得清楚。所以，一般对于本科生，对词法分析和语法分析掌握要求就相对要高一点了。 词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。不过编译原理在讲解词法分析的时候，重点把正则表达式和自动机原理加了进来，然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显，就是要让词法分析从程序上升到理论的地步。 语法分析部分就比较麻烦一点了。现在一般有两种语法分析算法，LL自顶向下算法和LR自底向上算法。LL算法还好说，到了LR算法的时候，困难就来了。很多自学编译原理的都是遇到LR算法的理解成问题后就放弃了自学。其实这些东西都是只要大家理解就可以了，又不是像词法分析那样非得自己写出来才算真正的会。像LR算法的语法分析器，一般都是用工具Yacc来生成，实践中完全没有比较自己来实现。对于LL算法中特殊的递归下降算法，因为其实践十分简单，那么就应该要求每个学生都能自己写。当然，现在也有不少好的LL算法的语法分析器，不过要是换在非C平台，比如Java,Delphi,你不能运用YACC工具了，那么你就只有自己来写语法分析器。 等学到词法分析和语法分析时候，你可能会出现这样的疑问：“词法分析和语法分析到底有什么？”就从编译器的角度来讲，编译器需要把程序员写的源程序转换成一种方便处理的数据结构（抽象语法树或语法树）,那么这个转换的过程就是通过词法分析和语法分析的。其实词法分析并非一开始就被列入编译器的必备部分，只是我们为了简化语法分析的过程，就把词法分析这种繁琐的工作单独提取出来，就成了现在的词法分析部分。除了编译器部分，在其它地方，词法分析和语法分析也是有用的。比如我们在DOS,Unix,Linux下输入命令的时候，程序如何分析你输入的命令形式，这也是简单的应用。总之，这两部分的工作就是把不“规则”的文本信息转换成一种比较好分析好处理的数据结构。那么为什么编译原理的教程都最终把要分析的源分析转换成“树”这种数据结构呢？数据结构中有Stack, Line,List…这么多数据结构，各自都有各自的特点。但是Tree这种结构有很强的递归性，也就是说我们可以把Tree的任何结点Node提取出来后，它依旧是一颗完整的Tree。这一点符合我们现在编译原理分析的形式语言，比如我们在函数里面使用函树，循环中使用循环，条件中使用条件等等，那么就可以很直观地表示在Tree这种数据结构上。同样，我们在执行形式语言的程序的时候也是如此的递归性。在编译原理后面的代码生成的部分，就会介绍一种堆栈式的中间代码，我们可以根据分析出来的抽象语法树，很容易，很机械地运用递归遍历抽象语法树就可以生成这种指令代码。而这种代码其实也被广泛运用在其它的解释型语言中。像现在流行的Java,.NET，其底层的字节码bytecode,可以说就是这中基于堆栈的指令代码的。 关于语义分析，语法制导翻译，类型检查等等部分，其实都是一种完善前面得到的抽象语法树的过程。比如说，我们写C语言程序的时候，都知道，如果把一个浮点数直接赋值给一个整数，就会出现类型不匹配，那么C语言的编译器是怎么知道的呢？就是通过这一步的类型检查。像C++语言这中支持多态函数的语言，这部分要处理的问题就更多更复杂了。大部编译原理的教材在这部分都是讲解一些比较好的处理策略而已。因为新的问题总是在发生，旧的办法不见得足够解决。 本来说，作为一个编译器，起作用的部分就是用户输入的源程序到最终的代码生成。但是在讲解最终代码生成的时候，又不得不讲解机器运行环境等内容。因为如果你不知道机器是怎么执行最终代码的，那么你当然无法知道如何生成合适的最终代码。这部分内容我自我感觉其意义甚至超过了编译原理本身。因为它会把一个计算机的程序的运行过程都通通排在你面前，你将来可能不会从事编译器的开发工作，但是只要是和计算机软件开发相关的领域,都会涉及到程序的执行过程。运行时环境的讲解会让你更清楚一个计算机程序是怎么存储，怎么装载，怎么执行的。关于部分的内容，我强烈建议大家看看龙书上的讲解，作者从最基本的存储组织，存储分配策略，非局部名字的访问，参数传递，符号表到动态存储分配(malloc,new)都作了十分详细的说明。这些东西都是我们编写平常程序的时候经常要做的事情，但是我们却少去探求其内部是如何完成。 关于中间代码生成，代码生成,代码优化部分的内容就实在不好说了。国内很多教材到了这部分都会很简单地走马观花讲过去，学生听了也只是作为了解，不知道如何运用。不过这部分内容的东西如果要认真讲，单独开一学期的课程都讲不完。在《编译原理及实践》的书上，对于这部分的讲解就恰到好处。作者主要讲解的还是一种以堆栈为基础的指令代码，十分通俗易懂，让人看了后，很容易模仿，自己下来后就可以写自己的代码生成。当然，对于其它代码生成技术，代码优化技术的讲解就十分简单了。如果要仔细研究代码生成技术，其实另外还有本叫做《Advance Compiler Desgin and Implement》,那本书现在由机械工业出版社引进的，十分厚重，而且是英文原版。不过这本书我没有把它列为推荐书给大家，毕竟能把龙书的内容搞清楚，在中国已经就算很不错的高手了，到那个时候再看这本《Advance Compiler Desgin and Implement》也不迟。代码优化部分在大学本科教学中还是一个不太重要的部分，就是算是实践过程中，相信大家也不太运用得到。毕竟，自己做的编译器能正确生成执行代码已经很不错了，还谈什么优化呢？ 关于实践 编译原理的课程毕竟还只是讲解原理的课程，不是专门的编译技术课程。这两门课程是有很大的区别的。编译技术更关注实际的编写编译器过程中运用到的技术，而原理的课关注讲解其基本理论。但是计算机科学本身就是一门实践性很强的课程，如果能够学以致用，那才叫真正的学会。李阳在讲解疯狂英语的时候就说到，只要当你会实际中运用一个单词一个词组的时候你才能叫学会了这个单词或者词组，而不是只是知道了它的拼写和意思。其实任何学习都是一样的，如果缺少了实践的结合，你不能算学会。 编译原理的课程主要就是讲解编译器产生的理论和原理，那么很简单，自己写个编译器就是最好的实践过程了。不过你得小心，编译系统可能是所有软件系统中最复杂的系统之一,不然为什么大学里面还会把编译器的编写开成一门叫做编译原理的课程来讲？我很佩服那些学了操作系统原理就开始自己写操作系统，学了编译原理就开始自己写编译器的人们，确实，在中国，敢这么做的学生太少了。且不管你这样做能不能做成功，至少有了这个尝试，会让你的程序设计，系统规划安排的功底增进不少。我下面给出一些关于实践过程中可能会遇到的困难，希望能够在你陷入困境的前帮你一把。 1. Lex和Yacc. 这两工具是作为词法分析很语法分析的工具。如果你自己写一个编译器，我十分不建议你连词法分析这种事情都亲手来写。Lex和Yacc应该是作为每本编译原理的教材的必备内容，可是在国内的教材中缺很少看到。这两个工具是Unix系统下的小东西，如果你要在Windows中运用，那么你最好去下在cygwin这个软件。它是个在Windows下模拟Unix的东东，里面就包含了flex.exe和bison.exe(yacc)这两个工具.这两个工具使用起来还挺麻烦的(其实unix 下的很多十分有用的工具都是这样), 不过在《编译原理与实践》这本书上对于这两个工具的讲解十分详细,还列举了不少实际的例子。 2. 做解释型语言比做生成机器代码的编译器简单。虽然说，做解释型的编译器，像Java那样的，你还得自己去写解释器，不过这样你就不必去查找机器代码的资料了。如果你做生成的最终机器代码编译器可能会遇到问题还有就是寄存器为基础的代码生成方法。前面说过，如果你生成的是以堆栈为基础的代码，那么其代码生成过程十分简单，需要考虑的东西也不多，如果你考虑最终的机器代码生成的话，你必须考虑机器的寄存器如何分配等麻烦的问题。 3. 考虑用别人已经生成的语法文件，尽量不要自己动手写词法文件和语法文件.以前一个朋友曾经说过,写出一个好的程序语言的语法定义,就几乎完成了一个编译器的一半.确实是这样,语法文件的编写是个很难的事情.现在网上到处都可以找到比如C语言,C++,Java, Tiny C,Minus C等语言的词法文件和语法文件,你完全可以自己下下来来用. 在《编译原理及实践》的书中，作者给出了一个Tiny C的全部代码.我自我感觉作者的这个编译器做得很不错,相对于其它php,perl等语言的源代码来说,简单得多,容易看懂,而且很清晰地展现了一个完成的编译系统的实现过程.其源代码可以在作者的网站上下载.

2004-4-27 10:21 sky-walker

鉴于不时的有人PM给偶，询问一些东东，特公布一些资料，以求安宁 <img src='style_emoticons/default/grin.gif' border='0' style='vertical-align:middle' alt='grin.gif' /> 下载网站： <a href='http://www.monmouth.com/~wstreett/lex-yacc/lex-yacc.html' target='_blank'>http://www.monmouth.com/~wstreett/lex-yacc/lex-yacc.html</a> 国外网站： <a href='http://www.faqts.com/knowledge_base/index.phtml/fid/1249' target='_blank'>http://www.faqts.com/knowledge_base/index.phtml/fid/1249</a> 国内的： 开放协作论坛 <a href='http://www.clinux.org/forum/index.php?categoryid=4' target='_blank'>http://www.clinux.org/forum/index.php?categoryid=4</a>

2004-4-27 10:30 sky-walker

Flex用法 <a href='http://www.monmouth.com/~wstreett/lex-yacc/flex_1.html' target='_blank'>http://www.monmouth.com/~wstreett/lex-yacc/flex_1.html</a> Bison用法 <a href='http://www.monmouth.com/~wstreett/lex-yacc/bison.html' target='_blank'>http://www.monmouth.com/~wstreett/lex-yacc/bison.html</a> 文件太大了，自己进去看吧，希望有用；没用的话。。。也别找偶 <img src='style_emoticons/default/grin.gif' border='0' style='vertical-align:middle' alt='grin.gif' />

2005-3-30 13:00 yokol

Walker 真乃强人！小弟在这里问一个问题： N ([0-9]+|(0X|0x)[0-9A-Fa-f]+) B ([0-9A-Fa-f][0-9A-Fa-f]?) W ([0-9A-Fa-f][0-9A-Fa-f]?[0-9A-Fa-f]?[0-9A-Fa-f]?) %a 16000 %o 19000 %e 6000 %k 4000 %p 25000 %n 2000 V680 {W}:{W}:{W}:{W}:{W}:{W}:{W}:{W} V670 ::{W}:{W}:{W}:{W}:{W}:{W}:{W} V6604 {W}:{W}:{W}:{W}:{W}:{W}:{N}\.{N}\.{N}\.{N} 的一部分倒是明白，但是后面的就不清楚了：（ 多谢指教

2007-6-20 17:21 刈烨

大哥，小弟求助啊！帮帮了！

我们要做个说明语句的词法分析器的课程设计，大哥些帮忙啊！
小弟不胜感激！