panda-grammar

    2.1.2 • Public • Published

    Panda Grammar

    Deprecated: Please use dashkite/parse instead.

    Panda Grammar is a parser combinator library for writing recursive descent parsers. What that means is that you write functions that consume input and return a value indicating what was parsed and combine these using other higher order functions. For example, you might have a function that parses a URL scheme. You could then use that function in a function that takes a sequence of such functions to parse entire URLs.

    Example: URL Parser

    Let's start by defining a few simple elements of a URL. These use the string and re helpers from Panda Grammar, which consume strings and regular expressions, respectively.

    (Examples in CoffeeScript because I like to write in CoffeeScript, but the semantics are the same as those of JavaScript.)

    separator = string "/"
    word = re /^\w+/
    qdelim = string "?"       # query delimiter
    cdelim = string "&"       # query continuation delimeter
    equal = string "="
    protocol = re /^https?/
    sdelim = string ":"       # scheme delimiter
    root = string "//"

    So far, so good. If you're familiar with the URL spec, you'll see that we're make a few simplifying assumptions, such as ignoring FTP URLs.

    Next we want to build functions using these functions to parse the various parts of a URL, like the scheme and path.

    scheme = all protocol, sdelim
    path = all root, list separator, word

    PG provides combinators, like all and list, that allow to combine the simple functions we've already defined. The only problem is that these will return nested arrays of everything that's parsed. That isn't super useful, which is why PG provides a rule combinator, so that you can transform these arrays into useful values.

    scheme = rule (all protocol, sdelim),
      ({value: [protocol]}) -> {protocol}
    
    path = rule (all root, list separator, word),
      ({value: [, components]}) -> {components, path: "/" + (components.join "/")}

    Rules take a function and pass the return value to a second function that can modify it. The return value from PG function is an object containing two properties: the parsed value and the rest of the input.

    For our scheme rule, we take the protocol and ignore the delimiter. For the path rule, we ignore the // and return both the path components and the reconstructed path.

    Here's a rule for query parameters that returns an object based on the query.

    assignment = rule (all word, equal, word),
      ({value: [key, , value]}) -> [key, value]
    
    query = rule (all qdelim, list cdelim, assignment),
      ({value: [, pairs]}) ->
        query = {}
        query[k] = v for [k, v] in pairs
        {query}

    We pull them altogether into another rule that parses and entire URL and merges the result into a single object.

    url = rule (all scheme, path, (optional query)),
      ({value}) -> Object.assign value...

    The finishing touch is to use the grammar combinator to define our parseURL function. The grammar helper checks to make sure that there's no input remaining to parse, returning undefined otherwise.

    parseURL = grammar url

    Let's try it out:

    assert.deepEqual (parseURL "https://foo/bar?baz=123"),
      protocol: "https"
      path: "/foo/bar"
      components: [ "foo", "bar" ]
      query:
        baz: "123"

    Installation

    npm i -S panda-grammar
    

    Usage

    import {<whichever functions you need>} from "panda-grammar"

    Limitations

    While parser combinators are a powerful way to write parsers, Panda Grammar is still under development. It's missing combinators for sets (order doesn't matter, each rule can only match once), look-aheads (important for certain edge cases, particular for recursive rules), memoization (allows parsing in polynomial time), and error handling support.

    That said, recursive descent parsers have an undeserved reputation for being impractical. A benchmark of JSON parsers demonstrate that parser combinator libraries (Parsimmon outperform conventional parser generator libraries like Jison and ANTLR. In fact, performance is comparable to a hand-written parser. Of course, JSON is relatively simple to parse, but the lesson remains: don't write off recursive descent parsers!

    API

    Terminology

    A product is an object with two properties:

    • value: what was parsed
    • rest: what remains to be parsed

    A consumer is a function that takes a string as input and returns a product or null, if nothing could be parsed.

    A combinator is a function that takes consumers as arguments and returns another consumer.

    re

    Takes a regular expression and returns a consumer that matches that regular expression.

    protocol = re /^https?/

    Warning

    Typically, you want to anchor the expression at the beginning of the input with ^. Unanchored regular expressions are useful for lookahead.

    word

    Equivalent to re /^\w+/.

    ws

    Equivalent to re /^\s+/.

    string

    Takes a string and returns a consumer that matches it.

    root = string "//"

    any

    Takes a list of consumers as arguments and returns a consumer that will return the product of the first match or null.

    food = any (string "pizza"), (string "wings"), (string "burrito")
    

    optional

    Takes a consumer and returns a consumer that returns its product if it matches. Otherwise returns a product where rest is the input string.

    url = all scheme, path, (optional query)

    all

    Takes a list of consumers as arguments and returns a consumer that matches each in the order given.

    url = all scheme, path, (optional query)

    many

    Takes a consumer and matches against it as many times as possible.

    program = many expressions

    list

    Takes two consumers, a delimiter and an item, and attempts to match items separated by delimiters.

    query = all qdelim, list cdelim, assignment

    between

    Takes a delimiter-pair string and a consumer, and attempts to match the consumer between the delimiters.

    between (string "{"), (string "}"), expression

    forward

    Takes a function that returns a consumer and returns a second consumer that delegates to it. Useful for referencing consumers that haven't been defined yet but exist within the closure of the function.

    program = many (forward -> expressions)

    rule

    Takes a consumer and a function that accepts a product and returns a value and returns a consumer that passes the given consumer's product to the given function. Useful for transforming the value of the product.

    assignment = rule all variable equals expression, (product) ->
      {value: [variable, expression]} = product
      variables[variable] = evaluate expression

    tag

    A rule that replaces the parsed value with an object with a property of the given name whose value is the parsed value.

    rule "variable", word

    merge

    Merges object values together.

    join

    Joins an array of values (presumably strings) together.

    grammar

    Takes a consumer and returns it's value if rest is empty.

    parseURL = grammar url
    assert.deepEqual (parseURL "https://foo/bar?baz=123"),
      protocol: "https"
      path: "/foo/bar"
      components: [ "foo", "bar" ]
      query:
        baz: "123"

    Install

    npm i panda-grammar

    DownloadsWeekly Downloads

    17

    Version

    2.1.2

    License

    SEE LICENSE IN LICENSE.md

    Unpacked Size

    29.5 kB

    Total Files

    6

    Last publish

    Collaborators

    • dyoder
    • freeformflow