meta-sexp

meta-sexp is a META parser generator using LL(1) grammars with s-expressions. meta-sexp uses in-memory string vectors, instead of commonly used streams, for efficiently stepping backward and forward through the input. It is tested on SBCL but should be portable to other implementations as well.

meta-sexp is implemented using several transformation methods. Therefore, besides builtin grammar transformations coming with meta-sexp by default, you are allowed to add your own transformation methods too.

Project is released under BSD license and currently maintained by Volkan YAZICI.

(Tarball comes with the latest .git source tree. Feel free to play with it.)

Inspired by src/streams/parser.lisp of the core-server project: https://github.com/evrim/core-server/blob/master/src/streams/parser.lisp

Idea is based on the META language discussed in `Pragmatic Parsing in Common Lisp' paper of Henry G. Baker [ACM Lisp Pointers 4, 2 (Apr/Jun 1991), 3-15]

Quick Introduction

In most of the time, you'll need to define your own parsers using CREATE-PARSER-CONTEXT methods and DEFRULE, DEFRENDERER macros.

• create-parser-context ((input string) &key start end attachment)
• create-parser-context ((input string-stream) &key buffer-size start end attachment)
• defrule (name (&rest args) (&optional attachment) &body body)
• defrenderer (name (&rest args) (&optional attachment) &body body)

In a rule or renderer body, if supplied, ATTACHMENT argument will get bound to ATTACHMENT keyword given to CREATE-PARSER-CONTEXT.

In some certain situations, you may also need to use DEFATOM too. See atoms.lisp for DEFATOM examples.

Here is a tiny example:

Here's a complete example with renderers and attachments.

What's the role of ATTACHMENT slot given to CREATE-PARSER-CONTEXT (or specified as a keyword while making an instance of PARSER-CONTEXT class)? Think it as a state storage unit between passes to defined rules and renderers. (For instance, in our above example, ATTACHMENT used as a common output stream.) Yes, it is possible to let this problem get solved by the programmer, e.g. via global variables. But this approach yields to another problem: thread safety. Anyway, that was the best that I can come up with; if you have any other ideas, I'd be happy to hear them.

Available Type Checkers

These functions (and types) are routines introduced using DEFATOM and operates on character codes. In case of need, you can add your own type checkers. (See source for examples.)

ALNUM? ALPHA? GRAPHIC? ASCII? BIT? DIGIT? EXTENDED? LOWER? NEWLINE? SPACE? TAB? UPPER? WHITE-SPACE?

Available Transformation Directives

(:ICASE FORM FORM ...)

Process supplied FORMs case-insensitive.

(:CHECKPOINT FORM FORM ...)

If form returns NIL, cursor will be back-positioned to its old location :CHECKPOINT keyword was used.

(:AND FORM FORM ...)

(:OR FORM FORM ...)

(:NOT FORM)

Besides its normal behaviour, (:NOT ...) expressions automatically get encapsulated in (:CHECKPOINT ...) clauses.

(:RETURN VAR VAR ...)

Returns supplied variables using VALUES function.

(:RENDER RENDERER ARG ARG ...)

Calls specified RENDERER (that is defined with DEFRENDERER) with supplied arguments.

(:? FORM FORM ...)

May appear once. (Similar to `?' in regular expressions.)

(:* FORM FORM ...)

May appear none or more. (Similar to `*' in regular expressions.)

(:+ FORM FORM ...)

Must appear at least once. (Similar to `{1,}' in regular expressions.)

(:TYPE TYPE-CHECKER)

(:TYPE (OR TYPE-CHECKER TYPE-CHECKER ...))

Checks type of the atom at the current position through supplied function(s).

(:RULE RULE ARG ARG ...)

(:RULE (OR RULE RULE ...) ARG ARG ...)

Tests input in the current cursor position using specified type/form. If any, supplied arguments will get passed to rule.

(:ASSIGN VAR FORM)

(:ASSIGN (VAR VAR ...) FORM)

Assigns returned value of FORM to VAR, and returns assigned value. (Latter form expands into MULTIPLE-VALUE-SETQ.)

(:LIST-PUSH ITEM-VAR LIST-ACCUM)

(:CHAR-PUSH CHAR-VAR CHAR-ACCUM)

(:CHAR-PUSH CHAR-ACCUM)

Pushes supplied ITEM-VAR/CHAR-VAR into specified LIST-ACCUM/CHAR-ACCUM. If :CHAR-PUSH is called with only one argument, current character gets read and pushed into supplied accumulator. (You can use MAKE-LIST-ACCUM and MAKE-CHAR-ACCUM functions to initialize new accumulators. Moreover, you'll probably need EMPTY-LIST-ACCUM-P and EMPTY-CHAR-ACCUM-P predicates too.)

(:LIST-RESET LIST-ACCUM)

(:CHAR-RESET CHAR-ACCUM)

Resets supplied accumulators.

(:EOF)

Returns true when reached to the end of supplied input data.

(:READ-ATOM)

Reads current atom at the cursor position.

(:DEBUG)

(:DEBUG VAR)

Prints current character and its position in the input data. If VAR is supplied, its current value gets printed.

If a form doesn't start with any of the above keywords, there're three possiblities remaining:

1. This can be a character.
2. This can be a string. (Expand it into character list form and return to 1st step.)
3. Treat as a custom form. (Will get evaluated as is.)

When you're in the third situation, to be able to get your META s-expressions compiled again, use META keyword. (See the second example in the Quick Introduction.)

Introducing New Transformations

Every transformation process issued by meta-sexp is controlled by TRANSFORM-GRAMMAR methods.

To introduce a new transformation directive, just create a new TRANSFORM-GRAMMAR method with related lambda list specializers. For instance, consider how :AND and :NOT directive transformations are implemented:

Also pay attention how meta-sexp handles unrecognized transformation directives:

With similar patterns, you can introduce new transformation directives to meta-sexp.

References

• ALIW project uses meta-sexp to parse the common wiki syntax that is adopted by the most popular wiki projects. (e.g. wikipedia, trac, moin moin.)

Account name Password

register