воскресенье, 2 мая 2010 г.

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

В предыдущей части я показал, как можно очень легко парсить простые элементы. Но в размеке reStructuredText также имеются сложные элементы, простейшим из которых является Section, вот несколько примеров:
=============
Hello world
=============

Hello world
-----------

Hello world
!!!!!!!!!!!
Секция обозначается с помощью "украшающей" линии, которая должна быть под заголовком секции. Также, "украшающая" линия может быть дополнительно и над заголовков. Если имеется только нижняя декорация, то количество символов в ней должно совпадать с количеством символов в названии секции, а само название не может начинаться с пробельного символа. Если есть и нижняя и верхняя декорация, то в начале названия можно вставлять пробельные символы, но длина заголовка должна быть меньше длины декорации. Верхняя (если есть) декорация должна совпадать с нижней. Декорация должна состоять из одинаковых символов, разрешены следующие символы: ! " # $ % & ' ( ) * + , - . / : ; < = > ? @ [ \ ] ^ _ ` { | } ~ . В общем, как-то так :)

Ядро wiki-parser - это чуть более 200 строк кода, которые обеспечивают конечный автомат, почти полностью управляемый с помощью регулярных выражений. Код несколько запутан, но концептуально это очень простая схема, позволяющая легко описывать разметку, например, подобную разметке dokuwiki. Однако, statemashin.py (из docutils) это значительно более сложная схема, которая допускает значительно большую гибкость, но и требует значительно больших усилий по программированию. И связано это с необходимостью обрабатывать конструкции, подобные описанным Section, а в разметке reStructuredText есть ещё, например, куда более сложные таблицы. Ключевая проблема - невозможность описания подобной разметки на основе регулярных выражений.

Однако, тут следует сделать оговорку, что нельзя составить необходимое регулярное выражение в Perl или Python, но библиотека cl-ppcre поддерживает фантастическую возможность - фильтры.

cl-ppcre имеет два варианта описания регулярных выражений - традиционный с помощью строки в стиле Perl, и вариант описания на основе s-выражений. Фактически, строковое представление всегда сначала парсится именно в форму s-выражений. Синтаксис символьной формы можно узнать с помощью функции ppcre:parse-string, например для тэга :entry в описании strong-элемента (см. предыдущую часть) получается следующее:
CL-USER> (ppcre:parse-string "\\*\\*(?=.*\\*\\*)")
(:SEQUENCE "**"
(:POSITIVE-LOOKAHEAD (:SEQUENCE (:GREEDY-REPETITION 0 NIL :EVERYTHING) "**")))
Эта возможность используется в ядре wiki-parser для построения "большого" регулярного выражения (оперировать s-выражениями проще, чем строками), также я порой использую эту возможность, когда затрудняюсь описать нужное мне в строковом виде (обычно, строковое представление удобней, но s-форма допускает большую гибкость). А ещё - s-представление даёт возможность указать произвольную функцию, которая будет работать как часть регулярного выражения. Т.е. когда нельзя написать традиционное регулярное выражение для описания синтаксиса, всегда можно указать произвольную функцию, которая будет производить необходимые проверки!. Для обработки секций я написал следующий код:
(defparameter +section-adornment+
'(#\! #\" #\# #\$ #\% #\&
#\' #\( #\) #\* #\+ #\,
#\- #\. #\/ #\: #\; #\<
#\= #\> #\? #\@ #\[ #\\
#\] #\^ #\_ #\` #\{ #\|
#\} #\~))

(defun regex-section-filter (pos)
(ignore-errors
(flet ((check-condition (flag)
(unless flag (return-from regex-section-filter nil))))
(let ((adornment nil)
(title nil)
(overline-p nil))
(check-condition (char= #\Newline
(char ppcre::*string* pos)))
(incf pos)
(check-condition (null (char= #\Newline
(char ppcre::*string* pos))))
(when (member (char ppcre::*string* pos)
+section-adornment+)
(let ((pos2 (position (char ppcre::*string* pos)
ppcre::*string*
:start (1+ pos)
:test-not #'char=)))
(check-condition (char= #\Newline
(char ppcre::*string* pos2)))
(setf adornment (subseq ppcre::*string* pos pos2)
overline-p t
pos (+ pos2 1))))
(unless overline-p
(check-condition (let ((sp (ppcre:scan "\\s" title)))
(or (null sp)
(> sp 0)))))
(let ((pos2 (position #\Newline
ppcre::*string*
:start pos
:test #'char=)))
(setf title
(subseq ppcre::*string* pos pos2))
(setf pos
(+ pos2 1)))
(let ((pos2 (position #\Newline
ppcre::*string*
:start pos
:test #'char=)))
(cond
(adornment (check-condition (string= adornment
(subseq ppcre::*string* pos pos2))))
(t (check-condition (> pos2 pos))
(setf adornment
(subseq ppcre::*string* pos pos2))
(check-condition (member (char adornment 0)
+section-adornment+))
(check-condition (null (find (char adornment 0)
adornment
:test-not #'char=)))))
(setf pos pos2))
(check-condition (if overline-p
(<= (length title)
(length adornment))
(= (length title)
(length adornment))))
pos))))

(define-mode section (30 :sections)
(:special (:filter regex-section-filter))
(:post-handler (item)
(let* ((lines (cdr (ppcre:split "\\n" (second item))))
(decoration (car (last lines)))
(overline-p (= (length lines) 3))
(title (if overline-p
(second lines)
(first lines))))
(list 'section
(trim-whitespaces title)
(char decoration 0)
overline-p))))
Функция regex-section-filter несколько нудновата, но главное это работает:
CL-USER> (wiki-parser:parse :re-structured-text
"**strong**
=============
Hello world
=============
*em*")
(WIKI-PARSER.RE-STRUCTURED-TEXT:TOPLEVEL
(WIKI-PARSER.RE-STRUCTURED-TEXT:STRONG "strong"))
(WIKI-PARSER.RE-STRUCTURED-TEXT:SECTION "Hello world" #\= T)
(WIKI-PARSER.RE-STRUCTURED-TEXT:EMPHASIS "em")))
Здесь распарсенный элемент WIKI-PARSER.RE-STRUCTURED-TEXT:SECTION имеет название, символ декорации и признак того, что имеется верхняя декорация.

Таким образом, при сохранении предельной простоты для описания тривиальных элементов имеется возможность и для обработки весьма сложной разметки (а код для обработки подобных элементов будет достаточно сложен при любом подходе). Эта схема кажется мне наиболее простой, как в понимании, так и в кодировании и тех, что я видел для обработки подобных разметок.

2 комментария:

  1. должно быть labels вместо flet?

    ОтветитьУдалить
  2. > должно быть labels вместо flet?

    Нет, зачем? В том плане, что с labels бы тоже работало, но check-condition очень проста функция, она не рекурсивная и не вызывает других.

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