пятница, 30 апреля 2010 г.

Парсим reStructuredText на Common Lisp. Часть 1.

Читая регулярно Russian Lambda Planet можно увидеть описания всевозможных грамматик, парсер-комбинаторов (или как там они называются) и прочих вещей, о которых мне даже думать страшно. Впрочем, наверно не одному мне, ибо в реальных проектах на php и python, которые я просматривал, ничего подобного не используется, а используется весьма простой и эффективный метод, основанных на регулярных выражениях и "машине состояний", позволяющий удобно сочетать описание грамматики с помощью рег. выражений с вставками произвольного кода. Мне, кстати, попадалось утверждения (которое я не могу не подтвердить, не опровергнуть, ибо абсолютно не разбираюсь в этих вопросе), что все эти грамматики бесполезны для разбора wiki-разметок. Так вот, поскольку у меня есть проблемы с математическим образование, то приходиться парсить по "быдлокодерски" ;)

Почему reStructuredText
Я имею большое желание начать писать мануал для RESTAS, но в мире Common Lisp нет инструмента для документирования, который бы меня устроил. С другой стороны, мне очень нравиться как сделана документация на Django, да и вообще, в мире Python с документированием всё нормально. Документация к Django основана на Sphinx, который использует reStructuredText, поддержку которого обеспечивает пакет docutils. А почему бы не реализовать соответствующий функционал для Common Lisp? Правда, я нашёл пакет cl-docutils, но его размер (около 10 000 строк кода) меня сильно смутил - ну зачем может потребоваться столько строк кода для решения подобной задачи??? Так что решил делать сам (у меня всяко столько кода не будет).

Моя система
Я уже пару раз рассказывал, что мой подход (библиотека wiki-parser) к парсингу (который я опробовал в restas-wiki и cl-closure-template) основан на подходе, подсмотренном в исходниках Dokuwiki, который я правда переработал с учётом возможностей Common Lisp, так что мне кажется, что он стал значительно мощнее. Итак, сначала объявим парсер:
(wiki-parser:define-parser #:wiki-parser.re-structured-text
(:use #:cl #:iter)
(:export #:paragraph))

(in-package #:wiki-parser.re-structured-text)

(define-toplevel-mode
(:allowed :formatting :sections :paragraphs))

(defmethod wiki-parser:parse ((markup (eql :re-structured-text)) (obj string))
(wiki-parser:parse #.*package* obj)))
Макрос define-parser создаёт новый пакет и проводит некоторую его инициализацию - данный подход, когда пакет используется в качестве объекта, я использую также и в RESTAS - это позволяет легко разбить описания синтаксиса на множество отдельных форм (вместо этих огромных простыней, которые можно наблюдать, например, в коде на базе cl-yacc).

Макрос define-toplevel-mode совершенно необходим и определяет какие режимы доступны в начальном состоянии, смысл их стане ясен чуть позже.

Метод wiki-parser:parse используется для непосредственного разбора текста.

Теперь, опередить правила для разбора, например, strong-элемента (например, "*Hello world*") можно чрезвычайно просто:
(define-mode strong (80 :formatting)
(:allowed :formatting)
(:not-allowed strong)
(:entry "\\*\\*(?=.*\\*\\*)")
(:exit "\\*\\*"))

CL-USER> (wiki-parser:parse :re-structured-text
"**Hello world**")
(WIKI-PARSER.RE-STRUCTURED-TEXT:TOPLEVEL
(WIKI-PARSER.RE-STRUCTURED-TEXT:STRONG "Hello world"))
Напомню, что парсер обеспечивает машину состояний и здесь макрос define-mode определяет режим для разбора strong-режима. Его параметры означают следующее
  • strong - название режима. Во-первых, оно фигурирует в результате разбора (как можно увидеть в примере), во-вторых - может использоваться при описании других режимов.
  • 80 - приоритет, регулярные выражения для всех определённых режимов собираются в одно регулярное выражение и с помощью приоритета можно (нужно) управлять очередность проверок.
  • :formatting - означает, что данный режим входит в группу :formatting. Например, выше в макросе define-toplevel-mode я указывал разрешённые режимы в начальном состоянии.
  • (:allowed :formatting) - означает, что внутри данного режима разрешены режимы из группы :formatting. Можно указать несколько групп или отдельных режимов. Легко заметить, что группы обозначается с помощью :keyword, а отдельный режим простым символом
  • (:not-allowed strong) - исключает режим strong из списка разрешённых состояний внутрирежима.
  • (:entry "\\*\\*(?=.*\\*\\*)") - регулярное выражение, позволяющее найти начало режима и убедиться, что он имеет правильное завершение
  • (:exit "\\*\\*") - регулярное выражения, определяющее завершение режима
Мне кажется, что всё предельно просто.


В разметках часто встречаются элементы, которые не имеют начального и завершающего "признака", например, надо опознавать простые гиперссылки. Это можно следующим образом:
(define-mode standalone-hyperlink (330 :formatting)
(:special "(?:ht|f)tp(?:s?)://[0-9a-zA-Z](?:[-.\\w]*[0-9a-zA-Z])*(?::(?:0-9)*)*(?:/?)(?:[a-zA-Z0-9\\-\\.\\?\\,/\\+&%\\$#\\*]*)?"))
Здесь тэг :special используется для описания регулярного выражения, которое позволяет "выкусить" кусок текста целиком:
CL-USER> (wiki-parser:parse :re-structured-text
"http://www.lisp.org/")
(WIKI-PARSER.RE-STRUCTURED-TEXT:TOPLEVEL
(WIKI-PARSER.RE-STRUCTURED-TEXT:STANDALONE-HYPERLINK "http://www.lisp.org/"))
В разметке reStructuredText широко используются ссылки, которые формируются следующим образом: Python_ или `Common Lisp`_. Здесь видно, в первом варианте отсутствует признак начала режима. Для разбора подобных элементов (в разметке reStructuredText используется несколько вариантов ссылок) я используют такой код:
(defun trim-backquotes (str)
(let ((last (1- (length str))))
(if (char= #\`
(char str 0)
(char str last))
(subseq str 1 last)
str)))

(define-mode reference (70 :formatting)
(:special "`.*`_"
"[^\\s]+_")
(:post-handler (item)
(let* ((str (second item)))
(list 'reference
(trim-backquotes
(subseq str 0 (1- (length str))))))))
Здесь тэг :post-handler используется для описания функции, которая должна быть вызвана для финальной обработки распарсенного элемента:
CL-USER> (wiki-parser:parse :re-structured-text
"Python_")
(WIKI-PARSER.RE-STRUCTURED-TEXT:TOPLEVEL
(WIKI-PARSER.RE-STRUCTURED-TEXT:REFERENCE "Python"))

CL-USER> (wiki-parser:parse :re-structured-text
"`Common Lisp`_")
(WIKI-PARSER.RE-STRUCTURED-TEXT:TOPLEVEL
(WIKI-PARSER.RE-STRUCTURED-TEXT:REFERENCE "Common Lisp"))
После описания всех режимов в конец файла необходимо вставить вызов (init-parser), который произведёт инициализация парсера. При определении какого-либо режима в Slime с помощью C-M-x (не С-с С-с) - данный вызов будет производиться автоматически.

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

8 комментариев:

  1. > Я имею большое желание начать писать мануал для RESTAS

    хотеть :)

    ОтветитьУдалить
  2. интересно, да)

    P.S. пока читал, нашел пару очепЯток:
    s/\(Мне, кстати, попадал\)о\(сь утверждения\)/\1и\2/
    s/не подтвердить, не опровергнуть/ни подтвердить, ни опровергнуть/
    s/\(не разбираюсь в этих вопрос\)е/\1ах/
    s/и определяет какие режимы доступны в начальном состоянии, смысл их стане/\0т/

    ОтветитьУдалить
  3. кстати, htmlize - прикольная штука для раскрашивания исходников (http://www.emacswiki.org/emacs/Htmlize)

    ОтветитьУдалить
  4. @antonoxf
    Безграмостность у меня врождённая, с этим трудно что-то поделать ;( Помню в начальных классах мы писали контрольные списывания - 2 была частая для меня оценка. В общем, в школе пока учился самым (и единственным) проблемным предметом был русский, а в универе - английский, плохо у меня с языками :(

    ОтветитьУдалить
  5. Кстати, "wiki" это от гавайского "быстро", так что можно так и объяснять название - мол, "быстрый (простой) парсер" :)

    ОтветитьУдалить
  6. @quasimoto
    На самом деле, от гавайского wiki-wiki, насколько я понимаю, отдельного слова wiki там нет ;)

    ОтветитьУдалить
  7. Сейчас, в рамках GSoC, в проекте Sphinx должны реализовать поддержку документирования проектов, написанных на других языках программирования.

    ОтветитьУдалить
  8. @bsdemon
    Ну это когда будет, и не факт что будет, потом, не кошерно так ;)

    ОтветитьУдалить