C編譯器實踐 (1) 引例
前言
????要想自動優(yōu)化C代碼, 還得首先分析C代碼. 所以, 學習怎么寫一個C編譯器很有必要.
????當然, 也可以使用開源的C編譯器代碼. 但是, 看懂別人的代碼都夠?qū)?個C編譯器了!
????最后, 寫一個編譯器并不是那么難的事, 接下來看一個例子.
????項目地址 :?https://gitee.com/chenguc/c-compiler-
文法
????文法就是描述文本排列的規(guī)則, 也就是什么字(word)可以跟在什么字之后, 什么詞(token)和什么詞構(gòu)成一個句子, 所有的句子構(gòu)成了一門語言(language).
?????以下是一個加減乘除表達式的文法, 表達式用E(expression)表示, 項用T(term)表示, 因子用F(factor)表示, + 就是加號, * 就是乘號, num就是一個數(shù)字, () 就是括號. 什么是項呢? 大家或許聽過 常數(shù)項, 多項式等, 項就是這個意思(只可意會不可言傳). 因子又是什么呢? 就是最基礎的東西, 數(shù)字當然是表達式最基礎的東西了, () 的優(yōu)先級非常高, 所以把()看成一個整體, 也認為是因子:
E ->?T?+ T | T
T ->?F?* F | F
F ->? (?E?)? | num
????其中, 藍色的是非終結(jié)符(nonterminal),? 黑色的是終結(jié)符(terminal), 橙色的是特殊符號, 用來描述文法的, 不屬于語言中的符號. 比如, -> 表示左邊由右邊構(gòu)成,? | 表示或者.
????E -> T + T | T 這句的意思就是, 表達式由 項 + 項 或者 項 構(gòu)成.
舉例
????(3 + 5) * 4 就是上述文法的一個句子, 因為這一串文本是能夠被上述文法匹配的.
????其中, 3, 4, 5都是終結(jié)符 num, + 和 * 也是終結(jié)符, (, ) 也是終結(jié)符. 可以看到的都是終結(jié)符, 而非終結(jié)符是由終結(jié)符或非終結(jié)符構(gòu)成的, 所以不能直接看到.
????num表示數(shù)字, 3, 4, 5 都是數(shù)字, 所以3, 4, 5都是num, 這應該很好理解. +, * 表示加號和乘號,(, ) 表示括號,?也應該很好理解(理解不了的大概可能或許需要看一下小學數(shù)學課本).?
? ? 以下用右邊的替換左邊的來證明 (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 連續(xù)多次替換得到.
所以 (3 + 5) * 4 就是?(num?+?num) * num, 就是一個完整的表達式.
編碼
????文法轉(zhuǎn)代碼是非常簡單的, 非終結(jié)符就對應一個函數(shù), 終結(jié)符就對應一個單詞(單詞由多個字符組成). 于是可以得到如下代碼:
#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");
}
匹配過程
????以下是匹配過程的一個圖示:
????????
????
????
????
