Methods for NFA-directed parsing?

"Bob Foster" <>
25 Jan 2003 01:11:35 -0500

          From comp.compilers

Related articles
Methods for NFA-directed parsing? (Bob Foster) (2003-01-25)
| List of all articles for this month |

From: "Bob Foster" <>
Newsgroups: comp.compilers
Date: 25 Jan 2003 01:11:35 -0500
Organization: AT&T Broadband
Keywords: parse, question
Posted-Date: 25 Jan 2003 01:11:35 EST

Can someone point to literature on algorithms for parsing using NFA
for regular or regular tree languages? Material available on the web
would be most helpful, though other sources are welcome, too.

To be clear, my interest is in using NFAs, not constructing them. In
introductory computer science, the standard approach seems to be
backtracking, with which I am already familiar. Obviously n-state
lookahead would be an option for some expressions. Some of the
techniques applied to context-free languages might be scaled back to
regular expressions. Etc.

In the best of worlds, in addition to papers on individual methods,
someone could recomment a "taxonomy" of interpretation techniques, as
was done by Watson for constructing NFAs.

Thank you.



B. W. Watson, A taxonomy of finite automata construction algorithms.
Computing Science Note 93/43, Eindhoven University of Technology, The
Netherlands, 1993.

Post a followup to this message

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