bugGrammatica - Bugs: bug #8202, Tokenizer: Create a single DFA or...


You are not allowed to post comments on this tracker with your current authentication level.

bug #8202: Tokenizer: Create a single DFA or NFA for all tokens

Submitter:  Per Cederberg <cederberg>
Submitted:  Fri 19 Mar 2004 10:08:13 AM UTC
Severity:  5 - Major Item Group:  Future Improvement
Status:  Fixed Assigned to:  cederberg
Open/Closed:  Closed

Discussion locked!

Sat 14 Mar 2009 09:35:45 AM UTC, comment #3: 

Version 1.5 was released on 2009-03-07. Closing this issue.

Per Cederberg <cederberg>
Group administrator
Tue 24 Feb 2009 09:56:08 PM UTC, comment #2: 

Fixed in trunk. A mixed approach finally provided the optimal performance; using a DFA for strings, an NFA for all simple regular expressions and native Java regular expressions for the rest. The previous built-in regular expression library is now unused and might be removed in a future version.

Per Cederberg <cederberg>
Group administrator
Sun 22 May 2005 09:32:46 AM UTC, comment #1: 

Hmm... This issue seems more convoluted that I first anticipated. It turns out that modern RE:s aren't regular expressions in the linguistic sense anymore. Actually, they are quite a bit more expressive and impossible to handle correctly with a simple DFA model or with the linguistically equivalent NFA.

So the solution a lot of people have adopted is to have a DFA implementation for the simple RE:s where it works, but using a backtracking pseudo-NFA for the complex RE:s. Or a hybrid that uses DFA:s for parts of the RE where it works, but falls back to  backtracking when not. These solutions have exponential performance in the worst case, but with some tricky optimization one might get a quite speedy implementation for most normal use.

Also a choice must be made regarding the handling of alternatives. Strict POSIX compliance requires evaluating all alternatives and choosing the longest one, whereas Perl and many other languages pick the alternatives in order. Grammatica currently uses a hybrid approach, due to oversight of some of the POSIX complexities. I suspect the traditional Perl way is best for Grammatica, but care must be taken to properly document the RE implementation this time around.

I'm uncertain yet on what the complete solution Grammatica should be. It seems quite a substantial rewrite is needed for the current backtracking interpreter, as it may experience stack overflows on large matches (using the stack for backtracking). Either the heap should be used for storing backtracking information or the various branches should be executed in parallell in some kind of priority queue.

Finally, some interesting articles on the subject to get back to when I start to implement this:


Per Cederberg <cederberg>
Group administrator
Fri 19 Mar 2004 10:08:13 AM UTC, original submission:  

Currently (version 1.4) the Tokenizer class creates a DFA (Deterministic Finite Automaton) with the string tokens, while the regular expression tokens are processed one at a time. It would be preferable to process all the tokens at once in a DFA as the tokenizer speed would thereby be much improved (see bug #3603).

From an implementation perspective, though, it looks a lot easier to create a NFA (Non-deterministic Finite Automaton) instead of a DFA, as the mapping from regular expressions to NFA is pretty straigh-forward. The main problem with an NFA is that it won't be as easy to find the best token match, especially not takning reluctant quantifiers into account.

When creating the DFA or NFA, care should be taken to support case-insensitivity (see bug #5060), tokenizer modes (see bug #3604) and full JDK 1.4 regular expression compability (see bug #3597).

Per Cederberg <cederberg>
Group administrator


(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

No files currently attached


Depends on the following items: None found

   bug dependencies.


Carbon-Copy List
  • -email is unavailable- added by cederberg (Posted a comment)

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.


    Follow 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2009-03-14 cederberg Open/ClosedOpen Closed
        Discussion LockNone Locked
    2009-02-24 cederberg StatusNone Fixed
        Assigned toNone cederberg
    2005-05-21 cederberg Dependencies- bugs #11737 is dependent
    2004-03-19 cederberg Dependencies- bugs # is dependent

    Back to the top

    Powered by Savane 3.13-e8ed.
    Corresponding source code