14 октября 2011

Common Lisp. Esrap.

Передо мной встала задача анализировать результат выполнения команд maxima (с включенным режимом imaxima). Сначала я выполнял это с помощью cl-ppcre, но регулярные выражения, будучи, несомненно, удобными, сложно расширяются.

Итак вот задача:

Пользователь имеет возможность вводить подряд несколько команд, не заглушая или заглушая вывод некоторых из них.

Пример:

1+1;
2+5/0;
wxplot2d(sin(x),[x,0,2]);
sin(x);
12345$
"some string";

Здесь присутствуют выводы числа, исключения, графика, символа, числа *заглушено*, строки.

Вот как будет выглядеть вывод программы maxima с загруженным пакетом imaxima.lisp.

^B^W\%o2^W2^E
^C(%i3) ^D
expt: undefined: 0 to a negative exponent.
 -- an error. To debug this try: debugmode(true);
^C(%i4) ^D
^B^W\%t4^W^Gmaxout_1.png^G^E
^B^W\%o4^W^E
^C(%i5) ^D
^B^W\%o5^W\sin x^E
^C(%i6) ^D
^C(%i7) ^D
^B^W\%o7^W\verb|some string|^E
^C(%i8) ^D

Буквы с предшевствующим символом '^' являются управляющими символами.
Эти управляющие символы являются маркерами того, какой смысл имеет строка между ними.

Простая строка вывода результата выглядит как:

^B^W\%o2^W2^E

Маркеры ^B и ^E обозначают, что строка является результатом команды.
Маркеры ^W отделяют подпись текущего вывода и по совместительству название символы связанного с данным выводом.

^C(%i3) ^D

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

^B^W\%t4^W^Gmaxout_1.png^G^E

Маркеры ^B и ^E нам уже знакомы, только подпись имеет формат %t. Переменная %t будет связана с именем файла.

expt: undefined: 0 to a negative exponent.
 -- an error. To debug this try: debugmode(true);

Исключение представлено просто текстом, без каких-либо маркеров.

Вывод разделяется переводом строк.

Сначала я наладил было парсинг на PEG.js на клиентской стороне, но вовремя опомнился и портировал правила на esrap. Esrap небольшая библиотека для построения парсеров. Ее использовал archimag в своем проекте cl-closure-templates, и отзывался о ней довольно положительно.

Начнем. Основная функция, которая будет нами использоваться defrule. Данная функция принимает первым аргументом правило, по которому производить разбор текста, и в другом параметре она принимает функцию, которая будет структурировать разобранные выражения. Правила напоминают простые регулярные выражения. Построение правил - нетрудное дело, если правильно думать.

Правила

Вот первая мысль для первого правила.

"У нас есть неограниченный список выражений".

Так и запишем.

(defrule expressions (* expression)
  (:lambda (list)
    list))

Правило (* expression) означает в expressions expression может встречаться 0 и более раз.

Форма :lambda задает функцию, которая будет иметь аргумент - список разобранных expression. Мы просто вернем этот список.

Вторая мысль:

"Перед выражением может быть пустое место, а затем либо строка вывода, либо приглашение ввода, либо просто текст(исключение)".

Вот соответственно правило:

(defrule expression (and (? whitespace) (or out in simpletext))
  (:destructure (w exp)
    (declare (ignore w))
    exp))

(and subexpression1 subexpression1 ... subexpressionN) означает совпадение последовательно расположенных выражений.

(? whitespace) означает, что выражение может встречаться 0 или 1 раз. При 0 будет возвращен nil.

(or subexpression1 subexpression1 ... subexpressionN) означает, что на данной позиции может встречаться одно из N выражений.

Здесь мы используем форму :destructure для того, чтобы "перенаправить" результат разбора в аргументы функции. Аргумент w будет результатом (? whitespace), и exp - (or out in simpletext). Игнорируем пробелы и возвращаем результат разбора выражения.

Следующая мысль:

"Пустое место - это 1 или несколько пробельных символов (#\space #\tab #\newline)"

(defrule whitespace (+ (or #\space #\tab #\newline))
  (:constant nil))

(+ subexpression) означает, что выражение встречает 1 и более раз.

Здесь мы не задаем функцию обработки, указывая какой результат для данного разбора всегда должен быть: (:constant nil).

Мысль:

"Строка вывода это маркеры ^B и ^E, а между ними выражение вывода, которое может содержать подпись, например, \%o2, строку имени файла, maxout_1.png, и текст."

Обозначим правила для маркеров:

(defrule startout #\Stx)

(defrule endout #\Enq)

Обозначим правило для строки вывода:

(defrule out (and startout (? outlbl)
              (? outimg)
              (* outtext) endout)
  (:destructure (m1 outlbl outimg expr m2)
    (declare (ignore m1 m2))
    (list (cons :lbl outlbl) (cons :img outimg) (cons :expr (text expr)) (cons :tex t))))

Данным выражением

(list (cons :lbl outlbl) (cons :img outimg) (cons :expr (text expr)) (cons :tex t))))

мы создали alist содержащий структуру разбора вывода. Здесь функция text соединяет переданный ей список строк, в данном случае expr будет содержать список символов и они будут объединены в одну строку.

Далее определяем правила для outlbl, outimg, и outtext.

;; Возращаем символ, если он не является маркером конца вывода
(defrule outtext (and (! endout) character)
  (:destructure (m1 ch)
    (declare (ignore m1))
    ch))

;; Определяем маркер для подписи
(defrule outlblbrace #\Etb
  )

;; Возвращаем подпись, игнорируя маркеры
(defrule outlbl (and outlblbrace (* outlbltext) outlblbrace)
  (:destructure (m1 expr m2)
    (declare (ignore m1 m2))
    (text expr)))

;; Возвращаем символ, если не является маркером конца подписи
(defrule outlbltext (and (! outlblbrace) character)
  (:destructure (m1 ch)
    (declare (ignore m1))
    ch))

;; Определяем маркер для имени файла
(defrule outimgbrace #\Bel
  )

;; Возвращаем имя файла, игнорируя маркеры
(defrule outimg (and outimgbrace (* outimgtext) outimgbrace)
  (:destructure (m1 expr m2)
    (declare (ignore m1 m2))
    (text expr)))

;; Возвращаем символ, если он не является маркером конца имени файла
(defrule outimgtext (and (! outimgbrace) character)
  (:destructure (m1 ch)
    (declare (ignore m1))
    ch))

Теперь по аналогии определим правила для строки приглашения ввода.

;; маркер начала
(defrule startin #\Etx
  )

;; маркер конца
(defrule endin #\Eot
  )

;; Записываем все что между маркерами
(defrule in (and startin (* intext) endin)
  (:destructure (m1 expr m2)
    (declare (ignore m1 m2))
    (list (cons :expr (text expr)))))

;; Возвращаем символ, если он не является маркером конца
(defrule intext (and (! endin) character)
  (:destructure (m1 ch)
    (declare (ignore m1))
    ch))

Если никакие выше правила не сработали значит перед нами просто текст вывода, это может быть текст исключения, или сессия работы maxima в lisp repl режиме.

;; Записываем текст
(defrule simpletext (+ simpletextcontent)
  (:lambda (list)
    (list (cons :expr (text list)))))

;; Возвращаем символ, если он не является каким-нибудь маркером начала
(defrule simpletextcontent (and (! (or startout startin)) character)
  (:destructure (m1 ch)
    (declare (ignore m1))
    ch))

Парсинг


Создадим функцию, которая осуществит разбор текста и возврат список alist'ов с выделенными частями текста.

(defun parse-expression (text)
  "Parsing imaxima output"
  (parse 'expressions text))

Пример выполнения:

CL-USER> (imaxima-esrap:parse-expression "^B^W\%o7^W9^E
^C(%i8) ^D
^B^W\%o8^W9^E
^C(%i9) ^D 
expt: undefined: 0 to a negative exponent.
    -- an error. To debug this try: debugmode(true);
^C(%i10) ^D 
^B\verb|asdfasdf|\verb| |^E 
^B^W\%o10^W\verb|asdfasdf|^E
 ^C(%i11) ^D                 
expt: undefined: 0 to a negative exponent.
     -- an error. To debug this try: debugmode(true);
^C(%i12) ^D 
 ^B^W\%t12^W/home/michael/maxout_1.png^E
 ^B^W\%o12^W^E")
(((:LBL . "%o7") (:IMG) (:EXPR . "9") (:TEX . T)) ((:EXPR . "(%i8) "))
 ((:LBL . "%o8") (:IMG) (:EXPR . "9") (:TEX . T)) ((:EXPR . "(%i9) "))
 ((:EXPR . "expt: undefined: 0 to a negative exponent.
    -- an error. To debug this try: debugmode(true);
"))
 ((:EXPR . "(%i10) "))
 ((:LBL) (:IMG) (:EXPR . "verb|asdfasdf|verb| |") (:TEX . T))
 ((:LBL . "%o10") (:IMG) (:EXPR . "verb|asdfasdf|") (:TEX . T))
 ((:EXPR . "(%i11) "))
 ((:EXPR . "expt: undefined: 0 to a negative exponent.
     -- an error. To debug this try: debugmode(true);
"))
 ((:EXPR . "(%i12) "))
 ((:LBL . "%t12") (:IMG) (:EXPR . "/home/michael/maxout_1.png") (:TEX . T))
 ((:LBL . "%o12") (:IMG) (:EXPR . "") (:TEX . T)))
NIL
CL-USER> 

alist я выбрал не случайно, после того как я разобрал вывод, я преобразовываю alist в json с помощью функции json:encode-json-to-string и отправляю клиентскому javascript'у.

А, вообще, так как в лиспе код является данными и наоборот, при разборе выражений можно возращать некоторый код, который затем выполнять, тем самым выполучаете интерпретатор (а на sbcl компилятороинтерпретатор) очень малой ценой. archimag в cl-closure-templates так вроде и делает, пойдя еще дальше и генерируя с помощью parenscript, на основе сгенерированного кода, код javascript . Для сравнения: разработчики Qt до сих пор не прикрутили свои классы к QtScript, то что предлагается qtscriptbindingsgenerator - это через гланды.

Комментариев нет:

Отправить комментарий