C编译器实践 (1) 引例
前言
要想自动优化C代码, 还得首先分析C代码. 所以, 学习怎么写一个C编译器很有必要.
当然, 也可以使用开源的C编译器代码. 但是, 看懂别人的代码都够写2个C编译器了!
最后, 写一个编译器并不是那么难的事, 接下来看一个例子.
项目地址 : https://gitee.com/chenguc/c-compiler-
文法
文法就是描述文本排列的规则, 也就是什么字(word)可以跟在什么字之后, 什么词(token)和什么词构成一个句子, 所有的句子构成了一门语言(language).
以下是一个加减乘除表达式的文法, 表达式用E(expression)表示, 项用T(term)表示, 因子用F(factor)表示, + 就是加号, * 就是乘号, num就是一个数字, () 就是括号. 什么是项呢? 大家或许听过 常数项, 多项式等, 项就是这个意思(只可意会不可言传). 因子又是什么呢? 就是最基础的东西, 数字当然是表达式最基础的东西了, () 的优先级非常高, 所以把()看成一个整体, 也认为是因子:
E -> T + T | T
T -> F * F | F
F -> ( E ) | num
其中, 蓝色的是非终结符(nonterminal), 黑色的是终结符(terminal), 橙色的是特殊符号, 用来描述文法的, 不属于语言中的符号. 比如, -> 表示左边由右边构成, | 表示或者.
E -> T + T | T 这句的意思就是, 表达式由 项 + 项 或者 项 构成.
举例
(3 + 5) * 4 就是上述文法的一个句子, 因为这一串文本是能够被上述文法匹配的.
其中, 3, 4, 5都是终结符 num, + 和 * 也是终结符, (, ) 也是终结符. 可以看到的都是终结符, 而非终结符是由终结符或非终结符构成的, 所以不能直接看到.
num表示数字, 3, 4, 5 都是数字, 所以3, 4, 5都是num, 这应该很好理解. +, * 表示加号和乘号,(, ) 表示括号, 也应该很好理解(理解不了的大概可能或许需要看一下小学数学课本).
以下用右边的替换左边的来证明 (3 + 5) * 4 是符合上述文法的.
(1) E -> T, 应用 E -> T + T | T 的右边那个(或者就是哪个都行);
(2) E -> F * F, 应用 T -> F * F 得到;
(3) E -> F * num, 应用 F -> num 得到;
(4) E -> ( E ) * num, 应用 F -> ( E )得到;
(5) E -> (T + T) * num, 应用 E -> T + T 得到;
(6) E -> (num + num) * num, 应用 E -> T, T -> F, F -> num 连续多次替换得到.
所以 (3 + 5) * 4 就是 (num + num) * num, 就是一个完整的表达式.
编码
文法转代码是非常简单的, 非终结符就对应一个函数, 终结符就对应一个单词(单词由多个字符组成). 于是可以得到如下代码:
#include <iostream>
using namespace std;
bool E(const char*& p);
bool F(const char*& p)
{
// F -> ( E )
if (*p == '(')
{
E(++p);
return *p == ')';
}
// F -> num
if (isdigit(*p))
{
++p;
return true;
}
return false;
}
bool T(const char*& p)
{
if (F(p) == false)
return false;
if (*p == '*')
{
if (F(++p) == false)
return false;
}
return true;
}
bool E(const char*& p)
{
if (T(p) == false)
return false;
if (*p == '+')
{
if (T(++p) == false)
return false;
}
return true;
}
int main()
{
const char *text = "(3+5)*4";
const char *p = text;
if (E(p))
cout << text << " 是表达式" << endl;
else
cout << text << " 不是表达式" << endl;
system("pause");
}
匹配过程
以下是匹配过程的一个图示:
