simple grammar example
Aldo Calpini
I'm preparing a talk about Perl6 for the Italian Perl Workshop, and I
would like to have a slide comparing a BNF (yacc/bison) grammar to a
Perl6 one, to show how powerful in parsing/lexing Perl6 regexen are.
so I ask your assistance in helping me putting up a simple, yet
impressive enough, sample.
I've taken this bison example (an RPN calculator, stripped down version
from http://www.gnu.org/software/bison/manual/html_node/Rpcalc-Rules.html):
input: /* empty */
| input line
;
line: '\n'
| exp '\n'
;
exp: NUM
| exp exp '+'
| exp exp '-'
| exp exp '*'
| exp exp '/'
;
%%
and this is my attempt at a "port" to Perl6:
grammar RPN {
rule input { <line>* }
rule line { <exp>? \n }
rule exp {
[ NUM
| <exp> <exp> <'+'>
| <exp> <exp> <'-'>
| <exp> <exp> <'*'>
| <exp> <exp> <'/'>
]
}
rule NUM { \d+ } # could be more complex, I know :-)
}
if $data ~~ RPN.input { say "valid RPN data" }
am I missing something obvious here? will the above code work in Perl6?
do you have perhaps a better example, or just an idea about what to show?
cheers,
Aldo
Luke Palmer
Looks good. This doesn't grok whitespace, so it will accept:
3+4*5
But not
3 + 4 * 5
So you need to add a C<:w> modifier to your C<exp> rule.
Also, if this is going to be an explanation rather than just a picture,
I suggest you go with Perl's usual versatile power, and store the
operators in a declarative data source.
grammar RPN {
my @operator = << + - * / >>;
rule input { <line>* }
rule line { <exp>? \n }
rule exp :w{ <NUM> | <@operator> }
rule NUM { \d+ }
}
if $data ~~ /<RPN.input>/ { say "valid expression" }
Luke
Sean O'Rourke
> I'm preparing a talk about Perl6 for the Italian Perl Workshop, and I
> would like to have a slide comparing a BNF (yacc/bison) grammar to a
> Perl6 one, to show how powerful in parsing/lexing Perl6 regexen are.
> am I missing something obvious here? will the above code work in Perl6?
> do you have perhaps a better example, or just an idea about what to show?
A few points:
* Remember that with Yacc, you also need a lexer, while P6 combines
lexing and parsing. Though it would complicate the example, it
would make P6 look better to include a lex definition for NUM and
the regex rule in P6.
* I'd do infix, because it's not too much more complex, because it's
more natural and familiar, and because it will show the differences
in how you write recursive descent versus LALR grammars.
* To really show where P6 rocks, you need to show dynamic features. A
simple example might be using a language with keywords kept in
variables, allowing you change between e.g. "for, while, if", "pour,
tandis-que, si", etc. (hey, you could use LWP::Simple to babelfish
your language on the fly!). A more complicated example might parse
a construct that would add rules to the grammar, something that
would be really hard with Yacc.
/s
Rafael Garcia-Suarez
> Also, if this is going to be an explanation rather than just a picture,
> I suggest you go with Perl's usual versatile power, and store the
> operators in a declarative data source.
>
> grammar RPN {
> my @operator = << + - * / >>;
>
> rule input { <line>* }
> rule line { <exp>? \n }
> rule exp :w{ <NUM> | <@operator> }
>
> rule NUM { \d+ }
This becomes too weak.
rule exp :w{ <NUM> | <exp> <exp> <@binary_operator> }
is stronger.
But it involves left-recursion, so it's typically better adapted to
yacc-like parser generators. Probably not to P6 rules...
Rafael Garcia-Suarez
> * To really show where P6 rocks, you need to show dynamic features. A
> simple example might be using a language with keywords kept in
> variables, allowing you change between e.g. "for, while, if", "pour,
> tandis-que, si", etc.
Small correction : "pour, tant_que, si" :)
Sean O'Rourke
Ouch! High school French fails me once again...
/s
Luke Palmer
Whoops, yeah, that's what I meant to write. That is, after I realized
we were working with an RPN caluclator and not an infix one. And even
then my brain was broken.
That left recursion won't do. I can't remember my transformation rules
well enough to know how to put that in a form suitable for a recursive
descent parser. To be honest, I've never seen an RPN calculator modeled
with a grammar.
To be sure, a prefix calculator should be the easiest:
rule exp :w { <@operator> <exp> <exp> | <NUM> }
Luke
Rafael Garcia-Suarez
> That left recursion won't do. I can't remember my transformation rules
> well enough to know how to put that in a form suitable for a recursive
> descent parser. To be honest, I've never seen an RPN calculator modeled
> with a grammar.
Well, the main advantage of an RPM syntax is to avoid the need for a
grammar. The parsing stack and the execution stack are the same.
> To be sure, a prefix calculator should be the easiest:
>
> rule exp :w { <@operator> <exp> <exp> | <NUM> }
Indeed.
With infix operators you need precedences.
Garrett Goebel
>
> I'm preparing a talk about Perl6 for the Italian Perl Workshop, and I
> would like to have a slide comparing a BNF (yacc/bison) grammar to a
> Perl6 one, to show how powerful in parsing/lexing
> Perl6 regexen are.
>
> impressive enough, sample.
Since you're doing slides, I don't know how useful this will be, but I
noticed the other day that Damian has released Perl6::Rules.
http://search.cpan.org/~dconway/Perl6-Rules-0.03/Rules.pm
It's the long promised implementation of Perl 6 regex syntax in Perl 5. It
implements most, but not all of Perl 6 regex syntax due to limitations of
Perl 5.
--
Garrett Goebel
IS Development Specialist
ScriptPro Direct: 913.403.5261
5828 Reeds Road Main: 913.384.1008
Mission, KS 66202 Fax: 913.384.2180
www.scriptpro.com gar...@scriptpro.com