cfpq_data.grammars.converters.cfg#

Create a context-free grammar from different formats.

Functions

cfg_from_cnf(cnf)

Create a context-free grammar [2] from given context-free grammar in Chomsky normal form [1].

cfg_from_regex(regex, *[, start_symbol])

Create a context-free grammar [1] from given regular expression [2].

cfg_from_rsa(rsa)

Create a context-free grammar [1] from given Recursive State Automaton [2].

cfg_from_cnf(cnf: CFG) CFG[source]#

Create a context-free grammar [2] from given context-free grammar in Chomsky normal form [1].

Parameters:

cnf (CFG) -- Context free grammar in Chomsky normal form.

Examples

>>> from cfpq_data import *
>>> gr = cnf_from_text("S -> a b")
>>> cfg = cfg_from_cnf(gr)
>>> cfg_to_text(cfg)
'S -> a#CNF# b#CNF#\na#CNF# -> a\nb#CNF# -> b'
Returns:

cfg -- Context-free grammar.

Return type:

CFG

References

cfg_from_regex(regex: Regex, *, start_symbol: Variable = Variable(S)) CFG[source]#

Create a context-free grammar [1] from given regular expression [2].

Parameters:
  • regex (Regex) -- Regular expression.

  • start_symbol (string) -- Start symbol of a context-free grammar.

Examples

>>> from cfpq_data import *
>>> expr = regex_from_text("a*")
>>> cfg = cfg_from_regex(expr)
>>> cfg_to_text(cfg)
'S -> \nS -> A0\nS -> S S\nA0 -> a'
Returns:

cfg -- Context-free grammar.

Return type:

CFG

References

cfg_from_rsa(rsa: RecursiveAutomaton) CFG[source]#

Create a context-free grammar [1] from given Recursive State Automaton [2].

Parameters:

rsa (RSA) -- Recursive State Automaton.

Examples

>>> from cfpq_data import *
>>> gr = rsa_from_text("S -> (a | b)*")
>>> cfg = cfg_from_rsa(gr)
>>> cfg_to_text(cfg)
'S -> \nS -> a S\nS -> b S'
Returns:

cfg -- Context-free grammar.

Return type:

CFG

References

[2] (1,2)

Alur R., Etessami K., Yannakakis M. (2001) Analysis of Recursive State Machines. In: Berry G., Comon H., Finkel A. (eds) Computer Aided Verification. CAV 2001. Lecture Notes in Computer Science, vol 2102. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44585-4_18