如何优化这个语法规则？

Question

我正在使用 TatSu python 库实现语法。我的语法工作正常，但有一条规则占用了相当多的时间。在大约 3000 行的块上（更大语法的一部分），如果我采用此完整规则，则解析整个块大约需要 42 秒。如果我将此规则减少到仅几个标记，则运行时间会从 42 秒下降到 33 秒（改进约 20%）。

规则如下所示，它应该匹配一系列由“/”分隔的事件。

events
    =
    '/'%{event}
    ;
event
    =
    'D' | 'U' | 'Z' | 'P' | 'L' | 'H' | 'x' | 'X' | 'T' | 'V' | 'l' | 'h' | 't' | 'v' | 'N' | 'A' | 'B' | 'F' | '?' | 'G' | 'R' | 'Q' | 'M'
    | 'ForceDown' | 'ForceUp' | 'ForceOff' | 'ForcePrior' | 'CompareLow' | 'CompareHigh' | 'CompareUnknown' | 'CompareOff'
    | 'CompareValid' | 'CompareLowWindow' | 'CompareHighWindow' | 'CompareOffWindow' | 'CompareValidWindow' | 'ForceUnknown'
    | 'LogicLow' | 'LogicHigh' | 'LogicZ' | 'Unknown' | 'ExpectHigh' | 'ExpectLow' | 'ExpectOff' | 'Marker'
    ;

如果我将 event 更改为以下内容，我的解析速度会更快。

event
  =
  /[DUZPLHXT]/
  ;

那么是否可以通过某种方式改进上述规则以获得更快的处理速度？感谢您的任何想法。

Answer 1

正如您所指出的，对于具有许多只是标记的选项的规则，使用模式（正则表达式）效率更高。

但运行时间最终取决于一些规则如何相互调用。

您可以尝试的一个简单优化是添加一个 cut (˜) 表达式，这样每个 event 最多尝试一次（尽管 cut应该隐含在 % 表达式中）。

event
    =
    (
    'D' | 'U' | 'Z' | 'P' | 'L' | 'H' | 'x' | 'X' | 'T' | 'V' | 'l' | 'h' | 't' | 'v' | 'N' | 'A' | 'B' | 'F' | '?' | 'G' | 'R' | 'Q' | 'M'
    | 'ForceDown' | 'ForceUp' | 'ForceOff' | 'ForcePrior' | 'CompareLow' | 'CompareHigh' | 'CompareUnknown' | 'CompareOff'
    | 'CompareValid' | 'CompareLowWindow' | 'CompareHighWindow' | 'CompareOffWindow' | 'CompareValidWindow' | 'ForceUnknown'
    | 'LogicLow' | 'LogicHigh' | 'LogicZ' | 'Unknown' | 'ExpectHigh' | 'ExpectLow' | 'ExpectOff' | 'Marker'
    ) ~
    ;

就是说，因为规则非常词法类型，所以我会选择正则表达式。

event
    =
    /(?x)
    'D' | 'U' | 'Z' | 'P' | 'L' | 'H' | 'x' | 'X' | 'T' | 'V' | 'l' | 'h' | 't' | 'v' | 'N' | 'A' | 'B' | 'F' | '?' | 'G' | 'R' | 'Q' | 'M'
    | 'ForceDown' | 'ForceUp' | 'ForceOff' | 'ForcePrior' | 'CompareLow' | 'CompareHigh' | 'CompareUnknown' | 'CompareOff'
    | 'CompareValid' | 'CompareLowWindow' | 'CompareHighWindow' | 'CompareOffWindow' | 'CompareValidWindow' | 'ForceUnknown'
    | 'LogicLow' | 'LogicHigh' | 'LogicZ' | 'Unknown' | 'ExpectHigh' | 'ExpectLow' | 'ExpectOff' | 'Marker'
    /
    ;

如何优化这个语法规则？

How to optimize this grammar rule?

grammar

tatsu