Search code examples
parsingocamllexocamllexocamlyacc

Transition table overflow, automaton is too big

I want to add the support of structured references with Excel tables to my lexer & parser of Excel formulas.

I added the following regular expressions to 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'

In lexer_e.mll, I added the identifier as follows. And parser_e.mly will call Parser_structref.mly which parse a structured reference.

| lex_structref as r           { STRUCTREF r }

However, compiling the whole programe gave me the following error:

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

Removing | lex_Column' from let lex_structref made the compiling work.

Is there anything I write wrong, or is it because my previous lexer & parser (which works fine) was already big and adding a little stuff explodes it? How could I diagnostic that?

Solution

  • Besides the comments which help optimize the lexer, there is a workaround: ocamllex -ml does not limit the number of states, transitions, table size. Use it when there is no other choices.