用C++语言手工编写的词法分析器,语法分析器
上一篇 / 下一篇 2007-01-13 11:05:57 / 个人分类：值得学习的例子
查看( 47 ) / 评论( 0 ) / 评分( 0 / 0 )
整数计算器
利用生成的语法树，轻易的编写出一个整数加，减，乘，除计算器。
修改Lexer和Parser，可以从终端读入源代码。
=================== 2006-06-30 ============================
主要参考资料：《编译原理与实践》Kenneth C.Louden ,机械工业出版的翻译版。Compiler Construction Principles and Practice by Kenneth C. Louden --- Online。我参考了几本国外教材的中译本，不过这本对我帮助最大。词法分析器主要仿照书里面的代码，仿照的意思就是我写代码时会不时的翻翻书。其它代码我是看着屏幕完成的。
=================== 2006-06-27 ============================
更新if语句的语法树结构。
=================== 2006-06-26 ============================
这个页面估计不会有实质内容的更新了。我如此喜欢树形结构，以至于关于树形结构的东西我都想实现一遍。语法分析就是使用树形结构的一个用例。文档对象模型(DOM)也是。
=================== 2006-06-23 ============================
这篇文章只是我学习编译原理的日记。我不是要写一个生成机器代码的编译器，我想写一个生成其它语言的编译器。可能是生成html或者c语言代码？
简介：
这是一个基于某个自定义的文法（将在下面给出）所编写的部分功能的编译器。已经实现了词法分析（Lexer.h/cpp），语法分析（Parser.h/cpp）并建立中序(表达式是中序，其它的语句有特定的结构)语法分析树，语法分析树数据结构（SyntaxTreeNode.h/cpp和SyntaxTree.h/cpp）。
文法定义：
S: Statement
B: Boolean
L: Block
I: Identifier
N: Number
E: Expression
Seperator: 分隔符，包括';' '\n' '\t'等，建议使用';'
S = if B then S (else S)? | while Boolean do S | I=E | '{' L '}'
L = S? D L? | <epsilon>
E = T {'+' T}
T = F {'*' F}
F = I | N
B = T2 {'|' T2}
T2 = F2 {'&' F2}
F2 = E <Relop> E
Relop = '<' | '>' | '=='
N = [0-9]+
I = [A-Za-z][0-9A-Za-z]*我主要是想把它写成 C 语言的语法。
基本思想和功能：
词法分析器Lexer提供了nextToken()接口供语法分析器Parser使用。但是，词法分析器也可以单独使用，比如为了输出源文件的记号序列。调用Parser的parse()方法将返回一棵源文件对应的语法分析树的指针。之后可以调用display()方法输出格式化的语法分析树。目前Parser只能建立语法分析树和判断源文件是否存在语法错误并指出错误的地方，无法生成可执行代码。
基本模块简介：
(4.1) Lexer模块公用方法：
Lexer(char *filename); // filename: 源文件
void reset(); // 如果想再次从头分析源文件，调用此方法
bool isReady(); // Lexer是否已经准备就绪
char *getSrc(); // 得到源文件的拷贝的指针
int getIndex(); // 当前已经分析到的字符的位置
Token nextToken(); // 获取下一个记号，永远不会返回NULL
(4.2) Parser模块公用方法：
Parser(char* sourcefile); // sourcefile: 源文件
void printError(); // 打印出错误在源文件中的位置
SyntaxTree* parse(); // 得到一棵语法分析树，并返回它的指针
(4.3) SyntaxTree模块公用方法
void display(FILE *fo=stdout); // 将语法树输出到文件中，默认输出到标准输出语法分析树输出格式
程序使用文本字符输出语法分析树，类似
'='---5
+-----ID
表示ID=5, ID表示标识符。以后将实现存储标识符的表格，从而可以显示标识符的名字。
'='---'+'---5
| '+'---b
+-----ID
表示ID=ID+5
whl---'='---'+'---5
| | +-----ID
| +-----ID
+-----'>'---3
+-----ID
表示while ID>3 then ID=ID+5
if ---blk---whl---'='---9
| | | +-----ID
| | +-----'>'---ID
| | +-----3
| +-----blk---'='---'+'---'*'---ID
| | | | +-----9
| | | +-----8
| | +-----ID
| +-----'='---3
| +-----ID
+-----'>'---8
+-----ID
对应下面的程序：
if a>8 then{
b = 3;
a = 8 + 9 * t;
}else{
while 3>a do
a=9;
}
下面的程序：
if a>8+3*d+6 | 3>4 & e<8 then{
s=2;
b=15;
if a<b then{
s = 8+te
i = 4*8
}else{
s = 0;
}
a=8+9;
rel=8*7;
}else{
while d>a do
begin
a=9+a;
b=7;
c=5+17*a;
end
}
生成树：
if ---blk---whl---blk---'='---'+'---'*'---ID
| | | | | | +-----17
| | | | | +-----5
| | | | +-----ID
| | | +-----blk---'='---7
| | | | +-----ID
| | | +-----'='---'+'---ID
| | | | +-----9
| | | +-----ID
| | +-----'>'---ID
| | +-----ID
| +-----blk---'='---'*'---7
| | | +-----8
| | +-----ID
| +-----blk---'='---'+'---9
| | | +-----8
| | +-----ID
| +-----blk---if ---blk---'='---0
| | | | +-----ID
| | | +-----blk---'='---'*'---8
| | | | | +-----4
| | | | +-----ID
| | | +-----'='---'+'---ID
| | | | +-----8
| | | +-----ID
| | +-----'<'---ID
| | +-----ID
| +-----blk---'='---15
| | +-----ID
| +-----'='---2
| +-----ID
+-----'|'---'&'---'<'---8
| | +-----ID
| +-----'>'---4
| +-----3
+-----'>'---'+'---6
| +-----'+'---'*'---ID
| | +-----3
| +-----8
+-----ID源代码的可执行例子的使用方法：
下载源码包
代码已经在下列环境编译并测试：
Linux debian 2.6.8-2-686
gcc version 4.0.3 (Debian 4.0.3-1)
GNU Make 3.81rc2
使用相同或者相近的环境，进入源代码所在的目录，运行
./compiler
解析附带的test.txt文件。同一个目录下还附带了test_complex.txt（复杂）和test_error.txt（出错）两个文件供测试。
compiler可执行文件的使用方法为
./compiler [srcfile [outfile]]
解析srcfile源文件并输出语法分析树到outfile文件。
运行
make clean
make
将再次编译源文件。
如果在Windows下使用VC6，新建立一个工程，将所有源码文件加入工程中后就可以编译运行了。
在DOS窗口运行，进入工程所在的目录，把源代码目录下的test.txt, test_complex.txt, test_error.txt
三个测试用例复制到Debug目录下，再进入Debug目录，
使用main代替上面的compiler命令就可以测试了。模块使用举例：
输出源文件的记号序列
Lexer lexer("source.c");
while((token = lexer.nextToken()) != ERROR){
// print token
// 已经得到一个记号
}输出语法树到屏幕和文件中，出错则输出出错信息
FILE *fp = fopen("tree.txt", "w");
Parser parser("source.c");
SyntaxTree *tree = parser.parse();
if(tree != NULL){
tree->display();
tree->display(fp);
}else{
parser.printError();
}
下载源码包
在线查看HTML格式化的所有源代码
Makefile|common.h|Lexer.h|Lexer.cpp|SyntaxTreeNode.h|SyntaxTreeNode.cpp|SyntaxTree.h|SyntaxTree.cpp|Parser.h|Parser.cpp|main.cpp
计算器源代码calc.cpp.html
