0

我正在硬编码一个递归体面的解析器，主要是为了学习目的，我遇到了一些麻烦。

我将使用 CSS3 语法的简短摘录作为示例：

simple_selector = type_selector | universal;
type_selector = [ namespace_prefix ]? element_name;
namespace_prefix = [ IDENT | '*' ]? '|';
element_name = IDENT;
universal = [ namespace_prefix ]? '*';

首先，我没有意识到它是andnamespace_prefix中的一个可选部分。这导致在输入输入时总是失败，因为它被盲目地考虑用于匹配生产的任何输入。type_selectoruniversaltype_selector*|*namespace_prefix

递归体面很简单，但我对它的理解是，在确定生产之前，我需要做很多（因为没有更好的词）探索性递归。所以我改变了我的作品的签名以返回布尔值。通过这种方式，我可以很容易地判断一个特定的制作是否成功。

我使用链表数据结构来支持任意前瞻，并且可以轻松地对该列表进行切片以尝试生成，然后如果生成不成功则返回我的起点。然而，在尝试制作时，我传递了可变状态，试图构建一个文档对象模型。这并没有真正奏效，因为我无法知道制作是否会成功。如果制作不成功，我需要以某种方式撤消所做的任何更改。

我的问题是这个。我应该使用抽象语法树作为中间表示然后从那里开始吗？这是您通常会做的事情来解决这个问题吗？因为问题似乎主要在于文档对象模型不是适合递归的树数据结构。

4

1 回答 1

1

我对 CSS 不是很熟悉，但通常你会做的是重构语法以尽可能地消除歧义。在您的情况下，可以在 type_selector 和 Universal 开头的 namespace_prefix 生产可以作为单独的可选生产拉到前面：

simple_selector = [ namespace_prefix ]? (type_selector | universal);
type_selector = element_name;
namespace_prefix = [ IDENT | '*' ]? '|';
element_name = IDENT;
universal =  '*';

但是，并非所有语法都可以简化为像这样的简单前瞻，对于那些您可以使用更复杂的 shift-reduce 解析器，或者 - 正如您所建议的 - 回溯。对于回溯，您通常只是尝试解析产生式并记录语法中的路径。一旦你有一个匹配输入的产品，你就可以使用记录的路径来实际执行该产品的语义操作。

于 2011-03-29T18:48:30.283 回答