Разбор строки с вложенными скобками с помощью Parse::RecDescent

Я пытаюсь использовать Parse::RecDescent для создания синтаксического анализатора, который может анализировать выражения в скобках и унарный оператор ?.

То, что у меня есть до сих пор, терпит неудачу, когда я создаю парсер, потому что правило expression является леворекурсивным:

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";
}

parsing parentheses perl parse-recdescent
person Nate Glenn    schedule 05.07.2012    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Во-первых, вы переходите от низшего приоритета к высшему.

parse  : expr /\Z/

expr   : list

list   : unary(s?)

unary  : unary '?'
       | term

term   : '(' expr ')'
       | STRING

STRING : /\w+/

Конечно,

unary  : unary '?'
       | term

не работает, потому что он леворекурсивный. Ассоциативность операторов и устранение левой рекурсии в Parse::RecDescent помогут избавиться от нее. Мы получили

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

Но это не поможет нам построить правильное дерево. Итак, давайте начнем с того, что выровняем «(s?)».

unary  : term unary_
unary_ : '?' unary_
       |

Затем мы можем использовать аргументы подправила для создания правильного дерева.

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

Все вместе:

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));
person ikegami    schedule 05.07.2012
comment
упс, это должно быть /\Z/. /\Z/ нужно убедиться, что после ваших выражений нет мусора. Рассмотрим ввод ( foo ) ) bar. Без /\Z/ неверный ) bar будет молча игнорироваться. - person ikegami; 06.07.2012
comment
Как и я, я не могу заставить его правильно разобрать выражение. Можете ли вы объяснить действия немного больше? unary соответствует, передавая термин в качестве аргумента unary_, который либо ничего не соответствует и возвращает аргумент обратно, либо соответствует '?' и вызывает унарный массив с анонимным массивом, состоящим из одного хэша значения, который... ммм... - person Nate Glenn; 06.07.2012
comment
Вы поймете это лучше, если добавите еще один унарный оператор к unary_. Цель состоит в том, чтобы создать [ 'postfix+' => [ 'postfix?' => [ string => 'foo' ] ] ] для foo?+ и [ 'postfix?' => [ 'postfix+' => [ string => 'foo' ] ] ] для foo+?. Я предлагаю вам прочитать связанный пост. - person ikegami; 06.07.2012
comment
Это не работает для связанного ввода, потому что я сделал ошибку в понимании вашей грамматики. Фиксированный. - person ikegami; 06.07.2012
comment
Добавлено еще несколько деталей для завершения кода. В частности, теперь он строит полезное расширяемое дерево синтаксического анализа. - person ikegami; 06.07.2012
comment
Чувак, это супер полезно. Это здорово, что вы нашли время вернуться и сделать это после того, как я уже принял ваш ответ. - person Nate Glenn; 06.07.2012