Skip to content

Expression Generator Module

SRToolkit.utils.expression_generator

This module contains helper functions for creating a PCFG with generic probabilities from the SymbolLibrary and to use it for generating random expressions.

create_generic_pcfg(symbol_library)

Creates a generic PCFG from the SymbolLibrary.

Examples:

>>> sl = SymbolLibrary.from_symbol_list(["+", "-", "*", "sin", "^2", "pi"], 2)
>>> print(create_generic_pcfg(sl))
E -> E '+' F [0.2]
E -> E '-' F [0.2]
E -> F [0.6]
F -> F '*' B [0.4]
F -> B [0.6]
B -> T [1.0]
T -> R [0.2]
T -> C [0.2]
T -> V [0.6]
C -> 'pi' [1.0]
R -> 'sin' '(' E ')' [0.4]
R -> P [0.15]
R -> '(' E ')' [0.45]
P -> '(' E ')' '^2' [1.0]
V -> 'X_0' [0.5]
V -> 'X_1' [0.5]

Parameters:

Name Type Description Default
symbol_library SymbolLibrary

The symbol library to use. Defaults to SymbolLibrary.default_symbols().

 required

Returns:

Type Description
str

A PCFG with generic probabilities, written as a string.
Source code in SRToolkit/utils/expression_generator.py 
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
def create_generic_pcfg(symbol_library: SymbolLibrary) -> str:
    """
    Creates a generic PCFG from the SymbolLibrary.

    Examples:
        >>> sl = SymbolLibrary.from_symbol_list(["+", "-", "*", "sin", "^2", "pi"], 2)
        >>> print(create_generic_pcfg(sl))
        E -> E '+' F [0.2]
        E -> E '-' F [0.2]
        E -> F [0.6]
        F -> F '*' B [0.4]
        F -> B [0.6]
        B -> T [1.0]
        T -> R [0.2]
        T -> C [0.2]
        T -> V [0.6]
        C -> 'pi' [1.0]
        R -> 'sin' '(' E ')' [0.4]
        R -> P [0.15]
        R -> '(' E ')' [0.45]
        P -> '(' E ')' '^2' [1.0]
        V -> 'X_0' [0.5]
        V -> 'X_1' [0.5]
        <BLANKLINE>

    Args:
        symbol_library: The symbol library to use. Defaults to SymbolLibrary.default_symbols().

    Returns:
        A PCFG with generic probabilities, written as a string.
    """
    symbols = symbol_library.symbols.values()
    E = [s["symbol"] for s in symbols if s["type"]=="op" and s["precedence"]==0]
    F = [s["symbol"] for s in symbols if s["type"]=="op" and s["precedence"]==1]
    BP = [s["symbol"] for s in symbols if s["type"]=="op" and s["precedence"]==2]
    R = [s["symbol"] for s in symbols if s["type"]=="fn" and s["precedence"]==5]
    P = [s["symbol"] for s in symbols if s["type"]=="fn" and s["precedence"]==-1]
    V = [s["symbol"] for s in symbols if s["type"]=="var"]
    Cc = [s["symbol"] for s in symbols if s["type"]=="const"]
    Cl = [s["symbol"] for s in symbols if s["type"]=="lit"]

    grammar = ""
    if len(E) > 0:
        for s in E:
            grammar += f"E -> E '{s}' F [{0.4/len(E)}]\n"
        grammar += "E -> F [0.6]\n"
    else:
        grammar += "E -> F [1.0]\n"

    if len(F) > 0:
        for s in F:
            grammar += f"F -> F '{s}' B [{0.4/len(F)}]\n"
        grammar += "F -> B [0.6]\n"
    else:
        grammar += "F -> B [1.0]\n"

    if len(BP) > 0:
        for s in BP:
            grammar += f"B -> B '{s}' T [{0.05/len(BP)}]\n"
        grammar += "B -> T [0.95]\n"
    else:
        grammar += "B -> T [1.0]\n"

    if len(Cc) + len(Cl) > 0:
        grammar += "T -> R [0.2]\n"
        grammar += "T -> C [0.2]\n"
        grammar += "T -> V [0.6]\n"
        if len(Cl) > 0 and len(Cc) > 0:
            for s in Cl:
                grammar += f"C -> '{s}' [{0.2/len(Cl)}]\n"
            for s in Cc:
                grammar += f"C -> '{s}' [{0.8/len(Cc)}]\n"
        elif len(Cl) > 0:
            for s in Cl:
                grammar += f"C -> '{s}' [{1/len(Cl)}]\n"
        elif len(Cc) > 0:
            for s in Cc:
                grammar += f"C -> '{s}' [{1/len(Cc)}]\n"
    else:
        grammar += "T -> R [0.3]\n"
        grammar += "T -> V [0.7]\n"

    if len(R) > 0:
        for s in R:
            grammar += f"R -> '{s}' '(' E ')' [{0.4/len(R)}]\n"
        if len(P) > 0:
            grammar += "R -> P [0.15]\n"
            grammar += "R -> '(' E ')' [0.45]\n"
        else:
            grammar += "R -> '(' E ')' [0.6]\n"
    else:
        if len(P) > 0:
            grammar += "R -> P [0.15]\n"
            grammar += "R -> '(' E ')' [0.85]\n"
        else:
            grammar += "R -> '(' E ')' [1.0]\n"

    if len(P) > 0:
        total = sum([1/abs(float(s[1:])) for s in P])
        for s in P:
            grammar += f"P -> '(' E ')' '{s}' [{(1/abs(float(s[1:])))/total}]\n"

    if len(V) > 0:
        for s in V:
            grammar += f"V -> '{s}' [{1/len(V)}]\n"

    return grammar

generate_from_pcfg(grammar_str, start_symbol='E', max_depth=40, limit=100)

Generates a random expression from a PCFG with monte-carlo sampling.

Examples:

>>> generate_from_pcfg("E -> '1' [1.0]")
['1']
>>> grammar = create_generic_pcfg(SymbolLibrary.default_symbols())
>>> len(generate_from_pcfg(grammar)) > 0
True

Parameters:

Name Type Description Default
grammar_str str

Grammar given as a string in the NLTK notation

 required
start_symbol

Non-terminal symbol used as the starting point

 'E'
max_depth

Maximum depth of the generated parse trees. If less than 0, expressions can have arbitrary depth

 40
limit

Number of times the function tries to generate a valid expression before raising an Exception.

 100

Raises:

Type Description
Exception

If the maximum number of tries is reached without generating a valid expression

Returns:

Type Description
List[str]

An expression written as a list of string tokens in the infix notation.
Source code in SRToolkit/utils/expression_generator.py 
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
def generate_from_pcfg(grammar_str: str, start_symbol="E", max_depth=40, limit=100) -> List[str]:
    """
    Generates a random expression from a PCFG with monte-carlo sampling.

    Examples:
        >>> generate_from_pcfg("E -> '1' [1.0]")
        ['1']
        >>> grammar = create_generic_pcfg(SymbolLibrary.default_symbols())
        >>> len(generate_from_pcfg(grammar)) > 0
        True

    Args:
        grammar_str: Grammar given as a string in the NLTK notation
        start_symbol: Non-terminal symbol used as the starting point
        max_depth: Maximum depth of the generated parse trees. If less than 0, expressions can have arbitrary depth
        limit: Number of times the function tries to generate a valid expression before raising an Exception.

    Raises:
        Exception: If the maximum number of tries is reached without generating a valid expression

    Returns:
        An expression written as a list of string tokens in the infix notation.
    """
    start_symbol = nltk.grammar.Nonterminal(start_symbol)
    grammar = nltk.PCFG.fromstring(grammar_str)
    expr = _expand(grammar, start_symbol, 0, max_depth)
    tries = 1
    while expr is None and tries < limit:
        expr = _expand(grammar, start_symbol, 0, max_depth)

    if expr is None:
        raise Exception(f"[Expression generation] Couldn't find an expression with max_depth {max_depth} from this grammar in {limit} tries.")

    return expr

generate_n_expressions(expression_description, num_expressions, unique=True, max_expression_length=50, verbose=False)

Generates a set of n expressions.

Examples:

>>> len(generate_n_expressions(SymbolLibrary.default_symbols(5), 100, verbose=False))
100
>>> generate_n_expressions(SymbolLibrary.from_symbol_list([], 1), 3, unique=False, verbose=False, max_expression_length=1)
[['X_0'], ['X_0'], ['X_0']]

Parameters:

Name Type Description Default
expression_description Union[str, SymbolLibrary]

Decription of expressions, given as either a grammar in the NLTK notation or a SymbolLibrary instance

 required
num_expressions int

Number of generated expressions

 required
unique

When True, each generated expression will be unique (not necesarily unequivalent to others)

 True
max_expression_length

Generated expressions will have at most "max_expression_length" tokens. If less than 0, expressions can be of arbitrary size.

 50
verbose

If True, adds a progress bar

 False

Returns:

Type Description
List[List[str]]

A list of expressions represented as lists of tokens
Source code in SRToolkit/utils/expression_generator.py 
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
def generate_n_expressions(expression_description: Union[str, SymbolLibrary], num_expressions: int, unique=True,
                            max_expression_length=50, verbose=False) -> List[List[str]]:
    """
    Generates a set of n expressions.

    Examples:
        >>> len(generate_n_expressions(SymbolLibrary.default_symbols(5), 100, verbose=False))
        100
        >>> generate_n_expressions(SymbolLibrary.from_symbol_list([], 1), 3, unique=False, verbose=False, max_expression_length=1)
        [['X_0'], ['X_0'], ['X_0']]

    Args:
        expression_description: Decription of expressions, given as either a grammar in the NLTK notation or a SymbolLibrary instance
        num_expressions: Number of generated expressions
        unique: When True, each generated expression will be unique (not necesarily unequivalent to others)
        max_expression_length: Generated expressions will have at most "max_expression_length" tokens. If less than 0, expressions can be of arbitrary size.
        verbose: If True, adds a progress bar

    Returns:
        A list of expressions represented as lists of tokens
    """
    if isinstance(expression_description, SymbolLibrary):
        grammar = create_generic_pcfg(expression_description)
    elif isinstance(expression_description, str):
        grammar = expression_description
    else:
        raise Exception("Description of expressions must be either a grammar written as a string or an instance of SymbolLibrary.")

    expressions = []
    expression_strings = set()
    if verbose:
        pbar = tqdm(total=num_expressions)
    while len(expressions) < num_expressions:
        try:
            expr = generate_from_pcfg(grammar, max_depth=max_expression_length*10)
        except:
            print("Couldn't generate a valid expression in 100 tries")
            continue
        if len(expr) > max_expression_length > 0:
            continue

        expr_string = "".join(expr)
        if expr_string not in expression_strings or not unique:
            expressions.append(expr)
            expression_strings.add(expr_string)
            if verbose:
                pbar.update(1)

    if verbose:
        pbar.close()
    return expressions