Source code for flpq_data.queries.cfpq.generators.c_alias_grammar

"""Returns a C Alias grammar that generates a language for the
flow-insensitive alias analysis of C programs."""

import logging
from typing import Tuple

from pyformlang.cfg import CFG, Variable

import flpq_data

__all__ = ["c_alias_grammar"]




def c_alias_grammar(
    *,
    assigment_labels: Tuple[str, str] = ("a", "a_r"),
    dereference_labels: Tuple[str, str] = ("d", "d_r"),
    start_symbol: Variable = Variable("S"),
) -> CFG:
    """Returns a C Alias grammar that generates a language for the
    flow-insensitive alias analysis of C programs [1]_.

    Parameters
    ----------
    assigment_labels : Tuple[str, str]
        Pair $(a, a_r)$ where label $a$ represents the assignment operation
        and $a_r$ is reverse to it.

    dereference_labels : Tuple[str, str]
        Pair $(d, d_r)$ where label $d$ represents pointer dereference
        relation and $d_r$ is reverse to it.

    start_symbol : Variable
        Start symbol of the grammar.

    Examples
    --------
    >>> from flpq_data import *
    >>> cfg = c_alias_grammar()
    >>> print(cfg_to_text(cfg))  # doctest: +NORMALIZE_WHITESPACE
    S -> d_r V d
    V -> V1 V2 V3
    V1 ->
    V1 -> V2 a_r V1
    V2 ->
    V2 -> S
    V3 ->
    V3 -> a V2 V3

    Returns
    -------
    cfg : CFG
        C Alias context-free grammar.

    References
    ----------
    .. [1] https://dl.acm.org/doi/10.1145/1328897.1328464
    """
    a, a_r = assigment_labels
    d, d_r = dereference_labels

    grammar_text = f"""{start_symbol.to_text()} -> {d_r} V {d}
    V -> V1 V2 V3
    V1 -> epsilon
    V1 -> V2 {a_r} V1
    V2 -> epsilon
    V2 -> S
    V3 -> epsilon
    V3 -> {a} V2 V3"""

    cfg = flpq_data.cfg_from_text(grammar_text)

    logging.info(
        f"Create a C Alias {cfg=} with {assigment_labels=}, {dereference_labels=}"
    )

    return cfg