The Meta Library

This is a reorganized version of the original text-only documentation. It became more and more unreadable, so here is a more structured HTML-Version.

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

1. Introduction

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]
The macro defined here is an attempt to implement Meta (with slightly adapted syntax) for Dylan. It is functional, but not yet optimized.

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.

3. Syntax of with-meta-syntax

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;
	

4. Meta expressions

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

Baker with-meta-syntax Description
fragment fragment try to match this
[a b c ... n] [a, b, c, ..., n] and/try all
{a b c ... n} {a, b, c, ..., n} or/first hit
@(type variable) type(type, variable) match any type
$foo loop(foo) zero or more
!Lisp (Dylan) call the code (and check result)

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

with-meta-syntax Description Could be written as
do(Dylan) call the code and continue (whatever the result is) (Dylan; #t)
finish() finish parsing successfully not possible
test(predicate) Match against a predicate. not possible
test(predicate, variable) Match against a predicate, saving the result. not possible
yes!(variable) Set variable to #t and continue. (variable := #t)
no!(variable) Set variable to #f and continue. (variable := #f; #t)
set!(variable, value) Set variable to value and continue. (variable := value; #t)
accept(variable) Match anything and save result. type(<object>, variable)

5. Example code

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)))
    
Direct translation to Dylan:

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;
    
Alternative version:
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;
    

Parsing finger queries

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;
    

6. References

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


David Lichteblau
Last modified: Sat Apr 10 20:47:23 CEST 1999