Distfix expression parsing library
==================================
Syntactical is a Haskell library to parse languages made exclusively, from a
syntactic point of view, of operators and function applications. It is based
on a modified shunting-yard algorithm. The modifications are done to allow
distfix operators and function application written with juxtaposition of
symbols (just like in Haskell).
The resulting parse trees are s-expressions. Further processing to create an
AST specific to the task at hand is left to the user (but this should be
straightforward).
Examples
--------
To create a parser, it is just needed to provide an operator table. To give a
feel of the library at work, here are some examples. The resulting parse trees
(s-expressions) are displayed using the characters ⟨ and ⟩ instead of the
parentheses (this is not enforced by the library).
-- input => output
1 + 2 => ⟨+ 1 2⟩
1 + 2 * 3 => ⟨+ 1 ⟨* 2 3⟩⟩
f a => ⟨f a⟩
1 + f a b => ⟨+ 1 ⟨f a b⟩⟩
-- parentheses for grouping are are just a closed operator
-- ␣ is the hole, in fact, the + above could be written ␣+␣
(a) => ⟨(␣) a⟩
-- if you know that parentheses are only used for grouping
-- (i.e. it can be viewed as an operator with the semantic
-- of the identity function), the parser can drop them.
(a) => a
-- the parser can also be configured to recognize two symbols
-- used to write directly s-expressions, here we use again the
-- characters ⟨ and ⟩. notice that a + b is written in infix
-- form.
⟨* (a + b) ⟨- 1 2⟩⟩ => ⟨* ⟨+ a b⟩ ⟨- 1 2⟩⟩
-- the library supports mixfix (also called distfix) operators
true ? 1 : 0 => ⟨␣?␣:␣ true 1 0⟩
# a => ⟨#␣ a⟩
a ! => ⟨␣! a⟩
1 + if true then 1 else a b + c => ⟨+ 1 ⟨if␣then␣else␣ true 1 ⟨+ ⟨a b⟩ c⟩⟩⟩
[ a | b ] => ⟨[␣|␣] a b⟩
Current state
-------------
The library works but is still a bit rough. Tests don't cover enough cases and
it is simple to overlook one. Documentation is missing (but a look at
tests/Simple is enough to start).
The HPC shows that a few things are not tested:
- a few unevaluated Hole values in Simple.hs shows that some operator
combinations are not tested)
- A AmbiguousContinue MiddleOrLast in findContinuing is never returned
- Surprisingly, it seems the fst element in Maybe (Associativity,Precedence)
- is not used.
Future and/or wishes
--------------------
- Make a version of the modified shunting-yard exposed as Parsec's
buildExpressionParser, i.e. the base token (or term) is specified by a
user-sipplied parser, with functions used to build the tree.
- Allow arbitray parsers to be used in holes, in addition of the SExpression
and Distfix kinds of holes currently available.
- Allow a new kind of hole called Repeat or Repetition or List (but List is a
constructor in the Tree data type). That new kind of hole allows a (possibly
empty) list of sub-expressions to appear in the hole, separated by an
operator part. E.g. closed "[" (Repeat ",") "]" would allow [ ], [ a ],
[ a , b ], [ a, b, c ] and so on. The result would be respectively ⟨[,] ⟨⟩⟩,
⟨[,] ⟨a⟩⟩, ⟨[,] ⟨a b⟩⟩, ⟨[,] ⟨a b c⟩⟩ and so on. It should also be possible
to use closed "[" (Repeat ";") "]" and closed "[" (Repeat ",") "]" in the
same operator table. The [,] (and [;]) would be user-constructed by adding a
'list' method to the Token class.
- Make use of the reparsing capability (the input and output type is the same).
E.g. it would be possible to differentiate between different kind of holes
based on its right part (by leaving it unparsed, then parsing it when the
right part is known).
- The biggest problem of this approach is that the parser can accept a lot of
invalid inputs. Probably a good approach would be to use s-expression
grammars.
- Turn the library into a command-line tool to generate parsers.
- Check the operator table for ambiguity separately of running the shunting-
yard.
- The showSExpr/showTree should not use concatMap and (++).
Before pushing to Hackage
-------------------------
- Write the doc
- Make sure it installs cleanly with cabal