Formal Grammars

Formal Grammars#

from numpy.random import choice

Using dictionaries#

One simple and intuitive way of implementing a grammar in python is as a dictionary:

The keys are the left hand side rules
The values are lists containing the possible strings that can be substituted by the key

NOTE: To see why we need to use lists as values rather than using a different key for each rule, try to repeat the same key more than once. What happens?

For instance, let’s write the grammar with the following rules: $$ S \rightarrow aS | bS | \epsilon $$

grammar = {
    'S': [
        'aS', 
        'bS', 
        ''
    ]
}

One thing we can do with this way of defining grammars is writing a function that randomly applies rule until we get to a string consisting only of terminals:

# always start with the starting symbol
current_sentence = 'S'
# while there is a non-terminal in the sentence
while 'S' in current_sentence:
    # substitute the first occurrence of S
    # with a randomly chosen substitution rule
    current_sentence = current_sentence.replace(
        'S', 
        choice((grammar['S'])),
        # NOTE: in this particular case there will always
        # only be one S, but this is not true for 
        # all grammars!
        1
    )
print('String: ', current_sentence)

String:  abaaa

Write a function that takes a grammar, a set of terminals, and a set of nonterminals, and determines where the grammar is in the Chomsky hierarchy (Spend about 20 minutes on this - if you see that you can do it, leave it!):

# Your function here

A new piece of python syntax: generators#

Before we move onto defining classes to model grammars, which allow richer structures than dictionaries, we need to briefly talk about generators. A generator is basically a function with a memory, which can return multiple things in succession. Suppose you have a generator called gen. A typical use case is to use it in a construction like for i in gen():, where i will take on in succession the values returned by the generator.

The definition is almost like a function, except generators have the keyword yield where functions have return, and the execution doesn’t stop at the return but can continue as long as future yield are possible.

The simple example is a generator that first yields (returns) 1 and then 2:

def simple_generator():
    # when getting things out of a generator,
    # the generator will return in the order
    # the yield statements are encountered
    
    # This is encountered first
    yield 1
    # Then this is encountered
    yield 2
    
for i in simple_generator():
    print(i)

1
2

A slightly more complex generator simply counts the odd integers starting with 1:

def odd_counter():
    i = 0
    while True:
        yield i*2+1
        i += 1

for i in odd_counter():
    if i <= 20:
        print(i, end=', ')
    else:
        break

1, 3, 5, 7, 9, 11, 13, 15, 17, 19,

Note that generators can also call themselves, like functions. Then we get recursive generators:

# Can you figure out what this generator does?
def recursive_gen(current_options, n):
    new_options = []
    for i in current_options:
        if sum(i) == n:
            yield i
        else:
            new_options.append(i+[1])
            new_options.append(i+[2])
    if all([sum(j)>n for j in new_options]):
        return 
    for i in recursive_gen(new_options, n):
        yield i

for i in recursive_gen([[1],[2],[3]], 6):
    print(i)

[2, 2, 2]
[3, 1, 2]
[3, 2, 1]
[1, 1, 2, 2]
[1, 2, 1, 2]
[1, 2, 2, 1]
[2, 1, 1, 2]
[2, 1, 2, 1]
[2, 2, 1, 1]
[3, 1, 1, 1]
[1, 1, 1, 1, 2]
[1, 1, 1, 2, 1]
[1, 1, 2, 1, 1]
[1, 2, 1, 1, 1]
[2, 1, 1, 1, 1]

Try to write the recursive_gen just as a normal function with return statements.

# Your code here!

Using classes#

NOTE: Before you work on the exercise in ‘Defining a grammar class’ please have a look at the rest of the notebook. This should give you an idea of what you need to do with that class, and therefore how to structure them internally.

Defining a grammars class#

Write a Grammar class to create context-free grammars. The __init__ method should take a start argument with the starting nonterminal symbol.

The class should also have the following method (i.e., function):

add_rule: add a rule to the grammar. The arguments of add_rule are:
1. The nonterminal on the left-hand side of the rule
2. The string on the right side of the rule, containing %s wherever a non-terminal appears
3. A list of non-terminal symbols, one for each %s, saying which non-terminals correspond to each %s.

#### your class definition here!

Once this is defined, you should be able to run the following code to define the grammar for palindrome which we discussed in class:

grammar = Grammar(start='S')

grammar.add_rule('S', 'a%sa', ['S'])
grammar.add_rule('S', 'b%sb', ['S'])
grammar.add_rule('S', '')

#### Define the palindrome grammar here!

Finding minimal formulas (more difficult!)#

Now add another method compute_first to the class above which generates the n shortest strings in the language.

You should be able to run for instance (given the palindrome grammar above):

grammar.compute_first(6)

Which should print out:

aa
bb
aaaa
abba
baab
bbbb

HINT: Think about this as exploring a tree (branches separating whenever more than one rule can be applied), and use the power of recursion to explore the tree. The recursive function can take a ‘present’ layer (the strings at the current nesting level) and progressively build the next layer by applying every rule to every sentence with nonterminals in the current layer, while yielding the sentences that only contain terminals. Then, yield the results of running the function on the next layer in a loop.

#### Test compute_first here!

def enumerate_palindromes(layer):
    # your function here


def compute_first(n):
    for i, m in enumerate(enumerate_palindromes(['S'])):
        if i <= n:
            print(m)
        else:
            break

compute_first(4)

aa
bb
aaaa
abba

Probabilistic context-free grammar#

Expand the Grammar class once more so that add_rule takes one more argument: The (unnormalized) probability of applying the rule rather than the other rules with the same left-hand side.

The following code for instance redefines the palindrome grammar above but with probabilities:

grammar = Grammar(start='S')

grammar.add_rule('S', 'a%sa', ['S'], 1)
grammar.add_rule('S', 'b%sb', ['S'], 1)
grammar.add_rule('S', '', 1)

#### your class definition here!

Add a method generate to Grammar to generate a random string in the language by iteratively applying the rules according to the defined probabilities. The following code should run (but possibly give a different answer on different runs):

grammar.generate()

printing e.g.,

aabbaa

#### Test generate here!

What happens when we increase…

the probability of the rule $S \rightarrow aSa$?
the probability of the rule $S \rightarrow bSb$?
the probability of the rule $S \rightarrow \epsilon$?