由 釋出
2010 年 5 月 9 日（最後更新：2010 年 5 月 10 日）

Bison 跟蹤

得分：4.3/5（15 票）
*****
又名：如何在 C++ 中建立解析器，而不使用 Flex 或 Bison 第一部分。

修訂：第二版

為什麼會有人想這樣做呢？（請原諒我的用詞）。這是因為你自己編寫的 C++ 解析器

- 產生更易讀的程式碼 首先，Flex 和 Bison 輸出的檔案可能很難理解，即使它們包含一些不錯的註釋。這會使它們難以整合到其他程式中。但是，既然你寫了大部分內容，並且希望閱讀這篇文章，你就對正在發生的事情有所瞭解。

它們還有可能體積龐大。

- 在生成 LALR 解析器時可以具有更多的超前令牌 Bison 在不生成 GLR 解析器時僅支援一個超前令牌。這意味著，如果你的語法像這樣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
%{
	#include <stdio.h>
%}

%token AND PLOW HORSE MULE OX CART

%%
PHRASE : work_animal AND PLOW
	|	cart_animal AND CART
	;
 
cart_animal : HORSE
	|	MULE
	;
 
work_animal : HORSE	
	|	OX	
	;
%%


...Bison 將無法從中建立解析器。

girlfriend:~ albatross$ bison /Users/albatross/Desktop/impossible.y
/Users/albatross/Desktop/impossible.y: conflicts: 1 reduce/reduce
/Users/albatross/Desktop/impossible.y:16.15-19: warning: rule never reduced because of conflicts: work_animal: HORSE
girlfriend:~ albatross$

如果刪除所有 AND 的例項，Bison 將會輕鬆處理，沒有任何問題。這就是一個超前令牌。有時，你需要更多。

- 更具可定製性 在這一點上放飛你的想象力。


本文將教你如何建立一個簡單的算術解析器，然後你可以將其用作其他解析器的框架。所以坐下來，喝杯提神的飲料，讓自己在我的無關緊要、冗餘的囉嗦中保持清醒，並享受這些囉嗦……否則就等著瞧！

前提條件
必須非常熟悉 C++ 標準庫（尤其是 deques 和 strings），並理解 C++/英語（換句話說，是一名有經驗的 C++ 程式設計師）。

哦，你還必須知道 Flex 和 Bison 是什麼，它們生成什麼，以及如何使用它們。

警告：本文可能會使用 C++ 的“邪惡”特性。如果你不適應使用所述技術，現在就可以親吻新娘，然後永遠保持沉默。（結束）

-總體思路 
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
 
 using namespace std;

//Given this struct:
struct uraldamage
{
   deque<float> deque1;
   deque<int> deque2;
   deque<bool> isoper;
   int charcount;
   int prioritycount;
   int maxpriority;
};

//Your program should be structured like this:
int preprocess(string & stringtheory);
int lexer(string & kitten, uraldamage & groindamage);
int parser(uraldamage & donotusethisasavariablename);
int main()
{
   cout<<"Gimme an arithmetic problem!\n";
   uraldamage data;
   string storeage;
   getline(cin, storeage, '=');
   preprocess(storeage);
   lexer(storeage, data);
   parser(data);
   cout << data.deque1.front();
   return 1337;
}


檔案讀取將在下一部分討論。

注意：我們使用 deques 而不是 maps 是有原因的。你能猜到是什麼嗎？

- 你的預處理器 這只是一個簡單的詞法分析器，有時也包含解析器，它能讓你的程式碼對主詞法分析器來說更容易理解。擁有一個總是個好主意；它能讓你的程式碼更具可讀性。

在這種情況下，我們想去除所有空格和逗號；我們的語法不需要它們。只需使用 cctype 的 iswhitespace(a_char); 和一個計數器 a_char==','; 來確定要刪除哪些字元（counter,1）。返回零。

- 你的詞法分析器
沒有詞法分析器的解析器就像一個香蕉船，裡面放的是醃黃瓜而不是香蕉（噁心）。

在這裡，我們將字串轉換為令牌：資料的小片段，它們具有與它們關聯的值，以便我們的解析器更好地管理。

注意：當我說是讀入 deque 時，我的意思是使用 push_back()。
G#：當我說是從 deque 中刪除時，我的意思是 erase()。
第一個計數器/整數指的是 groindamage.charcount。
第二個計數器/整數指的是 groindamage.prioritycount。
第三個計數器/整數指的是 groindamage.maxpriority。

首先，檢查字串中的第一個字元是否為減號。如果是，則在其前面插入一個零，然後將 0 和 '-' 的 ASCII 值讀入 deque1，將 4 和 4 讀入 deque2，並將 false 和 true 讀入 isoper。然後刪除字串中的減號，然後繼續。你還需要確保下一個令牌獲得的值為 3 而不是 0（稍後檢視）。

如果你沒找到減號，則跳過那部分。

使用 find_first_of("+-*/%^()") 來確定第一個運算子的位置。將其儲存在第一個整數中。然後，使用 atof() 將從第一個字元到但不包括第一個運算子的所有內容讀入 deque1。將 0 讀入 deque2，將 false 讀入 isoper。

然後將下一個字元的 ASCII 值讀入 deque 1，將 0 讀入 deque2，將 true 讀入 isoper。

然後刪除字串中直到幷包括運算子的所有內容。重複此操作，直到字串為空，然後返回零。

- 你的解析器
現在到了有趣的部分。任何做過算術的人都知道乘法比加減法優先。他們還知道指數運算比乘法優先，括號內的語句總是先求值。我們這些仔細觀察的人還會注意到，我們還需要確保負一的乘法必須發生在這些運算之前，而在我們當前的系統中，它不會先發生，而是最後發生。現在我們知道為什麼要有 deque2：用來確定運算順序。

你需要遍歷 deque1 的內容，並清除所有括號。逐個令牌讀取，將 deque2 中相應元素的值設定為 prioritycounter + 其原始值（應該已初始化為零……現在告訴您是否太晚了？）。

如果在任何時候，prioritycounter > maxpriority，則 maxpriority = prioritycounter。

如果你看到加號或減號，則將相應的 deque2 值設定為（原始值 + 0 + prioritycounter）。

如果你看到乘號、除號或取模號，則將相應的 deque2 值設定為（原始值 + 1 + prioritycounter）。

如果你看到冪號，則將相應的 deque2 值設定為（原始值 + 2 + prioritycounter）。

如果你看到左括號，將 prioritycounter 增加三，然後刪除該令牌。

如果你看到右括號，將 prioritycounter 減少三，然後刪除該令牌。

完成後，解析器將執行程式（maxpriority + 1）次，從具有最高 deque2 值的令牌開始。它將評估 deque1 中的一個表示式，該表示式在 isoper 中具有值 false true false，並評估它以獲得一個 float。然後，它將使用 erase 刪除這三個元素，並用結果 float、原始優先順序減一以及 false 寫入 deque1，deque 2，isoper。

當到達 deque 的末尾時，掃描並評估下一個較低的優先順序級別。

當到達優先順序 0 時，你可以線性進行，評估三個令牌，pop_front() 它們，並將結果值 push_front() 並重新啟動操作。當你的 deques 都減小到大小為一時，則返回零。

- 之後
第一次編譯時，你可能會遇到大量致命錯誤。花時間解決它們；這不是一件容易的事。好訊息是，既然你已經建立了第一個解析器，最難的部分已經結束了：你擁有了一個建立新解析器的框架。

如果這篇文章足夠受歡迎，我將撰寫第二篇文章，講解如何解析更接近人類語言的語言，同時解決超前令牌的問題。

本文可能隨時更改，恕不另行通知。

-信天翁