Написание простого парсера в Perl: с выходом lexer, куда идти дальше?

Question

Я пытаюсь написать простой язык манипулирования данными в Perl (только для чтения, это означало для преобразования SQL-вдохновил запросов в фильтры и свойства для использования с Vsphere Perl API: http://pubs.vmware.com/vsphere-60/topic/com.vmware.perlsdk.pg.doc/viperl_advancedtopics.5.1.html_)

настоящее время у меня что-то подобное на выходе лексического анализатора, если я понимаю, это правильно - список лексем, как это (Data :: Dumper печатает массив хэшей):

$VAR1 = { 
     'word' => 'SHOW', 
     'part' => 'verb', 
     'position' => 0 
    }; 
$VAR2 = { 
     'part' => 'bareword', 
     'word' => 'name,', 
     'position' => 1 
    }; 
$VAR3 = { 
     'word' => 'cpu,', 
     'part' => 'bareword', 
     'position' => 2 
    }; 
$VAR4 = { 
     'word' => 'ram', 
     'part' => 'bareword', 
     'position' => 3 
    }; 

Теперь то, что я хотел бы сделать, это построить синтаксическое дерево. Документация, которую я видел до сих пор, в основном касается использования модулей и генерации грамматик из BNF, но на данный момент я не могу обернуть вокруг себя.

Я хотел бы поработать с относительно простым процедурным кодом, вероятно, рекурсивным, чтобы сделать некоторую уродливую реализацию самостоятельно.

То, что я в настоящее время думает о строит строку из $token->{'part'}s так:

my $parts = 'verb bareword bareword ... terminator'; 

, а затем работает большой и уродливый регулярное выражение против него, (аб), используя возможности Perl, чтобы вставить код в регулярные выражения: http://perldoc.perl.org/perlretut.html#A-bit-of-magic:-executing-Perl-code-in-a-regular-expression:

$parts =~/
    ^verb(?{ do_something_smart })\s  # Statement always starts with a verb 
    (bareword\s(?{ do_something_smart }))+ # Followed by one or more barewords 
    | # Or 
    # Other rules duct taped here 
/x; 

Все, что я нашел до сих пор требует твердого знания CS и/или лингвистики, и я не в состоянии даже понять.

Что мне делать с выходом lexer для начала понимания и tinker с правильным анализом? Что-то вроде «создайте набор временных хэшей, представляющих меньшую часть оператора» или «удалите подстроки, пока строка не будет пустой, а затем подтвердите, что вы получаете».

Я знаю книгу Дракона и SICP, но в это время мне бы хотелось что-то светлее.

Спасибо!

Answer 1

Как уже упоминалось в нескольких комментариях выше, но здесь снова, как реальный ответ:

Вы могли бы Parser::MGC. (Отказ от ответственности: Я являюсь автором)

Начните с определения существующих (regexp?) Определений различных видов токенов и превратите их в методы «токена -...» с помощью метода generic_token.

Здесь вы можете начать создавать методы для анализа больших и больших структур вашей грамматики с использованием методов построения структуры.

Что касается собственно построения АСТ - возможно, это проще всего, просто чтобы испустить HASH ссылки с ключами, содержащими именованные части вашей структуры. Трудно сказать грамматическую структуру из вашего примера, заданного в вопросе, но вы можете, например, иметь концепцию «команды», которая является «глаголом», за которым следуют некоторые «существительные». Вы можете разобрать, что с помощью:

sub parse_command 
{ 
    my $self = shift; 

    my $verb = $self->token_verb; 

    my $nouns = $self->sequence_of(sub { $self->token_noun }); 
     # $nouns here will be an ARRAYref 

    return { type => "command", verb => $verb, nouns => $nouns }; 
} 

Это, как правило, вокруг этой точки в написании парсера, который я решил, что хочет некоторые фактические типизированные объекты вместо простых ссылок хэша.Один простой способ сделать это через другой из моих модулей: Struct::Dumb:

use Struct::Dumb qw(-named_constructors); 
struct Command => [qw(verb nouns)]; 

... 
return Command(verb => $verb, nouns => $nouns);