]> granicus.if.org Git - re2c/commit
Bind contexts (a.k.a. tags) to DFA transitions, not states.
authorUlya Trofimovich <skvadrik@gmail.com>
Mon, 2 May 2016 09:40:04 +0000 (10:40 +0100)
committerUlya Trofimovich <skvadrik@gmail.com>
Mon, 2 May 2016 09:40:04 +0000 (10:40 +0100)
commit5958a2366cdb1361b5158076924014a36ff19dcc
tree27f1f76c77b5f5fae8a7e868dea67bf5a4b99068
parentc1270ecf871b35b6503dba5778d09814895548b0
Bind contexts (a.k.a. tags) to DFA transitions, not states.

This is a very imortant change: it makes tracing tag conflicts as
simple as comparing tags on transitions during DFA construction.
If during determinization we get two identical transitions that
differ only in tags, then we have a tag conflict. Tags that cause
conflicts are called non-deterministic (since they don't allow
deterministic match).

This approach if very similar to Ville Laurikari's TDFA: as he does,
we first build TNFA and then apply determinization; however Laurikari's
TDFA uses complex bookkeeping to track all possible tag values,
while re2c simply forbids tags that cannot be matche efficiently.

Binding tags to transitions allows more fine-grained liveness
analyses, dead tag elimination and tag deduplication.
78 files changed:
re2c/Makefile.am
re2c/src/codegen/bitmap.cc
re2c/src/codegen/emit.h
re2c/src/codegen/emit_action.cc
re2c/src/codegen/emit_dfa.cc
re2c/src/codegen/go.h
re2c/src/codegen/go_construct.cc
re2c/src/codegen/go_emit.cc
re2c/src/ir/adfa/action.h
re2c/src/ir/adfa/adfa.cc
re2c/src/ir/adfa/adfa.h
re2c/src/ir/adfa/prepare.cc
re2c/src/ir/dfa/context_deduplication.cc
re2c/src/ir/dfa/context_selfoverlap.cc [deleted file]
re2c/src/ir/dfa/determinization.cc
re2c/src/ir/dfa/dfa.h
re2c/src/ir/dfa/minimization.cc
re2c/src/ir/skeleton/skeleton.cc
re2c/src/ir/skeleton/skeleton.h
re2c/test/bug57_original.bi--case-insensitive.c
re2c/test/config10.--skeleton.c
re2c/test/config10.c
re2c/test/config8.c
re2c/test/config9.b.c
re2c/test/contexts/cond_star0.ci--input(custom).c
re2c/test/contexts/cond_star0.ci.c
re2c/test/contexts/cond_star1.ci--input(custom).c
re2c/test/contexts/cond_star1.ci.c
re2c/test/contexts/cond_star2.ci.c
re2c/test/contexts/conf1.i--contexts--input(custom).c
re2c/test/contexts/conf1.i--contexts.c
re2c/test/contexts/conf2.i--contexts--input(custom).c
re2c/test/contexts/conf2.i--contexts.c
re2c/test/contexts/conf3.i--contexts--input(custom).c
re2c/test/contexts/conf3.i--contexts.c
re2c/test/contexts/conf4.i--contexts--input(custom).c
re2c/test/contexts/conf4.i--contexts.c
re2c/test/contexts/conf5.i--contexts--input(custom).c
re2c/test/contexts/conf5.i--contexts.c
re2c/test/contexts/conf6.--contexts--input(custom).c
re2c/test/contexts/conf6.--contexts.c
re2c/test/contexts/dedup0.i--input(custom).c
re2c/test/contexts/dedup0.i.c
re2c/test/contexts/dedup1.i--input(custom).c
re2c/test/contexts/dedup1.i.c
re2c/test/contexts/dedup2.i--input(custom).c
re2c/test/contexts/dedup2.i.c
re2c/test/contexts/dedup3.i--input(custom).c
re2c/test/contexts/dedup3.i.c
re2c/test/contexts/fix3.i--contexts.c
re2c/test/contexts/fix3_trail.i--contexts--input(custom).c
re2c/test/contexts/fix3_trail.i--contexts.c
re2c/test/contexts/fix4.i--contexts.c
re2c/test/contexts/fix4_trail.i--contexts--input(custom).c
re2c/test/contexts/fix4_trail.i--contexts.c
re2c/test/contexts/fix5.i--contexts.c
re2c/test/contexts/fix5_trail.i--contexts--input(custom).c
re2c/test/contexts/fix5_trail.i--contexts.c
re2c/test/contexts/overlap.i--input(custom).c
re2c/test/contexts/overlap.i.c
re2c/test/contexts/selfoverlap1_trail.i.c
re2c/test/contexts/yyaccept1.i.c [new file with mode: 0644]
re2c/test/contexts/yyaccept1.i.re [new file with mode: 0644]
re2c/test/ctx.--skeleton.c
re2c/test/ctx.b.c
re2c/test/ctx.c
re2c/test/ctx.s.c
re2c/test/input_custom_default.--input(custom).c
re2c/test/input_custom_default.--skeleton--input(custom).c
re2c/test/input_custom_fgetc.--input(custom).c
re2c/test/input_custom_fgetc.--skeleton--input(custom).c
re2c/test/input_custom_istringstream.--input(custom).c
re2c/test/input_custom_istringstream.--skeleton--input(custom).c
re2c/test/rexx.--skeleton.c
re2c/test/scanner_re2c.bi.c
re2c/test/scanner_re2c_default.--emit-dot.c
re2c/test/scanner_re2c_default.bi.c
re2c/test/strip_003.b--skeleton.c