Re: Perfecting State Elimination

Bjoern Hoehrmann <bjoern@hoehrmann.de>Mon, 01 Oct 2007 18:23:25 +0200

From comp.compilers

Related articles
Perfecting State Elimination bjoern@hoehrmann.de (Bjoern Hoehrmann) (2007-10-01)
Re: Perfecting State Elimination anton@mips.complang.tuwien.ac.at (2007-10-01)
Re: Perfecting State Elimination bjoern@hoehrmann.de (Bjoern Hoehrmann) (2007-10-01)
| List of all articles for this month |

 From: Bjoern Hoehrmann Newsgroups: comp.compilers,comp.theory Followup-To: comp.compilers Date: Mon, 01 Oct 2007 18:23:25 +0200 Organization: Arcor References: 07-10-006 Keywords: optimize, lex Posted-Date: 02 Oct 2007 00:40:46 EDT

* Bjoern Hoehrmann wrote in comp.compilers:
>[...]

I originally posted this in August, I suppose it got stuck in the
moderator's queue. [Stuck at his ISP, actually. -John]

I might as well answer my own question. While the transformation I
discussed is generally a good one, there is of course the inevitable
blowup caused by determinization of the auto- maton.

Unfortunately in my case I already start out with a DFA and would
need a small epsilon-NFA instead. Now NFA minimization is hard
and I haven't found any suitable reduction algorithm that would be
useful for my purposes. What I did come up with is this algorithm
that will compute a comperatively good removal sequence:

1. Ensure the automaton has only a single start and a single
final state with no incoming and respectively outgoing
transitions by adding new states and epsilon transitions
as necessary.

2. Compute for each state x which states are on all paths
Start --> x --> Final. This can be done in two breadth-
first traversals; for endpoint --> endpoint only the end-
point is on the path. For all others, the states that are
on the paths for all successors/predecessors are on the
path plus the state itself.

A simple approach would be to use a bitmap, starting with
all cells set to true, then setting the row for the end-
point, and during the traversal binary-and'ing the rows
of sucessors/predecessors with the current state's row
(while keeping bitmap[x][x] true).

3. Remove a state only after removing all states that must
visit it. In simple terms, this will collapse the auto-
maton starting with the most deeply nested states and
going outwards until only Start and Final are left.

regards,
--
Bjvrn Hvhrmann 7 mailto:bjoern@hoehrmann.de 7 http://bjoern.hoehrmann.de
Weinh. Str. 22 7 Telefon: +49(0)621/4309674 7 http://www.bjoernsworld.de
68309 Mannheim 7 PGP Pub. KeyID: 0xA4357E78 7 http://www.websitedev.de/

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.