用 C 語言開發(fā)一門編程語言 — 語法解析器（用一生去愛你）

目錄

文章目錄

目錄

前文列表

編程語言的本質(zhì)

詞法分析

語法分析

使用 MPC 解析器組合庫

安裝

快速入門

實(shí)現(xiàn)波蘭表達(dá)式的語法解析

波蘭表達(dá)式

正則表達(dá)式

代碼實(shí)現(xiàn)

前文列表

《用 C 語言開發(fā)一門編程語言 — 交互式解釋器l》

《用 C 語言開發(fā)一門編程語言 — 跨平臺(tái)的可移植性》

編程語言的本質(zhì)

在 19 世紀(jì) 50 年代，語言學(xué)家 Noam Chomsky 定義了一系列關(guān)于語言的重要理論。這些理論支撐了我們今天對(duì)于語言結(jié)構(gòu)的基本理解。其中重要的一條結(jié)論就是：自然語言都是建立在遞歸和重復(fù)的子結(jié)構(gòu)之上的。Chomsky 提出的理論是非常重要的。它意味著，雖然一門語言可以表達(dá)無限的內(nèi)容，我們?nèi)匀豢梢允褂糜邢薜囊?guī)則去解析所有用該門語言寫就的東西。這些有限的規(guī)則就叫語法（grammar）。

當(dāng)我們學(xué)習(xí)一門自然語言的時(shí)候，我們往往從語法開始。當(dāng)我們學(xué)習(xí)一門編程語言的時(shí)候也一樣，當(dāng)我們嘗試開發(fā)一門編程語言的時(shí)候亦如此，首先要考慮的就是語言的語法、及其語義。

詞法分析

大多數(shù)編程語言開發(fā)的第一步是詞法分析或分詞。通常使用 “Lex” 或 “Tokenizer” 來進(jìn)行描述，表示將一大堆文本分解成多個(gè)符號(hào)。

詞法分析器將包含源碼的文件作為輸入字符串，輸出包含標(biāo)記符號(hào)的列表。那么，在編譯的后半階段將不再參考這些字符串源代碼，所以詞法分析器必須產(chǎn)生所有后面各階段需要的信息。之所以會(huì)有這樣相對(duì)嚴(yán)格的格式設(shè)計(jì)，是因?yàn)檫@個(gè)階段詞法分析器可以做一些工作，比如移除注釋或檢測(cè)標(biāo)識(shí)符或數(shù)字等。如果你將這些邏輯規(guī)則放在詞法分析器里，那么在構(gòu)造語言的其它部分時(shí)就不必再考慮這些規(guī)則了，而且你可以方便地在同一個(gè)地方集中修改這些語法規(guī)則。

語法分析

編譯的第二階段就是語法分析。語法分析器把標(biāo)識(shí)符列表解析為一個(gè)帶結(jié)點(diǎn)的樹。用于存儲(chǔ)這種數(shù)據(jù)的樹稱為 AST（抽象語法樹）。

為了定義一門編程語言的語法，首先需要能夠正確解析用戶按照語法規(guī)則編寫的程序。為此，需要編程語言程序就需要一個(gè)語法解析器，用來判斷用戶的輸入是否合法，并產(chǎn)生解析后的內(nèi)部表示。內(nèi)部表示是一種計(jì)算機(jī)更容易理解的表示形式，有了它，我們后面的解析、求值等工作會(huì)變得更加的簡單可行。

使用 MPC 解析器組合庫

MPC（Micro Parser Combinators）是一個(gè)用于 C 的輕量且強(qiáng)大的解析器組合庫。你可以使用這個(gè)庫為任何語言編寫語法解析器。編寫語法解析器的方法有很多，使用解析器組合庫的好處就在于，它極大地簡化了原本枯燥無聊的工作，你只需要關(guān)注編寫高層的抽象語法規(guī)則就可以了。

MPC 可用于：

解析現(xiàn)有的，或開發(fā)新的編程語言

解析現(xiàn)有的，或開發(fā)新的數(shù)據(jù)格式

MPC 的特性：

正則表達(dá)式分析器生成器

語法分析器生成器

易于集成到 C 語言項(xiàng)目（以一個(gè)源文件的形式存在）

自動(dòng)生成錯(cuò)誤消息

Type-Generic（泛式類型）

Predictive, Recursive Descent

安裝

在我們正式編寫這個(gè)語法解析器之前，首先需要安裝 MPC 庫。MPC 庫的安裝非常簡單，只需要將源碼下載，把源文件 Copy 到我們的 C 語言項(xiàng)目中，然后在項(xiàng)目中包含 mpc 的頭文件并鏈接 MPC 庫即可。

下載：

$ git clone https://github.com/orangeduck/mpc.git

1

Copy：

$ ll 總用量 140 -rw-r--r-- 1 root root 111731 4月 7 18:12 mpc.c -rw-r--r-- 1 root root 11194 4月 7 18:12 mpc.h -rwxr-xr-x 1 root root 8632 4月 7 18:08 parsing -rw-r--r-- 1 root root 1203 4月 7 18:11 parsing.c

1

2

3

4

5

6

引入到 parsing.c：

#include "mpc.h"

1

編譯：

gcc -std=c99 -Wall parsing.c mpc.c -lreadline -lm -o parsing

1

-lm：鏈接數(shù)學(xué)庫。

快速入門

下面我們以編寫一個(gè) Doge（the language of Shiba Inu，柴犬語）語言的語法解析器為例，來快速熟悉 MPC 的用法。

首先解構(gòu)一下 Doge 語言的語法結(jié)構(gòu)：

Adjective（形容詞）：wow、many、so、such。

Noun（名詞）：lisp、language、c、book、build。

Phrase（短語）：由 Adjective + Noun 組成。

Doge（柴犬語）：由若干個(gè) Phrase 組成。

再來解釋一下 Doge 語言的語法描述：

Phrase 由 Adjective 和 Noun 組成。

Doge 由任意個(gè) Phrase 組成。

最后，我們就可以嘗試使用 MPC 來定義 Doge 語言的語法解析器了：

Step 1. 使用 MPC 定義 Adjective 和 Noun，為此我們創(chuàng)建兩個(gè)解析器。其中，mpc_or 函數(shù)會(huì)返回一個(gè)解析器，該解析器表示 “取其一”，因?yàn)槲覀冃枰獜?Adjective 和 Noun 中 “各取其一” 來組成 Phrase，所以分別定義了兩個(gè)解析器。

/* Build a parser 'Adjective' to recognize descriptions */ mpc_parser_t *Adjective = mpc_or(4, mpc_sym("wow"), mpc_sym("many"), mpc_sym("so"), mpc_sym("such") ); /* Build a parser 'Noun' to recognize things */ mpc_parser_t *Noun = mpc_or(5, mpc_sym("lisp"), mpc_sym("language"), mpc_sym("book"),mpc_sym("build"), mpc_sym("c") );

1

2

3

4

5

6

7

8

9

10

11

12

Step 2. 使用已經(jīng)定義好的 Adjective 、 Noun 解析器來定義 Phrase 解析器。mpc_and 函數(shù)會(huì)返回一個(gè)解析器，該解析器只接受各 “子句” 按照順序出現(xiàn)的語句。所以我們將先前定義的 Adjective 和 Noun 傳遞給它，表示：形容詞后面緊跟著名詞組成的短語。mpcf_strfold 和 free 指定了各個(gè)語句的組織（Fold）及刪除（Free）方式。在 mpcf_strfold 和 free 函數(shù)的幫助下，我們不用擔(dān)心什么時(shí)候加入和丟棄輸入，它們將自動(dòng)幫助我們完成。

mpc_parser_t *Phrase = mpc_and(2, mpcf_strfold, Adjective, Noun, free);

1

Step 3. 使用 Phrase 解析器來最終定義 Doge 語言的解析器，Doge 是由若干個(gè) Phrase 組成的，mpc_many 函數(shù)表達(dá)的正是這種邏輯關(guān)系。

mpc_parser_t *Doge = mpc_many(mpcf_strfold, Phrase);

1

上述語句表明 Doge 可以接受任意多條語句。這也意味著 Doge 語言是無窮的。下面列出了一些符合 Doge 語法的例子：

/* 一條 Doge 語句由若干個(gè) Phrase 組成，一個(gè) Phrase 由一個(gè) Adjective + 一個(gè) Noun 構(gòu)成。 */ "wow book such language many lisp" "so c such build such language" "many build wow c" "" "wow lisp wow c many language" "so c"

1

2

3

4

5

6

7

通過上述步驟，我們簡單的定義了一門 Doge 語言的描述自己實(shí)現(xiàn)了一門 Doge 語言的語法解析器。還可以繼續(xù)使用 mpc 提供的其他函數(shù)，一步一步地編寫能解析更加復(fù)雜的語法的解析器。

但是很顯然的，上述的代碼實(shí)現(xiàn)方式并不友好，隨著語法的復(fù)雜度的增加，代碼的可讀性也會(huì)越來越差。所以 mpc 還提供了一系列的函數(shù)來幫助用戶更加簡單地完成常見的任務(wù)，使用這些函數(shù)能夠更好更快地構(gòu)建復(fù)雜語言的解析器，并能夠提供更加精細(xì)地控制。具體的文檔說明可以參見項(xiàng)目主頁*（https://github.com/orangeduck/mpc）*。

下面，我們使用 MPC 提供的另一種更加簡易的代碼實(shí)現(xiàn)方式來編寫 Doge 語法解析器：將整個(gè)語言的語法規(guī)則寫在一個(gè)長字符串中，而不是使用啰嗦難懂的 C 語句。我們也不再需要關(guān)心如何使用 mpcf_strfold 或是 free 參數(shù)組織或刪除各個(gè)語句。所有的這些工作都是都是自動(dòng)完成的。

mpc_parser_t* Adjective = mpc_new("adjective"); mpc_parser_t* Noun = mpc_new("noun"); mpc_parser_t* Phrase = mpc_new("phrase"); mpc_parser_t* Doge = mpc_new("doge"); mpca_lang(MPCA_LANG_DEFAULT, " \ adjective : \"wow\" | \"many\" \ | \"so\" | \"such\"; \ noun : \"lisp\" | \"language\" \ | \"book\" | \"build\" | \"c\"; \ phrase : ; \ doge : *; \ ", Adjective, Noun, Phrase, Doge); /* Do some parsing here... */ mpc_cleanup(4, Adjective, Noun, Phrase, Doge);

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

使用 mpc_new 函數(shù)定義解析器的名字。

使用 mpca_lang 函數(shù)定義這些解析器的內(nèi)涵和解析器之間的邏輯關(guān)系，從而最終構(gòu)成一門語言的語法規(guī)則。

mpca_lang 函數(shù)的第一個(gè)參數(shù)是操作標(biāo)記，在這里我們使用默認(rèn)選項(xiàng) MPCA_LANG_DEFAULT。第二個(gè)參數(shù)是 C 語言的一個(gè)長字符串。這個(gè)字符串中定義了具體的語法規(guī)則。每個(gè)規(guī)則分為兩部分，用冒號(hào) : 隔開，使用 ; 表示規(guī)則結(jié)束：

冒號(hào)左邊是語法規(guī)則的名字，e.g. adjective、noun、phrase、doge。

右邊是語法規(guī)則的定義，e.g. adjective：wow、many、so、such。

mpca_lang 函數(shù)就是對(duì) mpc_many、mpc_and 、 mpc_or 這些函數(shù)的封裝，自動(dòng)地完成這些函數(shù)的工作，讓解析器定義的代碼變得干凈利落，不拖泥帶水。

定義語法規(guī)則的一些特殊符號(hào)的作用如下：

實(shí)現(xiàn)波蘭表達(dá)式的語法解析

波蘭表達(dá)式

就如我們常見的算數(shù)表達(dá)式 1+1 = 2。波蘭表達(dá)式也是一種數(shù)學(xué)標(biāo)記語言，它的特點(diǎn)是運(yùn)算符會(huì)在操作數(shù)的前面。我們考慮將波蘭表達(dá)式作為 Lisp 編程語言的數(shù)學(xué)運(yùn)算部分。

在編寫這種數(shù)據(jù)標(biāo)記語言的語法規(guī)則之前，我們還是先對(duì)其進(jìn)行語法解構(gòu)以及語法描述：我們觀察到，波蘭表達(dá)式總是以操作符開頭，后面跟著操作數(shù)或其他包裹在圓括號(hào)中的表達(dá)式。也就是說，波蘭表達(dá)式是由：程序（Program）是由一個(gè)操作符（Operator）加上一個(gè)或多個(gè)表達(dá)式（Expression）組成的。而每個(gè)表達(dá)式又可以是一個(gè)數(shù)字或者是包裹在圓括號(hào)中的一個(gè)操作符加上一個(gè)或多個(gè)表達(dá)式。

所以我們對(duì)波蘭表達(dá)式進(jìn)行了如下解構(gòu)和描述：

正則表達(dá)式

有了語法規(guī)則的描述之后，我們還需要對(duì)針對(duì)語法的輸入進(jìn)行約束（e.g. 如何表達(dá)開始和結(jié)束輸入、如何規(guī)定可選字符和字符范圍等），因?yàn)橐粋€(gè)任意的輸入中，很可能包含了一些解析器還沒定義清楚的結(jié)構(gòu)。我們考慮使用正則表達(dá)式（Regular Expression）來實(shí)現(xiàn)這一目的。

正則表達(dá)式適合定義一些小型的語法規(guī)則，例如單詞或是數(shù)字等。正則表達(dá)式不支持復(fù)雜的規(guī)則，但它清晰且精確地界定了輸入是否符合規(guī)則。在 mpc 中，我們需要將正則表達(dá)式包裹在一對(duì) / 中。例如，Number 可以用 /-?[0-9]+/ 來表示。

代碼實(shí)現(xiàn)

根據(jù)上面的分析，我們可以定義波蘭表達(dá)式最終的語法規(guī)則：

#include #include #include "mpc.h" #ifdef _WIN32 #include static char buffer[2048]; char *readline(char *prompt) { fputs(prompt, stdout); fgets(buffer, 2048, stdin); char *cpy = malloc(strlen(buffer) + 1); strcpy(cpy, buffer); cpy[strlen(cpy) - 1] = '\0'; return cpy; } void add_history(char *unused) {} #else #ifdef __linux__ #include #include #endif #ifdef __MACH__ #include #endif #endif int main(int argc, char *argv[]) { /* Create Some Parsers */ mpc_parser_t *Number = mpc_new("number"); mpc_parser_t *Operator = mpc_new("operator"); mpc_parser_t *Expr = mpc_new("expr"); mpc_parser_t *Lispy = mpc_new("lispy"); /* Define them with the following Language */ mpca_lang(MPCA_LANG_DEFAULT, " \ number : /-?[0-9]+/ ; \ operator : '+' | '-' | '*' | '/' ; \ expr : | '(' + ')' ; \ lispy : /^/ + /$/ ; \ ", Number, Operator, Expr, Lispy); puts("Lispy Version 0.1"); puts("Press Ctrl+c to Exit\n"); while(1) { char *input = NULL; input = readline("lispy> "); add_history(input); /* Attempt to parse the user input. * 解析用戶的每一條輸入。 * 調(diào)用了 mpc_parse 函數(shù)，并將 Lispy 解析器和用戶輸入 input 作為參數(shù)。 * 它將解析的結(jié)果保存到 &r 中，如果解析成功，函數(shù)返回值為 1，失敗為 0。 */ mpc_result_t r; if (mpc_parse("", input, Lispy, &r)) { /* On success print and delete the AST. * 解析成功時(shí)會(huì)產(chǎn)生一個(gè)內(nèi)部結(jié)構(gòu)，并保存到 r 的 output 字段中。 * 我們可以使用 mpc_ast_print 將這個(gè)結(jié)構(gòu)打印出來，使用 mpc_ast_delete 將其刪除。 */ mpc_ast_print(r.output); mpc_ast_delete(r.output); } else { /* Otherwise print and delete the Error. * 解析失敗時(shí)則會(huì)將錯(cuò)誤信息保存在 r 的 error 字段中。 * 我們可以使用 mpc_err_print 將這個(gè)結(jié)構(gòu)打印出來，使用 mpc_err_delete 將其刪除。 */ mpc_err_print(r.error); mpc_err_delete(r.error); } free(input); } /* Undefine and delete our parsers */ mpc_cleanup(4, Number, Operator, Expr, Lispy); return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

編譯：

gcc -std=c99 -Wall parsing.c mpc.c -lreadline -lm -o parsing

1

運(yùn)行，嘗試解析一條波蘭表達(dá)式 + 5 (* 2 2)。

$ ./parsing Lispy Version 0.1 Press Ctrl+c to Exit lispy> + 5 (* 2 2) > regex operator|char:1:1 '+' expr|number|regex:1:3 '5' expr|> char:1:5 '(' operator|char:1:6 '*' expr|number|regex:1:8 '2' expr|number|regex:1:10 '2' char:1:11 ')' regex lispy> hello :1:1: error: expected '+', '-', '*' or '/' at 'h' lispy> / 1dog :1:4: error: expected one of '0123456789', '-', one or more of one of '0123456789', '(', newline or end of input at 'd' lispy> :1:1: error: expected '+', '-', '*' or '/' at end of input lispy> ^C

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

可以看見，上述的正常輸出就是一個(gè) AST（Abstract Syntax Tree，抽象語法樹），它用來表示用戶輸入的表達(dá)式的結(jié)構(gòu)。操作數(shù)（Number）和操作符（Operator）等需要被處理的實(shí)際數(shù)據(jù)都位于葉子節(jié)點(diǎn)上。而非葉子節(jié)點(diǎn)上則包含了遍歷和求值的信息。

C 語言 正則表達(dá)式

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。