Реализация приоритетности операторов с помощью грамматик Perl 5

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

Таблица приоритетности операторов

Приоритетность в математических ( и в любых других ) выражениях - вещь очень привычная. Для простого выражения:

3 + 5 * 6 

сначала будет выполнена операция умножения, а затем - сложения. Синтаксическое дерево можно представить в следующем виде :

+( *(5,6), 3 )

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

( 3 + 5 ) * 6 

Синтаксическое дерево будет выглядеть иначе:

*( +(3,5), 6 )

Как видим группирующие скобки вносят корректировку в последовательность вычислений.

И еще один пример выражения:

- (2 * -3)

в котором используется унарный оператор - (минус) перед группирующей скобкой. Для него дерево будет следующее:

-( *(2,-3) )

Унарный - имеет более высокий приоритет по сравнению с *.

Исходя из приведенных примеров можно составить таблицу приоритетов (3 - высший приоритет):

Грамматика, реализующая приоритетность, выглядит так:

 my $q = qr{
     <expr>
    <rule: expr>
                # бинарные операции +-
                <a=mult> <op=([+-])> <b=expr> 
                | <MATCH=mult> 

    <rule: mult> 
                <a=term> <op=([*/])> <b=mult> 
                | <MATCH=term>

     <rule: term> 
              <MATCH=Digit> 
            | <Sign=([+-])> \( <expr>\) # unary-
            | \( <MATCH=expr> \)   # группирующие скобки

    #токен, описывающий допустимый числовой агрумент
    <token: Digit>
            [+-]? \d++ (?: \. \d++ )?+ 
    }xms;

Как видим поиск совпадений начинается с поиска наиболее приоритетного унарного минуса и учета группирующих скобок (токен term), затем - операции * и / (правило mult) и т.д.

Представление синтаксичеcкого дерева в памяти

Результат успешной работы грамматик (структура совпадений правил) сохраняется в переменной %/. Отобразить результат можно следующим кодом:

use Data::Dumper;
    my $t = q! 3 + 5 * 6 !;
    if ($t =~ $q) {
        print Dumper \%/;
    } else {
     warn "Error parse"
    }

Так, для исходного примера 3 + 5 * 6, результат применения грамматик будет выглядеть следующим образом:

      # 3 + 5 * 6 
      {
          'a' => '3', # первый аргумент - число
          # второй аргумент - выражение
          'b' => {    
                   'a' => '5',
                   'b' => '6',
                   'op' => '*'
                 },
          'op' => '+' # оператор
       };

Для выражения с унарным минусом:

     #- (2 * -3)
     {
     'expr' => {
                  'a' => '2',
                  'b' => '-3',
                  'op' => '*'
                },
     'Sign' => '-' 
     }

Чтобы полученные структуры можно было использовать как элементы синтаксического дерева, требуется ассоциировать с каждым правилом класс. Для этого достаточно заменить rule на objrule с указанием класса:

    <objrule: ExpClass::mult>  # объект оператора
                <a=term> <op=([*/])> <b=mult> 
                | <MATCH=term>

В результате мы получаем структуру объектов, построенную в соответствии с приоритетностью, определенной на уровне грамматик.