Preface
当今世道，各种高级语言百花齐放。然而会有人发出这样的疑问–计算机真的能够识别这么多语言吗？稍微有点常识的人都知道，这显然是不可能滴！在计算机的世界里，他们能够直接识别的只有机器语言。然而，由于机器语言对人类不够友好，所以人们才发明了汇编，c，Java…许许多多的人类易读的编程语言，所以我个人对编程语言的理解一直是其实他们就是机器语言的语法糖，而编程语言的创造过程，就是定义一种合理的，没有二义性的语法规则，然后就是通过直接或间接的方式实现该语法到机器语言的转换过程。既然是这样的话，那么我们就很容易想到，计算机语言是一个自我完善的过程：首先我们定了一种非常简单的 x1(这里只是用来举例说明，有没有 x 语言有待考证)语言，然后用机器语言实现了这个非常简单的 x1 语言的编译器，创造了 x1 语言，实现了非常简单的新特性，然后我们再用 x1 语言(相对于机器语言较高级)实现了另一些新的特性的 x2 语言的编译器，创造了 x2 语言，…，如此下去，人们创造了汇编语言，从而创造了 c 语言，接着创造了世界上最好的语言 PHP(不知道是不是真的，反正大家都习惯这么说)。 在各种高级语言越来越强大的今天，我们可能很难再会去接触最原始的东西，高度封装确实提高了生产力，降低了学习成本，但是也使得现代程序员将太多精力花在了各种说明书上，而不清楚其本质。 毕业一年多，工作了一年多，对于计算机编程有了自己的看法，不再像在大学的时候认识的那样肤浅，反而觉得大学中学习的知识才是真正的干货，不禁感叹曾经浪费掉了大好光阴。好在陶渊明有词云：“悟已往之不谏，知来者之可追”。 闲暇之余，扒开 PHP(这里之所以是 PHP 并不因为他是世界上最好的语言，只是因为我目前从事的是 PHP 开发的工作而已)源码，了解了其内部构造和实现原理，百看不一练。今天就初步学习 yacc/lex 了，记录在我的博客中，以便以后翻阅巩固。
过程简述
一般来说编程语言的解释执行过程如下：
ONE. 词法分析 将源代码拆分成若干 Token 的过程
TWO.语法分析 将 Token 构建成 Syntax Tree 的过程
THREE.生成执行码 生成可执行文件
yacc（Yet Another Compiler Compiler）
下面是 wikipedia 中对 yacc 的描述
Yacc is a computer program for the Unix operating system. It is a Look Ahead Left-to-Right (LALR) parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specifically a LALR parser, based on an analytic grammar written in a notation similar to Backus–Naur Form (BNF). Yacc itself used to be available as the default parser generator on most Unix systems, though it has since been supplanted as the default by more recent, largely compatible, programs.
其安装非常简单
sudo apt-get install bison
lex/flex
lex 是一个生成词法分析器的工具。Lex 读进一个代表词法分析器规则的输入字符串流，然后输出以 C 语言实做的词法分析器源代码。传统上，lex 属于商业软件，但是有些根据原本 AT&T 代码这些版本的 Lex 可以以公开源代码的形式获得，并被视为某些系统的一部分，例如说 OpenSolaris 和贝尔实验室九号项目。另一个有名的 Lex 公开源代码版本是 flex，代表"快速的词法分析器"（fast lexical analyzer）
在 linux 下安装
sudo apt-get install flex
practice
- 实现一个简单的计算程序
首先定义 lex 规则，其扩展名为.l，在 lex 中可以很容易读懂其定义的规则，因为他用到的是正则表达式。
%{
/*
|------------------------------------------------------------------
| linger test
|------------------------------------------------------------------
| @author : liubang
| @date : 16/10/27 下午8:28
| @copyright : (c) iliubang.cn
| @license : MIT (http://opensource.org/licenses/MIT)
|------------------------------------------------------------------
*/
#include <stdio.h>
#include "y.tab.h"
int yywrap(void)
{
return 1;
}
%}
%%
"+" return ADD;
"-" return SUB;
"*" return MUL;
"/" return DIV;
"\n" return CR;
([1-9][0-9]*)|0|([0-9]+\.[0-9]+) {
double d;
sscanf(yytext, "%lf", &d);
yylval.double_value = d;
return DOUBLE_LITERAL;
}
[ \t] ;
. {
fprintf(stderr, "lexical error.\n");
exit(1);
}
%%
可以看到以上的代码主要包含两部分，%{ %}包含的部分和\%\% \%\%包含的部分。前一部分叫定义区块, 后者是规则区块，定义区块内的代码将会被原样输出，在定义区块中#include "y.tab.h"将会在 yacc 编译其规则文件后自动生成，ADD SUB MUL DIV CR DOUBLE_LITERAL等都是在 y.tab.h 中定义的 macro。
在定义区块中，有一个名为yywrap的 function，其作用是自动 link lex 的库文件。
至于规则区块，学过正则表达式的人一看就会明白，其作用就是使用正则表达式来描述 Token。规则区块的定义为：正则表达式，后边跟上 C 代码，这些代码用{}括起来，读入的字符流满足了正则，则执行其后的代码，匹配到的原字符被保存在yytext这个全局变量中。
接着来编写 yacc 的规则，其扩展名为.y。
%{
/*
|------------------------------------------------------------------
| linger test
|------------------------------------------------------------------
| @author : liubang
| @date : 16/10/27 下午8:43
| @copyright : (c) iliubang.cn
| @license : MIT (http://opensource.org/licenses/MIT)
|------------------------------------------------------------------
*/
#include <stdio.h>
#include <stdlib.h>
#define YYDEBUG 1
%}
%union {
int int_value;
double double_value;
}
%token <double_value> DOUBLE_LITERAL
%token ADD SUB MUL DIV CR
%type <double_value> expression term primary_expression
%%
line_list
: line
| line_list line
;
line
: expression CR
{
printf(">>%lf\n", $1);
}
;
expression
: term
| expression ADD term
{
$$ = $1 + $3;
}
| expression SUB term
{
$$ = $1 - $3;
}
;
term
: primary_expression
| term MUL primary_expression
{
$$ = $1 * $3;
}
| term DIV primary_expression
{
$$ = $1 / $3;
}
;
primary_expression
: DOUBLE_LITERAL
;
%%
int yyerror(char const *str)
{
extern char *yytext;
fprintf(stderr, "syntax error near %s\n", yytext);
return 0;
}
int main(void)
{
extern int yyparse(void);
extern FILE *yyin;
yyin = stdin;
if (yyparse()) {
fprintf(stderr, "Core Dump!\n");
exit(1);
}
}
yacc 规则定义跟 lex 相似，都用到了\%{\%} \%\%来包含代码块。
同样的是\%{\%}包裹的代码将被原样输出。
在\%union定义中，声明了记号和非终结符的类型，其最终会被编译成一个 c 语言的 union。这里定义了一个 int 类型的 int_value 和 double 类型的 double_value。
\%token开头的行是 Token 的声明，所有用到的 Token 类型都在这里定义。对于ADD SUB MUL DIV CR等记号只需要包含其类型即可，而对于值为DOUBLE_LITERAL的 Token，其类型被指定为<double_value>，这里的 double_value 正是来自于前面声明的 union 中的成员之一。
%%包裹的部分叫做规则区块，由语法规则和 C 语言编写的相应的行为两部分构成。在 yacc 中使用了类似于 BNF 范式来编写语法规则。由于使用了自然语言作为标记，理解上还是很容易的。下面举个简单的例子：
line_list /* 多行规则 */
: line /* 单行 */
| line_list line /* 或者多行后跟单行 */
;
line /* 单行 */
: expression CR /* 表达式后跟换��符 */
;
expression /* 表达式 */
: term /* 和项 */
| expression ADD term /* 或者表达式加上和项 */
{ /* 匹配后执行的action */
$$ = $1 + $3;
}
| expression SUB term /* 或者表达式减去和项 */
{ /* 匹配后执行的action */
$$ = $1 - $3;
}
;
term /* 和项 */
: primary_expression /* 一元表达式 */
| term MUL primary_expression /* 或者和项乘以一元表达式 */
{ /* 匹配后执行的action */
$$ = $1 * $3;
}
| term DIV primary_expression /* 或者和项除以一元表达式 */
{ /* 匹配后执行的action */
$$ = $1 / $3;
}
;
primary_expression /* 一元表达式 */
: DOUBLE_LITERAL /* 实数字面量 */
;
写好了规则，那么就来编译运行
yacc -dv foo.y
flex foo.l
gcc -std=c99 -Wall -g -o foo y.tab.c lex.yy.c
这样就生成了foo这个可执行文件
运行 foo
liubang@venux:~/workspace/c/my_lang/lex$ make run
1 + 3
>>4.000000
1/2
>>0.500000
4 * 5
>>20.000000
当然我个人在开发 c 程序的时候偏向于使用 make 工具来编译代码，这样会很方便。下面是我的 Makefile 文件:
CFLAGS = -O2 -g -Wall -std=c99
EXEC = foo
OBJS = y.tab.o \
lex.yy.o
%.c:
yacc -dv foo.y
lex foo.l
%.o: %.c
$(CC) $(CFLAGS) -o $@ -c $<
$(EXEC): $(OBJS)
$(CC) $(OBJS) -o $@
all: $(EXEC)
run: $(EXEC)
@./$(EXEC)
clean:
$(RM) $(OBJS) $(EXEC)
只需要执行make run命令即可运行！
附加
可能有人会疑惑，这玩意学着有什么用，那么有兴趣的你可以下载一份 PHP 的源代码，在 Zend(Zend 引擎核心文件)目录中你不难找到zend_language_scanner.l,zend_ini_scanner.l,zend_ini_parser.y,zend_language_parser.y这几个文件，打开其内容，是不是不再那么恐惧和陌生了呢。
Summary
本文只是初步介绍 yacc/lex 工具生成词法解析器和语法解析器的最基本用法，没有太多的阐述词法解析的原理和过程，所以更偏实践，再由于本人毕业一年多实在很久没写文章了，常常会提笔不知从何说起，所以写起来很慢，加之白天要工作，时间较紧，所以今天就到这里了，至于理论的阐述，需要时间来慢慢酝酿 😂！
评论