]> granicus.if.org Git - re2c/commit
Base '+' (one or more repetitions) on '*' (zero or more repetitions).
authorUlya Trofimovich <skvadrik@gmail.com>
Tue, 15 Dec 2015 12:44:47 +0000 (12:44 +0000)
committerUlya Trofimovich <skvadrik@gmail.com>
Tue, 15 Dec 2015 12:44:47 +0000 (12:44 +0000)
commit5cf441dc936c16e2264e49038ebe9a108dc750b9
tree97a6d2a15a78892f921949fd539ee27cba37813e
parent70b7e09fb6b367d659b5b970efd47bb5fdc80ef8
Base '+' (one or more repetitions) on '*' (zero or more repetitions).

Kleene star '*' (aka iteration, repetition, etc.) is a primitive
operation in regular expressions.

For some reason re2c used '+' as a primitive operation and expressed
'*' in terms of '+'. It is inconvenient, because all algorithms
described in literature are based on '*'.

Because we now express 'a+' as 'a* a', we have to set 'PRIVATE' attribute
on 'a': otherwize 'a' gets shared between the two occurences which causes
complex bugs.

Expressing 'a+' in a more intuitive way as 'a a*' rather than 'a* a'
causes the generated code to duplicate certain states. The generated code
is (supposedly correct), but re2c fails to deduplicate these states.
We therefore prefer 'a* a' expansion, which results in exactly the same
code as before.
re2c/bootstrap/src/parse/lex.cc
re2c/bootstrap/src/parse/parser.cc
re2c/src/ir/bytecode/calc_size.cc
re2c/src/ir/bytecode/compile.cc
re2c/src/ir/regexp/regexp.cc
re2c/src/parse/parser.ypp