instaparse

Instaparse 1.5.0 What if context-free grammars were as easy to use as regular expressions? Features Instaparse aims to be the simplest way to build parsers in Clojure. Turns standard EBNF or ABNF notation for context-free grammars into an executable parser that takes a string as an input and produces a parse tree for that string. No Grammar Left Behind: Works for any context-free grammar, including left-recursive, right-recursive, and ambiguous grammars. Extends the power of context-free grammars with PEG-like syntax for lookahead and negative lookahead. Supports both of Clojure's most popular tree formats (hiccup and enlive) as output targets. Detailed reporting of parse errors. Optionally produces lazy sequence of all parses (especially useful for diagnosing and debugging ambiguous grammars). "Total parsing" mode where leftover string is embedded in the parse tree. Optional combinator library for building grammars programmatically. Performant. Quickstart Instaparse requires Clojure v1.5.1 or later, or ClojureScript v1.7.28 or later. Add the following line to your leiningen dependencies: [instaparse "1.5.0"] Require instaparse in your namespace header: (ns example.core (:require [instaparse.core :as insta])) Creating your first parser Here's a typical example of a context-free grammar one might see in a textbook on automata and/or parsing. It is a common convention in many textbooks to use the capital letter S to indicate the starting rule, so for this example, we'll follow that convention: S = AB* AB = A B A = 'a'+ B = 'b'+ This looks for alternating runs of 'a' followed by runs of 'b'. So for example "aaaaabbaaabbb" satisfies this grammar. On the other hand, "aaabbbbaa" does not (because the grammar specifies that each run of 'a' must be followed by a run of 'b'). With instaparse, turning this grammar into an executable parser is as simple as typing the grammar in: (def as-and-bs (insta/parser "S = AB* AB = A B A = 'a'+ B = 'b'+")) => (as-and-bs "aaaaabbbaaaabb") [:S [:AB [:A "a" "a" "a" "a" "a"] [:B "b" "b" "b"]] [:AB [:A "a" "a" "a" "a"] [:B "b" "b"]]] At this point, if you know EBNF notation for context-free grammars, you probably know enough to dive in and start playing around. However, instaparse is rich with features, so if you want to know the full scope of what it can do, read on... Tutorial Notation Instaparse supports most of the common notations for context-free grammars. For example, a popular alternative to * is to surround the term with curly braces {}, and a popular alternative to ? is to surround the term with square brackets []. Rules can be specified with =, :, :=, or ::=. Rules can optionally end with ;. Instaparse is very flexible in terms of how you use whitespace (as in Clojure, , is treated as whitespace) and you can liberally use parentheses for grouping. Terminal strings can be enclosed in either single quotes or double quotes (however, since you are writing the grammar specification inside of a Clojure double-quoted string, any use of double-quotes would have to be escaped, therefore single-quotes are easier to read). Newlines are optional; you can put the entire grammar on one line if you desire. In fact, all these notations can be mixed up in the same specification if you want. So here is an equally valid (but messier) way to write out the exact same grammar, just to illustrate the flexibility that you have: (def as-and-bs-alternative (insta/parser "S:={AB} ; AB ::= (A, B) A : \"a\" + ; B ='b' + ;")) Note that regardless of the notation you use in your specification, when you evaluate the parser at the REPL, the rules will be pretty-printed: => as-and-bs-alternative S = AB* AB = A B A = "a"+ B = "b"+ Here's a quick guide to the syntax for defining context-free grammars: CategoryNotationsExample Rule: := ::= =S = A End of rule; . (optional)S = A; Alternation|A | B Concatenationwhitespace or ,A B Grouping()(A | B) C Optional? []A? [A] One or more+A+ Zero or more* {}A* {A} String terminal"" '''a' "a" Regex terminal#"" #''#'a' #"a" EpsilonEpsilon epsilon EPSILON eps ε "" ''S = 'a' S | Epsilon Comment(* *)(* This is a comment *) As is the norm in EBNF notation, concatenation has a higher precedence than alternation, so in the absence of parentheses, something like A B | C D means (A B) | (C D). Input from resource file Parsers can also be built from a specification contained in a file, either locally or on the web. For example, I stored on github a file with a simple grammar to parse text containing a single 'a' surrounded optionally by whitespace. The specification in the file looks like this: S = #"\s*" "a" #"\s*" Building the parser from the URI is easy: (insta/parser "https://gist.github.com/Engelberg/5283346/raw/77e0b1d0cd7388a7ddf43e307804861f49082eb6/SingleA") This provides a convenienent way to share parser specifications over the Internet. You can also use a specification contained in a local resource in your classpath: (insta/parser (clojure.java.io/resource "myparser.bnf")) defparser On ClojureScript, the (def my-parser (insta/parser "...")) use case has the following disadvantages: ClojureScript does not support slurp, so parser cannot automatically read from file paths / URLs. Having to parse a grammar string at runtime can impact the startup performance of an application or webpage. To solve those problems, a macro instaparse.core/defparser is provided that, if given a string for a grammar specification, will parse that as a grammar up front and emit more performant code. ;; Clojure (all versions) and ClojureScript (1.9.198 and above) (:require [instaparse.core :as insta :refer [defparser]]) ;; ClojureScript (prior to 1.9.198) (:require [instaparse.core :as insta :refer-macros [defparser]]) => (time (def p (insta/parser "S = A B; A = 'a'+; B = 'b'+"))) "Elapsed time: 4.368179 msecs" #'user/p => (time (defparser p "S = A B; A = 'a'+; B = 'b'+")) ; the meat of the work happen