cfpq_data.grammars.readwrite.cnf_template#

Read (and write) grammar templates in the .cnf format of the new-format graph archives, and materialize them over a concrete graph.

Functions

`cnf_template_from_cnf`(path)	Create a grammar template from a `.cnf` file.
`cnf_template_from_text`(text)	Create a grammar template from `.cnf` format text.
`cnf_template_to_cnf`(cfg, path)	Saves a grammar template to a `.cnf` file by `path`.
`cnf_template_to_text`(cfg)	Turns a grammar template into its `.cnf` format text representation.
`materialize`(cfg, graph)	Materialize a grammar template over the edge labels of a graph.
`materialize_grammar`(cnf_path, graph)	Load a `.cnf` grammar template and materialize it over a graph.

cnf_template_from_cnf(path: Path | str) → CFG[source]#

Create a grammar template from a .cnf file.

Parameters:

pathUnion[Path, str]: The path to the .cnf file with which the grammar template will be created.

Returns:

cfgCFG: Grammar template.

Examples

>>> from cfpq_data import *
>>> import pathlib, tempfile
>>> p = pathlib.Path(tempfile.mkdtemp()) / "g.cnf"
>>> _ = p.write_text("S\ta\tN1\nN1\tS\tb\n\nCount:\nS")
>>> cfg = cnf_template_from_cnf(p)
>>> len(cfg.productions)
2

cnf_template_from_text(text: str) → CFG[source]#

Create a grammar template from .cnf format text.

The template is a context-free grammar whose left-hand-side symbols are the non-terminals and all other symbols (including the indexed placeholder symbols such as load_i or load_r) are terminals; the start symbol is given by the Count: trailer.

Parameters:

textstr: The text with which the grammar template will be created.

Returns:

cfgCFG: Grammar template.

Examples

>>> from cfpq_data import *
>>> cfg = cnf_template_from_text("S\ta\tN1\nN1\tS\tb\n\nCount:\nS")
>>> cfg.start_symbol.value
'S'
>>> len(cfg.productions)
2

cnf_template_to_cnf(cfg: CFG, path: Path | str) → Path[source]#

Saves a grammar template to a .cnf file by path.

Parameters:

cfgCFG: Grammar template to save.
pathUnion[Path, str]: The path to the .cnf file where the grammar template will be saved.

Returns:

pathPath: The path to the .cnf file where the grammar template will be saved.

Examples

>>> from cfpq_data import *
>>> import pathlib, tempfile
>>> cfg = cnf_template_from_text("S\ta\tN1\nN1\tS\tb\n\nCount:\nS")
>>> p = pathlib.Path(tempfile.mkdtemp()) / "g.cnf"
>>> path = cnf_template_to_cnf(cfg, p)
>>> cnf_template_from_cnf(path).start_symbol.value
'S'

cnf_template_to_text(cfg: CFG) → str[source]#

Turns a grammar template into its .cnf format text representation.

One production per line, symbols separated by tabs (an epsilon production is a bare non-terminal), sorted by the left-hand side and then the right-hand side; the last two lines are Count: and the start symbol.

Parameters:

cfgCFG: Grammar template to convert.

Returns:

textstr: Grammar template text representation.

Examples

>>> from cfpq_data import *
>>> cfg = cnf_template_from_text("S\ta\tN1\nN1\tS\tb\n\nCount:\nS")
>>> cnf_template_to_text(cfg)
'N1\tS\tb\nS\ta\tN1\n\nCount:\nS'

materialize(cfg: CFG, graph: MultiDiGraph) → CFG[source]#

Materialize a grammar template over the edge labels of a graph.

Returns a context-free grammar whose terminals are the concrete edge labels: an indexed symbol is expanded per index present in the graph (the _i placeholder style, e.g. load_i -> load_5, and the bare style, e.g. load -> load_5 and load_r -> load_5_r), and a symbol with no matching label is kept as an inert terminal. Reversed labels (the _r suffix) resolve to the stored labels or to the labels derived by reversing the respective forward edges (see cfpq_data.graphs.utils.add_reverse_edges()); the returned grammar does not add the reversed edges to the graph itself.

Parameters:

cfgCFG: Grammar template (e.g. from cnf_template_from_cnf()).
graphMultiDiGraph: The graph whose edge labels (the label edge attribute) the template is materialized over.

Returns:

cfgCFG: Materialized context-free grammar.

Examples

>>> from cfpq_data import *
>>> g = nx.MultiDiGraph()
>>> _ = g.add_edges_from(
...     [(0, 1, {"label": "load_0"}), (1, 2, {"label": "store_0"}),
...      (0, 2, {"label": "alloc"}), (2, 3, {"label": "assign"})]
... )
>>> template = cnf_template_from_text(
...     "PT\tPTh\talloc\nPTh\tassign\nPTh\tload\tAl_st_PTh\n"
...     "Al_st_PTh\tAl\tst_PTh\nst_PTh\tstore\tPTh\nAl\tPT\n\nCount:\nPT"
... )
>>> cfg = materialize(template, g)
>>> sorted(symbol.value for symbol in cfg.terminals)
['alloc', 'assign', 'load_0', 'store_0']

materialize_grammar(cnf_path: Path | str, graph: MultiDiGraph) → CFG[source]#

Load a .cnf grammar template and materialize it over a graph.

A convenience wrapper over cnf_template_from_cnf() + materialize(): expands indexed symbols (e.g. load_i -> load_0, load_1, …) into explicit productions for each index present in the graph edge labels. Non-indexed grammars pass through unchanged.

Parameters:

cnf_pathUnion[Path, str]: Path to the .cnf grammar template file.
graphMultiDiGraph: The graph whose edge labels determine which indices are instantiated.

Returns:

cfgCFG: The explicitly-instantiated context-free grammar.

Examples

>>> from cfpq_data import *
>>> g = nx.MultiDiGraph()
>>> _ = g.add_edges_from(
...     [(0, 1, {"label": "load_0"}), (1, 2, {"label": "store_0"}),
...      (0, 3, {"label": "load_1"}), (3, 2, {"label": "store_1"}),
...      (0, 4, {"label": "alloc"})]
... )
>>> import pathlib, tempfile
>>> p = pathlib.Path(tempfile.mkdtemp()) / "g.cnf"
>>> _ = p.write_text(
...     "PT\tPTh\talloc\nPTh\tassign\n"
...     "PTh\tload_i\tAl_st_PTh_i\nAl_st_PTh_i\tAl\tst_PTh_i\n"
...     "st_PTh_i\tstore_i\tPTh\nAl\tPT\n\nCount:\nPT"
... )
>>> cfg = materialize_grammar(p, g)
>>> sorted(s.value for s in cfg.terminals)
['alloc', 'assign', 'load_0', 'load_1', 'store_0', 'store_1']