Home

fnparse is a library for creating functional parsers in the Clojure programming language. It presents an easy, functional way to create parsers from EBNF rules and was inspired by the paper Using Functional Parsing to Achieve Quality in Software Maintenance.

Library usage

fnparse requires clojure-contrib, the Clojure standard library.

fnparse’s distribution has src and test folders. To use fnparse, download this distribution and include its src folder in your program’s classpath—for instance, java -cp $CLOJURE_PATH:$CLOJURE_CONTRIB_PATH:path-to-fnparse/fnparse/src/ …

fnparse’s namespace is name.choi.joshua.fnparse. fnparse’s unit tests are stored in the tests folder.

For a little example of what fnparse can do, check out the sample JSON parser.

Note that fnparse is not necessarily a lexer. It’s mean to parse an already-created collection of tokens. fnparse is meant to be used in conjunction with a lexer, and it can build parsers based on any sort of token you wish. However, it might be easiest if you decide that Characters are your language’s tokens and the clojure.core/seq function be your lexer. The sample JSON parser is an example of that. (I’m deciding whether I want to create an optimized version of fnparse with compiler type hints for Characters, and whether it’s possible to let the library user decide on the type hints.)

Rules

A parser is a function that receives a sequence of tokens and creating some new, corresponding structure—depending on the parser’s grammar. The concept of fnparse is breaking down a parser into a bunch of rules that nicely correspond to the rules in its grammar.

Rules are functions (two arguments) that take a sequential collection of tokens and consumes the first few tokens. The two arguments are a collection of tokens and an info object (which can be anything). If a sequence of tokens is valid for a rule, the rule returns a 3-sized vector containing:

• An object called the result’s product, the product of the tokens that the rule consumed
• A sequence of the remaining tokens called the result’s remainder
• An object (usually a map) called the result’s info that includes additional information about the result. For instance, you could make a parser keep track of the current line and column using info.
  If a sequence of tokens is invalid for a rule, the rule simply returns nil.

Note that in order to directly use a rule, you must call it with two arguments: its initial tokens and its inital info: (root-rule initial-tokens initial-info). Most of the time, the functions below make that totally unnecessary except in an actual parser function, where the root rule would be directly used.