Главная / ПрограммированиеСоздаём язык программирования → Лекция П3. Автогенераторы парсеров. Racc

Автогенерация парсеров

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

Конечно, всё равно бы оставалась необходимость как-то объяснить компьютеру конструкции языка, которые надо распарсить. Но для этого есть BNF. BNF ведь тоже формальный (следовательно, машино-читаемый) язык — почему бы нам не сделать такую волшебную программу, которой можно скормить BNF, а на выходе получить готовый парсер…

И такие программы есть!

Исторически первой распространённый была GNU YACC, в наши дни используется её последователь GNU Bison.

Из более современных решений пользуется популярностью ANTLR.

Синтаксис у всех средств автогенерации похожий и близко соответствует тем или иным диалектам BNF.

В наших примерах мы будем использовать racc — Ruby-клон yacc/bison.

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

Ограничения и возможности

Большинство программ автогенерации парсеров (парсер-генераторов) являются вариантами LR-парсеров.

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

Большинство парсер-генераторов также позволяют указать приоритет операций и обозначить их лево- или правоассоциативность.

Существует отдельный класс парсер-генераторов, называемых PEG-парсерами (PEG означает parsing expression grammar), которые, отличаясь изящным синтаксисом (см. PEG.js, treetop), напоминающим синтаксис регулярных выражений (и потому, фактически, делающим лексер опциональным), тем не менее, как правило, лишены двух вышеуказанных возможностей.

Мы будем использовать парсер-генератор (racc) с консервативным синтаксисом, простым как молоток. На бензопилу перейти, при необходимости, будет не сложно.

Racc — краткое полное руководство

Посмотрим от начала до конца процесс создания парсера с помощью racc.

Установка racc

Для установки (при условии, что установлен Ruby) требуется установить соответствующий gem:

gem install racc

Компиляция парсера

Для компиляции парсера требуется использовать следующую команду:

racc parser.y -o parser.rb

parser.y — имя входного файла

parser.rb — имя выходного файла

Типовое использование парсера будет следующим:

# подключить сгенерированный racc-ом rb-файл
require_relative 'parser'

# написанный вручную лексер
def lex(string)
  # ...
end

# считываем строку на интерпретируемом языке
input = "..."

tokens = lex(input)

# получаем AST
ast = Parser.new.parse(tokens)

Основы синтаксиса racc

Синтаксис y-файла для racc-а, хоть и похож на Ruby, но не является Ruby-кодом (хотя содержит фрагменты Ruby-кода внутри фигурных скобок и дополнительных секциях, см. ниже).

y-файл, описывающий для racc грамматику парсера (и принципы получения AST) содержит, от начала до конца, следующие секции:

  • название класса: class MyParser;
  • приоритет операторов: prechigh ... preclow;
  • список типов токенов (TOKENS ...) и список правил конвертации (convert... end);
  • ожидаемое количество shift/reduce конфликтов: expect N;
  • дополнительные опции: omit_action_call, result_var)
  • список правил вывода (первое правило считается стартовым/целевым): rule... end;
  • дополнительная секция ---- header
  • дополнительная секция ---- inner
  • дополнительная секция ---- footer

Название класса

y-файл должен начинаться со слова class и следующего за ним Ruby-идентификатора, в соответствии с которым будет назван класс парсера в выходном файле:

class MyParser

Можно указать имя модуля в традиционной для Ruby манере:

class MyModule::MyParser

Тогда в выходном Ruby-коде парсера будет сгенерированы следующие строки:

module MyModule
  class MyParser
    # код парсера
  end
end

Приоритет операторов

Между ключевыми словами prechigh и preclow (которые призваны напомнить программисту, что в начале идут операторы с высоким приоритетом, а в конце с низким) помещаются строки, определяющие ассоциативность оператора (left, right, nonassoc) и соответствующей ему тип токена:

prechigh
  left '*' '/'
  left '+' '-'
  nonassoc '=='
preclow

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

Ключевое слово nonassoc будет запрещать (возвращать ошибку парсинга) ассоциативную запись соответствующего оператора, например 1 == 2 == 3.

Лексер и токены

Парсер, сегенерированный с помощью racc, будет принимать на вход от лексера поток токенов (терминалов) в следующем формате:

[<тип>, <значение>]

Для самого racc играет роль только тип токена, все остальные элементы в массиве предназначены для удобства разработчика и для формирования AST.

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

  • ruby-символ с большими буквами, например :NUMBER. Тогда в racc соответствующий терминал будет назван NUMBER (без двоеточия).
  • ruby-строка, например '+'. Тогда в racc соответствующий терминал будет назван '+' (также в кавычках).

Таким образом,

число "5" необходимо в лексере кодировать как [:NUMBER, 5];

оператор сложения как ['+', '+'] — в массиве должно быть не менее двух элементов, и у данного токена тип совпадает со значением;

или как [:PLUS, '+'] — более формальный вариант для любителей формализмов (не несёт практической выгоды по сравнению с первым);

или как [:BINARY, '+'].

В последнем случае, если лексер порождает другие токены с типом :BINARY (скажем, [:BINARY, '*']), то на уровне правил вывода их невозможно будет отличить (и также невозможно будет указать им разный приоритет в блоке prehigh... preclow). Как уже говорилось, racc «заглядывает» только в первый элемент массива.

Список типов токенов можно (но не обязательно) указать в y-файле после ключевого слова token:

token PLUS MINUS NUMBER

Если требуется токены, приходящие от лексера, переименовать перед дальнейшим парсингом, то используется блок convert... end. Например, вот так можно переименовать все токены с типом :PLUS в токены :OPERATION_PLUS:

convert
  PLUS 'OPERATION_PLUS'
end

Блок convert не рекомендуется использовать.

Ожидаемое количество shift/reduce конфликтов

При парсинге неоднозначных грамматик LR-парсер может столкнуться с конфликтом между продолжением чтения ленты для формирования текущего нетерминала (shift) и окончанием (reduce).

Например, в выражении 1 + 2 + 3 и грамматике:

<expression> ::= number "+" number

…парсер после считывания двойки имеет два пути:

  • свернуть (reduce) 1 + 2;
  • пойти дальше, считав второй плюс и т.д. (shift);

После ключевого слова expect можно указать количество shift/reduce конфликтов, которые ожидаются от данной грамматике (чтобы подавить предупреждение парсера):

expect N

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

Инструкция expect не рекомендуется к использованию.

Опция result_var

После ключевого слова option можно включить или отключить (добавив префикс no_) дополнительные опции парсер-генератора.

Практический интерес представлеяет опция result_var, которую рекомендуется отключать:

options no_result_var

В таком случае в блоках Ruby-кода (внутри фигурных скобок) будет недоступна «волшебная переменная» result, которой требуется присвоить возвращаемое значение, и результат будет требоваться вернуть с помощью ключевого слова return.

Меньше магии — проще код.

Список правил вывода

Правила вывода записываются на диалекте BNF со следующими синтаксическими особенностями:

  • нетерминалы пишутся маленькими буквами, без угловых скобок;
  • вместо знака ::= используется двоеточие :;
  • терминалы пишутся большими буквами, как NUMBER, или строками в одинарных кавычках, как '+' (см. выше про именование терминалов);
  • комментарии пишутся в скобка в стиле C: /* comment /*;
  • вместо ε (обозначения пустой строки) просто ничего не пишется (но, для удобства программиста, отмечается комментарием).

Например, наивная грамматика инфиксных выражений (при наличии блока prechigh ... preclow превращающаяся в однозначную) будет выглядеть так:

rule
  expression:
    expression '+' expression
    | expression '-' expression
    | expression '*' expression
    | expression '/' expression
    | '-' expression
    | '+' expression
    | '(' expression ')'
    | NUMBER
end

Все правила вывода заключаются между ключевыми словами rule... end.

В вышеприведённом примере предполагается, что от лексера приходят следующие токены:

[:NUMBER, <число>]
["+", "+"]
["-", "-"]
["*", "*"]
["/", "/"]
["(", "("]
[")", ")"]

В данном случае дифференцировка унарных и бинарных операций возложена на парсер.

К каждой ветке правила вывода (после блока кода, если он имеет место) также может быть «вручную» присоединён приоритет данного правила с помощью знака =:

expression:
  '-' expression =UNARY

В данном примере, приоритет унарного минуса в блоке prechigh ... preclow будет обозначен псевдотокеном UNARY:

prechigh
  right UNARY
  left '-' '+'

Racc, смотря на ветку "-" expression пытался бы найти "-" в списке приоритетов. Но если бы мы не ввели пседотокена UNARY, он был бы в списке приоритетов дважды: как бинарная операция и как унарная. Не понятно, какой из них выбрать для конкретного правила.

Поэтому мы, сохраняя возможность отличать унарный и бинарный минус на уровне грамматики (а не лексера), просто вводим некий новый токен UNARY (название произвольное), который не используется в правилах вывода, и присваиваем ему нужный приоритет в блоке prechigh ... preclow.

А затем сообщаем racc с помощью =UNARY, что для данной ветки правила надо использовать приоритет, соответствующий этому токену (а не "-", что было бы поведением по умолчанию).

Формирование AST

Для формирования AST к каждому правилу вывода требуется присоединить блок Ruby-кода, который бы извлекал целевой фрагмент AST из обработанных терминлов и нетерминалов.

Продолжая предыдущий пример, допустим, инфиксное выражение надо привести к варианту префиксного. В результате из выражения “1 + 2 * 3” требуется получить следующий AST:

["+",
  1,
  ["*",
    2,
    3
  ]
]

Тогда в грамматику требуется добавить следующие блоки кода формирования AST (внутри фигурных скобок используется полноценный Ruby-код):

expression:
  expression '+' expression   { return ['+', val[0], val[2]] }
  | expression '-' expression { return ['-', val[0], val[2]] }
  | expression '*' expression { return ['*', val[0], val[2]] }
  | expression '/' expression { return ['/', val[0], val[2]] }
  | '-' expression            { return ['-', val[1]] }
  | '+' expression            { return ['+', val[1]] }
  | '(' expression ')'        { return val[1] }
  | NUMBER

Присоединённый блок Ruby-кода будет выполнен в тот момент, когда парсер окончательно «сворачивает» (пользуясь соответствующей веткой правила вывода) нетерминал.

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

В массив val блока кода racc передаст фрагменты AST (для нетерминалов) и значение токенов лексера (второй элемент исходного массива, полученного от лексера) для терминалов, соответствующие символам (слева направо) в той ветке правила вывода, к которой присоединён блок кода.

Разберём на примере.

Для выражения 1 + 2 * 3 блок кода, соответствующий ветке умножения (строка 4) будет вызван перед блоком кода, присоединённым к ветке сложения (строка 2).

В каждый блок кода передаётся массив val, количество элементов которого равно количеству символов (терминалов и нетерминалов) в правой части соответствующей ветки правила вывода.

Каждый элемент массива val (индексация стандартно идёт с нуля) соответствует символу правила с данным номером (считая слева направо).

Например, для блока кода, присоединённого к правилу expression "+" expression:

  • в val[0] будет лежать фрагмент AST, соответствующий первому (левому) символу expression;
  • в val[1] будет лежать терминал от лексера ["(", "("];
  • в val[2] будет лежать фрагмент AST, соответствующий второму (правому) символу expression.

Задача блока кода: вернуть (return) фрагмент AST, соответствующий данному нетерминалу.

Возвращённый из присоединённого к стартовому (первому) правилу блока кода фрагмент AST становится результриующим деревом AST «распарсенной» строки (результатом метода do_parse, см. далее).

Если к некоторому правилу не присоединён блок кода, то это эквивалентно присоединению блока кода, который возвращает исходный массив val либо, если правило содержит в правой части лишь один символ (нетерминал или терминал), val[0].

Дополнительная секция ---- header

После инструкции ---- header (которая может следовать после блока правил) пишется Ruby-код, который будет добавлен в начало генерируемого rb-файла парсера:

---- header

# подключить дополнительные библиотеки
require 'json'

Дополнительная секция ---- inner

После инструкции ---- inner (которая может следовать после блока ---- header) пишется Ruby-код, который будет добавлен внутрь класса генерируемого парсера.

В данном блоке требуется определить:

  • публичный метод parse, который должен вызвать метод do_parse (do_parse будет определён самим racc);
  • метод next_token, который должен вернуть парсеру очередной токен с входной ленты;
  • по желанию, может быть переопределён конструктор (родительский конструктор не принимает аргументов, поэтому его следует вызывать как super() с пустыми скобками).

Типовой блок inner выглядит следующим образом:

---- inner

def initialize(tokens)
  @tokens = tokens.dup
  super()
end

def parse
  do_parse
end

private

def next_token
  @tokens.shift
end

В данном коде мы сохраняем массив токенов, переданных в конструкторе («входная лента»). Автоматически сгенерированный и недоступный нам код парсера будет вызывать внутри этого же класса метод next_token, когда будет готов обработать очередной символ входной ленту — мы просто отдаём очередной символ сохранённого массива.

Метод parse, в данном случае, не выполняет никакой подготовительной работы — просто вызывает (автосгенерированный) метод do_parse.

В случае использования данной inner-секции полученный с помощью racc парсер можно использовать традиционным образом:

# положим, парсер был сгенерирован в файл parser.rb:
require_relative 'parser'

# токены, полученные от лексера
tokens = [[:NUMBER, 5], "*", [:NUMBER, 7]]

Parser.new(tokens).parse

После инструкции ---- footer (которая может следовать после блока ---- inner) пишется Ruby-код, который будет добавлен в конец генерируемого Ruby-файла (вне контекста класса).

Все дополнительные секции (---- header, ---- inner, ---- footer) опциональны и могут присутствовать независимо от наличия других секций.

Пример

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

class InfixParser
  # Приоритеты от большего к меньшему:
  #   - правоассоциативное возведение в степень
  #   - правоассоциативные унарные оператора (псевдотокен)
  #   - левоассоциативные умножение и деление
  #   - левоассоциативные сложение и вычитание
  prechigh
    right '^'
    right UNARY
    left '*' '/'
    left '+' '-'
  preclow

  # блоки Ruby-кода ({ ... }) должны использовать
  # "return ...",
  # а не "result = ..."
  options no_result_var

  rule

  # Целевой нетерминал - expression (он первый в списке правил, хотя
  # в данном случае и единственный)
  expression:
    # для бинарных операций - строим постфиксное выражение в виде
    # массива из трёх элементов [<оператор>, <левый операнд>, <правый операнд>]
    expression "+" expression   { return ['+', val[0], val[2]] }
    | expression "-" expression { return ['-', val[0], val[2]] }
    | expression "*" expression { return ['*', val[0], val[2]] }
    | expression "/" expression { return ['/', val[0], val[2]] }
    | expression "^" expression { return ['^', val[0], val[2]] }

    # для унарных операций - строим постфиксное выражение в виде
    # массива из двух элементов [<оператор>, <операнд>]
    | "-" expression            { return ['-', val[1]] }        =UNARY
    | "+" expression            { return ['+', val[1]] }        =UNARY

    # для скобок - "раскрываем скобки", возвращая результат
    # обработки выражения внутри скобок
    | "(" expression ")"        { return val[1] }

    # для числа - возвращаем это число (блок кода не требуется)
    | NUMBER
end

---- inner

def initialize(tokens)
  @tokens = tokens.dup
  super()
end

def parse
  do_parse
end

private

def next_token
  @tokens.shift
end

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