Re: Parsing Expression Grammar

skjaero@gmail.com wrote:
> Does anybody have working examples of a Parsing Expression Grammar
> (http://en.wikipedia.org/wiki/Parsing_expression_grammar) for a Java
> like language? I know the Rats! package generates parsers based on
> PEG, but since Rats! is GPL`d I can`t use it for commercial use. It
> would help to actually see the set of needed production rules for the
> Java language as a base for designing a new language.




Umm, a parser generator license doesn't have much to do with the
generated code license. Just like while the GCC is under licensed
under GPL, it doesn't affect the copyright of the code that is
compiled using it. License of linked libraries might affect the usage
possibilities in a commercial setting, however.


The Rats runtime libraries seem to be licensed under LGPL. If that's
too restrictive also, I'd guess that it wouldn't be much of work to
rewrite those as well.




> The reason for this is that I have a working VM implementation that
> I need to test feed with bytecode samples, so it makes sense to
> start bringing in the compiler step.


For generating test data to Java (?) VM, you really don't need a full
compiler. Just grab a JVM assembler, such as Jasmin, write the test
suites in symbolic bytecodes, and you're done. The 'javap' tool
distributed with the JDK disassembles existing classes for you.


Or why not just write your test cases in regular Java, and compile
them using the regular compiler provided by the JDK?


> As opposed to LL and RL parsers, PEG parsers seem both more efficient
> AND unambiguous and handle context free languages. I was wondering
> if Java, apart from the usual dangling else conflicts, has been frame
> already in a PEG?


Uhm, using context free languages, it is always possible to write
ambiguous grammars, and actually there are context free languages that
are inherently ambiguous. So, you either have to deal with the
ambiguousity in the CFG's (e.g. precedence, associativity), or not use
context free languages.


About the efficiency, I would really like to see how a backtracking
parser with unlimited lookahead beats an LL(k) or LR(k) parser.


Personally, I've been toying with an OO-grammar -based parser
generator, which solves the problems presented in the example
object-oriented parser in Grune et al's "Modern Compiler Design". (See
the exercise A.1). Using backtracking for finding the correct parse
and the GoF bridge-pattern to delegate semantic actions to instances
of subclasses nicely solves the problem.


So far I haven't found motivation to try this toy to a real language
implementation, as OO-grammars are a little bit painful to write.
However, extending it to support PEG structures wouldn't be that big
job. I guess that it's not what you really need, but if I'm wrong, I'd
be happy to have some real data to feed to this toy. It won't beat the
efficiency of LL or LR parsers, but at least it generates readable
code.


br,
Pietu Pohjalainen

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