Re: Parser generator that supports regular expressions?

> Does anyone know of a YACC-like parse generator that allows regular
> expressions in rules (i.e. iteration, optionality, disjunction, grouping,
> etc.).


Not exactly, but I know why you're unlikely to find one in a hurry, if you
specially want to use an LR parser generator. If you use regular
expressions on the rhs of productions, then the subject of that production
can generate a potentially infinite set of strings, of arbitrary length.
Let's say we have a production A -> R, where R is a regular expression
(over (N union T)*). A shift reduce parser must reduce by A -> R whenever
it finds a member of the language generated by R on the stack in a
suitable context, where `suitable' is the usual LR context idea. LR
parsing can easily be extended to tell you where the right hand end of the
string is, but then you have to go back and find the left end before you
can do the reduction, and this turns out to be a lot more difficult than
you might expect. Lookahead computastion for LALR is much more complex
too.


Check out some of these references -- it's a long time since I looked at
this problem, but I think some of these people produced prototypes at
least. (I know I did, but since it was written in BCPL it isn't likely to
be much use to anyone any more. Anyway, it certainly wasn't lex
compatible.)


On the other hand, using regular expressions in grammars for recursive
descent is quite straighforward, and makes the parsers nicer too.


%A LaLonde, W.R.
%T Regular right part grammars and their parsers
%J Communications of the ACM
%V 20
%P 731--741
%D 1977


%A LaLonde, W.R.
%T Constructing LR parsers for regular right part grammars
%J Acta Informatica
%V 11
%P 177--193
%D 1979


%A LaLonde, W.R.
%T The construction of stack-controlling LR parsers for regular right
part grammars
%J ACM Transactions on Programming Languages and Systems
%V 3
%P 168--206
%D 1981


%A Chapman, N.P.
%T LALR(1,1) parser generation for regular right part grammars
%J Acta Informatica
%V 21
%P 29--45
%D 1984


%A Madsen, O.L.
%A Kristensen, B.B.
%T LR parsing of extended context free grammars
%J Acta Informatica
%V 7
%P 61--73
%D 1976


%A Nakata, I.
%A Sassa, M.
%T Generation of efficient LALR parsers for regular right part grammars
%J Acta Informatica
%V 23
%P 149--162
%D 1986


There's even a bit about this in


%A Chapman, N.P.
%T LR Parsing: Theory and Practice
%D 1987
%I Cambridge University Press
%C Cambridge


--

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