Mon, 22 Jun 1992 17:00:41 GMT

Related articles |
---|

Parser generator that supports regular expressions? stickler@utrio.helsinki.fi (1992-06-12) |

Re: Parser generator that supports regular expressions? N.Chapman@cs.ucl.ac.uk (Nigel Chapman) (1992-06-22) |

Here is one. Re: Parser generator that supports regular expressions? ipser@solomon.technet.sg (1992-06-23) |

Re: Parser generator that supports regular expressions? compres!bz@primerd.prime.com (1992-06-29) |

Newsgroups: | comp.compilers |

From: | Nigel Chapman <N.Chapman@cs.ucl.ac.uk> |

Keywords: | parse, LR(1), LL(1), bibliography |

Organization: | Compilers Central |

References: | 92-06-049 |

Date: | Mon, 22 Jun 1992 17:00:41 GMT |

*> 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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.