cpp-cheat/flex-bison
2017-08-25 09:17:26 +01:00
..
bison Remove ODE, improve index, move in X11 and GDB from linux 2015-03-31 00:11:02 +02:00
cpp Remove ODE, improve index, move in X11 and GDB from linux 2015-03-31 00:11:02 +02:00
flex Factor out and improve style of POSIX networking 2015-09-10 17:05:42 +02:00
configure REmove -y from apt-get install, it is destructive 2017-08-25 09:17:26 +01:00
README.md Remove ODE, improve index, move in X11 and GDB from linux 2015-03-31 00:11:02 +02:00
test Remove submodule 2015-06-12 12:34:21 +02:00

Flex and Bison

Parser generators.

Flex and Bison are GNU open source clones of Lex and Yacc respectively.

Flex

Tokenizer: splits input with regexes.

Why it works well with bison:

  • this step is O(n).
  • the Bison naive algorithm is O(n^3). Theoretical bounds are linked to matrix multiplication at O(n^2.40) and falling, but Bison is likely to

Bison

Parses deterministic context free languages, AKA deterministic LR.

Subset of context-free, superset of regex.

Sources

Very good intro source: Tom Niemann - Lex & Yacc Tutorial