An Overview Of The Marpa Parser
There are many exciting parser technologies out there, and one of the most promising is Marpa. This post discusses how Marpa improves over commonly used parsers.
Marpa
Marpa is a modern Earley parser that can parse all common grammars
in linear time, and can handle all context free grammars (CFGs).
Jeffrey Kegler developed the algorithm, implemented it as the C
library libmarpa, and created a convenient Perl5 interface.
-
visit the Marpa homepage.
-
read Jeffrey Kegler's blog.
-
use the Marpa::R2 Perl module.
-
read my Overview Of The Marpa Parser to learn about Marpa's advantages compared to other parsers.
Transforming Syntax
Or: how to write the easy part of a compiler
A Stack Overflow question asked how to translate a VB-like conditional into a C-like ternary. The other answers suggested regexes or treating it as Perl code *shudder*. But transpiling code to another language can be done correctly.
This post aims to cover:
- parsing with Marpa::R2,
- AST manipulation,
- optimization passes,
- compilation, and
- Perl OO.
In the end, we'll be able to do all that in only 200 lines of code!
Since this post is already rather long, we will not discuss parsing theory. You are expected to be familiar with EBNF grammar notation.