共计 5417 个字符，预计需要花费 14 分钟才能阅读完成。
后面介绍了借助 yacc 和 lex 自制计算器。《自制计算器（借助 yacc 和 lex）—《自制编程语言》一》
本文介绍下不必 yacc 和 lex 的实现过程，其实就是本人编写词法解析器和词法分析器来代替 yacc 和 lex。基于 C 语言实现
文中代码为了阐明大多是截图，能够对照行号介绍，不过不必放心，源代码我都传到这里了
1. 自制词法分析器
阐明：本计算器会将换行作为分隔符，把输出宰割成一个个算式。跨复数行的输出无奈被解析。
依据下面的阐明，词法分析器提供一下两个函数：
// 将接下来要解析的行置入词法分析器中
void set_line(char *line);
/*
* 从被置入的行中，宰割记号并返回
* 在行尾会返回 END_OF_LINE_TOKEN 这种非凡的记号
*/
void get_token(Token *token); get_token()承受的入参是一个 Token 构造体指针，函数会宰割出记号装入 Token 构造体并返回。上面是下面两个函数申明和 Token 构造体的定义：
词法分析器的头文件如下：
lexicalanalyzer.h
词法分析器的代码如下图：
lexicalanalyzer.c
词法分析器的运行机制为，每传入一行字符串，就会调用一次 get_token() 并返回分隔号的记号。因为词法分析器须要记下 set_line() 传入的行，以及该行已解析到的地位，所以设置了动态变量 st_line 和st_line_pos（第 7 行和第 8 行）。
set_line()函数，只是单纯设置 st_lin 和st_line_pos的值
get_token()负责将记号理论宰割进去，即词法分析器的外围局部。
第 16 行开始的 while 语句，会逐个依照字符扫描st_line。
记号中的 +、-、*、/ 四则运算符只占一个字符长度，一旦扫描到间接返回。
数值局部略微简单一些，因为数值由多个字符组成。应用 while 语句逐字符扫描时，以后扫描的字符很有可能只是一个数值的一部分，所以必须想个办法将合乎数值特色的值暂存起来。为了暂存数值，采纳一个枚举类型 LexerStatus* 的全局变量status（第 12 行）
LexerStatus枚举的定义在lexicalanalyzer.h中
status的初始状态为 INITIAL_STATUS，当遇到 0\~9 的数字时，这些数字会被放入整数局部（此时状态为为IN_INT_PART_STATUS）中（第 59 行）。一旦遇到小数点.，status 会由 IN_INT_PART_STATUS 变为 DOT_STATUS（第 65 行）。DOT_STATUS 再遇到数字会切换到小数状态 IN_FRAC_PART_STATUS（第 61 行）。在IN_INT_PART_STATUS 或IN_FRAC_PART_STATUS的状态下，如果再无数字或小数点呈现，则完结，承受数值并return。
依照下面的解决，词法分析器会齐全排除 .5、2..3 这样的输出。而从第 23 行开始解决，除换行以外的空白字符全副会被跳过。
因为是用于计算器的词法分析器，所以只解决了四则远算符和数值。如果须要扩大并能够反对编程语言的话，最好留神以下几个要点
1. 数值与标识符（如变量名等）能够依照上例的办法通过治理一个以后状态将其解析进去，比方自增运算符就能够设置一个相似IN_INCREMENT_OPERATOR的状态，但这样一来程序会变得简短。因而对于运算符来说，为其筹备一个字符串数组会更好，例如：
static char *str_operator_str[] = {
"++",
"--",
"+",
"-",
// 省略
};以后读入的记号能够与这个数组的元素做前向匹配，从而判断记号的品种。指针局部同样须要比特色对象再多读入一个字符用以反叛（比方输出
i + 2，就须要将2也读入看看有没有是i++的可能）。做判断时，像上例这样将长的运算符放到数组后面会比拟省事。另外，像if、while这些保留字，比较简单的做法是先将其判断为标识符，之后再去对照表中查找有没有相应的保留字。
2. 本次的计算器是以行尾单位的，st_line会保留一行中的所有信息，但在当下的编程语言中，换行个别和空白字符是等效的，因而不应该以行尾单位解决，而是从文件中逐字符（getc()等函数）读入解析会更好。上例中用while语句逐字符读取的中央就须要替换为getc()函数来读取。
2. 自制语法分析器
大多程序员即便没自制编程语言的背景，也能猜到词法分析器的运行机制，换成语法分析器就有点毫无脉络了。可能知觉是，只思考计算器程序，将运算符优先级最低的
-、+宰割进去，而后解决*和/，这样的思路根本正确。然而实际操作时会发现，用来保留宰割字符串的空间可能还有其余用处，而退出括号的解决也很难。
yacc 版本的计算器应用上面的语法规定：
expression /* 表达式的规定 */
: term /* 和项 */
| expression ADD term /* 或 表达式 + 和项 */
| expression SUB term /* 或 表达式 - 和项 */
;
term /* 和项的规定 */
: primary_expression /* 一元表达式 */
| term MUL primary_expression /* 或 和项 * 一元表达式 */
| term DIV primary_expression /* 或 和项 / 一元表达式 */
;
primary_expression /* 一元表达式的规定 */
: DOUBLE_LITERAL /* 实数的字面常量 */
; 这些语法规定能够用下图这样的语法图来示意：
语法图的示意还是比拟清晰的，比方我的项目 （term） 的语法图代表最后进入一元表达式（primary_expression），一元表达式能够间接完结，也能够进行 * 或/运算，而后又有一个一元表达式进入，反复这一流程。
本书（本系列）的语法图丽中，非终结符用长方形示意，终结符（记号）用椭圆形示意。
正如语法图示意，咱们借助 递归降落分析法 读入记号，而后执行语法分析，这就是咱们将要编写的语法分析器。
比方解析一个我的项目（term）的函数parse_term():
如语法图中最开始的 primary_expression 一样，第 41 行的 parse_primary_expression() 会被调用。递归降落分析法中，一个非终结符总对应一个处理函数，语法图里呈现非终结符就代表这个函数被调用。因而在第 43 行上面的 for 语句会形成一个有限循环，如果 *(MUL_OPERATOOR) 与/(DIV_OPERATOR)进入，循环会继续进行（其余字符进入则通过第 49 行的 break 跳出）。而第 52 行第二次调用 parse_primary_expression()，与语法图中的* 和/左边的 primary expression 绝对应。
比方遇到 1 * 2 + 3，第 42 行的parse_primary_expression() 将1读入，第 53 行的 my_get_token() 将*读入，接下来的第 52 行的 parse_primary_expression() 将2读入。之后的运算符依据品种不同别离执行乘法（第 54 行）或除法（第 56 行）。
至此已计算完 1 * 2，而后第 43 行的my_get_token() 读入的记号是 +。+ 之后在没有 term 进入，用 break 从循环跳出。但此时曾经将 + 读进来了，因而还须要用第 48 行的 unget_token() 将这个记号退回。parser.c没有间接应用 lexicalanalyzer.c 中写好的 get_token()，而应用了my_get_token()，my_get_token() 会对 1 个记号开拓环形缓冲区（Ring Buffer）（上面的 parser.c 代码的第 6 行的动态变量 st_look_ahead_token 是全副缓冲），能够借用环形缓冲区将最初读进来的 1 个记号用 unget_token() 退回。这里被退回的 +，会从新通过primary_expression() 第 68 行的 my_get_token() 再次读入。
残缺代码如下：
依据语法图能够看到，当命中非终结符时，会通过递归的形式调用其上级函数，因而这种解析器称为递归降落解析器。
自此，语法解析器曾经实现。parser.h:parser.c：
预读记号的解决
本书（本系列）采纳的递归降落解析法，会事后读入一个记号，一旦发现预读的记号是不须要的，则通过 unget_token() 将记号退回。
换一种思路，其实也能够思考“始终保持预读一个记号”的办法。依照这种思路，parser.c的 parse_term() 能够革新成上面：
// token 变量曾经放入了下一个记号
v1 = parse_primary_expression();
for (;;) {
// 这里无序再读入记号
if (token.kind != MUL_OPERATOR_TOKEN && token.kind != DIV_OPERATOR_TOKEN) {
// 不须要退回解决
break;
}
// token.kind 之后还会应用，所以将其备份
// 而 parse_primary_expression（）也就能够读入新的记号 kind = token.kind;
my_get_token(&token);
// primary_expression 的解析函数
v2 = parse_primary_expression();
if (token.kind == MUL_OPERATOR_TOKEN) {v1 *= v2;} else if (token.kind == DIV_OPERATOR_TOKEN) {v1 /= v2;}
}
return v1;上述两种实现其实本质根本一样。
3. 少许理论知识 -LL(1)与 LALR(1)
下面的语法解析器会对记号进行预读，并依照语法图的流程读入所有记号。这种类型的解析器叫作 LL(1) 解析器 。LL(1) 解析器所能解析的语法叫作 LL(1) 语法。
Pascal语法采纳的就是LL(1)
LL(1)解析器 在语法上须要非终结符与解析器外部的函数一一对应。也就是说，只看第一个进入的记号，是无奈判断需不需要持续往下读取，也不能晓得以后非终结符是什么。
比方在 Pascal 中，goto语句应用的标签只能是数字，这样限度的起因是，如果像 C 语言一样容许英文字母作为标识符的话，读入第一个记号时就没方法辨别这个记号到底是赋值语句的一部分，还是标签语句的一部分。因为无论赋值语句还是标签语句，开始的标识符是一样的。因而 LL(1) 语法 所做的解析器都比较简单，语法能表白的范畴比拟狭隘。
其实 LL(1) 语法和 BNF 是有点区别的，实际上 BNF 中的语法规定是这样的：
expression /* 表达式的规定 */
| expression ADD term /* 或 表达式 + 和项 */ 而在实现递归降落剖析时，如果依照这个规定在 parse_expression() 刚开始就调用 parse_expression()，会造成死循环，一个记号也读不了。
BNF 这样的语法称为 左递归，原封照搬左递归的语法规定是无奈实现递归降落剖析的。
yacc生成的解析器称为 LALR(1) 解析器 ，这种解析器能解析的语法称为LALR(1) 语法 。LALR(1) 解析器 是LR 解析器 的一种。
LL(1)的第一个 L，代表记号从程序员代码的最右边开始读入。第二个L 则代表 最左推导（Leftmost derivation），即读入的记号从左端开始置换为分析树。而与此绝对的 LR 解析器，从左端开始读入记号（与LL(1) 解析器 统一），然而产生归约时，记号从左边开始归约，这称为 最右推导（Rightmost derivation），即 LR 解析器 中的R。
递归降落剖析会按自上而下的程序生成分析树，所以称为递归“降落”解析器或递归“向下”解析器。而 LR 解析器 则依照自下而上的程序，也称为“自底而上”解析器。
此外，LL(1)、LALR(1)中的(1)，代表的是解析式所须要的前瞻符号（lookahead symbol），即记号的数量。
LALR(1)结尾的 LA 两个字母是 Look Ahead 的缩写，能够通过预读一个记号判明语法规定中所蕴含的状态并生成语法分析表。LL(1)、LALR(1)本篇理论制作的计算器采纳 LL(1) 语法作为解析器的，因而比较简单，适宜手写。如果采纳 LALR(1) 等LR语法的话，则更适宜用 yacc 等工具主动生成。
尽管
Pascal采纳的是LL(1)语法，但却同时存在赋值语句和过程调用（C 语言中是函数调用）。依照方才的介绍，这两者都由同一类标识符开始的，LL(1)解析器仿佛无奈辨别。
其实Pascal并没有从一开始就强行将其辨别，而是逆转思路，引入了一个同时代表“赋值语句或过程调用”的非终结符，而后在下一个记号读入后再将其离开。在 C 语言中，如果是通过
typedef命名的一些类型，其标识符yacc(LALR(1) 解析器)是无奈解析的。比方：Hoge *hoge_p = NULL;其中的型号到底是乘法运算符还是指针符号，单看Hoge这个标识符很难直观的得出结论。
对此，C 语言用了一个小窍门，即在标识符作为类型名被申明的时候，会有语法分析器告诉词法分析器，但凡遇到这个标识符，不要将其作为标识符，而作为类型名返回。
-
- –
本篇完
下一篇将让本文的计算器反对括号和正数。
