最近在看一本 [日] 前桥和弥写的《自制编程语言》，很感兴趣，里面第二章的案例就是试做一个计算器。
编程语言分为编译型语言和解释型语言两种。
编译语言比较有代表性的是 C/C++，最终输出机器码可执行文件。
想要输出机器码的话，必须要掌握机器码才行，即使学习了机器码并写出了编译器，也无法输出其他型号 cpu 运行的文件。
机器码的编程语言优点是运行速度非常快，但是学习起来非常有难度 = = 所以这本书选择了开发解释性语言 = = 可以用编程语言扩展应用程序。。。
解释性语言的解释一词来自英语的 interpreter，是“能进行翻译的意思”，程序员编写的代码通过解释器一边解析一边运行，但除了 DOS 的批处理脚本或 Unix 的 SHELL 脚本这么接近该定义，大多数解释型语言都会将源代码临时转换为某种中间形态。
这有段代码，
if(a == 10) {
printf("hoge\n");
} else {
printf("piyo\n");
}
大多数编程语言，都会将上面代码转换成一种叫语法分析树的东西。如上代码做成分析树如下图所示。
解释器会将源码或者分析树解析为字节码这种中间形态，并且一边解析一边运行，但是解释器并不会将源码翻译为机器码。
下面开始介绍计算器实例。
首先介绍 yacc 和 lex 这两个工具，一般编程语言的语法处理，都会有一下的过程。
- 词法分析 将源代码分割为若干个记号（token）的处理
- 语法分析 将从记号构建分析树 (parse tree) 的处理，分析树也叫语法树或者抽象语法树。
- 语义分析 经过语法分析生成的分析树，并不包含数据类型等语义信息，因此在语义分析阶段，会检查程序中是否含有语法正确但是存在逻辑问题的错误。 一般来说执行语义分析时主要会做数据类型的解析以及错误的检查。
- 生成代码 如果是 C 语言等生成机器码的编译器或 Java 这样生成字节码的编译器，在分析树构建完毕后会进入代码生成阶段。
比如说有如下代码：
if(a == 10) {
printf("hoge\n");
} else {
printf("piyo\n");
}
执行词法分析后，将被分割成如下所示的记号（每一个块就是一个记号）。
If ( a == 10 ) { printf ( “ hoge\n” ) ; } else { printf ( “piyo\n” ) ; }`
语法分析树如图：
执行词法分析的程序称为词法分析器（lexical analyzer)，lex 的工作原理就是根据词法规则自动生成的词法分析器。
执行语法分析的程序称为解析器(parser)，yacc 就是能根据语法规则自动生成解析器程序。
yacc 和 lex 一起使用可以将一个特殊格式的定义文件输出为 C 语言代码。
书中第一个例子是制作一个简单的计算器，因为一开始就讲“用 yacc/lex 制作编程语言”肯定会吃不消的。。我们先来看看有什么功能吧。。
看得出来 mycalc 可按照优先级输出结果。虽然使用了整数，但是内部是用 double 实现的运算。
lex 是自动生成词法分析器的工具，通过扩展名为.l 的文件，输出词法分析器的 C 语言代码。
词法分析器是将输入的字符串分割为记号的程序，因此必须首先定义 mycalc 所用到的符号。
- 运算符。在这个例子中可以使用四则运算，即 +、-、*、/
- 整数，比如 233
- 实数，比如 2.33
- 换行符。输入换行符进行运算，所以这也是个记号。
在 lex 中使用正则表达式定义记号。下面是 mycalc.l 文件。
%{
#include <stdio.h>
#include "mycalc.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 temp;
sscanf(yytext, "%lf", &temp);
yylval.double_value = temp;
return DOUBLE_LITERAL;
}
[\t] ;
. {
fprintf(stderr, "Lexical error!\n");
exit(1);
}
%%代码第 8 行为 %%，此行之前部分叫做定义区域。在定义区域内，可以定义初始状态或者为正则表达式命名。
| 记号 | 含义 |
|---|---|
| ADD | 加法运算符 + |
| SUB | 减法运算符 - |
| MUL | 乘法运算符 * |
| DIV | 除法运算符 / |
| CR | 回车符 |
| DOUBLE_LITERAL | double 类型的字面常量 |
第 4-6 行定义了 yywrap()函数，没有这个函数的话需要连接 lex 库文件。
第 9-24 行是规则区域，使用正则表达式描述记号。
在规则区域中遵循这样的书写方式：一个正则表达式后面紧跟若干个空格，后接 C 代码。如果输入匹配正则表达式，则执行后面的 C 代码。这里的 C 代码部分称为动作(action)。
第 9-13 行中会找到四则运算符以及换行符，通过 return 返回其特征符，特征符是在 y.tab.h 中用 #define 定义，用来区分记号种类的代号。
对于 + 或者 - 这样的记号只需要关注其记号种类即可，如果是 DOUBLE_LIBTERAL 记号，则记号的种类和记号的值都必须传递给解析器。
第 14 行匹配一个数值，记号的原始字符（比如输入 123.45 这个记号的原始字符就是 1"123.45"）会在相应动作中的被名为 yytext 的全局变量引用。
动作解析的值会存放在名为 yyval 的全局变量中，这个全局变量本质是一个联合体(union)，可以存放各种记号的值（在这个计算器程序只有 double 的值）。联合体的定义部分写在 yacc 的定义文件 mycalc.y 中。
到 26 行，出现一次 %%。表示规则区域的结束，这之后的代码称为用户代码区域。用户代码区域可以随意编写任意 C 代码，与定义区域不同的是，用户区域无需使用％{％}包裹。
yacc 是自动生成语法分析器的工具，输入扩展名为.y 的文件，就会输出语法分析器的 C 语言代码。mycalc.y 代码如下。
%{
#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("\e[32m[Netcan-Soft]>>\e[0m \e[36m%lf\e[0m\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, "\e[31m 解析错误: %s\e[0m\n", yytext);
return 0;
}
int main() {
extern int yyparse(void);
extern FILE * yyin;
yyin = stdin;
if(yyparse()) {
fprintf(stderr, "\e[31m 错误！\e[0m\n");
exit(1);
}
}第 1-5 行与 lex 相同，使用％{％}包裹一些 C 代码。
第 6-9 行声明了记号以及非终结符的类型。前面提过记号不仅要包含类型，还需要包含值。记号可能有很多类型，这些类型都声明在集合（共用体）中。
非终结符是由多个记号共同构成的，即代码中的 line_list、line、expression、term 这些部分。为了分割非终结符，非终结符最后都会以一个特殊记号结尾，这种记号称为终结符。
10-11 行是记号的声明。ADD、SUB、MUL、DIV、CR 等记号只需要包含记号的类型即可，而值为 DOUBLE_LITERAL 的记号，其类型被指定为 <double_value>，这里的 double_value 来自上面代码中 %union 集合中的一个成员名。
12 行声明了非终结符的类型。
与 lex 一样，13 行的 %% 为分界，之后的为规则区域。yacc 的规则区域是由语法规则以及 C 语言编写相应的动作两部分组成。
可将语法规则简化为下面的格式。
A
: B C
| D
;
即 A 的定义是 B 和 C 的组合或者 D。
14-16 行的书写方式，为了表示该语法规则在程序中可能出现一次以上。例如在 mycalc 中，输入一行后回车进行计算，之后还可以继续输入。
term
: primary_expression
| term MUL primary_expression
{
$$ = $1 * $3;
}
这些表达式中，$1、$3的意思是分别保存了 term 与 primary_expression 的值。即 yacc 输出解析器的代码时，栈中相应位置的元素将会被转换为一个能表述元素特征的数组引用。$$这里这代表 term 的值。
如果没有书写动作，例如 43-44 行，yacc 会自动补全一个 { $$ = $1 } 的动作，$$与 $1 的数据类型，分别与其对应的记号或者非终结符的类型一致。例如，DOUBLE_LITERAL 对应的记号被定义为：
%token <double_value> DOUBLE_LITERAL
expression、term、primary_expression 的类型则为：
%type <double_value> expression term primary_expression
这里的类型被指定为<double_value>，其实是使用了 %union 部分声明的联合体 double_value 成员。
生成可执行文件步骤如下，
# lex mycalc.l
# yacc -dv mycalc.y
# gcc y.tab.c lex.yy.c -o mycalc
