TatSu: Как оптимизировать следующую грамматическую логику, чтобы ускорить синтаксический анализ?

У меня в Татсу следующая грамматика. Чтобы сократить время синтаксического анализа, я реализовал операции вырезания (т. Е. Фиксацию определенной опции правила, когда конкретный токен виден).

Тем не менее, я все еще вижу длительное время автономной работы. Для файла с 830 КБ строк это займет около 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 ;
Источник

2 ответа

Решение

Вы можете значительно уменьшить количество вызовов, разложив на множители некоторые общие подвыражения.

Например:

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

можно записать как:

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

Использование TatSu поддержки зарезервированных слов также должно помочь.

Источник

Мне удалось значительно сократить время выполнения (примерно на 50%), выполнив две вещи:

  1. Вместо попытки синтаксического анализа создать AST для длинных строк. Я просто прочитал их все за раз, используя выражение регулярного выражения. Я обработаю строку позже.
  2. Я заметил, что большую часть времени занимает {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.
    ;
Источник
Другие вопросы по тегам