编写一个非常简单的解析器

Question

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

例如：

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

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

我为以下内容创建了令牌：

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 (;)

我特别不确定MATH这个标记的使用方法。通常我看到人们为整数和每个运算符创建一个特定的标记，但由于我只想允许二进制操作，所以我认为将它们分组成一个标记是有意义的。如果我要单独处理每个标记，我需要做一些额外的工作来确保我从不接受"5+4+1"。

所以问题1是，我使用哪些标记是正确的？

我的下一个问题是，我该如何使用这些标记来确保正确的语法？我的想法是基本上说，“好的，我知道我有这个标记，这是一个基于当前标记允许出现的标记列表。下一个标记是否在列表中？”

基于此，我列出了所有我的标记以及直接在它们后面出现的有效标记列表（为简单起见，未包括空格）。

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

问题在于我不确定如何最好地实现这个。实际上，我还需要跟踪空格，以确保标记之间有空格。但这意味着我必须一次性查看两个标记，这使问题变得更加棘手。而且，我也不确定如何管理“有效的下一个标记”内容，除非使用一些令人作呕的 if 块。我应该在尝试执行脚本之前检查语法是否有效，还是应该一次性完成所有操作，并在到达意外的标记时抛出错误？在这个简单的示例中，从左到右解析总是可以正常工作的，没有真正的优先规则（除了 MATH 这件事，但这也是我将其合并成一个标记的原因，即使它感觉不对）。即便如此，我也不介意设计一个更具可扩展性和优雅的解决方案。

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

我想我只是不确定如何实现这个，然后如何在一天结束时实际得出一个结果字符串。

我正在朝着正确的方向前进，是否有人知道可能会帮助我理解如何最好地实现像这样的简单东西的资源？我必须手动完成它，不能使用 ANTLR 等工具。

提前感谢您的帮助。

- ARW

---

你很幸运，我的朋友，有人已经完成了艰难的部分。http://irony.codeplex.com/ - asawyer

您也可以使用JavaScript进行自定义操作。http://stackoverflow.com/questions/12118077/using-javascript-for-custom-purposes - L.B

@asawyer，我认为你错过了“我必须手动完成，不能使用像ANTLR这样的工具”的部分，所以Irony很可能也不被允许使用... - Bart Kiers

@BartKiers 也许吧，但由于它生成的是普通的C#程序集，我认为这可能可行。 - asawyer

看看我的答案，了解如何构建递归下降解析器。实际上，它们相当容易构建。请参见https://dev59.com/v3E95IYBdhLWcg3wlu6z#2336769 - Ira Baxter

Answer 1

首先，您需要做的是丢弃所有的空格（除了字符串中的空格）。这样，当您将令牌添加到令牌列表中时，您可以确保该列表只包含有效的令牌。例如，考虑以下语句：

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

我将开始进行分词，首先基于空格（是的，在此处需要空格以进行分隔，但在此之后无用），将echo分开。然后，标记器遇到双引号并继续读取直到找到闭合双引号为止的所有内容。同样，我为&、date和()创建单独的标记。

现在，进入解析阶段，我们读取这些标记。解析器循环遍历标记列表中的每个标记。它读取echo并检查其是否有效（基于您所拥有的语言规则/函数）。它前进到下一个标记，并查看它是否是日期、字符串或数学运算符之一。类似地，它检查其余标记。如果在任何时候都不能使用某个标记，则可以抛出指示语法错误或其他错误的错误。

对于数学语句标记化，仅将包含在括号中的表达式与其余操作数和运算符分开组合。例如：9/3 + (7-3+1)将具有标记9、/、3、+和(7-3+1)。由于每个标记都有自己的优先级（您定义在标记结构中），因此可以从最高优先级标记开始评估到最低标记优先级。这样可以获得优先级表达式。如果您仍然有疑问，请告诉我。我将为您编写一些示例代码。

- DelegateX

---

非常感谢，这绝对有帮助。我今天下午会尝试一下，如果还有问题，我会接受您提供的示例代码。再次感谢！ - ARW

Answer 2

expect 是指您的解析器获取下一个标记，如果该标记不是正确的后续标记，则会失败。首先，您的解析器 expect ECHO 或 WHITESPACE。这些是唯一有效的起始术语。在看到“ECHO”之后，您的解析器 expect 其中之一：WHITESPACE|STRING|MATH|DATE；其他任何内容都是错误的。以此类推。

accept 是指您的解析器已经看到了完整的“语句”-ECHO，后跟有效的标记序列，然后是TERM。您的解析器现在有足够的信息来处理您的ECHO命令。

哦，手写解析器（特别是简单的解析器）往往是让人讨厌的if块（或道德等价物，如switch语句）的集合 :) 更加优雅的解决方案是某种状态机，而更高级的解决方案是像yacc或GOLD Parser Generator这样的语法生成器（它们反过来为您生成丑陋的if、switch和状态机）。

编辑提供更多细节。

为了梳理职责，创建一个“词法分析器”，其工作是读取输入并生成标记。这涉及决定标记的外观。一个简单的标记是单词“echo”。一个不太容易的标记是数学运算；标记将由一个或多个数字、一个运算符和一个或多个数字组成，之间没有空格。词法分析器将负责跳过空格，以及理解带引号的字符串和形成date()函数的字符。词法分析器将返回两个东西——读取的标记类型和标记值（例如，“MATH”和“9*15”）。

有了词法分析器来读取您的输入，解析器会消耗这些标记并确保它们按正确顺序出现。首先，您必须看到 ECHO 标记。如果没有，就会失败并显示错误消息。之后，您必须看到 STRING、DATE 或 MATH。如果没有，就会失败并显示错误消息。之后，您需要循环，观察是否出现 TERM，或者是 CONCAT 后跟另一个 STRING、DATE 或 MATH。如果看到 TERM，则退出循环。如果既没有看到 TERM 也没有看到 CONCAT，则会失败并显示错误消息。

您可以在解析过程中处理 ECHO 命令，因为它是一个简单的语法。每次找到一个 STRING、DATE 或 MATH，都要对其进行评估并将其连接到已有的内容上。当找到 TERM 时，退出函数并返回已构建的字符串。

有问题？评论？煎蛋卷？ :)

- prprcupofcoffee

---

谢谢David，这确实有帮助。我仍然在苦苦挣扎的是迭代所有标记的循环如何工作。例如，“expect”的实际实现会是什么样子？在WHITESPACE之后，我真正期望的取决于WHITESPACE之前的标记是什么，这就让人感到困惑。 "expect"实际上是如何使用的？它是一个以可能的标记列表作为参数并返回true / false的函数吗？它是否还会更改我的“当前”标记为“expect”刚刚读取的任何内容，然后我再次调用expect？只是对实现感到困惑 :/ - ARW