The Meta Library

1. Introduction
2. Exported Facilities
3. Syntax of with-meta-syntax
4. Meta expressions
5. Example code
6. References

This is an implementation of Meta, a technique used to simplify the task of writing parsers. [Baker91] describes Meta and shows the main ideas for an implementation in Common Lisp.

If all META did was recognize regular expressions, it would not be very useful. It is a programming language, however, and the operations [], {} and $ correspond to the Common Lisp control structures AND, OR, and DO.[8] Therefore, we can utilize META to not only parse, but also to transform. In this way, META is analogous to "attributed grammars" [Aho86], but it is an order of magnitude simpler and more efficient. Thus, with the addition of the "escape" operation "!", which allows us to incorporate arbitrary Lisp expressions into META, we can not only parse integers, but produce their integral value as a result. --[Baker91]

2. Exported facilities

The meta-library exports the meta-module with two macros:

with-meta-syntax

Implements Meta and provides some additional functionality to defines variables. See below.

with-collector

General facility to collect data into lists or vectors. Initially with-meta-syntax had this functionality integrated--a mess. Now there is this more modular approach.

Meta integrates the ability to parse from streams and strings in one facility. (The parsing of lists is not implemented yet, because it's rather useless in Dylan. This addition would be simple to do, though.)

with-meta-syntax source-type (source #key keys)
  [ variables ]
  meta;
  body
end
	

Arguments:

source-type---either parse-stream or parse-string

source---either a stream or a string, depending on source-type

keys---source-type specific.

meta---a Meta expression.

body---a body. Evaluated only if parsing is successful.

Values:

If parsing fails #f, otherwise the values of body.

Keyword arguments:

parse-stream does not accept keyword arguments currently.

parse-string recognizes the following keywords:

start---Index to start at

end---Index to finish before

pos---A name. A variable called pos will be defined which holds the current index during execution of the with-meta-syntax forms.

Special programming aids:

variables (variable [ :: type ] [ = init ], ...);

Bind variables to init, which defaults to #f;

Future versions will have further special forms.

Example fragments:

with-meta-syntax parse-stream (*standard-input*)
  body
end with-meta-syntax;

let query :: <string> = ask-user();
with-meta-syntax parse-string (query, start: 23, end: 42)
  body
end with-meta-syntax;

with-meta-syntax parse-string (query)
  ... ['\n', finish()] ...
  values(these, values, will, be, returned);
end with-meta-syntax;
	

Meta is a small, but featureful language, so naturally it has its own syntax. This syntax is adapted to Dylan's way of writing things, of course.

There are several basic Meta expressions implementing the core functionality. Additionally there are some pseudo-functions, syntactically function-like constructs which simplify certain tasks that would otherwise have to be written manually.

Basic Meta expressions as described by Baker

The same grammar which works for streams will works for strings, too. When parsing strings, more than just one-character look-ahead is possible, though. You can therefore not only match against characters, but also whole substrings. This does not work when reading from a stream.

Additional pseudo-function expressions

Parsing an integer (base 10)

Common Lisp version:

(defun parse-integer (&aux (s +1) d (n 0))
  (and
   (matchit
    [{#\+ [#\- !(setq s -1)] []}
    @(digit d) !(setq n (digit-to-integer d))
    $[@(digit d) !(setq n (+ (* n 10) (digit-to-integer d)))]])
   (* s n)))
    

define constant <digit> = one-of('0','1','2','3','4','5','6','7','8','9');

define function parse-integer (source :: <stream>);
  let s = +1; // sign
  let n = 0;  // number
  with-meta-syntax parse-stream (source) (d)
    [{'+', ['-', (s := -1)], []},
     type(<digit>, d), (n := digit-to-integer(d)),
     loop([type(<digit>, d), (n := digit-to-integer(d) + 10 * n)])];
    (s * n)
  end with-meta-syntax;
end function parse-integer;
    

define function parse-integer (source :: <stream>);
  with-meta-syntax parse-stream (source)
    variables (d, sign = +1, num = 0);
    [{'+', ['-', set!(sign, 1)], []},
     test(digit?, d), set!(num, digit-to-integer(d)),
     loop([test(digit?, d), set!(num, digit-to-integer(d) + 10 * num)])];
    sign * num;
  end with-meta-syntax;
end function parse-integer;
    

define function parse-finger-query (query :: )
  with-collector into-buffer user like query (collect: collect)
    with-meta-syntax parse-string (query)
      variables (whois, at, c);
      [loop(' '), {[{"/W", "/w"}, yes!(whois)], []},        // Whois switch?
       loop(' '), loop({[{'\n', '\r'}, finish()],           // Newline? Quit.
			{['@', yes!(at), do(collect('@'))], // @? Indirect.
			 [accept(c), do(collect(c))]}})];   // then collect char
      values(whois, user(), at);
    end with-meta-syntax;
  end with-collector;
end function parse-finger-query;
    

[Baker91] Baker, Henry. "Pragmatic Parsing in Common Lisp". ACM Lisp Pointers 4, 2 (Apr-Jun 1991), 3-15.