Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 20.06.2014 | нет комментариев

Эта статья была написана Аароном Паттерсоном, 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>

Подметьте, что 3-й вызов 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, тот, что в нашем случае будет основанным на событиях.

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

Наш анализатор будет состоять из 3 комбинированных объектов-частей: синтаксического анализатора, лексического анализатора и обработчи!, “}”] irb(main):009:0> tok.next_token => nil
В этом примере мы обернули строку JSON в объект StringIO для того, Дабы добиться утиной типизации с IO. Дальше испробуем прочитать несколько лексем. Всякая лексема, знакомая анализатору состоит из имени, которое идет первым элементом массива, тогда как в неведомых лексемах это место занимает один символ. Скажем, лексема строки будет выглядеть как [:STRING, "foo"], а незнакомая лексема, в частном случае, как ['(', '(']. Наконец, когда входные данные исчерпаны, на выходе получим nil.

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

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

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

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

Во-первых, мы добавим в 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 двукратно: в синтаксическом анализаторе и в обработчике документа. Конечный отвечает за конструкцию, тогда как 1-й за непосредственные значения (true, false и т. д.). Подмечу, что абсолютно обоснованным является примечание, что все реформирования обязаны осуществляться синтаксическим анализатором либо же, наоборот, быть из него всецело исключены.
  • Наконец, лексический анализатор использует буферизацию. Я сделал очерк версии без буферизации, которую дозволено взять отсель. Она достаточно сырая, но ее дозволено довести до ума применяя логику финального автомата.

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

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

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

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB