[нужен совет] DSL наверное

Вопрос как такое писать? Согласен на lisp.

1. Определиться с входным и выходным языками.

"входной язык"
foreach layers($type_of_layer) do
   CAD.resize circle from=12mm to=16mm
end

"выходной язык №1"
...
foreach layer ($LAYERS)
  CAD_command activate_layer $layer
  CAD_command set_object_filter type=circle size=12mm
  CAD_command select_obj_by_filter
  SELECTED=`CAD_command get_selection_list'
  if ($#SELECTED > 0) then
      CAD_command resize_selections size=16mm
  endif
  CAD_command deactivate_layer $layer
end

для языков надо составить грамматики, понять на что они будут похожи. Входной язык — это shell вроде BASH? Готовые грамматики где-то есть? Если да, это облегчит задачу

2. Определиться со схемой трансляции То есть, входной язык транслируется в выходной язык #1. Можно ли как-то переделать «выходной язык #1» в более удобный «выходной язык #2», и транслировать в него (eDSL)? Либо, транслировать из входного в вых. #2, а этот вых. #2 уже транслировать в вых.#1

Есть биндинги на лиспе к CAD

Нужен пример кода, как этот пример может выглядеть на лиспе. Какой это лисп, CL, Scheme или что-то ещё. Например (что-то вроде eDSL типа CL):

"выходной язык #2"
...
(let ((layer)) 
(
(foreach layer (LAYERS)
  ( ;begin foreach-body
  (CAD_command :activate_layer layer)
     (CAD_command :set_object_filter :type 'circle :size (12 . 'mm))
     (CAD_command :select_obj_by_filter)
     (setf-eval-cmd   SELECTED (CAD_command :get_selection_list))
   (if (> (array-length SELECTED) 0)
      (CAD_command :resize_selections :size (16 . 'mm)))
  (CAD_command :deactivate_layer layer)
  ); end foreach-body
) ;end foreach
); end let

То есть: привели DSL выходного языка к виду, похожему на eDSL. Здесь всё, что не является корректными лисп-формами должно быть реализовано макросами лиспа и разворачиваться в корректный лисп. Варианты: а) транслируем входной язык в «выходной #2», eDSL б) транслируем входной в «выходной №2», eDSL, который транслируем назад в «выходной #1», BASH-скрипт или что там. То есть, как это тестировать? Либо а) запускать через лисп-биндинги б) конвертировать в язык №1.

Вариант а) относительно проще, вариант б) — нужно писать pretty printer, шаблонизатор, который AST «языка №2» распечатает в виде «языка №1».

На этом этапе нужно

1. набрать достаточное количество примеров для описания такого DSL. Пример содержит соответствия (входной язык, выходной1, выходной2). Определиться с конструкциями DSL
2. Определиться, как это тестировать. То есть, a) вариант с eDSL «вых№2», б) DSL: «вх»->«вых.№2»->«вых.#1»
3. Написать такие примеры вручную и протестировать «оттранслированное вручную», то есть, по варианту а) или б)

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

1. описать грамматику языков, по крайней мере входного
2. описать pretty printer для выходного языка
3. определиться, на чём писать парсер

Выбираем, на чём писать парсер. Варианты:

1. lex+yacc-подобные, то есть cl-yacc или и т.п. LALR
2. PEG-подобные, то есть, cl-peg или OMeta на CL
3. ANTLR, то есть, сама тулза на ява, но сгенерированный ей парсер на Elisp для Emacs или Clojure

Выбираем, как писать pretty printer. Можно руками, можно через StringTemplate в ANTLR.

Варианты по разным парсерам:

1. yacc классический наиболее известный, плюс можно найти грамматику BASH и приспособить её. Минусы: долбаться с факторизацией леворекурсивных грамматик, с Shift-reduce или reduce-reduce конфликтами. Грамматика получается довольно хрупкой.
2. PEG, PEG или OMeta или здесь. Есть наследование грамматик, минусы, что готовых грамматик мало, надо искать, и возиться вручную, отлаживая грамматику. Второй минус, алгоритм не очень быстрый, но более функциональный, например см. работу.
3. ANTLR, LL(*). Есть готовые грамматики, их много, что-то можно адаптировать. Есть IDE для отладки грамматик.

Книги/документация:

• YACC: классические книги (Ахо, Ульман, Dragon Book), курсы по созданию компиляторов
• PEG: всё, что есть — в интернете. Packrat + PEG — диссертации Bryan Ford, плюс реализации самих парсеров + примеры к ним.
• ANTLR: см. примеры, архив с примерами книги «The Definitive ANTLR reference» By Terrence Parr (~400 стр.), (оно же) Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages — вторая более новая, с более наглядными примерами. Можно брать примеры и твикать похожие грамматики.

Настройка рабочей среды:

• YACC, cl-yacc: Берём ASDF2, или quicklisp, ставим через них cl-yacc, смотрим примеры. Пишем свой проект на ASDF2 по аналогии, правим грамматику из примеров на ту, какую нужно, тестируем.
• PEG: аналогично, но чуть более замороченно. Хотя Ometa2 in CL, CL-PEG без особых сложностей.
• ANTLR: суперский бонус, если есть Maven. См. пример про «Clojure + ANTLR» : поставили Maven, поставили Leiningen. Далее, Lein вытянул архетип ANTLR, запустили команду, он создал по архетипу-прототипу новый пустой проект под ANTLR с калькулятором. Потвикали грамматику, заменили своей отлаженной в ANTLRWorks (IDE), получили простой парсер на ANTLR, который собирается одной командой mvn install. Можно приспособить ANT. Можно собирать без всяких Maven/ANT, вручную запуская ANTLR для генерации парсера и javac *.java для сборки сгенерированного парсера.

Чем ещё запомнился ANTLR:

• с ним довольно трудно разобраться не читая книжку, где описано всё его Java API (хотя на Сlojure проще, чем на Java, см. ссылку). С другой стороны, можно разобраться по примерам.
• StringTemplate рулит, см. в examples-v3.tar.gz перенастраиваемый транслятор в питон, Ява байткод и т.п. Пример, кажется, Cminus.
• Tree parser в ANTLR рулит, см. Tree parser grammars
• Особенно он рулит для связки с лиспом. Когда мы написали простую грамматику + tree parser grammar, потом делаем

  ...
   CommonTree AST = MyParser.MainRule.getTree();
   String LISP_AST = AST.toStringTree();
  

  и получаем AST, записанный в виде S-выражений, разве что форматирование плывёт (можно записать в файл и напустить на него GNU indent или ещё какой pretty printer, или можно написать свой Sexprs pretty printer, вручную обойдя дерево и распечатывая с учётом оступов)

То есть, общая схема парсера/транслятора на ANTLR становится такой:

• парсер разбирает программу на входном языке и распечатывает AST в виде S-выражений (AST.toStringTree())
• этот Sexpr AST грузим в лисп. Естественно, он не компилируется — не все токены AST являются корректными лисп-формами
• пишем макросы, которые транслируют токены AST в корректный лисп

Если нужно пойти по варианту б) и транслировать из eDSL в BASH, то самый прямой вариант — через StringTemplate. См. в книжке главу про «rewrite parsers vs. generators» или в примерах про трансляцию Сminus программы в питон, Java bytecode, Java.

Менее прямой, но более гибкий, что ли, вариант — написать pretty printer на лиспе. Который возьмёт Sexpr AST на лиспе и распечатает его в виде BASH.

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

Это конечно, в простых случаях, когда не нужнен семантический анализатор построенного АСТ и трансформации простые.

> Хм. По-моему, фраза про read-table технически совершенно корректна.

Завивит от грамматики. Если её преобразовывать к какому-то простому виду, в который легко выражаются Sexprs (например, sweet expressions (whitespace python syntax), Iexpr (infix syntax)) — можно обойтись и без неё. Если грамматика более алголоподобная (констекстнозависимая), придётся возиться с readtable.

> lisp (sbcl) я сам прикрутил. В этом CAD'e очень легко сделать биндинг любого языка.

как прикрутил? Пример кода в студию.
И кстати, что это за CAD?

* )); end let

>Входной язык — это shell вроде BASH? Готовые грамматики где-то есть? Если да, это облегчит задачу

http://ftp.gnu.org/gnu/bash/bash-3.2.tar.gz#parse.y

http://bazaar.launchpad.net/~db-keen/rush/dev/files/head:/lib/rubyunix/parser...

как прикрутил? Пример кода в студию.

Часть биндинга:

(defparameter *GEN-DIR-PREFIX* "@%#%@")
(defparameter *STATUS*    0)
(defparameter *READANS*   0)
(defparameter *COMANS*    0)
(defparameter *MOUSEANS*  0)


;;;да здесь повтор двух строк надо убрать
(defmacro readans (n)
    (if (= n 3) `(progn (setf *STATUS*  (read-line))
                        (setf *READANS* (read-line))
                        (setf *COMANS*  (read-line)))

                `(progn (setf *STATUS*  (read-line))
                        (setf *READANS* (read-line))
                        (setf *COMANS*  *READANS*))))

(defun COM (command &rest line)
    (format t "~aCOM ~a~^~{~^,~a=~a~}~%" *GEN-DIR-PREFIX* command line)
    (finish-output nil)
    (readans 2))

Использование:

(COM "action" :key1 "value1" :key2 "value2")

И кстати, что это за CAD?

CAM Genesis http://frontline-pcb.com

хотя можно и с readtable повозиться: http://www.nongnu.org/guile-reader/doc/guile-reader.html

How to Write an Interpreter in One Day
http://rpal.sourceforge.net/

Guile Scheme + lex/yacc

Invertible Syntax Descriptions: Unifying Parsing and Pretty Printing
http://lambda-the-ultimate.org/node/4191

Всем спасибо, загрузили достаточно. Посмотрю что смогу из литературы осилить.

> Настройка рабочей среды:

[поскипанно]

Yay, зачем столько монстров? Ставится haskell platform и вперёд. Prettyprinting можно выкинуть и писать проще.

И про caml/python забыл - для них так же вариации lex/yacc. В отличии от Си писать на этих языках для большинства людей проще.

на ocaml ещё можно легко бекенд к llvm написать, туториал довольно простой

Раз топикстартеру топик больше не нужен, я тут ещё один вопрос в тему задам. Закидайте, пожалуйста, ссылками на статьи по мутабельным грамматикам. Интересно почитать про/написать язык, в котором есть доступ к парсеру как у лиспа к readtable и возможность добавлять, удалять и модифицировать правила в грамматике этого парсера на ходу. При этом грамматика должна быть как минимум контекстно-свободная, а контекстно-зависимая ещё лучше (регулярная уже реализована в лиспе, охота большего). Хочется без полной перекомпиляции парсера при каждом изменении, потому что как сделать с перекомпиляцией вроде бы ясно. Также интересны идеи как к этому прикрутить вменяемый интерфейс. Я знаю, что в perl6 нечто подобное планируется, но rakudo этого ещё не умеет, а в остальных реализациях это, кажется, даже не заявляется.

> Закидайте, пожалуйста, ссылками на статьи по мутабельным грамматикам. Интересно почитать про/написать язык, в котором есть доступ к парсеру как у лиспа к readtable и возможность добавлять, удалять и модифицировать правила в грамматике этого парсера на ходу.

Может тебе про eDSL и их реализацию почитать лучше?

> Может тебе про eDSL и их реализацию почитать лучше?

Я интересуюсь. Что предлагаешь?