Pragmatic Perl

Выпуск 26. Апрель 2015

Грамматики в Perl 6

В этой статье рассказано об одной из наиболее мощных возможностей Perl 6 — грамматиках

Грамматики в Perl 6 — развитие темы регулярных выражений. Они позволяют создавать сколь угодно сложные парсеры текстов, поэтому не выходя за рамки Perl 6 вполне получится создать и свой DSL, и свой транслятор или интерпретатор другого языка. В этой статье мы попытаемся сделать подход к этой сложной задаче и разобраться, что к чему.

Введение

Источники

Подробная документация содержится в документах Synopsis 5: Regexes and Rules и Grammars. Полезно также ознакомиться с методами классов Grammar и Match. Официальные тесты, которые могут служить неплохими примерами кода, находятся в каталоге t/spec/S05-grammar и t/spec/S05-match. Пример создания граматики для чтения JSON можно изучить в исходниках модуля JSON::Simple. Наконец, многое можно почерпнуть из доклада «Perl 6: what can you do today?» (доступна и видеозапись).

Терминология

В Perl 6 вместо термина регулярные выражения официально закреплено слово регекс (regex). Синтаксис новых регексов заметно отличается от того, что было в Perl 5, однако многие элементы (например, квантификаторы * или + выглядят знакомо). Регексы создают с помощью ключевого слова regex:

my regex weekday {[Mon | Tue | Wed | Thu | Fri | Sat | Sun]};

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

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

say 'Thu' ~~ m/<weekday>/;
say 'Thy' ~~ m/<weekday>/;

Эти два сопоставления выведут следующее:

「Thu」
 weekday => 「Thu」
False

Резутат сопоставления — объект типа Match. Если его напечатать, то совпавшие подстроки будут отмечены скобками вида 「...」.

Кроме простых регексов существуют правила и токены (соответственно, ключевые слова rule и token).

Отличие токенов от правил прежде всего в том, что внутри правил автоматически обрабатываются пробельные символы (whitespaces) в сопоставляемой строке, а в токенах они являются частью регекса. Это будет видно на примерах далее.

my token number_token { <[\d]> <[\d]> }
my rule number_rule { <[\d]> <[\d]> }

Конструкция <[...]> создает символьный класс. В этом примере строка 42 совпадет с токеном number_token, но не совпадет с правилом number_rule. И наоборот, строка 4 2 успешно совпадет только с правилом, но не с токеном.

Объект $/

Объект типа Match, который создается в результате сопоставления с регексом, будет помещен в переменную $/. Из него же можно достать совпавшие подстроки. Синтаксис для захвата совпавших строк — круглые скобки. Нумерация ведется начиная с нуля. Доступ к совпавшим элементам осуществляется либо как к элементам массива: $/[0], либо с помощью эквивалентной сокращенной записи: $0.

При этом важно помнить, что в этих элементах окажется элемент типа Match. Чтобы получить необходимое текстовое или числовое значение, следует явно указать контекст, например: ~$0 или +$0.

'Wed 15' ~~ /(\w+) \s (\d+)/;
say ~$0; # Wed
say +$1; # 15

Грамматики

Следующий уровень организации регексов — грамматики. Грамматика аналогична классу с той лишь разницей, что она объявляется ключевым словом grammar и содержит правила и токены вместо методов. Пример — уже в следующем разделе.

Простой парсер

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

x = 42;
y = x;
print x;
print y;
print 7;

Начнем создавать грамматику для этого мини-языка. Прежде всего, программа на таком языке — это последовательность инструкций (statements), разделенных точкой с запятой. Поэтому на верхем уровне грамматика будет выглядеть так:

grammar Lang {
    rule TOP {
        ^ <statements> $
    }
    rule statements {
        <statement>+ %% ';'
    }
}

Lang — название грамматики, TOP — начальное правило, именно с него будет начинаться разбор. Правило начинается символом ^, обозначающим начало текста, и заканчивается символом $, который должен совпасть с окончанием программы. (В правилах все пробелы обрабатываются интуитивно правильно, то есть в начале программы, например, может быть любое число пробельных символов.)

То, что стоит между ^ и $, целиком вынесено в отдельное правило <statements>. В свою очередь, оно представляет собой последовательность как минимум одной (+) инструкции: <statement>+, причем они должны разделяться точкой с запятой. Символ-разделитель указан после двух процентов. Если бы процент был один, то любая инструкция была бы должна заканчиваться точкой с запятой. А два процента позволяют не ставить точку с запятой после последней инструкции.

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

rule statement {
    | <assignment>
    | <printout>
}

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

rule statement {
      <assignment>
    | <printout>
}
rule statement {
    | <assignment>
    | <printout>
}

Далее определены правила для присваивания и печати.

rule assignment {
    <identifier> '=' <expression>
}
rule printout {
    'print' <expression>
}

Здесь вновь встречаются литеральные выражения — строки '=' и 'print', а наличие или отсутствие пробелов вокруг них в разбираемой программе не имеет значения.

Правило expression должно совпадать и с переменной, и с числом, то есть это буквально является либо тем, либо другим:

rule expression {
    | <identifier>
    | <value>
}

Осталось расшифровать, что является именем переменной (идентификатором) и числом. Для этого вместо правил лучше создать токены — в них пробелы должны быть указаны явно (пробелы около фигурных скобок, обрамляющих описание токена, не учитываются).

Идентификатором сделаем последовательность буквенных символов:

token identifier {
    <:alpha>+
}

Здесь <:alpha> — предопределенный символьный класс, совпадающий с буквами.

А значениями могут быть только целые числа, то есть последовательности цифр:

token value {
    \d+
}

Грамматика готова. Теперь с ее помощью можно разобрать тестовый файл:

my $parsed = Lang.parsefile('test.lang');

(Для разбора текста, содержащегося в переменной, в классе грамматики существует метод parse($str).)

Если программа в файле записана в соответствии с правилами грамматики Lang, в переменной $parsed окажется объект типа Match, который можно распечатать (say $parsed) и посмотреть, как была разобрана исходная программа:

「x = 42;
y = x;
print x;
print y;
print 7;
」
 statements => 「x = 42;
y = x;
print x;
print y;
print 7;
」
  statement => 「x = 42」
   assignment => 「x = 42」
    identifier => 「x」
    expression => 「42」
     value => 「42」
  statement => 「y = x」
   assignment => 「y = x」
    identifier => 「y」
    expression => 「x」
     identifier => 「x」
  statement => 「print x」
   printout => 「print x」
    expression => 「x」
     identifier => 「x」
  statement => 「print y」
   printout => 「print y」
    expression => 「y」
     identifier => 「y」
  statement => 「print 7」
   printout => 「print 7」
    expression => 「7」
     value => 「7」

Этот вывод содержит структуру разобранной программы, а совпавшие для каждого правила или токена строки видны в скобках 「...」. Сначала показано совпадение, содержащее весь текст программы (а иначе не могло быть, потому что в главном правиле явно указано ^ … $). А затем, начиная со <statements>, следует дерево разбора, сначала на отдельные инструкции, а затем вглубь до токенов identifier или value.

Если программа окажется грамматически неверной, то результатом будет пустое значение: (Any). То же самое произойдет, если с грамматикой совпадет не весь файл, а только его начало.

Полная грамматика на текущий момент выглядит так:

grammar Lang {
    rule TOP {
        ^ <statements> $
    }
    rule statements {
        <statement>+ %% ';'
    }
    rule statement {
        | <assignment>
        | <printout>
    }
    rule assignment {
        <identifier> '=' <expression>
    }
    rule printout {
        'print' <expression>
    }
    rule expression {
        | <identifier>
        | <value>
    }
    token identifier {
        <:alpha>+
    }
    token value {
        \d+
    }
}

Простой интерпретатор

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

Нынешний мини-язык работает с переменными и числами. Числа являеются константами и описывают сами себя. А для хранения значений переменных необходимо создать хранилище. В простейшем случае это хеш:

my %var;

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

Действие, которое помещает значение в переменную (и одновременно создает ее при первом упоминании), — assignment. В описанной выше грамматике справа от знака равенства ожидается выражение (expression), которое может быть либо другой переменной, чье значение придется отыскать, либо числом. Чтобы упростить поиск переменных в этом месте, немного усложним грамматику и распишем правила в виде двух альтернатив, избавившись, таким образом, от правила expression:

rule assignment {
    | <identifier> '=' <value>
    | <identifier> '=' <identifier>
}
rule printout {
    | 'print' <value>
    | 'print' <identifier>
}

Грамматика позволяет описывать действия на каждое правило и на каждый вариант, который она способна разобрать. Действия — это блоки кода, внутри которых доступен объект $/, а к совпавшим подобъектам можно напрямую обращаться, используя имя. Например, $<identifier> будет содержать объект типа Match, совпавший с одноименным правилом или токеном внутри другого правила.

rule assignment {
    | <identifier> '=' <value>       {say "$<identifier>=$<value>"}
    | <identifier> '=' <identifier>
}

При интерполяции "$<identifier>=$<value>" объекты преобразуются к строке, что в этом примере однозначно дает имя переменной. Вне строк в двойных кавычках, однако, преобразование следует делать явно:

rule assignment {
    | <identifier> '=' <value>       {%var{~$<identifier>} = +$<value>}
    | <identifier> '=' <identifier>
}

Итак, создано действие, выполняемое для присваивания значения переменной. То есть из исходной тестовой программы будет работать строка x = 42;.

Во втором варианте правила assignment имя <identifier> встречается дважды, поэтому ссылаться на него как $<identifier> уже не получится, поскольку там окажется список. Но достаточно указать индекс элемента:

rule assignment {
    | <identifier> '=' <value>       {%var{~$<identifier>} = +$<value>}
    | <identifier> '=' <identifier>  {%var{~$<identifier>[0]} = %var{~$<identifier>[1]}}
}

Теперь удалось выполнить действия для строки y = x.

Помимо использования имен возможно расставить захватывающие круглые скобки и использовать переменные типа $0:

rule assignment {
    | (<identifier>) '=' (<value>)       {%var{$0} = +$1}
    | (<identifier>) '=' (<identifier>)  {%var{$0} = %var{$1}}
}

Унарный ~ при использовании переменной в качестве ключа хеша тоже можно опустить. (Но если не поставить плюс в +$1, то вместо числа в переменной окажется объект Match.)

Аналогично записываются действия для печати:

rule printout {
    | 'print' <value>      {say +$<value>}
    | 'print' <identifier> {say %var{$<identifier>}}
}

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

x => 42, y => 42

А в результате вызова метода Lang.parsefile напечатается результат работы тестовой программы из файла test.lang:

42
42
7

Еще раз посмотрим на грамматику целиком, а заодно и на всю программу:

my %var;

grammar Lang {
    rule TOP {
        ^ <statements> $
    }
    rule statements {
        <statement>+ %% ';'
    }
    rule statement {
        | <assignment>
        | <printout>
    }
    rule assignment {
        | (<identifier>) '=' (<value>)       {%var{$0} = +$1}
        | (<identifier>) '=' (<identifier>)  {%var{$0} = %var{$1}}
    }
    rule printout {
        | 'print' <value>      {say +$<value>}
        | 'print' <identifier> {say %var{$<identifier>}}
    }
    token identifier {
        <:alpha>+
    }
    token value {
        \d+
    }
}

Lang.parsefile('test.lang');

Обратите внимание: после того, как в правиле появились круглые скобки, в объекте с разобранным исходным текстом появились поля с номерами 0 и 1. Именованные поля (identifier и др.) тоже сохраняются. Это хорошо видно на примере разбора конструкции y = x:

statement => 「y = x」
 assignment => 「y = x」
  0 => 「y」
   identifier => 「y」
  1 => 「x」
   identifier => 「x」

Действия (actions)

В предыдущем примере действия, выполняемые в ответ на совпадение, были оформлены в виде блока прямо внутри правила или токена. Это удобно для простых грамматик с простыми действиями, однако в Perl 6 предусмотрена возможность вынести все действия в отдельный класс.

Действия, соответствующие правилам грамматики, должны быть оформлены в виде одноименных методов класса. При вызове метода ему передается объект $/ типа Match, содержащий текущий разобранный фрагмент.

Методы parse и parsefile ожидают инстанс класса с действиями в параметре :actions:

grammar G {
    rule TOP {^ \d+ $} 
}
class A {
    method TOP($/) {say ~$/}
}
G.parse("42", :actions(A));

В этом примере и в грамматике G, и в классе A (от слова Actions) определены правило и метод с именем TOP. Далее при разборе текста "42" происходит удачное поглощение всего текста правилом ^ \d $, после чего вызывается метод A::TOP. Единственный аргумент $/ выводится на печать после явного (унарным оператором ~) преобразования в строку. В данном случае тот же результат даст и преобразование в число: say +$/.

AST и атрибуты

В предыдущем примере для разбора программы на мини-языке было исключено правило expression, из-за чего правила assignment и printout пришлось усложнить, перечислив в каждом из них альтернативы для всех возможных случаев, в нашем примере эти возможности — принять либо число, либо переменную. На этот шаг пришлось пойти, потому что иначе было непонятно, как получить значение, которое надо либо присвоить, либо вывести на печать, когда само значение вычленяется разными способами: для числа это делает токен value, а для переменной следует посмотреть в хеш %var по ключу, извлекаемому токеном identifier.

Рассмотрим, как вернуть стройность грамматики, одновременно сохранив возможность альтернативы. Итак, прежде всего возвращаем правило expression:

rule assignment {
    <identifier> '=' <expression>
}
rule printout {
    'print' <expression>
}
rule expression {
    | <identifier>
    | <value>
}

Построенная при разборе иерархия — синтаксическое дерево, способно хранить результаты выполнения действий на предыдущих (нижележащих) шагах. Специально для этого у объекта типа Match есть поле ast, а в каждом узле есть возможность непосредственно получать результат, вычисленный в дочерних узлах. AST = abstract syntax tree, и абстрактное оно именно потому, что при его использовании можно абстрагироваться от способа получения результата в текущем узле: имеется конкретный результат, а способ его вычисления неважен.

Действие может сохранить результат своей работы (и таким образом передать его выше по дереву), вызвав метод $/.make, который сохраняет данные, которые далее могут быть прочитаны из поля made (или используя синонимичное обращение ast).

Начнем заполнять атрибуты синтаксического дерева (то есть вычисленные значения, связанные с узлом), начиная с токенов identifier и value. Результат совпадения с первым из них — строка с именем переменной, второго — число:

method identifier($/) {
    $/.make(~$0);
}
method value($/) {
    $/.make(+$0);
}

Теперь поднимемся на уровень выше и построим значение для выражения (expression), которое может быть либо значением переменной, либо числом.

Поскольку правило expression содержит две альтернативы, нужно прежде всего понять, какая из них совпала, это легко сделать, проверив наличие в объекте $/ поля identifier или value. Запись $<identifier> — упрощенный вариант конструкции $/<identifier> (именно поэтому в качестве аргумента метода удобно использовать переменную $/, а не любую другую с обычным именем, например, $match).

Для каждой ветви результат вычисляется по-своему. Для числа это преобразование из поля value: +$<value>, а для переменной — чтение нужного значения из хеша: %var{$<identifier>}. Полученное значение сохраняется в атрибуте узла синтаксического дерева с помощью вызова $/.make().

method expression($/) {
    if $<identifier> {
        $/.make(%var{$<identifier>});
    }
    else {
        $/.make(+$<value>);
    }
}

Чтобы разрешить использовать еще необъявленные переменные, можно записать:

$/.make(%var{$<identifier>} // 0);

На этом этапе правило expression будет содержать конкретное значение, а было ли оно получено из константы или переменной — неважно. Поэтому сразу упрощается обработка вышележащих правил assignment и printout. Начнем со второго:

method printout($/) {
    say $<expression>.ast;
}

Все очень просто: на печать выводится значение, которое уже подготовлено и находится в поле ast.

Действие для правила assignment чуть посложнее, но тоже умещается в одну строку:

method assignment($/) {
    %var{$<identifier>} = $<expression>.made;
}

Этот метод при вызове должен получить объект $/, в котором есть поля identifier и expression. Первое преобразуется в строку и дает имя переменной. Из второго берется атрибут узла (для разнообразия на этот раз через вызов made).

Последнее замечание по поводу класса с действиями. Хеш %var, в котором хранятся значения переменных, целесообразно сделать данными класса, а не глобальной переменной. Соответственно, в классе появляется строка has %.var;, а обращение внутри методов будет выглядеть как %!var{...}.

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

Lang.parsefile('test.lang', :actions(LangActions.new()));

Полный пример грамматики с действиями для копипейста:

grammar Lang {
    rule TOP {
        ^ <statements> $
    }
    rule statements {
        <statement>+ %% ';'
    }
    rule statement {
        | <assignment>
        | <printout>
    }
    rule assignment {
        <identifier> '=' <expression>
    }
    rule printout {
        'print' <expression>
    }
    rule expression {
        | <identifier>
        | <value>
    }
    token identifier {
        (<:alpha>+)
    }
    token value {
        (\d+)
    }
}

class LangActions {
    has %var;

    method assignment($/) {
        %!var{$<identifier>} = $<expression>.made;
    }
    method printout($/) {
        say $<expression>.ast;
    }
    method expression($/) {
        if $<identifier> {
            $/.make(%!var{$<identifier>} // 0);
        }
        else {
            $/.make(+$<value>);
        }
    }
    method identifier($/) {
        $/.make(~$0);
    }
    method value($/) {
        $/.make(+$0);
    }
}

Lang.parsefile('test.lang', :actions(LangActions.new()));

Хочу обратить внимание на несколько головоломный момент. Имена переменных выделяет токен identifier, который сохраняет имя в атрибуте ast. При этом при разборе конструкции x = y токен срабатывает дважды, но дальнейшие действия с переменными будут зависеть от того, с какой стороны от знака равенства они стоят. Переменная x будет фигурировать внутри метода assignment, в то время как из переменной y будет сделано готовое значение в методе expression. У меня возник вопрос о том, как же так? уже только после того, как программа с написанной грамматикой заработала. Мораль этого лирического отступления: если аккуратно расписать правила языка, то грамматика будет работать правильно и как ожидалось.

Калькулятор

Рассказ про построение грамматики был бы не полным без классического примера — калькулятора, который умеет вычислять значение арифметического выражения произвольной сложности, состоящего из операций +, -, *, / и скобок. Этот пример хорош тем, что несмотря на простоту выполняемых действий он должен уметь делать вычисления с учетом приоритета операций и группировки, в том числе со вложенными скобками.

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

<term>+ %% ['+'|'-']

То же самое можно записать более традиционно:

<term> [['+'|'-'] <term>]*

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

<factor>+  %% ['*'|'/']

На месте term или factor может стоять либо значение value, либо подвыражение group, заключенное в скобки:

rule group {
    '(' <expression> ')'
}

Внутри скобок начинается новый виток рекурсии, и все, что находится в них, разбирается точно так же, как и выражение expression на верхнем уровне.

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

token value {
    | \d+['.' \d+]*
    | '.' \d+
}

Полная грамматика для калькулятора выглядит так:

grammar Calc {
    rule TOP {
        ^ <expression> $
    }
    rule expression {
        | <term>+ %% $<op>=(['+'|'-'])
        | <group>
    }
    rule term {
        <factor>+  %% $<op>=(['*'|'/'])
    }
    rule factor {
        | <value>
        | <group>
    }
    rule group {
        '(' <expression> ')'
    }
    token value {
        | \d+['.' \d+]*
        | '.' \d+
    }
}

Обратите внимание на конструкцю $<op>=(...) в правилах expression и term. Это именованный захват. Все, что находится в круглых скобках, окажется в поле $<op> переменной $/.

Теперь перейдем к классу действий. На верхнем уровне метод TOP возвращает вычисленное ниже значение, которое должно находиться в поле ast:

class CalcActions {
    method TOP($/) {
        $/.make: $<expression>.ast
    }

   . . .
}

Так же тривиально выглядят действия для вычисления group и value:

method group($/) {
    $/.make: $<expression>.ast
}

method value($/) {
    $/.make: +$/
}

Правило factor содержит две альтернативы, поэтому необходимо выбрать правильную ветвь, после чего все опять просто:

method factor($/) {
    if $<value> {
        $/.make: +$<value>
    }
    else {
        $/.make: $<group>.ast
    }
}

Теперь перейдем к правилу term. Здесь обработка чуть более сложная: во-первых, впервые встретилась необязательная последовательность, число повторений которой может быть любым. Во-вторых, необходимо определить, какая производится операция — умножение или деление. Символ арифметической операции сохраняется в переменной $<op>.

Дерево разбора для выражения 3*4*5 выглядит так:

expression => 「3*4*5」
 term => 「3*4*5」
  factor => 「3」
   value => 「3」
  op => 「*」
  factor => 「4」
   value => 「4」
  op => 「*」
 factor => 「5」
  value => 「5」

Здесь хорошо видно, что все factor и op находятся на одном уровне. Внутри действия они будут видны как элементы массивов $<factor> и $<op>. Всегда будет доступен как минимум один $<factor>. Сами значения узлов будут к этому моменту уже известны и находятся в ast. Соответственно, нужно пройтись по всем элементам этих двух массивов и сделать для каждого из них умножение или деление.

method term($/) {
    my $result = $<factor>[0].ast;

    if $<op> {
        my @ops = $<op>.map(~*);
        my @vals = $<factor>[1..*].map(*.ast);

        for 0..@ops.elems - 1 -> $c {
            if @ops[$c] eq '*' {
                $result *= @vals[$c];
            }
            else {
                $result /= @vals[$c];
            }
        }
    }

    $/.make: $result;
}

В этом коде звездочка встречается в новом качестве, как плейсхолдер, сообщающий перлу, что надо работать с тем, что есть под рукой.

Массив @ops, где хранится список символов операций, состоит из элементов, полученных из элементов массива $<op> путем преобразования в строку:

my @ops = $<op>.map(~*);

Сами значения, окажутся в массиве @vals. На этот раз значения взяты из поля ast. Чтобы массивы @vals и @ops точно соответствовали друг другу, из $<factor> взят срез, начиная со второго элемента:

my @vals = $<factor>[1..*].map(*.ast);

Действия для expression — либо взять вычисленное значение group, либо сделать последовательность сложений и вычитаний. Здесь алгоритм почти совпадает с тем, что только что делалось для умножения и деления:

method expression($/) {
    if $<group> {
        $/.make: $<group>.ast
    }
    else {
        my $result = $<term>[0].ast;

        if $<op> {
            my @ops = $<op>.map(~*);
            my @vals = $<term>[1..*].map(*.ast);

            for 0..@ops.elems - 1 -> $c {
                if @ops[$c] eq '+' {
                    $result += @vals[$c];
                }
                else {
                    $result -= @vals[$c];
                }
            }
        }

        $/.make: $result;
    }
}

Наконец, код, который будет направлять данные из аргумента командной строки на разбор и печатать результат:

my $calc = Calc.parse(@*ARGS[0], :actions(CalcActions));
say $calc.ast;

Проверка работоспособности калькулятора:

$ perl6 calc.pl '42 + 3.14 * (7 - 18 / (505 - 502)) - .14'
45

Читателю предлагается самостоятельно научить калькулятор работать с отрицательными числами, а затем соединить две грамматики таким образом, чтобы интерпретатор мини-языка умел вычислять арифмитические выражения (для этого надо модифицировать правило и действия expression), а затем разрешить использовать в выражениях переменные (здесь потребуется расширить правило term).

Задание со звездочкой (еще один смысл звездочки): разобраться с метаоператорами и избавиться от циклов внутри методов term и expression.

Исходные файлы

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

■ Андрей Шитов