使用yacc的方法

被遗忘的强大的工具

UNIX系统的功能的之所以强大，不是在于它本身有多好的内核，

而是在于它为我们提供了很多能完成小功能的命令,而这些命令的组

合使用使得它更加的强大。其实在这里它为我们体现了这样的一个观

点：

要完成一个项目，或者是个大型的程序。应该先从小做起，然后

不断的发展壮大。

在本文中，主要为您介绍一写UNIX 系统下面的3 个命令的，似乎

它不常用。可能make用得多一些，但是他们功能确实强大。

yacc 语法分析程序生成器,可以从语言的语法描述生成语法

分析程序。

make 通过指定和控制程序对复杂的程序进行编译的程序。

lex 类似yacc的程序，主要用语生成词法分析程序。

本文主要通过一个经典的hoc(high-order calculator)程序出

发，结合笔者自身在学习过程中的一些体会为您介绍它。本文只涉及

基本原理，我们假设您懂得C语言，或者身边正好有C语言方面的书。

下面我们进入正题：

1 hoc计算器

hoc 是一个功能强大的四则运算计算程序，当然在这里我不方便

去揣摩如果让您去开发一个类似的程序您会采用什么样的思路。下面

就来看看开发一个四则运算的小程序经典思路。

首先需要向您阐述一下巴科斯-诺尔范式(Backus-Naur Form)，(正则

文法)作为一个四则运算，我们可以简单抽象成下面这样一个表达形

式

语句->表达式

表达式->token

表达式->表达式+表达式

表达式->表达式-表达式

表达式->表达式*表达式

表达式->表达式/表达式

表达式->(表达式)

或者我们用另外一个依赖关系来表达这样一个事实。

语句:表达式

表达式:token

表达式+表达式

表达式-表达式

表达式*表达式

表达式/表达式

(表达式)

其实看到这里您也许会觉得这样是否会非常得像我们平时写的

makefile文件呢？我无法回答makefile的语法和这有什么直接的联

系。但是makefile文件确实体现这样一个依赖关系的推导式的思想。

对于该疑问我们暂且放下。回归正题，其实按照严格的语法，上面的

形式语言描述是不完整的，在该文法中我们没有指定操作操作符号的

优先关系和运算符的结合性。

2 yacc程序

yacc 是一个语法分析生成器，它是叫一种语言的规范化的描述转换

成一个语法分析程序。作为yacc主要分4个阶段。

1） 描述语法（如上面所写的那样），yacc 可以帮我们检查我们描

述的语法的错误以及二义性。

2） 语法对应的C程序。

3） 词法分析程序。（词法的块一般标记为token）。

4） 控制流程，调用yacc生成的语法分析程序。

yacc 一般是将语法和语义操作封装为一个语法分析函数，名字是

(yyparse)。如果没有任何问题，yacc将为我们创建一个C程序文件，

我们可以使用任何的C编译器去编译该文件。值得我们注意的是语法

分析程序的入口必须命名为yylex。

因为每次yyprase在进行语法分析的时候都会去调用一个名为yylex

的函数。不过这一切都不是固定的。如果您有兴趣的话您可以在yacc

创建了C程序文件后，手工去修改一下函数的名字也可以的。

下面再为您介绍一下yacc的输入文件格式：

%{

C语句

%}

Yacc定义：词法标记(token),语法变量等

%%

语法规则动作

%%

其它的C代码

这就是一个yacc的输入原文件的格式，在经过yacc处理后会把输出

一个名字为y.tab.c的文件。该文件的格式一般是

%{和%}之间的C语句

第二个%%后的C语句

我真得很欣赏yacc 程序的设计者，它直接为我们生成C 文件，而不

是已经被编译过的目标文件。在这一点上，我觉得真是做得太好了。

其实在这一点上它体现了UNIX 的处理一般方法。其实该方法非常的

灵活。当我们有了新的想法我们甚至可以移植代码，正是因为这个原

因，我们得以将代码移植到WINDOWS平台上去。在本文的最后将为您

介绍如何将y.tab.c在WINDOWS平台下面的Visual Studio IDE环境

编译。不过yacc 确实强大，但是我们要想掌握它的话也是非常的不

容易，但是当您一旦会用了yacc 后您回发觉您掌握它而花费的努力

是值得的。它提供了一个可以随语言定义变化而随意快速生成C原代

码的一个途径。

下面我们首先来看看一个 yacc的输入文件

%{

/* 该部分在本文中未涉及到*/

%}

%token NUMBER

%left '+' '-'

%left '*' '/'

%%

list:

|list 'q' {exit(0);};

|list '/n'

|list expr '/n' {printf("/t%ld/n", $2);}

;

expr: NUMBER {$$ = $1;}

|expr '+' expr {$$ = $1 + $3;}

|expr '-' expr {$$ = $1 - $3;}

|expr '*' expr {$$ = $1 * $3;}

|expr '/' expr {$$ = $1 / $3;}

|'(' expr ')' {$$ = $2;}

;

%%

#include <stdio.h>

#include <ctype.h>

int lineno;

void main(int argc, char *argv[])

{

yyparse();

}

int yylex()

{

int c;

while((c = getchar()) == ' ' || c == '/t')

;

if(c == EOF)

return 0;

if(isdigit(c))

{

ungetc(c, stdin);

scanf("%d", &yylval);

return NUMBER;

}

if(c == '/n')

lineno++;

return c;

}

yyerror(char *s)

{

fprintf(stderr, "%s", s);

fprintf(stderr, " near line %d/n", lineno);

}

我分别用3种颜色区别了yacc输入文件的3个部分，这部分程序

包括了许多的信息，在这里不一一解释，也不详细描述分析器如何来

工作。更多的信息请参考yacc手册。希望读者能更多的自己去思考。

首先来解释一下第一部分。提供选择的规则用|分割，当输入的语

法规则被识别出后，该动作将被执。对应的C代码动作在最后被体现

出来，如下所示：

它的基本结构是

| 动作标志 {C代码}

值得注意的地方是C 代码最后一定要写上;yacc 无法为我们检查

这一问题，只是这个问题将在最后的C编译器检查出来，我曾经就遇

见过一次，又是初学。都不知道该从什么地方去检查问题。$n($1,$2)

分别表示子成分的返回值，$$是整个表达试的返回值。一般来说$$

就是$1，除非用户将它设置为其它的值。那么在上面中，我们可以这

样去理解。一个换行符号(/n)可以被识别为一个list。换句话说就

是一个语句的结束点。这有点像我们的C 语法中必须要用符号(;)来

结束一句一样的道理。

如果您学过编译原理，我们也可以从推导式的概念上来理解这一

个问题。List 可以推导出(;)(expr;)这样2 种可能性。expr 可以同

理去这样理解。这样把问题推导下去。下图是一个语法分析过程的推

导树。

/n

list

2

expt

expr

+ *

toke

n

3 4

toke

n

toke

n

好了，我们继续再看看蓝色部分的代码，在当中使用了%left 来

指定结合的方式。这样意味着(a-b)-c不会被解释成a-(b-c),您可以

试着将%left改为%right看看有什么效果。

关于C 代码的部分，我不想做太多的详细解释了。您只需要记着

yyprase,yylex,yyerror 就行了。有yyprase 是yacc 程序将会为我

们按照我们的描述文法创建的解析器代码，yylex是词法分析的部分

（将句子打断为token 串的功能）yyerror 是yacc 程序统一的错误

出口点。

3 编译

在看懂上面的代码后，OK，下面我们继续看看如何使用yacc生成

语法分析程序，您完全可以使用您个人最喜欢的文本编辑器去编辑这

样一个文件，您只需要保证您编辑的文件的内容和上面的一样。我们

假设您保存的文件的名字是guoguo.y

在shell命令行中执行命令:

yacc guoguo.y

看看屏幕有没有什么错误的提示？如果有的话，请仔细检查一下

guoguo.y文件里面有没有不符合yacc输入文件格式的地方。如果没

有错误，那就恭喜您了，实在就太棒了。我们可以继续进行下面的实

验。

下面一步，我们查看一下当前目录下面是不是有个y.tab.c 的文

件。这简直太好了。yacc 已经为我们创建了一个可以按照我们指定

的文法进行语法分析的一个c原程序。这一切结果我们都要感谢yacc

的作者steve Johnon 先生。呵呵，还是回归正题吧。我们拿到这个

c程序可以直接编译连接它。试着在shell命令中执行命令：

cc –o guoguo y.tab.c。

编译它，如果一切顺利的话，我们将得到一个名字为guoguo的执

行程序。如果今天您运气差了点的话，可能会在cc 编译的时候会报

告一些错误出来，无法创建guoguo 执行程序。不过您不要紧张，让

我们一起来和您分析一下可能的错误。下面我把我在学习过程中曾经

遇到过的问题列举出来。

问题1：

cc -o guoguo y.tab.c

"hoc.y", line 10: error: Syntax error before or at: }

"hoc.y", line 21: warning: statement not reached

"hoc.y", line 43: error: Syntax error before or at: <EOF>

*** Error code 1 (bu21)

这样的错误，CC编译器已经值出在文件hoc.y的10行出了错误。

这样的错误一般来说是规则的对应动作C 函数没有;号结束符号.对

于稍有一些经验的程序员来说这样的问题其实很好定位的。但是为什

么我要在这里说这个问题呢？如果您观察够仔细的话，您也许会注意

到我们编译的是y.tab.c文件，我们用cc编译器是在编译y.tab.c 文

件呀？它怎么能知道是hoc.y 文件的第10 行出了问题了呢？oh my

god!我相信上帝不会和我们开这个玩笑的。这一点问题您必须要了解

清楚，其实它非常有意思的。仔细看看y.tab.c 文件后您知道，在

y.tab.c文件中加上了#line 的C预处理命令。这个#line 的预处理

命令是告诉C编译器如何定位y.tab.c的行号处理的。我在这里扩展

一下，如果您经常都在写UNIX下面的ec程序，通常我们常常可以在

日志中通过__FILE__宏来得到行号，要知道ec 程序都是被预先处理

成.c的文件然后再又C编译器去编译它。因为ec程序和c程序之间

一些EXEC SELECT,EXEC UPDATA……等代码的处理将首先被ec 预编

译器解释成一些C 代码。这样一来ec 程序的行数和C 程序的行数有

有差别了。但是__FILE__只能处理C程序的那个行号。那么我们是否

就无法知道在ec程序中的行号了呢？其实不然。在ec的预编译器中

都加了#line指令的处理。这就是为什么我们能直接能在日志文件中

看到EC 原程序的行数。而不是被预编译为C程序的行数了。如这样：

xxx.ec->L->38 了。至于#line 具体的工作是怎么完成的，我在这里

不再描述，读者可以自行去研究。

好了，这个就是我在编译y.tab.c 的程序的时候遇见了的一个问

题。当解决了这个问题后。就得到C 编译器为我们生成的执行程序

guoguo。执行一下看看

1+2 Enter

3

2*3 Enter

0

2.0+1.2 Enter

Syntax error near line 2

上面的Enter 部分是表示我在键盘敲入了Enter 键。千万不要以

为是我敲入了Enter字母哦！从上面的结果来看，好象有逻辑问题。

在加法运算的时候guoguo 程序能正常工作。但是剩法的时候缺没办

法正常的工作。另外一个问题，我们目前的代码无法完成浮点类型的

计算。这个结果有2个问题值得我们去思考。有兴趣的读者可以试去

解决它。

1． 为什么2*3的结果是0

2． 我们怎么完成浮点数的运算。

由于本文仅仅是入门级的对yacc介绍，所以例子也是个非常的简

单的例子，其实用用yacc 还可以完成更加复杂的语法分析的程序，

有兴趣的朋友建议可以在网上去搜索一下hoc6的yacc的原程序。它

对我们学习yacc将会有非常高的知道价值。yacc所创建的分析器程

序，是采用LALR(1)设计的，在《UNIX 程序员手册》中有对中有对

yacc 非常详细的描述。另外它还分析了其它类似的分析器产生器的

原理。也许您还可以设计出来采用递归下降法的代码生成器。

4 y.tab.c代码的移植问题

有时候我们可能需要我们的语法分析程序y.tab.c 能够运行的

WINDWOS平台上。其实不难，只需要将y.tab.c的程序复制到WINDOWS

上去。只是需要在编译的时候需要注意2点问题。

1. 屏蔽y.tab.c 中的#include <unistd.h>语句，在cl.exe 中无

这个文件。这个文件主要是好象描述一些POSIX 标准的头文件

的。在LINUX下面它主要描述0x80系统调用的函数原形。也许

在这一点TMD 有点搞笑，我不知道Visual Studio 环境中为什

么没这个文件。不过你还可以试着使用著名的DOS下面的djgpp

（GUN for windows (32bit)gcc 编译器）编译器去编译它,编

译出来的程序完成可以在32位环境下使用，但是它好象编译出

来的程序不符合PE 执行文件格式，NT 系统下面有些程序好象

无法正常运行！它可以不修改#include <unistd.h>一句。

2. 如果您是在命令行中编译y.tab.c编译的时候cl.exe中一定要

加上/D "__NO_GETTXT__" 参数。因为WINDOWS 平台上没有

_gettxt函数。如果您是在IDE需要在您在project->settings

中的C/C++标签中的Preprocessor definitions 中加上宏

__NO_GETTXT__。

5 结束言

首先，语言开发工作很有用，它可以使我们集中精力去完成语法

的规则的定义。例如我们的设计我们自己系统的脚本文件。然后yacc

又提供了给我们一个非常广阔的空间，可以让我们自由的去发挥。

其次，把工作当做语言来开发，而不仅仅是“写一个程序”，这个

思考方式是具有一定的意义的。它给我们指导了一个思想。一个程序

将组织为语言处理器要求句法规则，换句话说就是用户接口。并构造

实现它。这一点也许和我们传统的编程概念不太一样。其实它体现了

“语言”并不局限于我们传统的编程语言-它还包括了很多其它的东

东。

最后，UNIX下面的大量的小工具；单独或者是组合使用；帮助我

们完成了很多的机械的工作。这也许就正是显示它存在的价值和意义

吧。

欢迎大家能来邮件和我一起讨论本文中的一些相关的问题。至于

本文中提到的make 和lex 命令由于时间关系，我会在以后再为大家

描述。文中不正确的地方尽请大家能指正。

我将在下一期的文中，为大家整理一篇自己在曾经网络编程上遇

见的一些问题《TCP服务端编程一些问题》文章。

天用唯勤 阳凌

yl.tienon@gmail.com

2006-07-23

本文地址：http://www.45fan.com/a/question/72008.html