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.
The meta-library exports the meta-module with two macros:
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
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.
#f
, otherwise the values of
body.
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.
variables (variable [ :: type ] [ = init ], ...);
Bind variables to init, which defaults to #f;
Future versions will have further special forms.
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.
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.
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) |
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;
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.