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

我正在编写一个非常基本的Web服务器,它必须支持极其有限的特殊服务器端脚本语言。 基本上所有我需要支持的是“回声”,只有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这样的工具。

预先感谢您的帮助。


你需要做的第一件事是放弃所有的空格(除了字符串中的空格)。 这样,当您将标记添加到标记列表时,您确定该列表仅包含有效标记。 例如,请考虑以下声明:

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

我将开始标记化并首先根据空格分隔回显 (是的,这里需要空白区域来分隔它,但之后没有用处)。 然后令牌生成器遇到双引号并继续读取所有内容,直到找到最后的双引号 。 同样,我为date()创建单独的标记。

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

回声
“这是日期:”

日期
()

现在,在解析阶段,我们读取这些令牌。 解析器遍历令牌列表中的每个令牌。 它读取回声并检查它是否有效(基于您对该语言的规则/功能)。 它前进到下一个标记并查看它是日期字符串还是数学 。 同样,它检查其余的标记。 如果在任何时候,一个令牌不应该在那里,你可以抛出一个错误指示语法错误或什么的。

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


expect是解析器获取下一个标记的过程,如果标记不是正确的后续标记,则失败。 首先,你的解析器expects ECHO或WHITESPACE。 这些是唯一有效的开始条款。 看过“ECHO”后,您的解析器expects WHITESPACE | STRING | MATH | DATE之一; 其他任何事情都是错误的。 等等。

accept是当你的语法分析器看到一个完整的“语句”时 - ECHO,然后是有效的令牌序列,然后是TERM。 你的解析器现在有足够的信息来处理你的ECHO命令。

呵呵,手写的解析器(尤其是简单的)经常是令人厌恶的if块的集合(或者像switch语句那样的道德等价物):)更高层次的优雅性将是某种状态机,并且更进一步这是一个像yacc或GOLD Parser Generator这样的语法生成器(它反过来会让你很难看, ifswitch ,以及状态机等)。

编辑提供更多细节。

为了帮助理清责任,创建一个“词法分析器”,其工作是读取输入并生成令牌。 这涉及决定什么样的令牌。 一个简单的标记是“回声”一词。 一个不太容易的标记是数学运算; 该令牌将由一个或多个数字,一个运算符和一个或多个数字组成,其间不会有空格。 词法分析器将负责跳过空白,以及理解引用的字符串和构成date()函数的字符。 词法分析器会返回两件事 - 读取的令牌类型和令牌值(例如“MATH”和“9 * 15”)。

通过使用词法分析器来读取输入,解析器会消耗令牌并确保它们处于正确的顺序。 首先你必须看到ECHO令牌。 如果没有,则失败并显示错误消息。 之后,你必须看到STRING,DATE或MATH。 如果没有,则失败并显示错误消息。 之后,你循环,观看TERM,或CONCAT,然后是另一个STRING,DATE或MATH。 如果你看到TERM,打破循环。 如果您看不到TERM和CONCAT,则会失败并显示错误消息。

您可以在解析时处理ECHO命令,因为它是一个简单的语法。 每次找到STRING,DATE或MATH时,都要对其进行评估并将其与已有的连接起来。 当你找到TERM时,退出该功能并返回组合字符串。

有问题吗? 注释? 煎蛋? :)

链接地址: http://www.djcxy.com/p/11407.html

上一篇: Writing an extremely simple parser

下一篇: Name resolution of functions inside templates instantiated with qualified types