Синтаксический анализ XML

Скорее всего можно было бы написать другую тему для этой статьи. Например: "когда можно применять грамматики, а когда нет" или "не всегда грамматики подходят", или вот такую модную "эти грамматики - они не всегда серебрянные". Но речь пойдет о обработке XML, в том числе с помощью грамматик Perl 5.

Задачей процесса синтаксического анализа текста почти всегда является построение дерева объектов. Каждый из объектов ассоциируется с той или иной сущностью обрабатываемого текста. Например, если производится обработка текста языка программирования, то объектами в итоге становятся операторы, подпрограммы, циклы или арифметические операторы. Поэтому, какие бы не взяли инструменты синтаксического анализа, в каждом присутствует механизм построения деревьев.

У меня возникла ситуация, когда грамматики оказались не самым оптимальным с точки зрения простоты решением. Конечно же важную роль играют исходные условия, а они такие: необходим синтаксический анализ XML. Ниже приведу пример такого XML:

<wd>
      <object class="isauth" id="auth_switch">
       <auth> 
        <object class="comp_unauth" id="ExitCP"/>
      </auth>
    </object>
    </wd>

Тэг wd является корневым, а его содержимое должно в итоге отобразиться в виде некой структуры в памяти:

<object class="isauth" id="auth_switch" >
        └── auth
            └──<object class="comp_unauth" id="ExitCP">

Решение с помощью грамматик Perl 5

Итоговое решение с помощью грамматик Perl 5 получилось следующее:

    use Regexp::Grammars;
    my $q = qr{
    \A <File> \Z
    
    # Описание блока целиком
    # <wd>...</wd>
    <rule: File><start_block> <[childs]>+ <end_block>
    <rule: start_block>\<wd>
    <rule: end_block>\<\/wd>
    
    #Допустимые тэги
    <token: childs>           
                     <MATCH=object> |
                     <MATCH=any_tag> 
    
    #objrule - создает объект указанного класса
    <objrule: WebDAO::Lexer::object> <tag( tagname=>'object' )>
    <objrule: WebDAO::Lexer::any_tag> <tag>
    
    <rule: attribute> <name=([_\w]+)>=['"]<value=(?: ([^'"]+) )>['"]
    
    #argument :tagname
    <rule: tag>
        <matchpos>
        <matchline>
        (?{  
            $ARG{'tagname'} = 
                defined ($ARG{'tagname'}) 
                    ? quotemeta $ARG{'tagname'}
                    : '(\w+)';
            # setup defaults
                $MATCH{childs} //=[];
                $MATCH{attribute} //=[];
         })
        (?:         
         < <tagname=:tagname> 
               <[attribute]>* />
        )
        |
        (?:
        < <tagname=:tagname> <[attribute]>* >
                    <[childs]>*
           </ <:tagname> >
        )
  }xms;

Для описания отдельно взятого тэга в примере используется правило rule:tag. Грамматики Perl 5 предоставляют возможность передачи параметров для правил. Эта особенность позволяет точно описать допустимые тэги:

    #Допустимые тэги
    <token: childs>           
                     <MATCH=object> |
                     <MATCH=any_tag> 
    # правило для тэга 'object' 
    <objrule: WebDAO::Lexer::object> <tag( tagname=>'object' )>>
    #если параметр tagname не указан, то допускается любой тэг
    <objrule: WebDAO::Lexer::any_tag> <tag>

Параметр tagname используется в описании тэга XML для двух допустимых форм:

        (?:
         # пустой тэг
         < <tagname=:tagname>  <[attribute]>* />
        )
        |
        (?:
        < <tagname=:tagname> <[attribute]>* >
            # допускаются вложенные тэги
                    <[childs]>*
           </ <:tagname> >
        )

В случае, если правило совпадает, то создается объект указанного класса:

    <objrule: WebDAO::Lexer::object> <tag( tagname=>'object' )>
    <objrule: WebDAO::Lexer::any_tag> <tag>

Итоговое дерево доступно после применения грамматики к исходному тексту:

if ( $txt =~ $q ) {
        #результат в переменной %/ 
        return {%/}->{File}->{childs};
    }

Наличие параметров для правил позволяет сократить количество кода и делает грамматики отдельным языком программирования.

Решение с помощью XML::Flow

Так как целью является синтаксическое дерево и простота решения, то здесь пригодилась библиотека XML::FLow для работы с XML ^[1]:

 sub parse {
    my $self     = shift;
    my $txt      = shift || return [];

    #Соответствие тэгов классам
    my %classmap = (
        object    => 'WebDAO::Lexer::object',
        default   => 'WebDAO::Lexer::any_tag',
    );
    our $result = [];
    
    # обработчики тэгов
    my %tags = (
        # корневой тэг
        wd => sub { shift; $result = \@_ },
        # * обработчик для любого тэга XML
        '*' => sub {
            my $name   = shift;
            my $a      = shift;
            my $childs = \@_;
            my $class  = $classmap{$name} || $classmap{'default'};
            #создаем экземпляр класса
            my $o = $class->new(
                name   => $name,
                attr   => $a,
                childs => $childs
            );
            #и возвращаем его как результат обработчика
            return $o;
        }
    );
    my $rd = new XML::Flow:: \$txt;
    $rd->read( \%tags );
    $result;
 }

Несмотря на то, что основное предназначение библиотеки - это серилизация структур данных в XML, есть и дополнительная возможность - синтаксическая обработка XML в потоковом режиме.

Принцип работы следующий: встретив закрывающий тэг XML, вызывается обработчик, которому в качестве параметров передаются атрибуты тэга и результаты обработчиков вложенных в него тэгов.

Например, для следующего XML:

<wd>
          <object>
                 <auth />
          </object>
    </wd>

Схема вызовов будет следующей:

call_wd (
        call_object ( 
               call_auth()
         )
    )

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

# корневой тэг
        wd => sub { shift; $result = \@_ },

А так как обработчики тэгов возвращают созданные объекты, то в переменную $result сохранится уже готовое дерево.

Итоги обоих решений

Решение с помощью XML::Flow получилось простым главным образом из-за наличия уже готовой библиотеки для работы с XML. Но это не уменьшает значимость грамматик в Perl 5 и вообще средств синтаксического анализа.

Если учесть прекращение развития XHTML и вообще общую тенденцию ухода от XML, то будущее однозначно за грамматиками !

^[1] Библиотека XML::Flow. http://search.cpan.org/perldoc?XML::Flow