使用yacc的方法

使用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