]> granicus.if.org Git - re2c/commit
Allow nondeterministic tags.
authorUlya Trofimovich <skvadrik@gmail.com>
Wed, 30 Nov 2016 11:21:27 +0000 (11:21 +0000)
committerUlya Trofimovich <skvadrik@gmail.com>
Wed, 30 Nov 2016 11:21:27 +0000 (11:21 +0000)
commit559b89742880c09a66e139b0d855e128731e5528
tree71c277ab9e163e29cd3dc1748c54d97632621c77
parentc4d95e30efee42d585850b334a3c2c7931be9103
Allow nondeterministic tags.

This commit makes some important changes:

    - Each DFA state under construction keeps a set of tag versions
      (which version of each tag is actual for each NFA sub-state).

    - Tag versions now have priorities which allow to disambuguate
      between two competing configurations when building tagged epsilon-
      closure. We try to maximaze value of each tag, thus versions
      that correspond to greater tag value have greater priority.

    - Comparison of DFA states (when trying to find an existing state
      equal to the new one) has become more complex. We try to find
      a similar enough (not necessarily identical) state: one that is
      equal to the new state up to reordering of tag versions. Mapping
      should be either bijective or injective (new state must be less
      or equally versatile then the old one), default is bijective.
      Mapping should not violate tag priorities: relative order of
      versions must hold (absolute values of priorities don't have to
      coincide).

    - On each update tag gets new version: if tag is updated to bottom,
      it gets negative version; otherwise it gets positive version.

    - Different tags that updated by the same transition still get
      different versions. This may seem to be a waste: we know exactly
      that input position is equal for all tags on the same transition,
      even more, for all tags on all outgoung transitions from the same
      state, so we can alocate exactly one version for all of them.
      However, allocating one version for different tags creates states
      with a very specific tag configurations: these states don't map
      to existing states and the automaton gets bloated (sometimes
      exponentially). Furthermore, allocating independent versions is
      good for optimizations.

    - Second pass of optimizations: it only makes difference for one
      test case (usually the first pass does a good job), but it's cheap
      (all the necessary infrastructure is in place) and powerful.

    - The resulting automaton is similar to Laurikari's TDFA, except
      for one important difference: re2c's automaton makes use of
      lookahead tags, while Laurikari's does not.
33 files changed:
re2c/src/conf/warn.cc
re2c/src/ir/dfa/cfg/optimize.cc
re2c/src/ir/dfa/closure.cc
re2c/src/ir/dfa/closure.h
re2c/src/ir/dfa/determinization.cc
re2c/src/ir/dfa/find_state.cc
re2c/src/ir/dfa/find_state.h
re2c/src/ir/dfa/tagpool.cc
re2c/src/ir/dfa/tagpool.h
re2c/src/ir/tag.h
re2c/src/ir/tcmd.cc
re2c/src/ir/tcmd.h
re2c/src/util/lookup.h
re2c/test/tags/fallback4.i--tags.c
re2c/test/tags/fallback6.i--tags.c
re2c/test/tags/fix3.i--tags.c
re2c/test/tags/fix3_trail.i--tags--input(custom).c
re2c/test/tags/fix3_trail.i--tags.c
re2c/test/tags/fix4.i--tags.c
re2c/test/tags/fix4_trail.i--tags--input(custom).c
re2c/test/tags/fix4_trail.i--tags.c
re2c/test/tags/fix5.i--tags.c
re2c/test/tags/fix5_trail.i--tags--input(custom).c
re2c/test/tags/fix5_trail.i--tags.c
re2c/test/tags/nondet_alt1.--tags.c
re2c/test/tags/nondet_alt2.--tags.c
re2c/test/tags/nondet_cat1.--tags.c
re2c/test/tags/nondet_cat2.c [deleted file]
re2c/test/tags/nondet_cat2.re [deleted file]
re2c/test/tags/nondet_cat3.i.c
re2c/test/tags/nondet_cat3.i.re
re2c/test/tags/nondet_cat4.--tags.c
re2c/test/tags/nondet_iter.--tags.c