Parsing string with nested parentheses using Parse::RecDescent

Question

I'm trying to use Parse::RecDescent make a parser which can parse parenthetical expressions and the unary operator ?.

What I have so far is failing when I create the parser because the rule expression is left-recursive:

use strict;
use warnings;
use Parse::RecDescent;

my $test = <<END;
((foo)? bar)
END

my $grammar = q(
    parse: expression(s)
    expression: string | parend | expression(s)
    parend : "(" (string | expression) ")" /\??/
    string : /\w+/ /\??/

);
my $parser = Parse::RecDescent->new($grammar);
my $result = $parser->parse($test);
if($result){
    print $result;
}else{
    print STDERR "Invalid grammar\n";
}

ikegami · Accepted Answer · 2012-07-05T21:54:26.073

6

First, you go from lowest priority to highest priority.

parse  : expr /\Z/

expr   : list

list   : unary(s?)

unary  : unary '?'
       | term

term   : '(' expr ')'
       | STRING

STRING : /\w+/

Of course,

unary  : unary '?'
       | term

doesn't work because it's left-recursive. Operator Associativity and Eliminating Left-Recursion in Parse::RecDescent can help you get rid of it. We get

unary  : term unary_(s?)
unary_ : '?'

But that's not going to construct the right tree for us. So let's start by flattinging out the "(s?)".

unary  : term unary_
unary_ : '?' unary_
       |

Then we can use subrule args to create the right tree.

unary  : term unary_[ $item[1] ]
unary_ : '?' unary_[ [ 'postfix?' => $arg[0] ] ]
       | { $arg[0] }

All together:

use strict;
use warnings;
use Data::Dumper      qw( Dumper );
use Parse::RecDescent qw( );

my $grammar = <<'END';
   {
      use strict;
      use warnings;
   }

   parse  : expr /\Z/ { $item[1] }

   expr   : list

   list   : unary(s?) { [ $item[0] => @{ $item[1] } ] }

   unary  : term unary_[ $item[1] ]
   unary_ : '?' unary_[ [ 'postfix?' => $arg[0] ] ]
          | { $arg[0] }

   term   : '(' expr ')' { $item[2] }
          | STRING { [ string => $item[1] ] }

   STRING : /\w+/

END

my $parser = Parse::RecDescent->new($grammar)
   or die "Invalid grammar\n";
my $tree = $parser->parse("((foo bar)? baz)\n")
   or die "Invalid text\n";
print(Dumper($tree));

edited Jul 05 '12 at 21:54

answered Jul 05 '12 at 19:31

ikegami

367,544
15
269
518

oops, that should be `/\Z/`. The `/\Z/` is to make sure there's no junk after your expressions. Consider the input `( foo ) ) bar`. Without `/\Z/`, the incorrect `) bar` would silently be ignored. – ikegami Jul 05 '12 at 20:03
As is I can't get it to properly parse the expression. Can you explain the actions a little more? unary matches, passing the term as an argument to unary_, which either matches nothing and passes the argument back or matches the '?' and calls unary with an anonymous array consisting of one value hash that... uhhmmm... – Nate Glenn Jul 05 '12 at 20:03
You'll understand it better if you add another unary operator to `unary_`. The goal is to create `[ 'postfix+' => [ 'postfix?' => [ string => 'foo' ] ] ]` for `foo?+` and `[ 'postfix?' => [ 'postfix+' => [ string => 'foo' ] ] ]` for `foo+?`. I suggest you read the linked post. – ikegami Jul 05 '12 at 20:06
It doesn't work for the linked input cause I made an error in understanding your grammar. Fixed. – ikegami Jul 05 '12 at 20:16
Added a few more details to complete code. Specifically, it now builds a useful, extendable parse tree. – ikegami Jul 05 '12 at 21:55
Man, this is super useful. It's awesome that you'd take the time to come back and do this after I'd already accepted your answer. – Nate Glenn Jul 05 '12 at 22:21

Parsing string with nested parentheses using Parse::RecDescent

1 Answers1

Linked