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:

• types (List[Tuple[str, str]]) -- List of pairs \((op_i, cp_i)\) with opening and closing parentheses for each type.

• eps (bool) -- Whether the empty string belongs to the language generated by the grammar.

• start_symbol (Variable) -- Start symbol of the grammar.

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'

Returns:

cfg -- A Dyck context-free grammar.

Return type:

CFG

References

[1]

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