TatSu：如何优化以下语法逻辑以加快解析时间？

Question

我在 TatSu 中有以下语法。为了减少解析时间，我实施了剪切操作（即，一旦看到特定标记，就提交特定规则选项）。

但是，我仍然看到运行时间很长。在一个大约 830K 行的文件上，大约需要 25 分钟（没有剪切表达式接近 40 分钟）。我认为进一步改进是可能的，但我不确定如何以更好的方式重写以下逻辑。

我认为占用大部分时间（通过观察 TatSu 语法匹配痕迹）的主要问题是 vec_data_string/ vec_data_strings。关于如何进一步改进这一点有什么建议吗？

pattern_stmt
    =
    (('V'|'C')&'{' | 'Vector' | 'Condition') '{' ~ {vec_data_block} '}'
    | ('Macro' | 'Call') identifier '{' ~ {vec_data_block} '}'
    | ('Macro' | 'Call') identifier ';'
    | ('W' | 'WaveformTable') ~ identifier ';'
    | annotation
    | 'Loop' ~ integer '{' ~ [pattern_statements] '}'
    | 'MatchLoop' ~ ('Infinite' | integer) ~ '{' ~ pattern_statements 'BreakPoint' ~ '{' ~ pattern_statements '}' ~ '}'
    | ('GoTo' | 'ScanChain') ~ identifier ';'
    | 'BreakPoint' '{' ~ pattern_statements '}'
    | ('BreakPoint' | 'IddqTestPoint' | 'Stop') ~ ';'
    | 'TimeUnit' ~ "'" ~ number [siunit] "'" ~ ';'
    ;
vec_data_block
        =
        | signal_reference_expr '=' ~ vec_data_string ';'
        signal_reference_expr '{' ~ {vec_data_strings} '}'
    vec_data_strings
        =
        {vec_data_string ';'}+
        ;
    vec_data_string
        =
        {wfc_data}+
        | {hex_data}+
        | {dec_data}+
        ;
    wfc_data
        =
        ['\r' ~ integer] wfcs
        | hex_mode
        | dec_mode
        ;
    hex_data
        =
        ['\r' ~ integer] hex
        | wfc_mode
        | dec_mode
        ;
    dec_data
        =
        ['\r' ~ integer] integer
        | wfc_mode
        | hex_mode
        ;
    hex_mode
        =
        '\h' ~ [wfcs] {hex_data}+
        ;
    wfc_mode
        =
        '\w' ~ {wfc_data}+
        ;
    dec_mode
        =
        '\d' ~ [wfcs] {dec_data}+
        ;
    wfcs
        =
        /[a-zA-Z0-9#%]+/
        ;
    hex
        =
        /[0-9a-fA-F]+/
        ;

    integer::int
        =
        /\d+/
        ;

我的测试文件有很多这样的序列：

 "ALLPIs" = 001 \r27 Z 10001ZZ0 \r22 Z 0 \r22 Z 0 \r22 Z 0 \r20 Z 1111 \r133 Z 0Z0010; 
    "ALLPOs" = \r243 X ; 
    "ALLCIOs" = \r557 Z 0 \r10 Z 0ZZ0001001 \r19 Z ;

Answer 1

通过做两件事，我能够显着降低运行时间（大约 50%）：

而不是尝试解析为长字符串创建 AST。我只是使用正则表达式一次性阅读了所有内容。我将 post-稍后处理字符串。
我注意到 {vec_data_block} 占用了大部分时间。在每场比赛之后，它会尝试再进行 4 场比赛，但在继续匹配“}”标记之前失败了。为了解决这个问题，我添加了一个先行规则 (&'}')，如果它看到 '}' 标记则通过。这种行为类似于 'cut' 表达式，可以防止 4 次失败匹配 + 递归的发生。这是加速的大部分。不确定这是否是正确的方法，但它确实有效。

这是更新后的语法，其中有两个更改：

pattern_stmt
    =
    (('V'|'C')&'{' | 'Vector' | 'Condition') '{' ~ {vec_data_block} '}'
    | ('Macro' | 'Call') identifier '{' ~ {vec_data_block} '}'
    | ('Macro' | 'Call') identifier ';'
    | ('W' | 'WaveformTable') ~ identifier ';'
    | annotation
    | 'Loop' ~ integer '{' ~ [pattern_statements] '}'
    | 'MatchLoop' ~ ('Infinite' | integer) ~ '{' ~ pattern_statements 'BreakPoint' ~ '{' ~ pattern_statements '}' ~ '}'
    | ('GoTo' | 'ScanChain') ~ identifier ';'
    | 'BreakPoint' '{' ~ pattern_statements '}'
    | ('BreakPoint' | 'IddqTestPoint' | 'Stop') ~ ';'
    | 'TimeUnit' ~ "'" ~ number [siunit] "'" ~ ';'
    ;
vec_data_block
    =
    | &'}'  <-- Short circuit the next 4 matches if lookahead and find a '}'
    | signal_reference_expr '=' ~ vec_data_string ';'
    | signal_reference_expr '{' ~ {vec_data_strings} '}'
    | annotation
    | non_cyclized_data
    ;
non_cyclized_data
    =
    '@' integer event_pair ';'
     | '@' integer '{' ~ ';'.{event_pair} '}'
    ;
event_pair
    =
    signal_reference_expr '=' ~ event
    | annotation
    ;
vec_data_strings
    =
    {vec_data_string ';'}+
    | annotation
    ;
foo
    =
    /[0-9A-Za-z#%\r\h\d\w]+/
    ;
vec_data_string
    =
    {foo}+   <-- Just read the tokens into one big string for post-processing later.
    ;

Answer 2

您可以通过分解一些常见的子表达式来显着减少调用次数。

例如：

    | ('Macro' | 'Call') identifier '{' ~ {vec_data_block} '}'
    | ('Macro' | 'Call') identifier ';'

可以写成：

    | ('Macro' | 'Call') identifier (';' | '{' ~ {vec_data_block} '}')

使用 TatSu 对保留字的支持也应该有所帮助。

TatSu：如何优化以下语法逻辑以加快解析时间？

TatSu: How to optimize the following grammar logic for faster parse time?

tatsu