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

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这样的工具.

在此先感谢您的帮助.

Answer 1

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

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

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

我的令牌列表现在包含以下令牌：

echo
"这是日期："
&
date
()

现在，在解析阶段，我们读取这些标记。解析器循环遍历标记列表中的每个标记。它读取echo并检查它是否有效（基于该语言的规则/功能）。它前进到下一个标记并查看它是否是日期、字符串或数学。同样，它检查其余的令牌。如果在任何时候，令牌不应该存在，您可以抛出一个错误，指示语法错误或其他错误。

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