Rewriting Marpa rules

[Peter Stuifzand]

Hi,

I wrote down a few of the ways that we could rewrite rules for a Marpa grammar.

http://peterstuifzand.nl/2012/04/04/rewriting-marpa-rules.html

To the left side of the "=>" is a possible syntax. On the right side is the way this should be written for a real parser. The right hand side can actually be parsed by MarpaX::Parser::Marpa.

Are there any other ways that we can rewrite rules? I was also thinking about a way to include multiple grammars into one file, that could be cool.

--
Peter Stuifzand

[Jeffrey Kegler]

Alberto Simões and I have been talking, in connection with an article he would present at SLATE '12 in Braga, Portugal, about precedence.  That is, some people prefer to write the grammar

E ::= E + T
E ::= T
T ::= T * F
T ::= F
F :: number

as

E ::= E + E, precedence = '+', associativity = left
E ::= E * E, precedence = '*', associativity = left
E ::= number, precedence = 'term'

and then specify that the precedence from highest to lowest is 'term', '*', '+'.  This is how the Perl expression syntax is described in the perlop man page, and the precedence form is more convenient than the pure BNF when expressions get very complicated.  I believe the transformation from the precedence form to the pure BNF form that Marpa::XS accepts can be done mechanically.

-- jeffrey

[Ron Savage]

Hi Jeffrey

On 05/04/12 12:42, Jeffrey Kegler wrote:
> Alberto Simões and I have been talking, in connection with an article he
> would present at SLATE '12 in Braga, Portugal, about precedence. That is,
> some people prefer to write the grammar
>
> E ::= E + T
> E ::= T
> T ::= T * F
> T ::= F
> F :: number
>
> as
>
> E ::= E + E, precedence = '+', associativity = left
> E ::= E * E, precedence = '*', associativity = left
> E ::= number, precedence = 'term'
>
> and then specify that the precedence from highest to lowest is 'term', '*',
> '+'. This is how the Perl expression syntax is described in the perlop man
> page, and the precedence form is more convenient than the pure BNF when
> expressions get very complicated. I believe the transformation from the
> precedence form to the pure BNF form that Marpa::XS accepts can be done
> mechanically.

That sure looks labourious to construct. I hope the current syntax will
continue to be supported even if you allow the above to be used.......

--
Ron Savage
http://savage.net.au/
Ph: 0421 920 622

[Jeffrey Kegler]

The context of my remark is Peter's higher-level interface to Marpa.  Peter was asking about syntaxes that might be worth supporting, in addition to those directly supported by Marpa::XS, Marpa::R2, etc.

-- jeffrey

[Ruslan Zakirov]

On Thu, Apr 5, 2012 at 01:27, Peter Stuifzand <peter.s...@gmail.com> wrote:
> Are there any other ways that we can rewrite rules? I was also thinking
> about a way to include multiple grammars into one file, that could be cool.

[rule] as alternative to rule{0,1}.

--
Best regards, Ruslan.

[Jeffrey Kegler]

I've coded up some thoughts about the efficient rewriting of min,max rules.  The code is a gist on github.

The basic idea is to factor the ranges into powers of two and their remainders.  In this way, the number of rules grows logarithmically, and the parsing, even for large min, max numbers, can be quite efficient.  The trick is to make sure the rules are not ambiguous.  Here's a set of BNF rules for "X{7,42}".  Fixed size sequences of size N are named block_N, and sequences of X's which range from size 0 to size N are named "range_N".  The final rule is for "range_7_42", which is all series of X's of length anywhere from 7 to 42.

block_0 ::=
block_1 ::= X
block_16 ::= block_8 block_8
block_2 ::= X X
block_3 ::= X X X
block_32 ::= block_16 block_16
block_4 ::= block_2 block_2
block_7 ::= block_4 block_3
block_8 ::= block_4 block_4
range_15 ::= range_7
range_15 ::= block_8 range_7
range_3 ::= block_0
range_3 ::= block_1
range_3 ::= block_2
range_3 ::= block_3
range_31 ::= range_15
range_31 ::= block_16 range_15
range_35 ::= range_31
range_35 ::= block_32 range_3
range_7 ::= range_3
range_7 ::= block_4 range_3
repeat_7_42 ::= block_7 range_35

I haven't tested this BNF, but I think this all works out, and in Marpa it should be quite efficient.

-- jeffrey  kegler

On Wednesday, April 4, 2012 2:27:53 PM UTC-7, Peter Stuifzand wrote:

[Peter Stuifzand]

that reminds me of the fibonacci algorithm that uses the power function and a matrix multiply from chapter 3 of "Elements of Programming".

I used that to create the X{N} version of that rule. Code on GitHub.

It produces this for X{42}. A block_N is X repeated N times.

block_1  ::=  X
block_2  ::=  X X
block_4  ::=  block_2 block_2
block_8  ::=  block_4 block_4
block_16  ::=  block_8 block_8
block_32  ::=  block_16 block_16
block_40  ::=  block_32 block_8
block_42  ::=  block_40 block_2

I'm not sure if this would work, but looking a Jeffrey's example, this should be a reasonable way to make this work.

[Jeffrey Kegler]

For those following this discussion of factoring min-max rules, just in case the motive for what Peter & I are talking about is unclear, if you write X{42,8675309} the immediately obvious way, that's 8,675,268 rules.  If you use the min-max to BNF rewriter to generate the BNF, it does the same job with 95 rules.

-- jeffrey