由 发布
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 都减小到大小为一时，则返回零。

- 之后
第一次编译时，你可能会遇到大量致命错误。花时间解决它们；这不是一件容易的事。好消息是，既然你已经创建了第一个解析器，最难的部分已经结束了：你拥有了一个创建新解析器的框架。

如果这篇文章足够受欢迎，我将撰写第二篇文章，讲解如何解析更接近人类语言的语言，同时解决超前令牌的问题。

本文可能随时更改，恕不另行通知。

-信天翁