使用最少的分隔符解析列表

Question

我有一种包含 4 种语句的语言：s00、s01、s10、s11，其中前导 1 表示初始关键字，尾随 1 表示终止，并且我有一个分隔符“;”。我可以用“;”终止任何语句。我想解析一种允许最少使用“;”的语句列表的语言。解析器是 Dypgen，它是 GLR+。

示例：

{ x=1 fun f(){} x=1; x=1 var x=1 var x=1; x=1 }

有可能做到这一点吗？如果是这样，怎么办？如果没有，为什么？

我相信这是做不到的，主要是因为我想不出怎么做:) 然而，它似乎确实是上下文相关的：规则是你必须插入一个“;”在 A 和 B 之间，如果 A 未终止且 B 未启动，则 B 和 C 也是如此，这意味着 B 被使用两次。

然而，由于解析器是 GLR+，因此很容易将其用作

(s00|s01|s10|s11}*

规则，如果解析错误，则会抛出“;” （这是 s11 无操作）来解决歧义。如果解析器能够报告语法错误那就更好了。也许这可以在合并替代产品时完成。真正的问题是当它们重叠而不是合并时：如果发生这种情况，程序解析可能会爆炸。

Answer 1

我最近在顶级短语中遇到了类似的问题，其中一些在前一个短语中需要终止 ;; ，而其他短语（以短语引入关键字开头）则不需要。我通过将短语的句法类别一分为二，并为表达这种行为的短语序列提供了精细的规则，解决了我的问题。但这导致了分裂语法的重复。

在你的情况下，它会是这样的：

sequence:
  | (s00 | s10) sequence_closed
  | (s01 | s11) sequence_open
  | ε

sequence_closed:
  | s10 sequence_closed
  | s11 sequence_open
  | ';' sequence_open
  | ε

sequence_open:
  | s00 sequence_closed
  | s01 sequence_open
  | ε

如果你想允许多余的分隔符（你很可能想要），那就有点复杂了，但这就是想法。