EarleyParser

public struct EarleyParser : AmbiguousGrammarParser

A parser generator implementation that internally uses the Earley algorithm.

Creates a syntax tree in O(n^3) worst case run time. For unambiguous grammars, the run time is O(n^2). For almost all LR(k) grammars, the run time is O(n). Best performance can be achieved with left recursive grammars.

For ambiguous grammars, the runtime for parses may increase, as some expressions have exponentially many possible parse trees depending on expression length. This exponential growth can be avoided by only generating a single parse tree with syntaxTree(for:).

For unambiguous grammars, the Earley parser performs better than the CYK parser.

  • The grammar recognized by the parser

    Declaration

    Swift

    public let grammar: Grammar

  • Generates an earley parser for the given grammar.

    Creates a syntax tree in O(n^3) worst case run time. For unambiguous grammars, the run time is O(n^2). For almost all LR(k) grammars, the run time is O(n). Best performance can be achieved with left recursive grammars.

    Declaration

    Swift

    public init(grammar: Grammar)

  • Creates a syntax tree which explains how a word was derived from a grammar

    Throws

    A syntax error if the word is not in the language recognized by the parser

    Declaration

    Swift

    public func syntaxTree(for string: String) throws -> ParseTree

    Parameters

    string

    Input word, for which a parse tree should be generated

    Return Value

    A syntax tree explaining how the grammar can be used to derive the word described by the given tokenization

  • Generates all syntax trees explaining how a word can be derived from a grammar.

    This function should only be used for ambiguous grammars and if it is necessary to retrieve all parse trees, as it comes with an additional cost in runtime.

    For unambiguous grammars, this function should return the same results as syntaxTree(for:).

    Throws

    A syntax error if the word is not in the language recognized by the parser

    Declaration

    Swift

    public func allSyntaxTrees(for string: String) throws -> [ParseTree]

    Parameters

    string

    Input word, for which all parse trees should be generated

    Return Value

    All syntax trees which explain how the input was derived from the recognized grammar