2

假设我有以下布尔查询语法：

 Query     := <Atom> [ <And-Chain> | <Or-Chain> ]
 Atom      := "(" <Query> ")" | <Var> <Op> <Var> 
 And-Chain := "&&" <Atom> [ <And-Chain> ]
 Or-Chain  := "||" <Atom> [ <Or-Chain> ] 
 Var       := "A" | "B" | "C" | ... | "Z"
 Op        := "<" | ">" | "="

此语法的解析器将具有伪代码：

 parse(query) :=
   tokens <- tokenize(query)
   parse-query(tokens)
   assert-empty(tokens)

 parse-query(tokens) :=
   parse-atom(tokens)
   if peek(tokens) equals "&&" 
     parse-chain(tokens, "&&")
   else if peek(tokens) equals "||"
     parse-chain(tokens, "||")

 parse-atom(tokens) :=
   if peek(tokens) equals "("
     assert-equal( "(", shift(tokens) )
     parse-query(tokens)
     assert-equal( ")", shift(tokens) )
   else
     parse-var(tokens)
     parse-op(tokens)
     parse-var(tokens)

 parse-chain(tokens, connector) :=
   assert-equal( connector, shift(tokens) )
   parse-atom(tokens)
   if peek(tokens) equals connector
      parse-chain(tokens, connector)

 parse-var(tokens) :=
   assert-matches( /[A-Z]/, shift(tokens) )

 parse-op(tokens) :=
   assert-matches( /[<>=]/, shift(tokens) )

不过，我想确保的是，我的解析器会报告有用的解析错误。例如，给定一个以 开头的查询"( A < B && B < C || ..."，我想要一个类似的错误：

found "||" but expected "&&" or ")"

这样做的诀窍是它收集来自解析器不同部分的期望。我可以想办法做到这一点，但最终感觉有点笨拙。

就像，在 Java 中，我可能会GreedyError在尝试查看“&&”或“||”时抛出一个

// in parseAtom
if ( tokens.peek() == "(" ) {
    assertEqual( "(", tokens.shift() );
    try {
        parseQuery(tokens);
        caught = null;
    }
    catch (GreedyError e) {
        caught = e;
    }
    try { 
        assertEqual( ")", tokens.shift() );
    }
    catch (AssertionError e) {
        throw e.or(caught);
    }
}
// ...
// in parseChain
assertEqual( connector, tokens.shift() );
parseAtom(tokens);
if (tokens.peek() == connector) {
    parseChain(tokens, connector);
}
else {
    new GreedyError(connector);
}

或者，在 Haskell 中，我可能会使用它WriterT来跟踪我对当前令牌的最后一次失败比较，用于censor在每次成功的令牌匹配后清除。

但是这两种解决方案都让人觉得有点老套和笨拙。我觉得我错过了一些基本的东西，一些模式，可以优雅地处理这个问题。它是什么？

4

1 回答 1

1

构建一个 L(AL)R(1) 状态机。有关 LALR 的更多详细信息，请参见此处。

您要用于错误报告的是在每个状态中为 dot 设置的 FIRSTOF。当您了解解析器状态是如何生成的时，这个答案将是有意义的。

如果你有这样的一组状态，你可以记录下FIRSTOF集合与每个状态的并集；那么当处于该状态并且不可能进行转换时，您的错误消息是“Exepect（firstof currentstate）”。

如果您不想记录第一个集合，您可以轻松编写一个算法，该算法将爬过状态表来重建它。那将相当于您的“窥视”的算法。

于 2013-03-13T02:09:58.193 回答