Таблица переходов переполнена, автомат слишком большой

Я хочу добавить поддержку структурированные ссылки с таблицами Excel на мой лексер и парсер формул Excel.

Я добавил следующие регулярные выражения в lexer_structref.mll:

let lex_table_name = "DeptSales"
let lex_column_header = "Sales Amount"

(* EG: =[Sales Amount] *)
let lex_ColumnWOTable = "[" lex_column_header "]"

(* EG: =[Region]:[% Commission] *)
let lex_RangeWOTable = lex_ColumnWOTable ":" lex_ColumnWOTable

(* EG: =DeptSales[Sales Amount] *)
let lex_Column' = lex_table_name lex_ColumnWOTable

let lex_structref = lex_ColumnWOTable | lex_RangeWOTable | lex_Column'

В lexer_e.mll я добавил идентификатор следующим образом. И parser_e.mly вызовет Parser_structref.mly, который проанализирует структурированную ссылку.

| lex_structref as r           { STRUCTREF r }

Однако компиляция всей программы выдала следующую ошибку:

741 states, 34313 transitions, table size 141698 bytes
File "frontend/gen/lexer_e.mll":
transition table overflow, automaton is too big
make: *** [frontend/gen/lexer_e.ml] Error 3

Удаление | lex_Column' из let lex_structref усложнило компиляцию.

Есть ли что-то, что я пишу неправильно, или это потому, что мой предыдущий лексер и парсер (который отлично работает) уже был большим, и добавление небольшого количества вещей взрывает его? Как я мог это диагностировать?


parsing ocaml lex ocamllex ocamlyacc
person SoftTimur    schedule 13.08.2020    source источник
comment
Я не вижу большую часть вашего кода, поэтому я не совсем уверен, но похоже, что вы ожидаете, что лексер распознает сильно структурированные данные, возможно, с намерением их повторного анализа позже. Это правда? Если это так, вы, вероятно, создали монстра для конечного автомата лексера. Почти всегда лучше просто использовать лексер, чтобы разбить ввод на неделимые лексические единицы, и позволить синтаксическому анализатору определить реальную синтаксическую структуру.   -  person rici    schedule 14.08.2020
comment
Обратите внимание, что самый простой способ взорвать описание лексера — это использовать конечное повторение даже с умеренными коэффициентами повторения. Я не знаю, делаете ли вы это - опять же, ваш фрагмент слишком мал, чтобы высказать обоснованное мнение, - но если да, вы можете пересмотреть свое решение. В общих чертах повторения (будь то в лексическом или грамматическом анализе) должны быть очень короткими или неопределенными; если вам нужно установить ограничение, например, до восьми X или, что еще хуже, не более 64 символов, используйте бесконечное повторение и добавьте семантическое действие, которое проверяет ограничение.   -  person rici    schedule 14.08.2020
comment
Спасибо за комментарий. вы ожидаете, что лексер распознает сильно структурированные данные, возможно, с намерением повторно проанализировать их позже ==> Это правда. И что такое повторение?   -  person SoftTimur    schedule 14.08.2020
comment
Повторение обычно представляет собой оператор регулярного выражения {n,m} (если ваш инструмент поддерживает его), но его также можно написать вручную, просто повторив один и тот же подкомпонент несколько раз. Например: id | id "." id | id "." id "." id | id "." id "." id "." id, которое можно было бы записать как id ( "." id ( "." id ("." id)?)?)?)?, но в любом случае ожидается взрыв состояния. Бесконечное повторение производится операторами Клини * или + (или их эквивалентами) и не приводит к взрыву состояния.   -  person rici    schedule 14.08.2020

Ответы (1)


arrow_upward
0
arrow_downward

Кроме комментариев, помогающих оптимизировать лексер, есть обходной путь: ocamllex -ml не ограничивает количество состояний, переходов, размер таблицы. Используйте его, когда нет других вариантов.

person SoftTimur    schedule 18.08.2020