Source code for cfpq_data.grammars.generators.nested_parentheses_grammar
"""Returns a Nested Parentheses grammar that generates a language of the strings with nested parentheses of different
types. """
import logging
from typing import List, Tuple
from pyformlang.cfg import CFG, Production, Variable, Terminal
__all__ = ["nested_parentheses_grammar"]
[docs]
def nested_parentheses_grammar(
types: List[Tuple[str, str]],
*,
eps: bool = True,
start_symbol: Variable = Variable("S"),
) -> CFG:
"""Returns a Nested Parentheses grammar that generates a language of the strings with nested 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 = nested_parentheses_grammar([("a", "b"), ("c", "d")])
>>> cfg_to_text(cfg)
'S -> \\nS -> a S b\\nS -> c S d'
Returns
-------
cfg : CFG
A Nested Parentheses context-free grammar.
"""
variables = {start_symbol}
productions = set()
terminals = set()
if eps:
productions.add(Production(start_symbol, []))
else:
for op, cp in types:
productions.add(Production(start_symbol, [Terminal(op), Terminal(cp)]))
for op, cp in types:
terminals.update([Terminal(op), Terminal(cp)])
productions.add(
Production(start_symbol, [Terminal(op), start_symbol, Terminal(cp)])
)
cfg = CFG(
variables=variables,
terminals=terminals,
productions=productions,
start_symbol=start_symbol,
)
logging.info(f"Create a Nested Parentheses {cfg=} with {types=}, {eps=}")
return cfg
