Lexer Generator with Recursive Rules

Wed, 22 Dec 2010 12:47:36 -0500

          From comp.compilers

Related articles
Lexer Generator with Recursive Rules benhanson2@icqmail.com (2010-12-22)
| List of all articles for this month |

From: benhanson2@icqmail.com
Newsgroups: comp.compilers
Date: Wed, 22 Dec 2010 12:47:36 -0500
Organization: Compilers Central
Keywords: tools, available
Posted-Date: 23 Dec 2010 11:12:27 EST

Hi Everyone,

I have updated lexertl to allow recursive rules. I am still interested
in producing a LR or LALR parser generator, but I just don't have the
time so I've gone for a simpler target. I haven't released the new
source yet as I am still testing it. Here is an example of the 'even
number of 0s and 1s' problem:

        lexertl::rules rules_;

        rules_.add("INITIAL", "0", 1, "^ONE");
        rules_.add("INITIAL", "1", 1, "^ZERO");
        rules_.add("ZERO", "0", 1, "");
        rules_.add("ZERO", "1", 1, "^ZERO");
        rules_.add("ONE", "0", 1, "^ONE");
        rules_.add("ONE", "1", 1, "");

The '^' before a state name means push the current state. An empty
string for a state name means pop the state.

The acid test will be recursive rules inside other recursive rules and
still getting returned the token correctly.

So, is anyone interested in this technology? I already use lexertl at
work for simple resolver commands (amongst other things), so this new
feature will get properly used in anger at some stage, but I'm curious
if anyone else was interested in the 'good enough' approach to
recursive rules.

I was inspired by the work of Roberto Ierusalimschy and his LPEG
library. Similarly, I see this as a useful technology when searching
using an editor or find in files functionality. I currently use
boost::regex in my Notepad RE editor and it's easy to blow the
backtracking stack with simple expressions. A DFA engine with a stack
is likely to be a lot more reliable and of course can do matching
brackets etc.

If anyone has some example (very simple) grammars I could try, that
would be great. At this stage, the simpler the better.


Ben Hanson

Post a followup to this message

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