Re: Parsers for Programming Languages.

[Robert Feldt <address@hidden>]

Matthew Estes <matt@maintree.com> skrev den Tue, 16 Sep 2003 21:12:38 -0400:

> 	I've recently been doing some research into parsers and I have some questions. I'm not sure if this is the best group to ask this in, but since a) I was motivated to explore parsing because of interests in learning about programming languages b) the goal of my research is to make it easier to design programming languages I figure it would be a relevant topic.
> 	I was wondering if anyone knows much about 2-level grammars and other "general techniques". I have read the paper "Practical LL(1)-based Parsing of van Wijngaarden Grammars" by A.J. Fisher(1985, Acta Informatica 21, pg 559-584, no online copy available) and it was very much along the lines of what I'm interested, but I can't seem to find any more recent work(and 15+ years is a long time in Computer Science). I've heard of affix grammars, and maybe thats where I should go, but I like more general rather than less, and 2-level grammars seemed to be the right combination of readability/usability along with a snowball's chance of being able to be used by a formal technique or parser generator of some kind.
> 	Maybe this is a dead end, but I like the idea of parsing and compiling/interpreting being consumed more by higher level techniques so that it becomes easier to experiment with the constructs being modelled/attempted. I'm also interested in natural language applications as well.
> 	Any thoughts would be appreciated.
>
I'm not sure about the power vis-a-vis van Wijngaarden grammars but
Generalized/Tomita LR parsing is often powerful enough for parsing programming languages.

There are a couple of both powerful, easy-to-use and fast GLR
parsers available: Elkhound and DParser for example. The former
in C++ and the latter in C.

I did a compiler construction toolkit in Ruby (rockit) that also has
a GLR algorithm although it's in Ruby so very slow. Next version of Rockit will use DParser as backend so be much faster while giving an even simpler-to-use and automatically-AST-building front-end to it.

Regards,

Robert Feldt