I am working on a library for parsing and transforming trees. See "lib/treeparse.arc" and "lib/treeparse-examples.arc" in Anarki. It is based on work such as Parsec[1] and sjs's parsecomb[2]. The main difference is that this will operate on lists and trees rather than strings. [1] http://legacy.cs.uu.nl/daan/parsec.html
[2] http://arclanguage.org/item?id=1430
There are three basic ways parsers can be constructed (other than by creating new primitives.) * A parser for some atom is the literal itself -- i.e. (parse 'a input) will succeed on input '(a).
* A parser for sublists is a list of parsers -- this gives us the ability to parse arbitrary trees.
* More complex parsers can be formed by combining parsers -- using combinators.
Parser combinators are operators for constructing more elaborate parsers from simpler ones. Some of the more common ones are alt, many, seq, and maybe.Consider a simple parser which says "I expect to see zero or more a's, followed by either b or c, followed optionally by d". Here's how we could use combinators to construct it. ;;; S ::= [a*] {b | c} [d]
(= S (seq (many 'a) (alt 'b 'c) (maybe 'd)))
S is now a parser for the grammar given above. Here are some of the inputs that S would accept. '(b)
'(c)
'(c d)
'(b d)
'(a b d)
'(a a a b d)
Now we can do something a little more interesting. Tree parsing is especially useful for defining Lisp macros, because macros are essentially transformations on trees. To manipulate subtrees, we can use the filt combinator to attach a filter function to a parser. Here is a cond macro to convert conventional Lisp cond to Arc's if and do. (= forms (filt [list:cons 'do _] (many anything)))
(= clause (filt car (list (seq anything forms))))
(= S (filt [cons 'if _] (many clause)))
(mac cond clauses (parse-all S clauses))
| 
