Grammar

public struct Grammar
extension Grammar: CustomStringConvertible
extension Grammar: Equatable
extension Grammar: Codable

A context free or regular grammar consisting of a set of productions

In context free grammars, the left side of productions (in this framework also referred to as pattern) is always a single non-terminal.

Grammars might be ambiguous. For example, the grammar

<expr> ::= <expr> '+' <expr> | 'a'

can recognize the expression a+a+a+a in 5 different ways: ((a+a)+a)+a, (a+(a+a))+a, a+(a+(a+a)), a+((a+a)+a), (a+a)+(a+a).

  • Productions for generating words of the language generated by this grammar

    Declaration

    Swift

    public var productions: [Production]

  • Root non-terminal

    All syntax trees of words in this grammar must have a root containing this non-terminal.

    Declaration

    Swift

    public var start: NonTerminal

  • Creates a new grammar with a given set of productions and a start non-terminal

    Declaration

    Swift

    public init(productions: [Production], start: NonTerminal)

    Parameters

    productions

    Productions for generating words
    start

    Root non-terminal

  • Creates a grammar from the production rules defined in the provided ABNF grammar.

    Throws

    Syntax error if the abnf string is not in ABNF format. ABNFImportError, when the grammar has semantic issues.

    Declaration

    Swift

    init(abnf: String, start: String) throws

    Parameters

    abnf

    ABNF grammar
    start

    Starting symbol

  • Creates a new grammar from a specification in Backus-Naur Form (BNF)

    <pattern1> ::= <alternative1> | <alternative2>
<pattern2> ::= 'con' 'catenation'

    Declaration

    Swift

    init(bnf bnfString: String, start: String) throws

    Parameters

    bnf

    String describing the grammar in BNF
    start

    Start non-terminal

  • Creates a new grammar from a specification in Extended Backus-Naur Form (EBNF)

    pattern1 = alternative1 | alternative2;
pattern2 = 'con', 'catenation';

    Declaration

    Swift

    init(ebnf ebnfString: String, start: String) throws

    Parameters

    bnfString

    String describing the grammar in EBNF
    start

    Start non-terminal
  • bnf

    Returns a Backus-Naur form representation of the grammar.

    Production rules are encoded in the following form: pattern ::= production-result, where the pattern is always a single non-terminal and the production-result is a list of alternative results separated by | (or just one single result). The production result is a concatenation of terminal and non-terminal symbols. Terminals are delimited by single or double quotation marks; non-terminals are delimited by angle brackets (<, >). Concatenations consist of one or multiple symbols separated by zero or more whitespace characters.

    Example:

    <non-terminal-pattern> ::= <produced-non-terminal-pattern> | 'terminal' <concatenated-non-terminal>

    Declaration

    Swift

    public var bnf: String { get }

  • Returns a Extended Backus-Naur form representation of the grammar.

    Production rules are encoded in the following form: pattern = production-result;, where the pattern is always a single non-terminal and the production-result is a list of alternative results separated by | (or just one single result). The production result is a concatenation of terminal and non-terminal symbols. Terminals are delimited by single or double quotation marks; non-terminals are not delimited by a special character. Concatenations consist of one or multiple symbols separated by a comma.

    Example:

    non-terminal pattern = produced non-terminal | 'terminal', concatenated non-terminal;

    Declaration

    Swift

    public var ebnf: String { get }

  • Returns a Augmented Backus-Naur form representation of the grammar.

    Production rules are encoded in the following form: pattern = production-result, where the pattern is always a single non-terminal and the production-result is a list of alternative results separated by / (or just one single result). The production result is a concatenation of terminal and non-terminal symbols.

    Example:

       non-terminal-pattern = produced non-terminal / "terminal" concatenated non-terminal;

    Declaration

    Swift

    public var abnf: String { get }

  • Declaration

    Swift

    public var description: String { get }

  • Returns true, if the grammar is in chomsky normal form.

    A grammar is in chomsky normal form if all productions satisfy one of the following conditions:

    • A production generates exactly one terminal symbol
    • A production generates exactly two non-terminal symbols
    • A production generates an empty string and is generated from the start non-terminal

    Certain parsing algorithms, such as the CYK parser, require the recognized grammar to be in Chomsky normal form.

    Declaration

    Swift

    var isInChomskyNormalForm: Bool { get }

  • Declaration

    Swift

    public static func == (lhs: Grammar, rhs: Grammar) -> Bool

  • Non-terminals which cannot be reached from the start non-terminal

    Declaration

    Swift

    var unreachableNonTerminals: Set<NonTerminal> { get }

  • Nonterminals which can never produce a sequence of terminals because of infinite recursion.

    Declaration

    Swift

    var unterminatedNonTerminals: Set<NonTerminal> { get }

  • Generates a context free grammar equal to the current grammar which is in Chomsky Normal Form. The grammar is converted by decomposing non-terminal productions of lengths greater than 2, introducing new non-terminals to replace terminals in mixed productions, and removing empty productions.

    Chomsky normal form is required for some parsers (like the CYK parser) to work.

    In chomsky normal form, all productions must have the following form:

    A -> B C
D -> x
Start -> empty

    Note that empty productions are only allowed starting from the start non-terminal

    Declaration

    Swift

    public func chomskyNormalized() -> Grammar

    Return Value

    Chomsky normal form of the current grammar

  • Generates a grammar which recognizes all prefixes of the original grammar.

    For example if a grammar would generate a*(b+c), the prefix grammar would generate the empty string, a, a*, a*(, a*(b a*(b+ a*(b+c and a*(b+c)

    Declaration

    Swift

    func prefixGrammar() -> Grammar

    Return Value

    A grammar generating all prefixes of the original grammar