Jeffrey Kegler, the author of Marpa, was kind enough to suggest a few changes to the parser from the previous blog post. Two of the three regular expressions were replaced with calls to the Marpa recognizer. The first one was replaced with a call to the pause_span method, which returns the start and length of the lexeme that caused the pause. Passing these two values to the literal method which returns the substring from the input string....
I already wrote that I’m quite interested in the things Marpa can do for writing parsers. The latest release of Marpa includes an addition that makes parsing strange languages even more possible. The new functionality allows you to control the parser from your own code while it doesn’t stop you from using the internal scanner. To try out this new functionality in Marpa I tried to write a parser for a small language with just one function and heredocs....
Yesterday I released a piece of code the includes a parser, a rewriter and serializer for a small expression language. The code is an example how you can parse source code and build a tree, rewrite the tree using two expressions and serialize the tree back to a piece of ‘code’. The idea that I used here was to improve the language by adding a way to specify structural variables. The variables start with a colon :, but are otherwise like variables....
Last year I wrote about how we can build an extended syntax for Marpa on top of the basic interface. For the counted rule lhs ::= rhs{5} where you want to match the right hand side multiple times, we can just generate the rhs item 5 times. This isn’t the right thing. Jeffrey pointed out that you can build these {min,max} rules up out of blocks. Then I remembered a piece of code from Elements of Programming which explained that it’s possible to generate the Fibonacci series in O(log n) time....
I have been thinking on and off about how to make Marpa parse a template language. I tried many different ways to create a tokenizer for this parser, but until this week I couldn’t get something reliable. The week I started with the tokenizer from the example code from Jeffrey Kegler’s blog post about how to develop a parser iteratively. This got me on the right track to create my parser....
In my last post I wrote about what the different rewrites of more advanced rules would look like. The question now is, when do you have a grammar that’s basic enough? This is the basic configuration of the Marpa::XS class. In this configuration you can specify left hand sides and right hand sides and the star and plus operator. If your tree looks like this, then it’s basic enough. Parser ::= Rule+ Rule ::= Lhs DeclareOp Rhs Lhs ::= Name Rhs ::= Names Rhs ::= Name Star Rhs ::= Name Plus Names ::= Name+ This grammar consists of only 7 lines, so that’s pretty good....
Let’s try to write some rewrite rules for a next level Marpa to a lower level Marpa. The syntax is not important, this is about how we can rewrite the rules. In the actual grammars none of the left side patterns work, but all of the right side rewritten version should work. Alternations An alternation is a rule that can match either way B, C or D. A ::= B | C => A ::= B A ::= C A ::= B | C | D => A ::= B A ::= C A ::= D Plus, Star Plus means match one or more times, star means match zero of more times....
Tonight I wrote this parser in Perl with Marpa::XS. The nice thing about Marpa is that it will tell you which terminals (or tokens) it expects at the current position. So instead of guessing what the next token will be you can just try to parse a token and try it. I got the general idea from the TAP::Spec::Parser. The difference is that it will try all alternatives at once, while mine tries each after the other until one works....
I just wrote a small program to parse and generate a parser that parses Marpa. Marpa itself doesn’t include such a program for good reasons I assume. Or if it exists I couldn’t find it. But as this is a small program it only generates a part of the parser. It is also not bootstrapping. The repository contains a small tokenizer written in Perl. It tokenizes a line of text and passes this on to the token recognizer, which in turn calls the grammer....