2.1 yacc/lex是什么

如前文所述，本书会使用yacc和lex这两个工具。本章中将利用yacc/lex尝试编写一个简单的计算器程序。

一般编程语言的语法处理，都会有以下的过程。

1．词法分析

将源代码分割为若干个记号（token）的处理。

2．语法分析

即从记号构建分析树（parse tree）的处理。分析树也叫作语法树（syntax tree）或抽象语法树（abstract syntax tree, AST）。

3．语义分析

经过语法分析生成的分析树，并不包含数据类型等语义信息。因此在语义分析阶段，会检查程序中是否含有语法正确但是存在逻辑问题的错误。

一般来说执行语义分析时主要会做数据类型的解析以及错误检查，但本书中使用的crowbar语言并没有设置变量类型，因此也不会进行数据类型的检查，所以crowbar并不存在一个明确的语义分析阶段（Diksam中是存在这个阶段的，位于fix_tree.c源文件中，请参考本书6.3.4节）。

4．生成代码

如果是C语言等生成机器码的编译器或Java这样生成字节码的编译器，在分析树构建完毕后会进入代码生成阶段。

比如说有如下的代码：

                  if（a == 10）{
                      printf（"hoge\n"）;
                  } else {
                      printf（"piyo\n"）;
                  }

执行词法分析后，将被分割为如图2-1所示的记号（每一个块就是一个记号）：

图2-1 分割为记号

对此进行语法分析后构建的分析树，如图2-2所示（同图1-1）。

图2-2 if语句的分析树

执行词法分析的程序称为词法分析器（lexical analyzer）。lex的工作就是根据词法规则自动生成词法分析器。

执行语法分析的程序则称为解析器（parser）。yacc就是能根据语法规则自动生成解析器的程序。

顺便说一下，yacc是“Yet Another Compiler Compiler”的缩写。顾名思义，Compiler Compiler就是生成编译器的编译器。yacc其实只能生成编译器的一部分（解析器部分），却自称编译器的编译器，未免有些名不副实。而在yacc诞生时还因为存在其他几个编译器的编译器，所以yacc的作者干脆取“又一个（Yet Another）编译器的编译器”之意，起名为yacc。lex则只是简单地取自lexical analyzer。

yacc和lex一起使用，可以将一个特殊格式的定义文件输出为C语言代码。

因为两者都是很老的工具，所以数据传递都采用全局变量的方式，现在看起来实在有些简陋。即便如此，至少yacc仍然作为Perl、Ruby等语言的语法处理器活跃在第一线。词法分析器则相对简单，完全可以自己编写，所以正式的编程语言一般都不会使用lex。

yacc与lex在UNIX的标准环境下大多都已经预装了，在Windows等环境一般没有预装，所以需要使用其免费的替代品bison和flex（获得方法请参考1.6.1节）。

          a+++++b;