Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Example of Perl 6 grammar with operator precedence rules

I am very new to Perl and want to create a domain specific language with operators which have precedence using the new Perl 6 grammar features. For example to parse "1 + 2 * 6" in the correct way.

The documentation I've found until now (e.g. this) hasn't got examples with grammar rules for operators with precedence declarations.

I have this very simple example

use v6;

#use Grammar::Tracer;

grammar TestGrammar {

    token TOP {
        <digit> <infix> <digit>
    }

    token infix:sym<times> is equiv(&infix:<*>) { <sym> }

}

sub MAIN() {
    my $text = "1 times 2" ;
    say $text ;

    my $match = TestGrammar.parse($text);
    say $match;
}

This gives me

No such method 'infix' for invocant of type 'TestGrammar'

I just want to construct an abstract syntax tree.

like image 910
user2660278 Avatar asked Sep 01 '13 17:09

user2660278


1 Answers

AFAIK you can't setup infix operators and define precedence etc in grammars. These are only currently applicable to extending Perl 6.

Here a possible approach. It parses multiplicative terms before additions and also allows words or symbols, e.g. times or *.

use v6;

grammar TestGrammar {

    rule TOP      { <expr=.add> }

    rule add      { <expr=.multiply> +% [ <add-op> ] }
    rule multiply { <digit> +%  [ <mult-op> ] }

    proto token mult-op {*}
    token mult-op:sym<times>   { <sym>|'*' }
    token mult-op:sym<divided> { <sym>|'/' }

    proto token add-op {*}
    token add-op:sym<plus>     { <sym>|'+' }
    token add-op:sym<minus>    { <sym>|'-' }

}

sub MAIN() {
    for ("2+2", "2 + 2", "1 * 2", "1 + 2 * 6", "4 times 7 minus 3") {
        say $_;
        my $match = TestGrammar.parse($_);
        say $match;
    }
}

Note that % is the separator operator. <digit> +% [ <mult-op> ] means a list of digits separated by multiplicative operators (times, *, divided or /).

Alternate Solution Sep 2014:

S05 does mention that although rules and tokens are special methods, both can be declared as multi and take arguments just like regular methods.

This approach takes advantage of both recursion and multi-dispatch to implement operator precedence levels.

use v6;

grammar TestGrammar {

    rule TOP                { <expr(3)> }

    # operator multi-dispatch, loosest to tightest
    multi token op(3) {'+'|'-'|add|minus}
    multi token op(2) {'*'|'/'|times|divided}
    multi token op(1) {'**'}

    # expression multi-dispatch (recursive)
    multi rule expr(0)      { <digit> | '(' ~ ')' <expr(3)> }
    multi rule expr($pred)  { <expr($pred-1)> +% [ <op($pred)> ] }

}

sub MAIN() {
    for ("2+2", "2 + 2", "1 * 2", "1 + 2**3 * 6", "4 times (7 minus 3) * 3") {
        say $_;
        my $match = TestGrammar.parse($_);
        say $match;
    }
}
like image 134
dwarring Avatar answered Nov 07 '22 17:11

dwarring