编译原理实践:计算器
概述
本博客主要讲述如何利用编译原理的知识实现一个控制台计算器.如果之前利用栈(在学数据结构的时候)实现过计算器,一定会有所印象,写一个计算器程序最重要的就是把握运算优先级了.而本文换一个角度,利用文法的知识来实现一个功能齐全的计算器.虽然用编译原理的理论来做计算器实在有点杀鸡焉用宰牛刀的味道,但如此实践确实是有必要的.“合抱之木，生于毫末；九层之台，起于累土；千里之行，始于足下.”
需要说明的是,本文对于不懂编译原理的人来说基本算是天书了,所以,请仔细阅读预备知识.
预备知识
需要说明的是,越到后面会越发现,写一个程序并不是你会了几种语言的问题,语言只是一个工具,没有扎实的理论,永远写不出好的程序.
- 编译原理的知识.比如:如果你不知道怎么消除左递归,那么完全没必要往下看了.
- C语言(用于手工构造),lex/yacc(不懂这一部分可以只看手工构造)
原理分析
相信这一部分对于熟悉编译原理的人没有难度.以下是一个计算器输入语句的文法定义
expression : term | expression + term | expression - term;
term : primary_expression | term * primary_expression | term / primary_expression;
primary_expression : DOUBLE_LITERAL | ( expression ) | - primary_expression;
以上文法直接运用到yacc是没问题的,因为yacc生成的是一个LALR(1)解析器,但手工构造就没那么幸运了,老司机一眼就能看出来,这是一个左递归的BNF,所以需要消除左递归.
expression : term half_expression;
half_expression : + term half_expression | - term half_expression | ε;
term : primary_expression half_term;
half_term : * primary_expression | / primary_expression | ε;
primary_expression : DOUBLE_LITERAL | ( expression ) | - primary_expression;
求一下这个文法的FIRST和FOLLOW集:
构造一下预测分析表就知道是一个LL(1)文法.
以上是简单的原理分析.
手工构造
所谓手工构造就是自己编写程序,这里使用的是C语言,当然了,其他语言也可以.不过这里多说一句话,如果完整的实现一个编译器,必然要涉及将源程序转化为机器码,这是个面向底层的工作,十分适合C语言来处理.而且lex/yacc生成的也是C程序,虽然也有了像JavaCC等其他语言的词法/语法分析生成器,但还是建议使用C语言.
赵裕-GitHub-calculator存放了所有代码,llparser_version目录下就是手工构造的源代码.
手工构造一般采用递归下降法(也称递归子程序法),每当遇到一个终结符就会调用一个对应的子函数进行解析,这里不对源代码做原理性详细的分析,因为我假设你已经熟悉了理论层面的知识,只是缺乏一个实践的参照,学习理解这个程序最好的办法就是clone下来,自己进行单步调试,这是最有效的学习办法.
以下是概括性的程序说明:
- token.h存放基本的声明,如+,-,*,/,(,)的标记
- lexical_analyzer.c存放词法解析程序,起中包含的一个主要函数**get_token()**用于返回token
- parser.c存放语法分析程序,包含主函数,以及每个非终结符对应的函数.
- 语法分析程序对于超前读取的字符,如果不需要则退回,也可以保持始终预读一个字符.本代码采用前一种.
lex/yacc构造
关于lex/yacc
关于lex/yacc这里不做过多的介绍,学过编译原理或多或少都知道一点,O’Reilly出版社的Lex&Yacc是为数不多系统讲解这两个工具的书籍,需要深入了解的可以阅读阅读.
构造计算器
同样,相关代码放在了lex-yacc_version目录下面,这里也不直接给出代码,相对于手工构造的代码,lex和yacc的代码都十分易读(前提是你十分熟悉正则表达式和文法),只是你在使用这两个工具的时候必须熟悉他们的一套规则,这两个工具都有些年头了,所以有些地方或者说有些设计理念可能不是那么优雅,但他们确实十分强大!
最后,利用这两个工具生成的C代码很有必要打开看看,一般来说词法分析手工构造尚可,但语法分析利用工具确实省时省力又高效,所以,十分有必要看看到底生成的了怎样的代码.
即使不懂lex/yacc,只要按照如下步骤编译,应该就能得到C语言的目标代码:
使用**-dv参数是为了生成一个辅助文件y.output**,这个文件包含很多有用信息,而且如果出现了冲突可以给出详细的说明.可以自己打开看看,以下是该文件的一部分:
1 Grammar
2
3 0 $accept: line_list $end
4
5 1 line_list: line
6 2 | line_list line
7
8 3 line: expression CR
9 4 | error CR
10
11 5 expression: term
12 6 | expression ADD term
13 7 | expression SUB term
14
15 8 term: primary_expression
16 9 | term MUL primary_expression
17 10 | term DIV primary_expression
18
19 11 primary_expression: DOUBLE_LITERAL
20 12 | LP expression RP
21 13 | SUB primary_expression
22
23
24 Terminals, with rules where they appear
25
26 $end (0) 0
27 error (256) 4
28 DOUBLE_LITERAL (258) 11
29 ADD (259) 6
30 SUB (260) 7 13
31 MUL (261) 9
32 DIV (262) 10
33 CR (263) 3 4
34 LP (264) 12
35 RP (265) 12
36
37
38 Nonterminals, with rules where they appear
39
40 $accept (11)
41 on left: 0
42 line_list (12)
43 on left: 1 2, on right: 0 2
44 line (13)
45 on left: 3 4, on right: 1 2
46 expression (14)
47 on left: 5 6 7, on right: 3 6 7 12
48 term (15)
49 on left: 8 9 10, on right: 5 6 7 9 10
50 primary_expression (16)
51 on left: 11 12 13, on right: 8 9 10 13
52
53
54 State 0
55
56 0 $accept: . line_list $end
57
58 error shift, and go to state 1
59 DOUBLE_LITERAL shift, and go to state 2
60 SUB shift, and go to state 3
61 LP shift, and go to state 4
62
63 line_list go to state 5
64 line go to state 6
65 expression go to state 7
66 term go to state 8
67 primary_expression go to state 9
68
69
70 State 1
71
72 4 line: error . CR
73
74 CR shift, and go to state 10
75
76
77 State 2
78
79 11 primary_expression: DOUBLE_LITERAL .
80
81 $default reduce using rule 11 (primary_expression)
82 ......
View Code
小结
本文介绍了编译原理在编写计算器上的实践,讲的很简略(因为我没有讲解代码,也没有一步一步分析原理,毕竟这不是一两句话的事),充分理解这些在信息的最好方法就是自己对着代码敲一遍.
好久没写博客了,感觉之前写的好多质量都不够高,希望从本篇开始自己能够以一个更务实的心态写一些有水平的东西,做一些有深度的总结.
参考
«自制编程语言»,前桥和弥.
