自制计算器——《自制编程语言》二

Charlie_W

修改于 2021-04-14 10:52:54

1.6K0

修改于 2021-04-14 10:52:54

文章被收录于专栏：Charlie's Road

自制计算器——《自制编程语言》二

CharlieWang发布于 4 月 7 日

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