Alex slow on big regular expressions
- Dominant language
- Haskell
- Stars
- 323
- Forks
- 87
- PR merge metrics
- No merged PRs in 30d
Description
From this LBNF file, compiled with BNFC-2.8.4,
```
EInt. Exp ::= Integer;
EPlus. Exp ::= Exp "+" Integer;
comment "anananas" "anananas";
```
I get a huge regular expression to recognize block comments (started and ended by `anananas`):
[Lex.x.txt](https://github.com/simonmar/alex/files/5348518/Lex.x.txt)
Alex does produce a valid lexer from this, but this takes a rather long time.
I wonder whether Alex could be optimized by introducing sharing into the regular expressions and thus reuse automata generated from subexpressions (rather than computing them again).
Contributor guide
Research direction
Start with the attached Lex.x.txt and the Alex lexer-generation path that produces it from the LBNF example. Measure the time and size of the generated regular expression, then investigate whether repeated subexpressions can share generated automata. Done means the example still produces a valid lexer with substantially less generation work or output.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100