Analyse des tuples imbriqués à l'aide de regexp perl avec $^R

Question

Je veux apprendre comment créer un arbre syntaxique abstrait pour des tuples imbriqués en utilisant une regexp Perl avec exécution de code embarqué. Je peux facilement programmer cela en utilisant une grammaire Perl 6 et je suis conscient que l'utilisation de modules d'analyse syntaxique simplifierait la tâche en Perl 5, mais je pense que pour des tâches aussi simples, je devrais être capable de le faire sans modules en apprenant comment traduire mécaniquement à partir des définitions de la grammaire. Je n'ai pas trouvé de moyen de déréférencer $^R, alors j'essaie d'annuler l'imbrication involontaire à la fin de la définition de la règle TUPLE, mais le résultat est incorrect, par exemple certaines sous-chaînes apparaissent deux fois.

use v5.10;
use Data::Dumper;

while (<DATA>) {
    chomp;
    /(?&TUPLE)(?{$a = $^R})
    (?(DEFINE)
        (?<TUPLE>
            T \s (?&ELEM) \s (?&ELEM)
            (?{ [$^R->[0][0],[$^R->[0][1],$^R[1]]] })
        )
        (?<ELEM>
            (?: (a) (?{ [$^R,$^N] }) | \( (?&TUPLE) \) )
        )
    )/x;
    say Dumper $a;
}

__DATA__
T a a
T (T a a) a
T a (T a a)
T (T a a) (T a a)
T (T (T a a) a) (T a (T a a))

La structure de données de sortie attendue est une liste imbriquée :

['a','a'];
['a',['a','a']];
[['a','a'],'a'];
[['a','a'],['a','a']];
[[['a','a'],'a'],['a',['a','a']]]

Pour référence, je vais également partager mon code Perl 6 fonctionnel :

grammar Tuple {
  token TOP { 'T ' <elem> ' ' <elem> }
  token elem { 'a' | '(' <TOP> ')'}
}
class Actions {
  method TOP($/) {make ($<elem>[0].made, $<elem>[1].made)}
  method elem($/) {make $<TOP> ?? $<TOP>.made !! 'a'}
}

Answer 1

J'essaie de comprendre comment utiliser (?{ ... }) n'en vaut presque jamais la peine. En particulier, cela peut avoir un comportement inattendu ainsi que du backtracking. Il est également très difficile de déboguer de telles regex puisque le flux de contrôle a tendance à ne pas être évident.

Au lieu de cela, il est généralement plus facile d'écrire un analyseur récursif ad-hoc en descente avec m//gc -lexicalisation de style : Chaque chaîne Perl stocke le décalage de la dernière correspondance. Lorsque vous appliquez une regex avec m/\G ... /gc dans un contexte scalaire, il peut s'ancrer au dernier décalage et avancer le décalage si la correspondance réussit.

Ici :

use strict;
use warnings;
use Test::More;

sub parse {
  my ($str) = @_;
  pos($str) = 0;  # set match position to beginning
  return parse_tuple(\$str);
}

sub parse_tuple {
  my ($ref) = @_;
  $$ref =~ /\G T \s/gcx or die error($ref, "expected tuple start T");
  my $car = parse_element($ref);
  $$ref =~ /\G \s /gcx or die error($ref, "expected space between tuple elements");
  my $cdr = parse_element($ref);
  return [$car, $cdr];
}

sub parse_element {
  my ($ref) = @_;
  return 'a' if $$ref =~ /\G a /gcx;

  $$ref =~ /\G \( /gcx or die error($ref, "expected opening paren for nested tuple");
  my $tuple = parse_tuple($ref);
  $$ref =~ /\G \) /gcx or die error($ref, "expected closing paren after nested tuple");
  return $tuple;
}

sub error {
  my ($ref, $msg) = @_;
  my $snippet = substr $$ref, pos($$ref), 20;
  return "$msg just before '$snippet...'";
}

is_deeply parse('T a a'), ['a','a'];
is_deeply parse('T (T a a) a'), [['a','a'],'a'];
is_deeply parse('T a (T a a)'), ['a',['a','a']];
is_deeply parse('T (T a a) (T a a)'), [['a','a'],['a','a']];
is_deeply parse('T (T (T a a) a) (T a (T a a))'), [[['a','a'],'a'],['a',['a','a']]];
done_testing;

Answer 2

J'ai corrigé le code dans ma question. Il s'avère que j'ai accidentellement écrit $^R[1] au lieu de $^R->[1] . Je comprends maintenant pourquoi amon a dit que ces constructions sont difficiles à déboguer ;-)

use v5.10;
use Data::Dumper;

while (<DATA>) {
    chomp;
    /(?&TUPLE)(?{$a = $^R->[1]})
    (?(DEFINE)
        (?<TUPLE>
            T \s (?&ELEM) \s (?&ELEM)
            (?{ [$^R->[0][0],[$^R->[0][1],$^R->[1]]] })
        )
        (?<ELEM>
            (?: (a) (?{ [$^R,$^N] }) | \( (?&TUPLE) \) )
        )
    )/x;
    say Dumper $a;
}

__DATA__
T a a
T (T a a) a
T a (T a a)
T (T a a) (T a a)
T (T (T a a) a) (T a (T a a))