《自制编程语言》学习记录，内容根本是摘抄原书
其实原书并不是从头讲怎么写一个计算器的，而是上来就给了代码，对着代码解说。计算器代码的名字为
mycalc，外部齐全应用double进行运算。
1. 根底概念介绍
1.1 编程语言的语法解决个别有以下的过程：
1.1.1 词法剖析
将源代码宰割成若干个 记号 (token) 的解决。
1.1.2 语法分析
即从记号构建 分析树（parse tree）的解决。分析树也叫作 语法树（syntax tree）或 形象语法树（abstract syntax tree, AST）。
1.1.3 语义剖析
通过语法分析生成的分析树，并不蕴含数据类型等语义信息。因而在语义分析阶段，会检查程序中是否含有语法正确然而存在逻辑问题的谬误。
1.1.4 生成代码
如果是 C 语言等生成机器码的编译器或 Java 这样生成字节码的编译器，在分析树构建结束悔恨进入代码生成阶段。
比方如下的代码：
if (a == 10) {printf("hoge\n");
} else {printf("piyo\n");
}执行词法剖析后，将被宰割成如下图所示的 记号 (token):
对此进行语法分析后构建的分析树如下图：
执行词法剖析的程序称为
词法分析器（lexical analyzer），lex就是依据词法规定主动生成词法分析器
执行语法分析的程序称为解析器（parser），yacc就是能依据语法规定主动生成解析器的程序yacc和lex在 mac 上曾经预装。
1.2 lex：
lex 是主动生成词法分析器的工具，通过输出扩大名为 .l 的文件，输入词法分析器的 C 语言代码。
词法分析器是将输出的字符串宰割成记号的程序，因而必须首先定义 mycalc 所用到的记号。
mycalc所用到的记号包含如下：
○ 运算符。在 mycalc 中能够应用四则运算，即+、-、*、\。
○ 整数。如 1、2、3 等。
○ 实数。如 123.456 等。
○ 换行符。一个算式输出后，接着输出换行符就会执行计算，因而这里的换行符也应设置为记号
在 lex 中，应用 正则表达式 定义记号。
1.3 yacc：
yacc 是主动生成语法分析器的工具，输出扩大名为 .y 的文件，就会输入语法分析器的 C 语言代码。
2. 试做一个计算器
mycalc的理论运行成果如下（% 是命令提示符）：
2.1 为 mycalc 所编写的输出文件 mycalc.l 如下（用 lex 解析）：
- 第 11 行
%%，此行之前的局部叫作定义区块。在定义区块内，能够定义初始状态或者为正则表达式命名。 - 第 2 行到第 9 行，应用
%{和%}包裹的局部，是想让生成的词法分析器将这个局部代码原样输入。后续程序所需的头文件等都蕴含在这里。比方第 3 行用#include蕴含进来的y.tab.h头文件，就是之后 yacc 主动生成的头文件。上面的ADD、SUB、MUL、DIV、CR、DOUBLE_LITERAL等都是在y.tab.h中用#define定义的宏。
- 第 5 行到第 9 行定义了一个名为
yywrap()的函数。如果没有这个函数的话，就必须手动链接 lex 的库文件。 - 第 12 行到第 27 行是
规定区块。这一部分是应用正则表达式 * 去形容记号。
在规定区块中遵循如下的书写形式：一个正则表达式的前面紧跟若干个空格，后接 C 代码。如果输出的字符串匹配正则表达式，则执行前面的 C 代码。
- 第 12 行到第 16 行，找到四则运算符以及换行符，而后通过
return返回其特色符（就是在y.tab.h的宏定义）。
下面提到很屡次
记号（token），蕴含三局部含意：
对于+或-这样的记号来说，只须要关注其记号品种就能够了，而如果DOUBLE_LITERAL记号，记号的品种和值都必须传递给解析器
- 第 17 行的正则表达式是一个匹配“数值”的表带是。表达式匹配胜利的后果（即下面列举的记号三要素），“记号的原始字符”会在相应的动作中被名为
yytext的全局变量援用。并进一步应用第 19 行的sscanf()解析
对于第 17 行正则表达式的解释见这里
- 第 23 行的正则表达式
[\t]是对空格以及制表符进行匹配，对应动作为空，因而能够疏忽每一行的空白字符。 - 第 24 行的
.会匹配任意一个字符，这里用于检测是否输出了程序不容许的字符。 - 第 28 行的
%%示意规定区块的完结，这之后的代码被称为用户代码区块。用户代码区块能够编写任意的 C 代码。
2.2 为 mycalc 所辨析的输出文件 mycalc.y 如下（用 yacc 解析）：
- 第 1 行到第 5 行与 lex 雷同，应用
%{%}包裹了一些 C 代码 - 第 4 行有一句
#define YYDEBUG 1，这样将全局变量yydebug设置为一个非零值后会开启 Debug 模式，能够看到程序运行中语法分析的状态。 - 第 6 行到第 9 行申明了记号以及
非终结符的类型。非终结符是由多个记号独特形成，即代码证的line_list、line、expression、term这些局部。为了宰割非终结符，非终结符最初都会以一个非凡的记号结尾。这种记号称作终结符 - 第 10 行到第 11 行是记号的申明。
myclac所用到的记号类型都在这里定义。ADD、SUB、MUL、DIV、CR等记号只须要蕴含记号的类型就能够，而值DOUBLE_LITERAL的记号，其类型被指定为<double_value>。这里的double_value是来自下面代码中%union汇合的一个成员名（第 8 行）。 - 第 12 行申明了非终结符的类型。
- 第 13 行的
%%是分界，之后的是规定区块。yacc 的规定区块由语法规定以及 C 语言编写的相应动作两局部形成。
语法规定
在 yacc 中，会应用相似 BNF(巴克斯范式)的标准来编写语法规定。将上图的规定代码抽出并正文如下：
// 语法规定代码 2-0
line_list /* 多行的规定 */
: line /* 单行 */
| line_list line /* 或者是一个多行后接单行 */
;
line /* 单行的规定 */
: expression CR /* 一个表达式后接换行符 */
;
expression /* 表达式的规定 */
: term /* 和项 */
| expression MUL term /* 或 表达式 + 和项 */
| expression SUB term /* 或 表达式 - 和项 */
;
term /* 和项的规定 */
: primary_expression /* 一元表达式 */
| term MUL primary_expression /* 或 和项 * 一元表达式 */
| term DIV primary_expression /* 或 和项 / 一元表达式 */
;
primary_expression /* 一元表达式的规定 */
: DOUBLE_LITERAL /* 实数的字面常量 */
;为了看得更分明，能够将愈发规定简化成上面的格局：
A
: B C
| D
; 即 A 的定义是 B 与 C 的组合，或者为 D。
第 1 行到第 4 行的书写形式，示意该语法规定在程序中可能会呈现一次以上。mycalc中，输出一行语句而后回车后会执行运算，之后还能够持续输出语句，所以设计成反对呈现一次以上的模式。
请留神下面的计算器语法规定，语法规定自身就蕴含了运算符的优先程序以及联合法则。如果不思考运算法的优先程序，上文的语法规定应该如下：
expression /* 表达式的规定 */
: term /* 和项 */
| expression ADD term /* 或 表达式 + 和项 */
| expression SUB term /* 或 表达式 - 和项 */
| expression MUL term /* 或 表达式 * 和项 */
| expression DIV term /* 或 表达式 / 和项 */
;
primary_expression /* 一元表达式的规定 */
: DOUBLE_LITERAL /* 实数的字面常量 */
;yacc 解析流程
对照 语法规定代码 2-0跟踪下解析 1 + 2 * 3 的执行流程
首先，yacc 生成的解析器会保留在程序外部的栈。在这个栈中，记号会像俄罗斯方块中的方块一样，一个个堆积起来。
词法分析器分进去的记号（最后是 1）会由左边入栈并沉积到右边。
像这样一个记号进入并沉积的过程叫作
移进（shift)
mycalc所有的计算都是采纳 double 类型，所以记号 1 即是DOUBLE_LITERAL。当记号进入的同时，会触发咱们定义的规定:
primary_expression
: DOUBLE_LITERAL
; 而后记号会被换成primary_expression。
相似这样触发某个规定并进行置换的过程叫作
归约（reduce）
primary_expression进一步触发规定：
term
: primary_expression 而后被归约成term。
再进一步依据规定：
expression
: term 最终被归约为一个expression。
接下来，记号 + 进入，在进入过程中，因为没匹配到任何一个规定，所以只进行移进不做任何归约。
接下来是记号 2 进入。
通过上述同样的规定，记号 2(DOUBLE_LITERAL) 会通过 primary_expression 被归约为term。
这里记号 2 本应该匹配到如下的规定：
expression
| expression ADD term yacc 事后读取下一个要进入的记号，这里咱们被动下一个进入的会是 *，因而该当思考到记号2 会匹配到 term 规定的可能性。
term
| term MUL primary_expression 归约结束后再一次移进。
接下来记号 3 进入。
被归约为 primary_expression 后，
term、*、primary_expression这一部分将匹配规定：
term
| term MUL primary_expression 被归约为 term。
之后，expression、+、term 匹配规定：
expression
| expression ADD term 最终被归约为expression。
每次触发归约时，yacc 都会执行该规定的相应动作。比方乘法对应的执行规定：
term
| term MUL primary_expression
{$$ = $1 * $3;} $1、$3的意思别离保留了 term 与primary_expression的值。即 yacc 输入解析器的代码时，栈中相应地位的元素会转换为一个能表白元素特色的数组援用。这里的 $2 是乘法运算符（*），并不存在记号值，所以这里援用 $2 的话会报错。
$1与 $3 进行乘法运算，而后将后果赋给$$，这个后果值保留在栈中。
如果没有书写动作，yacc 会主动补全一个
{$$ = $1}的动作。当DOUBLE_LITERAL被归约为primary_expression、primary_expression被归约为term的时候，DOUBLE_LITERAL蕴含的数值也会被继承。
2.3 生成执行文件
mac 下按程序执行如下命令，就会输入名为 mycalc 的执行文件
yacc -dv mycalc.y // 运行 yacc
lex mycalc.l // 运行 lex
cc -o mycalc y.tab.c lex.yy.c // 应用 C 编译器编译留神：依照上述的命令，在新款的 MacOS 上在最初一步编译时会报错，相似问题看这。
所以想要失常编译咱们须要改一下 mycalc.y 的后面局部：
%{
#include <stdio.h>
#include <stdlib.h>
#define YYDEBUG 1
int yylex(); // 减少申明
int yyerror(const char *str); // 减少申明
%} 最终的可执行文件关上之后如下图：
整个过程会生成若干文件：
y.tab.c中蕴含 yacc 生成的语法分析器的代码，lex.yy.c是词法分析器的代码。y.tan.h是为了将 mycalc.y 中定义的记号及联合体 (union) 传递给lex.yy.c。
2.4 抵触
理论用 yacc 试做一下解析器，可能会被 抵触（conflict）困扰。所谓抵触，就是遇到语法中模糊不清的中央时，yacc 报出呃谬误。
比方 C 语言的 if 语句，就有很显著的语法含糊问题：
if (a == 0)
if (b== 0)
printf(在这里 a 和 b 都为 0n);
else
printf(这里 a 非 0n); 下面的代码中，else对应的 if 是不清晰的。这就会引起抵触。
yacc 运行时，遇到上面任意一种状况都会发生冲突。
- 同时能够进行多个归约。称为归约 / 归约抵触。
- 满足移进的规定，同时又满足归约的规定。称为移进 / 归约抵触
即使发生冲突，yacc 仍会生成解析器。如果存在归约 / 归约抵触，则优先匹配后面的语法规定，移进 / 归约抵触则会优先匹配移进规定。
将 mycalc.y 做如下批改：
// 原代码
expression
: term
| expression ADD term更为：
// 原代码
expression
: term
| expression MUL term变更悔恨产生 3 个移进 / 归约抵触：
yacc -dv mycalc.y
conflicts: 3 shift/reduce 再看 y.output 文件，前半部分：
Terminals which are not used // 没有应用 ADD 的正告
ADD
State 5 conflicts: 1 shift/reduce // 抵触信息（见下文）State 14 conflicts: 1 shift/reduce
State 15 conflicts: 1 shift/reduce
Grammar
0 $accept: line_list $end
1 line_list: line
2 | line_list line
3 line: expression CR
4 expression: term
5 | expression MUL term
6 | expression SUB term
7 term: primary_expression
8 | term MUL primary_expression
9 | term DIV primary_expression
10 primary_expression: DOUBLE_LITERAL
Terminals, with rules where they appear mycalc.y中应用 |（竖线，示意或） 书写上面的语法规定:
1 line_list: line
2 | line_list line实际上与上面的写法一样：
1 line_list: line
2 line_list: line_list line y.output文件中会给每一行规定附上编号。
下面的规定 0，是 yacc 主动附加的规定，$accept代表输出的内容，$end代表输出完结。
y.output文件的后半部分会将解析器可能遇到的所有 ” 状态 ” 全副列举进去：
state 0
0 $accept: . line_list $end
DOUBLE_LITERAL shift, and go to state 1
line_list go to state 2
line go to state 3
expression go to state 4
term go to state 5
primary_expression go to state 6
state 1
10 primary_expression: DOUBLE_LITERAL .
$default reduce using rule 10 (primary_expression)
state 2
0 $accept: line_list . $end
2 line_list: line_list . line
$end shift, and go to state 7
DOUBLE_LITERAL shift, and go to state 1
line go to state 8
expression go to state 4
term go to state 5
primary_expression go to state 6
state 3
1 line_list: line .
$default reduce using rule 1 (line_list)
state 4
3 line: expression . CR
5 expression: expression . MUL term
6 | expression . SUB term
SUB shift, and go to state 9
MUL shift, and go to state 10
CR shift, and go to state 11
state 5
4 expression: term .
8 term: term . MUL primary_expression
9 | term . DIV primary_expression
MUL shift, and go to state 12
DIV shift, and go to state 13
MUL [reduce using rule 4 (expression)]
$default reduce using rule 4 (expression)
下略yacc 生成解析器的阶段，将解析器所能遇到的所有状态都列举进去，并做成一个解析对照表（Parse Table），表中记录了“状态 A 下某幢记号进入后会转换成状态 B”这样的映射关系。
依据 y.output 结尾的信息：
State 5 conflicts: 1 shift/reduce
State 14 conflicts: 1 shift/reduce
State 15 conflicts: 1 shift/reduce 能够看到 state 5 引起了抵触：
state 5
4 expression: term .
8 term: term . MUL primary_expression
9 | term . DIV primary_expression
MUL shift, and go to state 12
DIV shift, and go to state 13
MUL [reduce using rule 4 (expression)]
$default reduce using rule 4 (expression) 第一行 state 5 为状态编号，接下来的 3 行是 y.output 前半部分中输入的语法规定（4，8，9）。语法规定两头的 . 代表记号在以后规定下呗转换到哪个水平。比方 state 5 状态下，记号最多被转换成term，而后须要期待下一个记号进行归约。
再上面，记录的是以后状态下，下一个记号进入时如何变动。具体来讲，当 MUL(*) 记号进入悔恨进行移进并转换到state 12，如果进入的是DIV(/)，则进行移进并转移到state 13。
再上面：
MUL [reduce using rule 4 (expression)] 意思当 MUL 进入后，能够依照 state 4 进行归约。这就是移进 / 归约抵触。
yacc 默认移进优先，所以 MUL 进入悔恨转移到state 12:
state 12
8 term: term MUL . primary_expression
DOUBLE_LITERAL shift, and go to state 1
primary_expression go to state 16如果是归约的话，参照的规定是这样的:
4 expression: term上述演示的一个抵触，正是因为咱们将 ADD 改为 MUL 后，* 运算优先级被升高导致的。
2.5 错误处理
能够利用 yacc 的性能给 mycalc.y 实现一个简略的谬误复原机制：
// 批改后的代码
line
: expression CR
{printf(">>%lfn", $1);
}
| error CR
{
yyclearin;
yyerrok;
}这个错误处理的函数，我没能测试出什么后果。所以只放这段代码。
3 完结
以上完结了一个 mycalc 计算器的代码流程，编译完之后的确有一个终端计算器。然而实际上代码都是原书提供的，跟着思路走了一遍。还是没能理解太对自制编程语言常识，算是对词法剖析等根底概念有点理解。后续会不借助 jacc 和 lex 从新制作一个计算器。本文完结。