Parser combinator library in Golang

A library to construct top-down recursive backtracking parsers using parser-combinators. Before proceeding you might want to take at peep at theory of parser combinators. As for this package, it provides:

• A standard set of combinators.
• Regular expression based simple-scanner.
• Standard set of tokenizers based on the simple-scanner.

To construct syntax-trees based on detailed grammar try with AST struct

• Standard set of combinators are exported as methods to AST.
• Generate dot-graph EG: dotfile for html.
• Pretty print on the console.
• Make debugging easier.

NOTE that AST object is a recent development and expect user to adapt to newer versions

Quick links

• Go documentation.
• Using the builtin scanner.
• Simple HTML parser.
• Querying Abstract Syntax Tree
• Projects using goparsec.
• Articles.
• How to contribute.

Combinators

Every combinator should confirm to the following signature,

    // ParsecNode type defines a node in the AST
    type ParsecNode interface{}

    // Parser function parses input text, higher order parsers are
    // constructed using combinators.
    type Parser func(Scanner) (ParsecNode, Scanner)

    // Nodify callback function to construct custom ParsecNode.
    type Nodify func([]ParsecNode) ParsecNode

Combinators take a variable number of parser functions and return a new parser function.

Using the builtin scanner

Builtin scanner library manages the input buffer and implements a cursor into the buffer. Create a new scanner instance,

    s := parsec.NewScanner(text)

The scanner library supplies method like Match(pattern), SkipAny(pattern) and Endof(), refer to for more information on each of these methods.

Panics and Recovery

Panics are to be expected when APIs are misused. Programmers might choose to ignore errors, but not panics. For example:

• Kleene and Many combinators take one or two parsers as arguments. Less than one or more than two will throw a panic.
• ManyUntil combinator take two or three parsers as arguments. Less than two or more than three will throw a panic.
• Combinators accept Parser function or pointer to Parser function. Anything else will panic.
• When using invalid regular expression to match a token.

Examples

• expr/expr.go, implements a parsec grammar to parse arithmetic expressions.
• json/json.go, implements a parsec grammar to parse JSON document.

Clone the repository run the benchmark suite

    $ cd expr/
    $ go test -test.bench=. -test.benchmem=true
    $ cd json/
    $ go test -test.bench=. -test.benchmem=true

To run the example program,

    # to parse expression
    $ go run tools/parsec/parsec.go -expr "10 + 29"

    # to parse JSON string
    $ go run tools/parsec/parsec.go -json '{ "key1" : [10, "hello", true, null, false] }'

Projects using goparsec

• Monster, production system in golang.
• GoLedger, ledger re-write in golang.

If your project is using goparsec you can raise an issue to list them under this section.

Articles

• Parsing by composing functions
• Parser composition for recursive grammar
• How to use the Maybe combinator

How to contribute

• Pick an issue, or create an new issue. Provide adequate documentation for the issue.
• Assign the issue or get it assigned.
• Work on the code, once finished, raise a pull request.
• Goparsec is written in golang, hence expected to follow the global guidelines for writing go programs.
• If the changeset is more than few lines, please generate a report card.
• As of now, branch master is the development branch.