3

我正在从单独的词法分析器和解析器转移到对字符数组进行操作的组合解析器。一个问题是如何正确处理空白。

问题

采用由一系列字符“a”和“b”组成的语言。输入中允许使用空格，但不会影响程序的含义。

我目前解析这种语言的方法是：

var token = function(p) {
    return attempt(next(
         parse.many(whitespace),
         p));
};

var a = token(char('a'));
var b = token(char('b'));

var prog = many(either(a, b));

这可行，但需要不必要的回溯。对于诸如 ' _ __ba_alb' 之类的程序（在帖子中空格被剥离，所以让 _ 成为一个空格），在匹配 'b' 时，空格被解析两次，第一次解析失败a时a，再次解析b. 简单地删除attempt是行不通的，因为如果消耗了任何空格，either则永远不会达到。b

尝试

我的第一个想法是将token呼叫移到either：

var a = char('a');
var b = char('b');

var prog = many(token(either(a, b)));

这可行，但现在prog不能轻易重用。在构建解析器库时，这似乎需要定义解析器两次：一个版本实际使用“a”或“b”并且可以在其他解析器中使用，另一个版本可以正确处理空格。它还要求解析器明确了解每个解析器的操作方式以及它如何处理空白，从而使解析器定义变得混乱。

问题

预期的行为是可以在令牌之前使用任意数量的空格。如果解析令牌失败，它会回溯到令牌的开头而不是空格的开头。

如果不对输入进行预处理以生成令牌流，如何表达这一点？有什么好的，真实世界的代码示例吗？我发现最接近的是用于解析的高阶函数，但这似乎并没有解决我的具体问题。

4

1 回答 1

0

我在自己构建的 JSON 解析器中解决了这个问题。这是我的解决方案的关键部分，我在其中遵循了“两次编写解析器”的方法：

  1. 为每个标记定义基本解析器——数字、字符串等。

  2. 定义一个token组合器——它接受一个基本的令牌解析器并输出一个空格咀嚼解析器。正如您所指出的，应该在之后进行咀嚼，以便只解析一次空格：

    function token(parser) {
    // run the parser, then munch whitespace
}

  3. 使用token组合器生成咀嚼令牌解析器

  4. 使用 3. 中的解析器为该语言的其余部分构建解析器

拥有两个相似版本的解析器我没有问题，因为每个版本实际上都是不同的。这有点烦人，但代价很小。你可以在这里查看完整的代码。

于 2014-01-22T20:57:48.330 回答