CYKParser

public struct CYKParser : AmbiguousGrammarParser

A parser based on the CYK algorithm.

The parser can parse non-deterministic and deterministic grammars. It requires O(n^3) runtime.

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 should be used instead, as it has linear or quadratic runtime.

The original CYK parsing can only recognize grammars in Chomsky normal form. This parser automatically transforms the recognized grammar into Chomsky normal form and transforms the parse tree back to the original grammar. Nullable items are ommited in the parse tree of the CYK parser.

  • The grammar which the parser recognizes

    Declaration

    Swift

    public let grammar: Grammar

  • Initializes a CYK parser which recognizes the given grammar.

    The parser can parse non-deterministic and deterministic context free languages in O(n^3).

    Declaration

    Swift

    public init(grammar: Grammar)

    Parameters

    grammar

    The grammar which the parser recognizes.

  • 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