Как определить грамматику для кода clojure, используя instaparse?

Question

Я новичок в разборе и хочу проанализировать некоторый код clojure. Я надеюсь, что кто-то может привести пример того, как код clojure может быть проанализирован с использованием instaparse. Мне просто нужно сделать цифры, символы, ключевые слова, полы, векторы и пробелы.

Несколько примеров, которые я хочу разобрать:

(+ 1 2 
   (+ 3 4))

{:hello "there"
 :look '(i am 
           indented)}

Answer 1

Ну, есть две части на ваш вопрос. Первая часть разбора выражения

(+ 1 2 
   (+ 3 4))

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

Лучший способ понять, как будет работать парсер, - разбить его на более мелкие части. Итак, в первой части мы просто рассмотрим некоторые правила синтаксического анализа, а во второй части мы создадим наши секспы.

1. Простой пример

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

   (def parser
       (insta/parser
           "sexp = number
            number = #'[0-9]+'
           "))
   

   sexp описывает грамматику высшего уровня для sexpression. Наша грамматика гласит, что у sexp может быть только число. В следующей строке указывается, что число может быть любой цифрой 0-9, а + похож на регулярное выражение + это означает, что он должен повторяться одно число любое количество раз. Если мы запустим наш парсер, мы получим следующее дерево разбора:

   (parser "1")     
   => [:sexp [:number "1"]]
   

   Ингоринг скобок

   Мы можем игнорировать определенные значения, добавив угловые скобки < к нашей грамматике. Так что если мы хотим разобрать "(1)" так же просто 1 мы можем исправить нашу грамматику как:

   (def parser
       (insta/parser
           "sexp = lparen number rparen
            <lparen> = <'('>
            <rparen> = <')'>
            number = #'[0-9]+'
           "))
   

   и если мы снова запустим парсер, он проигнорирует левую и правую скобки:

   (parser "(1)")
   => [:sexp [:number "1"]]
   

   Это станет полезным, когда мы напишем грамматику для sexp ниже.

   Добавление пробелов

   Теперь происходит, если мы добавим пробелы и запустим (parser "( 1 )")? Ну, мы получаем ошибку:

   (parser "( 1 )")
   => Parse error at line 1, column 2:
      ( 1 )
       ^
      Expected: 
      #"[0-9]+"
   

   Это потому, что мы не определили концепцию пространства в нашей грамматике! Таким образом, мы можем добавить пробелы как таковые:

   (def parser
       (insta/parser
           "sexp = lparen space number space rparen
            <lparen> = <'('>
            <rparen> = <')'>
            number = #'[0-9]+'
            <space>  = <#'[ ]*'> 
           "))
   

   Опять * похож на регулярное выражение * и это означает ноль или более одного вхождения пробела. Это означает, что следующие примеры будут возвращать один и тот же результат:

   (parser "(1)")         => [:sexp [:number "1"]]
   (parser "( 1 )")       => [:sexp [:number "1"]]
   (parser "(       1 )") => [:sexp [:number "1"]]
   

2. Строим Sexp

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

   Таким образом, sexp содержит больше, чем просто числа, определенные нашей простой грамматикой. Одно из представлений высокого уровня о sexp, которое мы можем иметь, состоит в том, чтобы рассматривать их как операцию между двумя круглыми скобками. Так что в основном как ( operation ), Мы можем написать это прямо в нашей грамматике.

   (def parser
       (insta/parser
           "sexp = lparen operation rparen
            <lparen> = <'('>
            <rparen> = <')'>
            operation = ???
           "))
   

   Как я уже говорил выше, угловые скобки < скажите instaparse игнорировать эти значения при создании дерева разбора. Теперь, что такое операция? Ну, операция состоит из оператора, как + и некоторые аргументы, такие как числа 1 а также 2, Таким образом, мы можем сказать, написать нашу грамматику как:

   (def parser
       (insta/parser
           "sexp = lparen operation rparen
            <lparen> = <'('>
            <rparen> = <')'>
            operation = operator + args
            operator = '+'
            args = number
            number = #'[0-9]+'
           "))
   

   Мы указали только один возможный оператор, + Просто для простоты. Мы также включили правило числовой грамматики из простого примера выше. Наша грамматика, однако, очень ограничена. Единственный действительный sexp, который это может разобрать, (+1), Это потому, что мы не включили понятие пробелов и заявили, что аргументы могут иметь только одно число. Таким образом, на этом этапе мы сделаем две вещи. Мы добавим пробелы и укажем, что аргументы могут иметь более одного числа.

   (def parser
       (insta/parser
           "sexp = lparen operation rparen
            <lparen> = <'('>
            <rparen> = <')'>
            operation = operator + args
            operator = '+'
            args = snumber+
            <snumber> = space number
            <space>  = <#'[ ]*'> 
            number = #'[0-9]+'
           "))
   

   Мы добавили space с помощью правила пространственной грамматики мы определили в простом примере. Мы создали новый snumber который определяется как space и number и добавил + чтобы понять, что он должен появиться один раз, но он может повторяться любое количество раз. Таким образом, мы можем запустить наш парсер так:

   (parser "(+ 1 2)")
   => [:sexp [:operation [:operator "+"] [:args [:number "1"] [:number "2"]]]]
   

   Мы можем сделать нашу грамматику более устойчивой, имея args ссылка на sexp, Таким образом, мы можем иметь секс в нашем сексе! Мы можем сделать это, создав ssexp который добавляет space в sexp а затем добавить ssexp в args,

   (def parser
       (insta/parser
           "sexp = lparen operation rparen
            <lparen> = <'('>
            <rparen> = <')'>
            operation = operator + args
            operator = '+'
            args = snumber+ ssexp* 
            <ssexp>   = space sexp
            <snumber> = space number
            <space>  = <#'[ ]*'> 
            number = #'[0-9]+'
           "))
   

   Теперь мы можем бежать

   (parser "(+ 1 2 (+ 1 2))")
    =>   [:sexp
          [:operation
           [:operator "+"]
           [:args
            [:number "1"]
            [:number "2"]
            [:sexp
             [:operation [:operator "+"] [:args [:number "1"] [:number "2"]]]]]]]
   

3. Трансформации

   Этот шаг может быть выполнен с использованием любого количества инструментов, которые работают с деревьями, таких как iveive, zippers, match и tree-seq. Instaparse, однако, также включает свою собственную полезную функцию под названием insta\transform, Мы можем построить наши преобразования, заменив ключи в нашем дереве синтаксического анализа допустимыми функциями clojure. Например, :number становится read-string превратить наши строки в действительные числа, :args становится vector строить наши аргументы.

   Итак, мы хотим преобразовать это:

    [:sexp [:operation [:operator "+"] [:args [:number "1"] [:number "2"]]]]
   

   В это:

    (identity (apply + (vector (read-string "1") (read-string "2"))))
    => 3
   

   Мы можем сделать это, определив наши параметры преобразования:

   (defn choose-op [op]
    (case op
       "+" +))
   (def transform-options
      {:number read-string
       :args vector
       :operator choose-op
       :operation apply
       :sexp identity
    })
   

   Единственная сложность здесь была добавление функции choose-op, То, что мы хотим, это передать функцию + в apply, но если мы заменим operator с + это будет использовать + как обычная функция. Таким образом, это превратит наше дерево в это:

    ... (apply (+ (vector ...
   

   Но с помощью choose-op это пройдет + в качестве аргумента apply в качестве таких:

    ... (apply + (vector ...
   

Заключение

Теперь мы можем запустить наш маленький интерпретатор, соединив анализатор и преобразователь:

(defn lisp [input]
   (->> (parser input) (insta/transform transform-options)))

(lisp "(+ 1 2)")
   => 3

(lisp "(+ 1 2(+ 3 4))")
   => 10

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

Надеюсь, этого короткого вступления достаточно, чтобы начать работу над своими собственными проектами. Вы можете новые строки, объявив грамматику для \n и вы даже можете не игнорировать пробелы в дереве разбора, удалив угловые скобки <, Это может быть полезно, учитывая, что вы пытаетесь сохранить отступ. Надеюсь, это поможет, если не просто написать комментарий!