关于编程语言:自制计算器自制编程语言二

后面介绍了借助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语言用了一个小窍门，即在标识符作为类型名被申明的时候，会有语法分析器告诉词法分析器，但凡遇到这个标识符，不要将其作为标识符，而作为类型名返回。

本篇完

下一篇将让本文的计算器反对括号和正数。