DOCSEARCHbyAlgolia
Submit Docs

instaparse

repository·master·Indexed 25 days ago

https://github.com/engelberg/instaparse

A Clojure and ClojureScript library for building executable parsers from context-free grammars using EBNF or ABNF notation. It supports left and right recursion, lookahead (&), negative lookahead (!), and ordered choice (/), producing parse trees in :hiccup or :enlive formats. Features include a defparser macro for performance, tree transformation via insta/transform, and tools for handling ambiguous grammars.

Tokens
10.5K
Snippets
36
Records
58
Agent score
84%

What's inside instaparse

  1. Understand instaparse performance characteristics

    master

    instaparse is designed for flexibility, allowing it to handle arbitrary context-free grammars that include ambiguity, backtracking, and a mixture of left and right recursion.

    Performance Goals:

    • Linear Time: For typical real-world grammars, running time aims to be linear relative to input size ($O(n imes ext{log}_{32} n)$ in Clojure).
    • LL(1) Competitiveness: If a grammar is unambiguous and LL(1), instaparse aims to be competitive with specialized LL(1) parser generators.
    • Graceful Degradation: Performance is designed to degrade gracefully as grammar ambiguity and backtracking increase.

    Memory Usage: Because instaparse supports backtracking and ambiguity, it requires the entire input text to reside in memory, and it caches significant intermediate results. Users should expect higher memory consumption compared to strict LL(1) or LALR(1) parsers.

  2. Control tree structure by hiding content or tags

    master

    By default, every rule in your grammar creates a new level of nesting in the output tree, tagged with the rule name. You can use angle brackets <> to modify this behavior.

    Hide Content

    Wrap tokens in angle brackets to prevent them from appearing in the output tree. This is useful for delimiters like parentheses or whitespace. Example: <'('> seq-of-A-or-B <')'> hides the parentheses.

    Hide Tags (Flattening)

    Wrap a rule name in angle brackets to hide the tag and its associated nesting level. This allows you to define a rule for semantic clarity without adding extra layers to the tree. Example: <seq-of-A-or-B> = ('a' | 'b')*.

    Reveal Hidden Information

    When calling the parser, use the :unhide keyword argument to debug your tree:

    • :unhide :content: Shows hidden tokens.
    • :unhide :tags: Shows hidden rule tags.
    • :unhide :all: Shows both hidden tokens and tags.
    ;; Hide content (parentheses)
(def paren-ab-hide-parens
  (insta/parser
    "paren-wrapped = <'('> seq-of-A-or-B <')'>
     seq-of-A-or-B = ('a' | 'b')*"))

;; Hide tags (flattening the rule)
(def paren-ab-hide-tag
  (insta/parser
    "paren-wrapped = <'('> seq-of-A-or-B <')'>
     <seq-of-A-or-B> = ('a' | 'b')*"))

;; Reveal hidden info for debugging
(paren-ab-hide-both-tags "(aba)" :unhide :all)

  3. Optimize instaparse grammar performance

    master

    While instaparse is designed to be resilient to grammar wording, you can improve performance by following these best practices:

    1. Use LL Grammars: If possible, write your grammar in an LL style.
    2. Prefer String Literals: Use string literals ('apple') instead of regular expressions (#'apple') for exact matches.
    3. Use Regex for Repetition: Use * and + inside regular expressions rather than outside. For example, use #'\s*' instead of #'\s'* for whitespace.
    4. Define Tokens via Regex: Define complex tokens entirely within a single regular expression rather than building them character-by-character with multiple rules.
    5. Minimize Ambiguity: Ambiguity increases processing time. Use insta/parses with various inputs to identify multiple interpretations.
    6. Avoid Internal Ambiguity: Use insta/parses with the :partial true flag to check if a rule requires the parser to look far ahead before resolving an interpretation.
    7. Check Hidden Ambiguity: Use insta/parses with the :unhide :all flag to reveal if hidden content (like whitespace) is causing ambiguity.
    8. Prefer Repetition over Recursion: Use * and + instead of recursive rules for simple repetition (e.g., <A> = 'a'+ is better than <A> = 'a' A | 'a').
    9. Use Faster Output Formats: As of version 1.2, the enlive output format is slightly faster than hiccup.

  4. Best practices for auto-whitespace and token definitions

    master

    When using :auto-whitespace, ensure that your tokens are defined using single regular expressions rather than character-by-character rules. If you define a token using multiple rules (e.g., month = ('M'|'m') 'arch'), the auto-whitespace feature will incorrectly allow spaces between the individual components (e.g., M arch).

    Correct approach: Use a single regex: month = #'[Mm]arch'.

  5. Install Instaparse via Leiningen

    master

    To use Instaparse in your Clojure project, add the following dependency to your project.clj file using Leiningen:

    [instaparse "1.5.0"]

    Note: Instaparse requires Clojure v1.5.1 or later, or ClojureScript v1.7.28 or later.

    [instaparse "1.5.0"]

  6. Hide grammar parts using Angle Brackets in ABNF

    master

    Instaparse supports angle bracket notation <...> in ABNF mode. This is used to hide specific parts of the grammar from the resulting tree structure.

    Warning: While ABNF uses angle brackets for prose descriptions, instaparse treats them as structural instructions. Scan your ABNF source for existing angle brackets (e.g., in URI specifications) to ensure they aren't intended as prose before using this feature.

    P = <a prime number>

  7. Express preference with ordered choice (`/`)

    master

    While the standard alternation operator | is unordered, you can use the / operator to express a preference for one alternative over another. The parser will try the first alternative first and only proceed to the next if the first fails. This brings the preferred parse result to the top of the list of possible parses.

    (def preferential-tokenizer
	  (insta/parser
	    "sentence = token (<whitespace> token)*
	     <token> = keyword / identifier
	     whitespace = #'\\s+'
	     identifier = #'[a-zA-Z]+'
	     keyword = 'cond' | 'defn'"))

  8. Create a parser using insta/parser

    master

    You can create an executable parser by passing a grammar string (using standard EBNF or ABNF notation) to the insta/parser function. The resulting parser can then be called with a string input to produce a parse tree.

    (def as-and-bs
  (insta/parser
    "S = AB*
     AB = A B
     A = 'a'+
     B = 'b'+"))

;; Usage:
(as-and-bs "aaaaabbbaaaabb")

  10. Enable case-insensitive non-terminals in ABNF

    master

    By default, instaparse treats ABNF non-terminal rule names as case-sensitive to maintain compatibility with EBNF and other grammar maps.

    If you are using an ABNF grammar where non-terminal rules are referred to using inconsistent casing (e.g., S = 'a' s), you can enable case-insensitivity by binding the dynamic variable instaparse.abnf/*case-insensitive* to true during parser construction.

    Warning: When this mode is enabled, instaparse converts all non-terminals to uppercase. You must ensure your tree traversals and transformations expect uppercase rule names in the resulting parse tree.

    (def phone-uri-parser
  (binding [instaparse.abnf/*case-insensitive* true]
    (insta/parser "https://raw.github.com/Engelberg/instaparse/master/test/instaparse/phone_uri.txt"
                  :input-format :abnf)))

  11. Optimize memory usage with the :optimize :memory flag

    master

    Instaparse provides an experimental :optimize :memory flag to reduce memory consumption when parsing large files containing many independent, repeating chunks.

    Requirements for Optimization

    To benefit from this optimization, your grammar's top-level production should follow a pattern where it finishes with a repeating structure, such as:

    • start = chunk+
    • start = header chunk+

    Crucially, the chunk rule must be written without ambiguity regarding where a chunk begins and ends.

    How it works

    When enabled, the parser attempts to parse one chunk at a time and then 'forgets' all backtracking information before moving to the next chunk. This prevents the accumulation of history that typically consumes memory in large parses.

    Safety and Fallback Behavior

    • Correctness: The output is guaranteed to be identical to a standard parse.
    • Automatic Fallback: If the parser encounters a section of text that does not match the repeating chunk rule, it cannot backtrack using the optimized strategy. Instead, it will automatically restart the entire parsing process using the standard (non-optimized) strategy.
    • Risk: If your input file is so large that memory optimization is a strict necessity, a parsing error late in the file will trigger the fallback to the standard strategy, which may lead to memory exhaustion.
    (def my-parser (insta/parser my-grammar))
(my-parser text :optimize :memory)

  12. Enable tracing in Instaparse

    master

    In Clojure, you can inspect a trace of the parser's execution by passing the optional keyword argument :trace true to insta/parse or insta/parses.

    Note that the first time you call a parser with :trace true, there may be a slight pause as Instaparse recompiles itself to support tracing. This instrumentation is only active when explicitly requested, so there is no performance penalty for standard usage.

    The trace is printed to standard output and includes details about initiated parses, results found, and profiling data.