c# - 编写一个极其简单的解析器

Question

我正在编写一个非常基本的 Web 服务器，它必须支持极其有限的特殊服务器端脚本语言。基本上我需要支持的只是“echo”，只有 2 个操作数的加法/减法/乘法(无除法)，一个输出日期的简单“date()”函数以及使用“&”运算符连接字符串。

一个例子可以是:

echo "Here is the date: " & date();
echo "9 x 15 = : & 9*15;

我已经完成并创建了生成 token 所需的代码，但我不确定我是否使用了正确的 token 。

我为以下内容创建了 token :

ECHO - The echo command
WHITESPACE - Any whitespace
STRING - A string inside quotations
DATE - The date() function
CONCAT - the & operator for concatenation
MATH - Any instance of binary operation (5+4, 9*2, 8-2, etc)
TERM - The terminal character (;)

我特别不确定的数学题。通常我看到人们专门为整数创建一个 token ，然后也为每个运算符创建一个 token ，但由于我只想允许二进制操作，我认为将其分组为一个 token 是有意义的。如果我分别做每件事，我将不得不做一些额外的工作以确保我永远不会接受“5+4+1”。

那么问题 1 是我使用哪些代币的方向正确吗？

我的下一个问题是接下来我该如何处理这些标记以确保语法正确？我想到的方法基本上是说，“好吧，我知道我有这个 token ，这是一个基于当前 token 允许出现的下一个 token 列表。列表中的下一个 token 是什么？”

基于此，我列出了我所有的标记以及哪些标记可以直接出现在它们之后(为简单起见，不包括空格)。

ECHO        ->      STRING|MATH|DATE
STRING      ->      TERM|CONCAT
MATH        ->      TERM|CONCAT
DATE        ->      TERM|CONCAT
CONCAT      ->      STRING|MATH|DATE

问题是我完全不确定如何最好地实现它。实际上，我还需要跟踪空格以确保标记之间有空格。但这意味着我必须一次向前看两个 token ，这变得更加令人生畏。我也不确定如何在没有 if block 的一些令人厌恶的部分的情况下管理“有效的下一个标记”的东西。我应该在尝试实际执行脚本之前检查有效语法，还是应该一次执行所有操作，并在遇到意外标记时抛出错误？在这个简单的例子中，从左到右解析一切都会很好，没有真正的优先规则(除了 MATH 的东西，但这就是为什么我将它组合成一个标记的部分原因，即使它感觉不对。)即便如此，我也不会介意设计更具可扩展性和优雅的解决方案。

在我关于编写解析器的研究中，我看到很多关于创建“accept()”和“expect()”函数的引用资料，但我找不到关于它们应该做什么或如何做的任何明确描述应该工作。

我想我只是不确定如何实现它，以及如何在一天结束时实际得出结果字符串。

我的方向是否正确？有人知道可以帮助我理解如何最好地实现像这样简单的东西的资源吗？我需要手动完成，不能使用像 ANTLR 这样的工具。

在此先感谢您的帮助。

Answer 1

您需要做的第一件事是丢弃所有空格(字符串中的空格除外)。这样，当您将 token 添加到 token 列表时，您可以确保该列表仅包含有效 token 。例如，请考虑以下语句:

echo "Here is the date: " & date();

我将开始标记化并首先根据空格分隔 echo(是的，此处需要空格来分隔它，但之后就没用了)。然后分词器遇到双引号并继续读取所有内容，直到找到结束双引号。同样，我为 &、date 和 () 创建了单独的标记。

我的 token 列表现在包含以下 token :

echo
"Here is the date: "
&
date
()

现在，在解析阶段，我们读取这些标记。解析器遍历标记列表中的每个标记。它读取 echo 并检查它是否有效(基于您对该语言的规则/功能)。它前进到下一个标记并查看它是否是date、string 或ma​​th。同样，它检查其余的标记。如果在任何时候，一个 token 不应该在那里，您可以抛出一个错误指示语法错误或其他东西。

对于数学语句分词，只需将括号中包含的表达式与其余操作数和运算符分开组合即可。例如:9/3 + (7-3+1) 将具有标记 9、/、3、+ 和 (7-3+1)。由于每个 token 都有自己的优先级(您在 token 结构中定义)，您可以从最高优先级 token 开始评估到最低 token 优先级。这样你就可以优先表达。如果您仍然感到困惑，请告诉我。我会给你写一些示例代码。