詞法分析器 (Scanner)
- Series: [ep0], [ep1], [ep2], [ep3]
- Source code: aben20807/learn_compiler
詞法分析器 (Scanner)
這裡我們不需要像編譯系統的課本或課程中提到的演算法來用 C 語言寫一個詞法分析器,而是利用 flex (lex) 這個詞法分析器產生器,它讓使用者可以用一些高階的定義詞法分析的模式,接著自動產生對應的詞法分析器。
使用這類工具的原因如下:
- 減少人工撰寫造成的錯誤
- 開發快速且方便除錯
修課學生不是每一個都對編譯器有興趣,但這是必修課
然而實際上真實的複雜語言,如 C++、Rust、Go 1 2 3 大多都是手寫來達到更高的設計彈性。
flex (lex) 三大區塊
用兩個 %%
來作為區隔:
- Definition section: 又分作兩個小區塊 (可對照下方完整程式碼): %{ 定義標頭檔、全域變數 %}、正規表達式標籤、condition (
%x
) 4、選項 (%option
) 5 - Rules section: 定義判斷為 token 的規則。定義的順序會影響優先度所以要考慮是否會覆蓋其他規則,例如關鍵字應該要優先於變數名,否則像是
decl
,print
會被判定為 ident。這同時也是為何.
(匹配所有字元) 會放在最下面 - C Code section: 定義 main 函式、其他函式
<< Definition section >>
%%
<< Rules section >>
%%
<< C Code section >>
正規表達式
這裡主要利用正規表達式 (Regular Expression, regex, regexp, RE) 來判斷一個輸入中有那些 token,例如 apple
不是任何一個保留關鍵字,所以就是一般的變數名稱。由於本系列所採用的是簡化版的語言,變數只有大小寫字母組成,所以這裡就直接定義 ident
個標籤負責對應 {letter}+
其中 letter
對應 az 或是 AZ 其中一個字元。
完整程式碼
mycompiler.l
:
|
|
測試範例
input/in01.lc
:
decl x = 1 + 4
decl y = 2
decl num = x + y * (3 + 5)
print num
- Result (其他檔案,如 Makefile 請參考 Source code):
$ make
$ ls
input/ lex.yy.c Makefile mycompiler.l myscanner*
$ ./myscanner < input/in01.lc
decl DECL
x IDENT
= ASSIGN
1 NUMLIT
+ ADD
4 NUMLIT
\n NEWLINE
decl DECL
y IDENT
= ASSIGN
2 NUMLIT
\n NEWLINE
decl DECL
num IDENT
= ASSIGN
x IDENT
+ ADD
y IDENT
* MUL
( LPAR
3 NUMLIT
+ ADD
5 NUMLIT
) RPAR
\n NEWLINE
print PRINT
num IDENT
\n NEWLINE
Finish scanning.
References
- Lexical Analysis With Flex, for Flex 2.6.2
- Lexical Analysis With Flex, for Flex 2.6.3
- westes/flex
- YY_NO_UNPUT, YY_NO_INPUT
Footnotes
https://doc.rust-lang.org/nightly/nightly-rustc/src/rustc_lexer/lib.rs.html ↩︎
https://doc.rust-lang.org/nightly/nightly-rustc/src/rustc_parse/lib.rs.html ↩︎
https://www.cs.virginia.edu/~cr4bd/flex-manual/Start-Conditions.html ↩︎
https://www.cs.virginia.edu/~cr4bd/flex-manual/Scanner-Options.html#Scanner-Options ↩︎