《自制编程语言》学习记录，内容根本是摘抄原书其实原书并不是从头讲怎么写一个计算器的，而是上来就给了代码，对着代码解说。计算器代码的名字为
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-0line_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 // 运行yacclex mycalc.l // 运行lexcc -o mycalc y.tab.c lex.yy.c //应用C编译器编译留神：依照上述的命令，在新款的MacOS上在最初一步编译时会报错，相似问题看这。
所以想要失常编译咱们须要改一下mycalc.y的后面局部：
%{#include <stdio.h>#include <stdlib.h>#define YYDEBUG 1int 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 的正告 ADDState 5 conflicts: 1 shift/reduce // 抵触信息（见下文）State 14 conflicts: 1 shift/reduceState 15 conflicts: 1 shift/reduceGrammar 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_LITERALTerminals, with rules where they appear mycalc.y中应用|（竖线，示意或）书写上面的语法规定:
1 line_list: line2 | line_list line实际上与上面的写法一样：
1 line_list: line2 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 6state 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 6state 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 11state 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/reduceState 14 conflicts: 1 shift/reduceState 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从新制作一个计算器。本文完结。