自己動手做編譯器: 實現 c 語言的詞法解析
對編譯器設計和開發而言，表明你能有效入門的證明就是你能做出一個針對 C 語言的編譯器。完成了 C 語言編譯器，你在編譯原理領域裏算是寫出了第一個 hello world 程序。於是爲了確認我們開發的 GoLex 功能完善，我們看看它是否能對 C 語言的語法有準確的解。
首先我們修改一處正則表達式解析的 bug，在 RegParser.go 中的 term 函數做如下修改：
...
else {
/*
匹配 "." 本質上是匹配字符集，集合裏面包含所有除了\r, \n 之外的ASCII字符
*/
start.edge = CCL
if r.lexReader.Match(ANY) {
for i := 0; i < ASCII_CHAR_NUM; i++ {
if i != int('\r') && i != int('\n') {
start.bitset[string(i)] = true
}
}
//bug here
//越過 '.'
r.lexReader.Advance()
...如果上面代碼不修改，我們解析表達式”(.)” 時就會陷入死循環。另外在 LexReader 的 Advance 函數也需要做 bug 修改，修改如下：
func (l *LexReader) Advance() TOKEN {
...
if l.inquoted || sawEsc {
l.currentToken = L
//bug here
//當讀取到反斜槓時代碼會進入 esc()函數，在裏面我們已經越過了反斜槓後面的字符，因此這裏代碼會導致我們越過反斜槓後面兩個字符
//if sawEsc {
// //越過 / 後面的字符
// l.currentInput = l.currentInput[1:]
//}
} else {
l.currentToken = l.tokenMap[l.Lexeme]
}
...
}另外在 nfa_interpretion.go 中的 EpsilonClosure 做如下 bug 修改：
func EpsilonClosure(input []*NFA) *EpsilonResult {
...
if node.edge == EPSILON {
//bug here
/*
result.results 是當前 epsilon 集合，應該判斷它是否包含了給定節點，而不是在輸入的 input
中判斷，因爲 node 就來自於 input 最後的節點
*/
if node.next != nil && stackContains(result.results, node.next) == false {
input = append(input, node.next)
}
//bug here
if node.next2 != nil && stackContains(result.results, node.next2) == false {
input = append(input, node.next2)
}
...
}上面我們註釋掉了部分代碼，註釋掉的原因在代碼註釋中也給了說明。另外還有一個 bug 在 CLex 的 input.c 的 ii_advance() 中，修改如下：
int ii_advance() {
...
//bug here,
int c = *Next;
Next++;
return c;
}接着我們看看如何設置 input.lex 的內容，首先我們看模板文件的頭部內容：
%{
/*
C 語言語法解析,yyout.h 用於定義字符串標籤值，search.h 定義關鍵字表的查詢接口
*/
#include "yyout.h"
#include "search.h"
%}在模板文件的頭部我們包含了兩個頭文件，yyout.h 主要用於定義一系列枚舉值，分別對應 C 語言代碼中字符串的標籤，例如 ID, STRING 等，search.h 定義在關鍵字表中進行二分查找的函數定義，我們分別看看這些文件的內容。
在 CLex 工程中創建 yyout.h, 其內容如下所示：
//
// Created by MAC on 2023/11/30.
//
#ifndef UNTITLED_YYOUT_H
#define UNTITLED_YYOUT_H
/* token value lexeme */
#define _EOI 0 /*輸入結束標誌*/
#define NAME 1 /*變量名 int a;*/
#define STRING 2 /*字符串常量 char* c="abc";*/
#define ICON 3 /*整型常量或字符串常量 1,2,3 'a', 'b', 'c';*/
#define FCON 4 /*浮點數常量*/
#define PLUS 5 /* + */
#define MINUS 6 /* - */
#define START 7 /* * */
#define AND 8 /* & */
#define QUEST 9 /* ? */
#define COLON 10 /* ? */
#define ANDAND 11 /* && */
#define OROR 12 /* || */
#define RELOP 13 /* > >= < <= */
#define EQUOP 14 /* == != */
#define DIVOP 15 /* / % */
#define OR 16 /* | */
#define XOR 17 /* ^ */
#define SHIFTOP 18 /* >> << */
#define INCOP 19 /* ++ -- */
#define UNOP 20 /* ! ~ */
#define STRUCTOP 21 /* . -> */
#define TYPE 22 /* int float char long ...*/
#define CLASS 23 /* extern static typedef ...*/
#define STRUCT 24 /* struct union */
#define RETURN 25 /* return */
#define GOTO 26 /* goto */
#define IF 27 /* if */
#define ELSE 28 /* else */
#define SWITCH 29 /* switch */
#define BREAK 30 /* break */
#define CONTINUE 31 /* continue */
#define WHILE 32 /* while */
#define DO 33 /* do */
#define FOR 34 /* for */
#define DEFAULT 35 /* default */
#define CASE 36 /* case */
#define SIZEOF 37 /* sizeof */
#define LP 38 /* ( 左括號 */
#define RP 39 /* ) 右括號 */
#define LC 40 /* { 左大括號 */
#define RC 41 /* } 右大括號 */
#define LB 42 /* [ 左中括號 */
#define RB 43 /* } 右中括號 */
#define COMMA 44 /* , */
#define SEMI 45 /* ; */
#define EQUAL 46 /* = */
#define ASSIGNOP 47 /* += -= */
#endif //UNTITLED_YYOUT_H添加 search.h，並設置內容如下：
//
// Created by MAC on 2023/11/30.
//
#ifndef UNTITLED_SEARCH_H
#define UNTITLED_SEARCH_H
/**
在關鍵字表中進行折半查找
*/
extern char* bsearch(char* key, char* base, int nel, int elsize, int (*compare)());
#endif //UNTITLED_SEARCH_H後面我們會對 bsearch 函數的實現邏輯進行詳細說明，下面我們接着模板文件中一些正則表達式的宏定義
%{
/*
C 語言語法解析,yyout.h 用於定義字符串標籤值，search.h 定義關鍵字表的查詢接口
*/
#include "yyout.h"
#inlucde "search.h"
#include <stdio.h>
#include <stdarg.h>
void handle_comment();
void yyerror(char* fmt, ...);
%}
let [_a-zA-z]
alnum [_a-zA-Z0-9]
h [0-9a-fA-F]
o [0-7]
d [0-9]
suffix [UulL]
white [\x00-\s]
%%上面定義中 let 表示的是字符，它包括了下橫杆，alnum 是字符和數字的組合，也包括下橫杆，h 對應 16 進制數，o 對應 8 進制數，suffix 對應整形數後綴，white 把 ascii 中 0 到空格這段區間中的字符全看作空格。
下面我們看 c 語言對應正則表達式的定義
"/*" {handle_comment();}
\"(\\.|[^\"])*\" {printf("this is a string: %s\n", yytext); /*return STRING*/;}
\"(\\.|[^\"])*[\r\m] yyerror("Adding missing \" to string constant\n")第一個正則表達式就是匹配字符串”/_“, 在 c 語言中他意味着進入到註釋部分，一旦遇到這兩個字符，我們就調用 handle_comment() 函數進行處理。上面有一個不好理解的表達式那就是 \ “ _.| [^ \ “] ) * \ “ 這裏需要注意，其中的反斜槓作用是轉義，\” 表示這裏的雙引號就是一個普通字符，他不代表正則表達式中的特殊符號。這個表達是匹配 c 語言中的字符串常量，例如：
char* ptr = "hello world!";上面代碼中，hello world 字符串就可以匹配我們上面定義的表達式。也就是當我們一旦遇到一個雙引號開始時，我們就進入字符串識別階段，直到我們遇到第二個雙引號爲止。從第一個雙引號開始，所有不是雙引號的字符我們都需要把它作爲字符串的字符來看待，這也是 [^ \” ] 這個表達式的作用。需要注意的是我們還特意匹配 \ \ . ，這裏第一個反斜杆是轉義字符，也就是在第一個雙引號後，所有反斜槓加一個字符的組合都當做一個特定字符來識別，例如：
char* ptr = "hello \n world!";注意上面代碼中 \ n 代表一個字符，也就是換行符，而不是兩個字符。表達式 \ “( \ \ . | [ ^ \ “] ) *[\r\m] 字符串中所有字符必須在同一行，字符串中不能用回車或換行來分成兩行。另外在上面模板代碼中我們增加了一個輸出錯誤的函數 yyerror，我們將其實現在模板函數中，該函數本質是對 printf 的封裝，只不過它輸出到標準錯誤輸出，其實也是控制檯，同時它使用了 c 語言的可變長參數機制，這樣我們能給他輸入任意多個參數，其實現我們在下面給出。我們採用增量開發的方式，先看看 GoLex 是否能正確處理當前的模板內容，首先我們先給出當前整個模板內容：
%{
/*
C 語言語法解析,yyout.h 用於定義字符串標籤值，search.h 定義關鍵字表的查詢接口
*/
#include "yyout.h"
#include "search.h"
void handle_comment();
%}
let [_a-zA-z]
alnum [_a-zA-Z0-9]
h [0-9a-fA-F]
o [0-7]
d [0-9]
suffix [UulL]
white [\x00-\s]
%%
"/*" {handle_comment();}
\"*\\.|[^\"])*\" return STRING;
\"(\\.|[^\"])*[\r\n] yyerror("Adding missing \" to string constant\n")
%%
void handle_comment() {
int i;
while (i = ii_input()) {
if (i < 0)
ii_flushbuf(); //放棄當前識別的字符串
else if (i == '*' && ii_lookahead(1) == '/') {
//識別到註釋末尾
printf("at the end of comment...");
ii_input();
break;
}
}
if (i == 0) {
yyerror("End of file in comment\n");
}
}
void main() {
ii_newfile("/Users/my/Documents/CLex/input.txt");
yylex();
}需要注意 handle_comment 函數的實現，他將所有出現在 /_ 之後的字符全部丟棄，直到它遇到
_ / 爲止。我們運行 GoLex 然後將生成的 lex.yy.c 中內容拷貝到 CLex 中的 main.c 看看運行情況。在 CLex 的 input.txt 文件中，我們設置用於測試正則表達式的內容：
/*this is a c comment*/
"this is a c string that contains \s \t and \" "
"this is a error c comment完成上面工作後，我們編譯 CLex 看看其運行結果：
從上面結果看給定正則表達式的識別結果與預期一致。我們繼續在模板文件中添加新的表達式然後看看識別效果是否正確，添加的新表達式如下：
'.'|
'\\.'|
'\\{o}({o}{0}?)?'
'\\x{h}({h}{h}?)?'|
'0{o}*{suffix}?'|
0x{h}+{suffix}?|
[1-9]{d}*{suffix}? return ICON;在上面表達式中匹配如下代碼的等號右邊部分：
int a = 'a'; //匹配'.'
int b = '\t'; //匹配 '\\.'
int c = '\123'; //匹配 \\{o}({o}{o}?)?
int d = '\x123'; //匹配 '\\x{h}({h}{h}?)?'
int e = 012L; //匹配 0{o}{suffix}?
int f = 0x123L; //匹配 0x{h}+{suffix}?
int g = 123L; //匹配 [1-9]{d}*{suffix}?可以看到上面數值都對應 c 語言中整型的定義。我們看看 c 語言浮點數的定義：
({d}+|{d}+\.{d}*|{d}*\.{d}+)([eE][-+]?{d}+)?[fF]? return FCON;上面表達式匹配例子如下：
float a = 1f;
float b = 3.14;
float c = 314e-10; //3.14完成上面內容後運行 GoLex 生成 lex.yy.c，將其內容拷貝到 CLex 的 main.c，並在 CLex 中的 input.txt 添加如下字符串來進行測試：
'a'
'b'
'\t'
'\f'
'\123'
012
0123L
0x123
0x123L
123
123L
3.14
123.456
1e3
123e+3
123.456e+3
1e-3
123.456e-4f最後我們編譯並運行 CLex 後所得結果如下：
at the end of comment...
this is a string: "this is a c string that contains \s \t and \" "
find ICON: 'a'
find ICON: 'b'
find ICON: '\t'
find ICON: '\f'
find ICON: '\123'
find ICON: 012
find ICON: 0123L
find ICON: 0x123
find ICON: 0x123L
find ICON: 123
find ICON: 123L
find FCON: 3.14
find FCON: 123.456
find FCON: 1e3
find FCON: 123e+3
find FCON: 123.456e+3
find FCON: 1e-3
find FCON: 123.456e-4f
ERROR on line 4, near <"this is a error c comment
>
Adding missing " to string constant接着我們增加對 c 語言操作符的詞法解析，在 input.lex 中添加如下內容：
"(" {printf("it is LP\n"); /*return LP;*/}
")" {printf("it is RP\n"); /*return RP;*/}
"{" {printf("it is LC\n"); /*return LC;*/}
"}" {printf("it is RC\n"); /*return RC;*/}
"[" {printf("it is LB\n"); /*return LB;*/}
"]" {printf("it is RB\n"); /*return RB;*/}
"->"|
"." {printf("struct operator:%s\n", yytext); /*return STRUCTOP;*/}
"++"|
"--" {printf("INCOP: %s\n", yytext); /*return INCOP;*/}
"*" {printf("START OP\n"); /*return START;*/}
[~!] {printf("UNOP:%s\n", yytext); /*return UNOP;*/}
"*" {printf("START OP\n"); /*return START;*/}
[/%] {printf("DIVOP: %s\n", yytext); /*return DIVOP;*/}
"+" {printf("PLUS\n"); /*return PLUS;*/}
"-" {printf("MINUS\n"); /*return MINUS;*/}
<<|>> {printf("SHIFTOP: %s\n",yytext); /*return SHIFTOP;*/}
[<>]=? {printf("RELOP: %s\n", yytext); /*return RELOP;*/}
[!=]= {printf("EQUOP: %s\n", yytext); /*return EQUOP;*/}
[*/%+-&|^]=|
(<<|>>)= {printf("ASSIGN OP: %s\n", yytext); /*return ASSIGNOP;*/}
"=" {printf("EQUAL: %s\n", yytext); /*return EQUAL;*/}
"&" {printf("AND: %s\n", yytext); /*return AND;*/}
"^" {printf("XOR: %s\n", yytext); /*return XOR;*/}
"|" {printf("OR: %s\n", yytext); /*return OR;*/}
"&&" {printf("ANDAND: %s\n", yytext); /*return ANDAND;*/}
"||" {printf("OROR: %s\n", yytext); /*return OROR;*/}
"?" {printf("QUEST: %s\n", yytext); /*return QUEST;*/}
":" {printf("COLON: %s\n", yytext); /*return COLON;*/}
"," {printf("COMMA: %s\n", yytext); /*return COMMA;*/}
";" {printf("SEMI: %s\n", yytext); /*return SEMI;*/}然後執行 GoLex，生成新的 lex.yy.c，將其拷貝到 CLex 的 main.c 中，同時在 CLex 的 input.txt 中添加如下用於測試的新內容：
(
)
{
}
[
]
->
.
++
--
/
%
+
-
<<
>>
<
>
<=
>=
!=
==
*=
/=
+=
-=
&=
|=
^=
<<=
>>=
=
^
|
&&
||
?
:
,
;然後我們執行 CLex 對添加的新字符串進行解析，最後所得結果如下：
t is LP
it is RP
it is LC
it is RC
it is LB
it is RB
struct operator:->
struct operator:.
INCOP: ++
INCOP: --
DIVOP: /
DIVOP: %
PLUS
MINUS
SHIFTOP: <<
SHIFTOP: >>
RELOP: <
RELOP: >
RELOP: <=
RELOP: >=
EQUOP: !=
EQUOP: ==
ASSIGN OP: *=
ASSIGN OP: /=
ASSIGN OP: +=
MINUS
EQUAL: =
AND: &
EQUAL: =
ASSIGN OP: |=
ASSIGN OP: ^=
ASSIGN OP: <<=
ASSIGN OP: >>=
EQUAL: =
XOR: ^
OR: |
ANDAND: &&
OROR: ||
QUEST: ?
COLON: :
COMMA: ,
SEMI: ;最後我們還需要完成關鍵字識別，在 c 語言中有很多特定的字符串有專門的作用，他們不能用於做變量名，例如 int, float, struct 等，當詞法解析遇到這些特定字符串時，需要將他們作爲保留字或關鍵字，而不能將他們識別爲變量名，因此我們的做法是首先識別出當前字符串，然後再將他們到關鍵字表中進行查詢，看看所識別的字符串是否屬於保留字或關鍵字，由此我們繼續對 GoLex 中的 input.lex 做如下添加：
{let}{alnum}* {return id_or_keyword(yytext);}
. {yyerror("Illegal character<%s>\n", yytext);}
%%
//用於表示關鍵字表中的一個字段
typedef struct {
char* name;
int val;
} KWORD;
KWORD Ktab[] = {
{"auto", CLASS},
{"break", BREAK},
{"case", CASE},
{"char", TYPE},
{"continue", CONTINUE},
{"default", DEFAULT},
{"do", DO},
{"double", TYPE},
{"else", ELSE},
{"extern", CLASS},
{"float", TYPE},
{"for", FOR},
{"goto", GOTO},
{"if", IF},
{"int", TYPE},
{"long", TYPE},
{"register", CLASS},
{"return", RETURN},
{"short", TYPE},
{"sizeof", SIZEOF},
{"static", CLASS},
{"struct", STRUCT},
{"switch", SWITCH},
{"typedef", CLASS},
{"union", STRUCT},
{"unsigned", TYPE},
{"void", TYPE},
{"while", WHILE}
};
int cmp(KWORD*a, KWORD* b) {
return strcmp(a->name, b->name);
}
int id_or_keyword(char* lex) {
KWORD* p;
KWORD dummy;
dummy.name = lex;
p = (KWORD*)bsearch(&dummy, Ktab, sizeof(Ktab)/sizeof(KWORD), sizeof(KWORD),cmp);
if (p) {
printf("find keyword: %s\n", yytext);
return p->val;
}
printf("find variable :%s\n", yytext);
return NAME;
}{let}{alnum}* 表示變量名必須以下劃線或字母開頭，後面可以跟着字母或數字。結構體 KWORD 用於定義關鍵字表中的一個字段，KTab 用來定義 c 語言的關鍵字，這裏需要特別注意，那就是 KTab 中每個條目中的字符串是升序排列，也就是”auto”<”break”<…<”while”，這種安排是爲了後面我們能在該表中進行折半查找。當解析到一個字符串他滿足變量名的規則時，id_or_keyword 就會被調用，他將當前識別的字符串在 KTab 表中查找，如果能找到對應條目，說明當前字符串是 c 語言的關鍵字，要不然就是普通變量名，這次修改後代碼運行的效果請在 B 站搜索 coding 迪斯尼，查看調試演示過程，本文代碼下載地址：
鏈接: https://pan.baidu.com/s/1ekBNQ94ajhswWVQSBIVZ7g 提取碼: wsir
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/MRiEMe_8ILfOz0ydY7pJ3A