Старая версия
Здесь находится настоящий сайт
Парсер META - классическая система разбора
Чтобы строить дерево документа нам нужен парсер HTML. Простой. В январе 1991 года появилась статья Henry G. Baker “Прагматичный парсинг на Common Lisp”, в которой он описывает META — классическую простую и одновременно эффективную технику построения рекурсивных нисходящих парсеров.
Язык META
Компилятор META — это набор макросов, который укладывается в полусотню строк. Именно эта простота и определила выбор парсера HTML для игрушечного web-движка.
Для реальных задач никогда не используйте регулярные выражения для парсинга. Если искушение не пропало, то прочтите статью ещё раз.
Выражения META состоят из символов, строк, последовательности [], альтернативы {}, звезды Клини $, проверка символа по условию @ и вычисление выражения !.
Вот как выглядит парсинг целого числа с одновременным вычислением собственно его значения:
(deftype digit () '(member #\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9))
(defun ctoi (d) (- (char-code d) #.(char-code #\0)))
(defun parse-int (&aux (s +1) d (n 0))
(and
(matchit
[{#\+ [#\- !(setq s -1)] []}
@(digit d) !(setq n (ctoi d))
$[@(digit d) !(setq n (+ (* n 10) (ctoi d)))]])
(* s n)))
! является мощной конструкцией META, которая позволяет делать интересные вещи, такие как модификация грамматики на ходу.
Ядро META
Выражения META преобразуются reader-макросами во внутреннее представление — структуру meta (функция печати здесь только для отладки):
(defstruct (meta
(:print-function
(lambda (m s d &aux (char (meta-char m)) (form (meta-form m)))
(ecase char
((#\@ #\! #\$) (format s "~A~A" char form))
(#\[ (format s "[~{~A~^ ~}]" form))
(#\{ (format s "{~{~A~^ ~}}" form))))))
char
form)
(defun meta-reader (s c) (make-meta :char c :form (read s)))
Распознаём операторы META, ничего кроме создания структур meta:
(mapc #'(lambda (c) (set-macro-character c #'meta-reader)) '(#\@ #\$ #\!))
Распознаём последовательность и альтернативы:
(set-macro-character #\[
#'(lambda (s c) (make-meta :char c :form (read-delimited-list #\] s t))))
(set-macro-character #\{
#'(lambda (s c) (make-meta :char c :form (read-delimited-list #\} s t))))
(mapc #'(lambda (c) (set-macro-character c (get-macro-character #\) nil)))
'(#\] #\}))
И, наконец, компилятор META:
(defun compileit (x)
(typecase x
(meta
(ecase (meta-char x)
(#\! (meta-form x))
(#\[ `(and ,@(mapcar #'compileit (meta-form x))))
(#\{ `(or ,@(mapcar #'compileit (meta-form x))))
(#\$ `(not (do () ((not ,(compileit (meta-form x)))))))
(#\@ (let ((f (meta-form x))) `(match-type ,(car f) ,(cadr f))))))
(t `(match ,x))))
(defmacro matchit (x) (compileit x))
Осталось определиться с тем, как скармливать парсеру входные данные. Статья предлагает такие варианты как считывание из потока, из строки и из списка. Наш игрушечный движок будет читать из строки хотя бы потому, что так легче “откатываться” на несколько символов назад.
(defmacro match (x)
(etypecase x
(character
`(when (and (< index end) (eql (char str index) ',x))
(incf index)))
(string
`(let ((old-index index)) ; 'old-index is a lexical variable.
(or (and ,@(map 'list #'(lambda (c) `(match ,c)) x))
(progn (setq index old-index) nil))))))
(defmacro match-type (x v)
`(when (and (< index end) (typep (char str index) ',x))
(setq ,v (char str index)) (incf index)))
Чтобы эти макросы работали, строку нужно описывать как лексические переменные str, index и end.
И одно замечание на прощание: ядро использует reader-макросы, так что нужно следить чтобы всё функции, которые вызываются при работе компилятора META, были доступны на этапе компиляции. Следует использовать (eval-when (:compile-toplevel) ...) в таких случаях.