Парсим 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 много элементов, синтаксис которых не выразить на основе традиционных регулярных выражений (по-крайней мере, я не знаю как это сделать). Что делать с ними я расскажу в следующий раз.