Yellow Rabbit

Парсер META - классическая система разбора

Web-движок на Lisp: язык 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) ...) в таких случаях.