语言解析-如何处理规则中的多个选项

Question

我一直在写语言解析器。它基于BNF样式规则，其中规则包含选项列表或终端令牌。例如：

# Rule A matches the current token stream position if it matches rule B
# followed by rule C followed by a semicolon
rule_a:
  rule_b rule_c ";"

# Rule B matches the current token stream position if the token 
# there equals "foo"
rule_b:
  "foo"

# Rule C matches the current token stream position if it matches
# either rule D or rule E
rule_c:
  rule_d | rule_e

rule_d:
  "bar"

rule_e:
  "bar bar"

我遇到的具体问题是，如果在解析规则C时，规则D和E都匹配当前令牌流，但是直到后来（规则A进行），才可以发现只有D或E中的一个是正确的选择吗？递归到这种语法树时，似乎必须以某种方式保存历史记录，以便可以再次尝试遍历特定的语法树遍历，但采用的选项与上次不同。

作为使用上述规则的示例，如果我尝试解析以下文本该怎么办：

foo bar bar;

遍历调用树看起来像这样，这里使用缩进来显示递归深度。

parse(token = "foo", rule = rule_a)
  parse(token = "foo", rule = rule_b)
    parse(token = "foo", rule = terminal_token("foo")
      success: consume "foo", return true
    success: return true
  // So far so good, keep going with rule_a
  parse(token = "bar", rule = rule_c)
    parse(token = "bar", rule = rule_d) // Try rule D first.
      parse(token = "bar", rule = terminal_token("bar")
        success: consume "bar", return true
      success: return true
    success: return true // Rule D matched.
  // Still good, keep going.      
  parse(token = "bar", rule = terminal token ";") // second "bar" here
    fail: return false // "bar" != ";"
  fail: return false. // Sequence rule_b rule_c ";" did not match

因此，现在解析失败了，即使尝试使用规则E而不是规则D也会成功。我很难找到一种很好的方法来跟踪针对哪些令牌尝试了哪些规则。如果规则A最终如上所述失败，则应再次尝试，这一次应尝试某些子规则中的其他选项-在这种情况下，在解析rule_c时选择第二个选项（rule_e）。但这真的很快变得复杂-语法越复杂，规则就可能越长，每个规则都有多个选择。因此，对于我来说，目前尚不清楚，如果还有其他方法可以尝试解析，那么如何从失败的解析结果中知道，如何彻底尝试所有解析呢？

Answer 1

仅一小部分语法可以用预测分析器进行分析。有时，您可以按照可解析的方式重新整理语法，但是通常会有一定的代价：语法变得更难阅读和/或无法准确表示语言的语法结构。正如您所说，可以进行回溯，但需要一定量的簿记，并且可能大大降低解析速度。