cfpq_data.grammars.generators.dyck_grammar

dyck_grammar(types: List[Tuple[str, str]], *, eps: bool = True, start_symbol: Variable = Variable(S)) → CFG

Returns a Dyck grammar that generates a Dyck language [1] of the balanced strings with parentheses of given types.

Parameters:

typesList[Tuple[str, str]]

List of pairs \((op_i, cp_i)\) with opening and closing parentheses for each type.

epsbool

Whether the empty string belongs to the language generated by the grammar.

start_symbolVariable

Start symbol of the grammar.

Returns:

cfgCFG

A Dyck context-free grammar.

References

[1]

https://en.wikipedia.org/wiki/Dyck_language

Examples

>>> from cfpq_data import *
>>> cfg = dyck_grammar([("a", "b"), ("c", "d")])
>>> cfg_to_text(cfg)
'S -> \nS -> a S b S\nS -> c S d S'