Пишем свой синтаксический анализатор JSON (в горошек и с перламутровыми пуговицами)

Эта статья была написана Аароном Паттерсоном, Ruby разработчиком из Сиэтла, штат Вашингтон. Он увлечен разработкой на Ruby вот уже 7 лет и будет рад поделиться своей любовью к этому замечательному языку.

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

В этой статье мы рассмотрим ряд инструментов компиляции для использования в связке с Ruby. А для погружения в предмет мы напишем синтаксический анализатор JSON. Уже слышу недовольные возгласы вроде: «ну Аарон, ну зачем? Разве их уже не 1,234,567 штук понаписано?» Вот именно! У нас уже 1,234,567 анализаторов JSON написанных на Ruby! И мы тоже будем производить анализ JSON, потому что грамматика его достаточно проста для завершения работы за один раз, и потому что она тем не менее достаточно сложна, чтобы можно было с умом применить разработанные для Ruby инструменты компиляции.

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

Что нам понадобится

Тестировать я буду на Ruby 1.9.3, но работать должно на любой реализации которую вы выберете. Главным образом мы будем пользоваться такими инструментами, как Racc и StringScanner.

Racc:

Racc понадобится нам для автоматической генерации анализатора. Это генератор LALR-анализаторов во многом похожий на YACC. Последняя аббревиатура расшифровывается как «Yet Another Compiler Compiler» (еще один компилятор компиляторов), однако поскольку это версия для Ruby, то получилось Racc. Racc занимается тем, что преобразует свод правил грамматики (файл с расширением .y) в файл на Ruby, который описывает правила перехода для конечного автомата. Последние интерпретируются конечным автоматом (средой выполнения) Racc. Среда выполнения поставляется вместе с Ruby, однако в ней нет того инструмента, который преобразует файлы с расширением ".y" в таблицы состояний автомата. Установите его, выполнив gem install racc.

Здесь и далее мы будем заниматься написанием ".y" файлов, однако, конечные пользователи не смогут их запустить. Чтобы это сделать, их сначала нужно преобразовать в исполняемый код на Ruby, а затем упаковать этот код в наш gem. По сути, это значит, что устанавливать gem Racc будем только мы, а конечным пользователям он ни к чему.

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

StringScanner:

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

Приступим! Сначала создадим объект StringScanner и обработаем с его помощью несколько символов:

irb(main):001:0> require 'strscan'
=> true
irb(main):002:0> ss = StringScanner.new 'aabbbbb'
=> #<StringScanner 0/7 @ "aabbb...">
irb(main):003:0> ss.scan /a/
=> "a"
irb(main):004:0> ss.scan /a/
=> "a"
irb(main):005:0> ss.scan /a/
=> nil
irb(main):006:0> ss
=> #<StringScanner 2/7 "aa" @ "bbbbb">
irb(main):007:0>

Заметьте, что третий вызов StringScanner#scan вернул nil, поскольку регулярное выражение в этой позиции уже не подходит. А также то, что когда вызывается inspect для экземпляра StringScanner, можно увидеть текущую позицию обработчика в строке (в данном случае 2/7).

Обработчик также можно перемещать посимвольно используя StringScanner#getch:

irb(main):006:0> ss
=> #<StringScanner 2/7 "aa" @ "bbbbb">
irb(main):007:0> ss.getch
=> "b"
irb(main):008:0> ss
=> #<StringScanner 3/7 "aab" @ "bbbb">
irb(main):009:0>

Метод getch возвращает следующий символ и сдвигает указатель на один вперед.

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

Основы Racc

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

Давайте рассмотрим пример. Предположим, мы хотим проверять подстановки регулярного выражения вида: (a|c)*abb. Иными словами, регистрировать случаи, когда за произвольным числом символов 'a' или 'c' следует 'abb'. Чтобы перевести это в грамматику Racc, мы попробуем разбить это регулярное выражение на составные части, а затем снова соберем в единое целое. Каждый отдельно взятый элемент грамматики называется порождающим правилом или продукцией. Итак, разобьем это выражение на части, чтобы посмотреть, как выглядят продукции и какой формат у Racc грамматики.

Сначала создадим файл грамматики. В начале файла идет объявление Ruby класса, который мы хотим получить, за которым следует ключевое слово rule означающее, что мы собираемся объявить продукции, вслед за которым идет ключевое слово end, указывающее на их конец:

class Parser
rule
end

Теперь добавим продукцию для «a|c». Назовем ее a_or_c:

class Parser
rule
  a_or_c : 'a' | 'c' ;
end

В итоге у нас есть правило a_or_c, которое выполняет сопоставление с символом 'a' либо 'c'. Для того, чтобы выполнить сопоставление один или более раз, мы создадим рекурсивную продукцию, которую назовем a_or_cs:

class Parser
rule
  a_or_cs
    : a_or_cs a_or_c
    | a_or_c
    ;
  a_or_c : 'a' | 'c' ;
end

Как я уже сказал, продукция a_or_cs имеет рекурсивный характер, будучи эквивалентна регулярному выражению (a|c)+. Дальше добавим продукцию для 'abb':

class Parser
rule
  a_or_cs
    : a_or_cs a_or_c
    | a_or_c
    ;
  a_or_c : 'a' | 'c' ;
  abb    : 'a' 'b' 'b';
end

И завершит все продукция string:

class Parser
rule
  string
    : a_or_cs abb
    | abb
    ;
  a_or_cs
    : a_or_cs a_or_c
    | a_or_c
    ;
  a_or_c : 'a' | 'c' ;
  abb    : 'a' 'b' 'b';
end

Эта итоговая продукция выполняет сопоставление с шаблоном, в котором за одним или большим количеством символов 'a' или 'c' следует 'abb' либо же присутствует отдельностоящая строка 'abb'. Все это эквивалентно нашему исходному регулярному выражению вида (a|c)*abb.

Аарон, но это так нудно!

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

class Parser
rule
  string
    : a_or_cs abb
    | abb         { puts "Нашел abb, ня!" }
    ;
  a_or_cs
    : a_or_cs a_or_c
    | a_or_c
    ;
  a_or_c : 'a' | 'c' ;
  abb    : 'a' 'b' 'b';
end

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

Создаем анализатор

Наш анализатор будет состоять из трех составных объектов-частей: синтаксического анализатора, лексического анализатора и обработчика документа. Синтаксический анализатор, построенный на грамматике Racc, будет обращаться к лексическому анализатору за данными из потока ввода. Каждый раз, когда синтаксическому анализатору удается вычленить элемент JSON из общего потока данных, он посылает соответствующее событие обработчику документа. Обработчик документа отвечает за сбор данных из JSON и переводе их в структуру данных на Ruby. В процессе анализа исходных данных в JSON формате будут производиться вызовы, показанные на графике ниже:

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

Лексический анализатор

Наш лексический анализатор строится на объекте IO. Именно из него мы будем считывать исходные данные. При каждом вызове next_token лексический анализатор считывает одну лексему из потока входных данных и возвращает ее. Работать он будет со следующим списком лексем, который мы позаимствовали из спецификаций JSON:

• Strings (Строки)
• Numbers (Числа)
• True (Истина)
• False (Ложь)
• Null (Нет значения)

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

Значения возвращаемые next_token:

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

Класс лексического анализатора Tokenizer:

Посмотрим на код класса и разберем что он делает:

module RJSON
  class Tokenizer
    STRING = /"(?:[^"\]|\(?:["\/bfnrt]|u[0-9a-fA-F]{4}))*"/
    NUMBER = /-?(?:0|[1-9]d*)(?:.d+)?(?:[eE][+-]?d+)?/
    TRUE   = /true/
    FALSE  = /false/
    NULL   = /null/

    def initialize io
      @ss = StringScanner.new io.read
    end

    def next_token
      return if @ss.eos?

      case
      when text = @ss.scan(STRING) then [:STRING, text]
      when text = @ss.scan(NUMBER) then [:NUMBER, text]
      when text = @ss.scan(TRUE)   then [:TRUE, text]
      when text = @ss.scan(FALSE)  then [:FALSE, text]
      when text = @ss.scan(NULL)   then [:NULL, text]
      else
        x = @ss.getch
        [x, x]
      end
    end
  end
end

Сначала идут объявления нескольких регулярных выражений, которые мы будем использовать в связке с обработчиком строк StringScanner. Построены они на основе определений взятых с json.org. Экземпляр StringScanner создается в конструкторе. Поскольку он требует строку при создании, мы вызываем read объекта IO. Это, впрочем, не исключает альтернативной реализации, в которой лексический анализатор считывает данные из IO объекта не целиком, а по мере надобности.

Основная работа выполняется в методе next_token. Он возвращает nil, если в обработчике строк больше нет данных, в противном случае проверит каждое регулярное выражение, пока не найдет подходящее. Если соответствие было обнаружено, он вернет имя лексемы (например, :STRING) вместе с текстом, который совпал с шаблоном. Если ни одно из регулярных выражений не подошло, будет произведено считывание одного символа из обработчика, и считанное значение будет возвращено одновременно как имя лексемы и ее значение.

Давайте передадим лексическому анализатору пример строки в формате JSON и посмотрим какие лексемы получим на выходе:

irb(main):003:0> tok = RJSON::Tokenizer.new StringIO.new '{"foo":null}'
=> #<RJSON::Tokenizer:0x007fa8529fbeb8 @ss=#<StringScanner 0/12 @ "{"foo...">>
irb(main):004:0> tok.next_token
=> ["{", "{"]
irb(main):005:0> tok.next_token
=> [:STRING, ""foo""]
irb(main):006:0> tok.next_token
=> [":", ":"]
irb(main):007:0> tok.next_token
=> [:NULL, "null"]
irb(main):008:0> tok.next_token
=> ["}", "}"]
irb(main):009:0> tok.next_token
=> nil

В этом примере мы обернули строку JSON в объект StringIO для того, чтобы добиться утиной типизации с IO. Дальше попробуем прочитать несколько лексем. Каждая лексема, знакомая анализатору состоит из имени, которое идет первым элементом массива, тогда как в неизвестных лексемах это место занимает один символ. Например, лексема строки будет выглядеть как [:STRING, "foo"], а неизвестная лексема, в частном случае, как ['(', '(']. Наконец, когда входные данные исчерпаны, на выходе получим nil.

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

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

Пришло время заняться синтаксисом. Для начала немного поработаем граблями. Нам нужно реализовать генерацию файла на Ruby на основе .y-файла. Как раз работа для rake¹.

Описываем задачу компиляции:

Во-первых, мы добавим в rake-файл правило которое гласит: «преобразовать .y-файлы в .rb-файлы используя следующую команду»:

rule '.rb' => '.y' do |t|
  sh "racc -l -o #{t.name} #{t.source}"
end

Затем добавим задачу «compile», зависящую от сгенерированного parser.rb файла.

task :compile => 'lib/rjson/parser.rb'

Поскольку файл с описанием грамматики хранится в lib/rjson/parser.y, то теперь, когда мы запускаем rake compile, rake автоматически преобразует .y-файл в файл с расширением .rb, используя Racc.

И, наконец, мы поставим задачу «test» в зависимость от задачи «compile», чтобы, когда мы запускаем rake test, производилась автоматическая генерация скомпилированной версии:

task :test => :compile

Теперь можно переходить непосредственно к составлению и проверке .y-файла.

Разбираем спецификацию JSON.org:

Сейчас мы займемся переводом диаграмм с json.org в формат грамматики Racc. В корне исходного документа должен находиться либо объект, либо массив, поэтому мы создадим продукцию document, которая выполняет сопоставление объекту — object или массиву — array:

rule
  document
    : object
    | array
    ;

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

  array
    : '[' ']'
    | '[' values ']'
    ;

Продукция для значений (values) определяется рекурсивно, как одно значение, либо несколько значений, разделенных запятой:

  values
    : values ',' value
    | value
    ;

В спецификации JSON значение (value) определено как строка, число, объект, массив, true (истина), false (ложь) или null (отсутствие значения). Наше определение будет сходным, единственное различие будет в том, что для непосредственных значений вроде NUMBER (число), TRUE (истина) и FALSE (ложь) мы используем соответствующие имена лексем, определенных в лексическом анализаторе:

  value
    : string
    | NUMBER
    | object
    | array
    | TRUE
    | FALSE
    | NULL
    ;

Переходим к определению продукции для объекта (object). Объекты могут быть пустыми, либо состоящими из пар (pairs):

  object
    : '{' '}'
    | '{' pairs '}'
    ;

Пар может быть одна или несколько и между собой они должны разделятся запятыми. Снова воспользуемся рекурсивным определением:

  pairs
    : pairs ',' pair
    | pair
    ;

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

  pair
    : string ':' value
    ;

Теперь сообщим Racc о наших лексемах из лексического анализатора, добавив определение в самом начале, и наш синтаксический анализатор готов:

class RJSON::Parser
token STRING NUMBER TRUE FALSE NULL
rule
  document
    : object
    | array
    ;
  object
    : '{' '}'
    | '{' pairs '}'
    ;
  pairs
    : pairs ',' pair
    | pair
    ;
  pair : string ':' value ;
  array
    : '[' ']'
    | '[' values ']'
    ;
  values
    : values ',' value
    | value
    ;
  value
    : string
    | NUMBER
    | object
    | array
    | TRUE
    | FALSE
    | NULL
    ;
  string : STRING ;
end

Обработчик документа

Обработчик документа будет получать события от нашего синтаксического анализатора. Он и займется сборкой нашего несравненного Ruby объекта из восхитительных кусочков JSON! Количество событий оставляю на ваше усмотрение, а сам ограничусь 5:

• start_object — вызывается в начале объекта
• end_object — вызывается в конец объекта
• start_array — вызывается в начале массива
• end_array — вызывается в конце массива
• scalar — вызывается в терминальных случаях типа строк, true, false и т. д.

При помощи этих пяти событий мы соберем объект, отражающий исходную структуру JSON.

Следим за событиями

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

module RJSON
  class Handler
    def initialize
      @stack = [[:root]]
    end

    def start_object
      push [:hash]
    end

    def start_array
      push [:array]
    end

    def end_array
      @stack.pop
    end
    alias :end_object :end_array

    def scalar(s)
      @stack.last << [:scalar, s]
    end

    private

    def push(o)
      @stack.last << o
      @stack << o
    end
  end
end

Каждый раз, когда синтаксический анализатор обнаруживает начало объекта, обработчик добавляет в конец стека список с символом «hash», чтобы обозначить начало ассоциативного массива. События, которые являются дочерними, будут добавлены к родителю, а когда будет обнаружен конец объекта, родитель будет вытолкнут со стека.

Не исключаю, что это сложно понять с первого раза, поэтому рассмотрим несколько примеров. Передав на входе JSON-строку вида {"foo":{"bar":null}}, мы получим в переменной стека @stack следующее:

[[:root,
  [:hash,
    [:scalar, "foo"],
    [:hash,
      [:scalar, "bar"],
      [:scalar, nil]]]]]

Взяв, к примеру, массив вида ["foo",null,true], в @stack получим следующее:

[[:root,
  [:array,
    [:scalar, "foo"],
    [:scalar, nil],
    [:scalar, true]]]]

Преобразуем в Ruby:

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

def result
  root = @stack.first.last
  process root.first, root.drop(1)
end

private
def process type, rest
  case type
  when :array
    rest.map { |x| process(x.first, x.drop(1)) }
  when :hash
    Hash[rest.map { |x|
      process(x.first, x.drop(1))
    }.each_slice(2).to_a]
  when :scalar
    rest.first
  end
end

Метод result удаляет узел root и передает то, что осталось, методу process. Когда process обнаруживает символ hash, он формирует ассоциативный массив, используя дочерние элементы, полученные в результате рекурсивного вызова process. По аналогии с этим, рекурсивным вызовом на дочерних элементах строится массив, когда встречается символ array. Скалярные значения — scalar возвращаются без обработки (что предотвращает бесконечную рекурсию). Теперь, если мы вызовем result из нашего обработчика, то на выходе получим готовый Ruby объект.
Посмотрим, как это работает на практике:

require 'rjson'

input   = StringIO.new '{"foo":"bar"}'
tok     = RJSON::Tokenizer.new input
parser  = RJSON::Parser.new tok
handler = parser.parse
handler.result # => {"foo"=>"bar"}

Доработка программного интерфейса:

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

module RJSON
  def self.load(json)
    input   = StringIO.new json
    tok     = RJSON::Tokenizer.new input
    parser  = RJSON::Parser.new tok
    handler = parser.parse
    handler.result
  end
end

Поскольку наш анализатор изначально строился в расчете на IO объект, мы можем добавить метод для тех, кто хотел бы передавать на входе сокет или дескриптор файла:

module RJSON
  def self.load_io(input)
    tok     = RJSON::Tokenizer.new input
    parser  = RJSON::Parser.new tok
    handler = parser.parse
    handler.result
  end

  def self.load(json)
    load_io StringIO.new json
  end
end

Убеждаемся, что интерфейс стал чуть удобнее:

require 'rjson'
require 'open-uri'

RJSON.load '{"foo":"bar"}' # => {"foo"=>"bar"}
RJSON.load_io open('http://example.org/some_endpoint.json')

Мысли вслух

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

Написанный нами анализатор получился достаточно гибким. Мы можем:

• Использовать его в событийной парадигме, реализуя объект-обработчик Handler
• Использовать упрощенный интерфейс и просто передавать на вход строки
• Передавать на вход поток в формате JSON посредством IO объекта

Надеюсь, эта статья придаст вам уверенности, и вы начнете самостоятельно экспериментировать с технологиями анализа и компиляции, реализованными в Ruby. Если у вас остались ко мне вопросы, милости прошу в комментарии.

P.S.

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

• Здесь представлена окончательная версия грамматики нашего анализатора. Обратите внимание на — inner раздел .y-файла. Все, что представлено в этом разделе, будет добавлено в класс синтаксического анализатора, который получается в результате автоматической генерации. Именно таким путем мы передаем объект-обработчик в синтаксический анализатор.
• Наш синтаксический анализатор на самом деле осуществляет преобразование терминальных узлов JSON в Ruby. Поэтому мы осуществляем преобразование JSON в Ruby дважды: в синтаксическом анализаторе и в обработчике документа. Последний отвечает за структуру, тогда как первый за непосредственные значения (true, false и т. д.). Замечу, что вполне обоснованным является замечание, что все преобразования должны осуществляться синтаксическим анализатором или же, напротив, быть из него полностью исключены.
• Наконец, лексический анализатор использует буферизацию. Я сделал набросок версии без буферизации, которую можно взять отсюда. Она довольно сырая, но ее можно довести до ума используя логику конечного автомата.

На этом все. Спасибо за внимание!

---

¹ англ. rake — грабли

Замечания по переводу просьба отправлять в личку.

Автор: sumproxy

Источник