共计 7891 个字符，预计需要花费 20 分钟才能阅读完成。
《自制编程语言》学习记录，内容根本是摘抄原书
其实原书并不是从头讲怎么写一个计算器的，而是上来就给了代码，对着代码解说。计算器代码的名字为
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 从新制作一个计算器。本文完结。
