Practical: CYK Parsing¶
Working with Charts¶
Familiarise yourself with the following two types of charts that are useful for parsing CFGs.
In [1]:
from muprocdurham.pcfg import SetChart, DictSetChart, cat_pretty
from muprocdurham.jupyter import no_linebreaks
from muprocdurham import seed_everything
seed_everything(42)
no_linebreaks()
SetChart¶
A SetChart stores sets of elements/symbols in each cell. You can initialise and print it like this:
In [2]:
chart = SetChart(3)
print(chart.pretty(haxis=True))
╱╲
╱ ∅╲
╱╲ ╱╲
╱ ∅╲╱ ∅╲
╱╲ ╱╲ ╱╲
╱ ∅╲╱ ∅╲╱ ∅╲
│ │ │ │
0 1 2 3
You can access a cell via chart[start, end], where start and end are the index of the left and right boundary of the sub-chart ("triangle") of which the corresponding cell is the top. The following simply adds the (start, end) pairs to each cell to give you an overview of the indexing.
In [3]:
for start in range(chart.n):
for end in range(start + 1, chart.n + 1):
chart[start, end].add((start, end))
print(chart.pretty(haxis=True))
╱╲
╱ ╲
╱ ╲
╱ ╲
╱{(0, 3)}╲
╱╲ ╱╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱{(0, 2)}╲╱{(1, 3)}╲
╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱{(0, 1)}╲╱{(1, 2)}╲╱{(2, 3)}╲
│ │ │ │
0 1 2 3
Exercise: Add the symbol 'A' to the very top cell, the symbol 'B' to the center bottom cell, the symbol 'C' to the cell spanning from 1 to 3, and finally a second symbol 'D' to the very top cell.
Hint: chart[start, end] gives you access to the corresponding set in that cell, which you can then manipulate.
Your result should look as below.
In [4]:
chart = SetChart(3)
# vvvvvvvvvvvvvvvvvv
# Put your code here!
# ^^^^^^^^^^^^^^^^^^
print(chart.pretty(haxis=True))
╱╲
╱ ╲
╱ ╲
╱ {D,A}╲
╱╲ ╱╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ∅╲╱ {C}╲
╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ∅╲╱ {B}╲╱ ∅╲
│ │ │ │
0 1 2 3
Finally, to help with orientation, you can also print the level, which corresponds to the length of the span (the corresponding subsequence) associated to the cells.
In [5]:
print(chart.pretty(haxis=True, laxis=True))
╱╲ level
╱ ╲
╱ ╲
╱ {D,A}╲ 3
╱╲ ╱╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ∅╲╱ {C}╲ 2
╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ∅╲╱ {B}╲╱ ∅╲ 1
│ │ │ │
0 1 2 3
DictSetChart¶
A DictSetChart is similar to a SetChart, just that is stores a dictionary of sets in each cell. This means that you can store a set of values along with each of the symbols.
Exercise: In the top cell, add the values 1 and 2 to the symbol 'A' and the value 3 to the symbol 'B'.
Hint: chart[start, end] gives you access to a dict of sets in that cell, which you can then manipulate.
Your result should look as below.
In [6]:
chart = DictSetChart(2)
# vvvvvvvvvvvvvvvvvvvvv
# Put your code here!
# ^^^^^^^^^^^^^^^^^^^^^
print(chart.pretty())
╱╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ {A:{1,2},B:{3}}╲
╱╲ ╱╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ {}╲╱ {}╲
Minimal Example by Hand¶
- non-terminals:
{A, B} - terminals:
{a, b} - start symbol:
A - rules:
A --> A AA --> B AA --> aB --> b
Sequence to parse: a a b b a
In [7]:
chart = SetChart(5)
sequence = 'aabba'
# fill base level 1
chart[0, 1].add('A') # A --> a
chart[1, 2].add('A') # A --> a
chart[2, 3].add('B') # B --> b
chart[3, 4].add('B') # B --> b
chart[4, 5].add('A') # A --> a
# fill level 2
chart[0, 2].add('A') # A --> A A (split at 1)
chart[3, 5].add('A') # A --> B A (split at 4)
# fill level 3
chart[2, 5].add('A') # A --> B A (split at 3)
# fill level 4
chart[1, 5].add('A') # A --> A A (split at 2)
# fill level 5
chart[0, 5].add('A') # A --> A A (split at 1)
chart[0, 5].add('A') # A --> A A (split at 2)
print(chart.pretty(haxis=True, laxis=True))
print(' ' + ' '.join(sequence))
╱╲ level
╱ ╲
╱ {A}╲ 5
╱╲ ╱╲
╱ ╲ ╱ ╲
╱ ∅╲╱ {A}╲ 4
╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ∅╲╱ ∅╲╱ {A}╲ 3
╱╲ ╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ {A}╲╱ ∅╲╱ ∅╲╱ {A}╲ 2
╱╲ ╱╲ ╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ {A}╲╱ {A}╲╱ {B}╲╱ {B}╲╱ {A}╲ 1
│ │ │ │ │ │
0 1 2 3 4 5
a a b b a
CYK Parsing¶
Simple CYK Parser¶
We are now equipped for implementing a CYK parser for a context-free grammar (CFG). Below is a template class, which you can complete using the pseudocode from the lecture slides.
In [8]:
class CFG:
def __init__(self, non_terminal_rules, terminal_rules, start_symbol):
# store the non-terminal rules as triplets: A --> B C is stored as ('A', 'B', 'C')
self.non_terminal_rules = set(tuple(r) for r in non_terminal_rules)
# store the terminal rules as pairs: A --> a is stored as ('A', 'a')
self.terminal_rules = set(tuple(r) for r in terminal_rules)
# the start symbol
self.start_symbol = start_symbol
# the chart is initialised by the init_chart() function called by the parse() function
self.chart = None
# extracting the non-terminal and terminal symbols from the rules
self.non_terminal_symbols = set.union(*[{x1, x2, x3} for x1, x2, x3 in self.non_terminal_rules])
self.terminal_symbols = {y for x, y in self.terminal_rules}
# make sure the start symbol is in the set of non-terminal symbols
assert start_symbol in self.non_terminal_symbols, f"Start symbol '{start_symbol}' must be in non-terminals"
def init_chart(self, n):
# Override this function for using other chart types
self.chart = SetChart(n)
def parse(self, sequence):
n = len(sequence)
self.init_chart(n)
# fill bottom row using terminal rules
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
# Put your code here!
# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
# fill rows, bottom up, using non-terminal rules
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
# Put your code here!
# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
# return whether the sequence is valid (i.e. whether the start symbol is in the top cell)
return self.start_symbol in self.chart[0, n]
def fill_terminal_cell(self, start, symbol):
# go through all terminal rules to fill cell
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
# Put your code here!
# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
def fill_non_terminal_cell(self, start, split, end):
# go through all non-terminal rules to fill cell
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
# Put your code here!
# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Test your implementation using the minimal example from the lecture.
In [9]:
cfg = CFG(
non_terminal_rules=[('A', 'A', 'A'), ('A', 'B', 'A')],
terminal_rules=[('A', 'a'), ('B', 'b')],
start_symbol='A'
)
print("non-terminal rules:", cfg.non_terminal_rules)
print("terminal rules:", cfg.terminal_rules)
print("start symbol:", cfg.start_symbol)
print("non-terminal symbols:", cfg.non_terminal_symbols)
print("terminal symbols:", cfg.terminal_symbols)
print("valid sequence:", cfg.parse("aabba"))
print(cfg.chart.pretty())
non-terminal rules: {('A', 'A', 'A'), ('A', 'B', 'A')}
terminal rules: {('A', 'a'), ('B', 'b')}
start symbol: A
non-terminal symbols: {'B', 'A'}
terminal symbols: {'a', 'b'}
valid sequence: True
╱╲
╱ ╲
╱ {A}╲
╱╲ ╱╲
╱ ╲ ╱ ╲
╱ ∅╲╱ {A}╲
╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ∅╲╱ ∅╲╱ {A}╲
╱╲ ╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ {A}╲╱ ∅╲╱ ∅╲╱ {A}╲
╱╲ ╱╲ ╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ {A}╲╱ {A}╲╱ {B}╲╱ {B}╲╱ {A}╲
Getting Parse Trees¶
We can now extend our implementation to also remember splitting points, so we can later reconstruct all possible parse trees.
Exercise: Override the fill_terminal_cell and fill_non_terminal_cell functions to remember possible splitting points for each symbol.
Hint: You can call chart[start, end][x] to add symbol x to a cell but leave the set of splitting points empty (e.g. for level 1 at the bottom of the chart).
Exercise (HARD): Implement a get_trees method that uses the stored splitting points to compute all possible parse trees.
Hints:
- If two trees have the same shape but different symbols in their inner nodes, they correspond to different parse trees.
- You can represent a tree with a
SetChartthat only contains the symbols that appear in the tree. - Start from the top and construct trees recursively (for any possible split, any combination of a right sub-tree and a left sub-tree is a valid tree).
In [10]:
class TreeCFG(CFG):
def init_chart(self, n):
# chart stores dicts from symbols to sets of possible splitting points
self.chart = DictSetChart(n)
def fill_terminal_cell(self, start, symbol):
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
# Put your code here!
# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
def fill_non_terminal_cell(self, start, split, end):
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
# Put your code here!
# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
def get_trees(self, symbol=None, start=None, end=None, chart=None, draw_tree=True):
trees = [] # list of all possible trees represented in charts
n = self.chart.n
if (symbol, start, end, chart) == (None, None, None, None):
(symbol, start, end, chart) = (self.start_symbol, 0, n, SetChart(n, empty="", left="", right=""))
# handle terminal transitions
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
# Put your code here!
# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
# go through all possible splitting points and the associated symbols
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
# Put your code here!
# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
return trees
Test your implementation again on the (slightly extended) minimal example.
In [11]:
cfg = TreeCFG(
non_terminal_rules=[
('A', 'A', 'A'),
('C', 'C', 'C'),
('A', 'C', 'C'),
('C', 'A', 'A'),
('A', 'B', 'A'),
('C', 'B', 'A')
],
terminal_rules=[
('A', 'a'),
('B', 'b'),
],
start_symbol='A'
)
print("valid sequence:", cfg.parse("aabba"))
print(cfg.chart.pretty())
valid sequence: True
╱╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ {C:{('A', 'A', 1),('A', 'A', 2),('C', 'C', 2)},A:{('A', 'A', 1),('A', 'A', 2),('C', 'C', 2)}}╲
╱╲ ╱╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ {}╲╱ {C:{('A', 'A', 2)},A:{('A', 'A', 2)}}╲
╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ {}╲╱ {}╲╱ {A:{('B', 'A', 3)},C:{('B', 'A', 3)}}╲
╱╲ ╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ {C:{('A', 'A', 1)},A:{('A', 'A', 1)}}╲╱ {}╲╱ {}╲╱ {A:{('B', 'A', 4)},C:{('B', 'A', 4)}}╲
╱╲ ╱╲ ╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ {A:∅}╲╱ {A:∅}╲╱ {B:∅}╲╱ {B:∅}╲╱ {A:∅}╲
In [12]:
trees = cfg.get_trees()
print(f"There are {len(trees)} possible parse trees:")
print(cat_pretty(trees, crosses=True, grid_off=True))
There are 3 possible parse trees:
| |
A | A | A
╱ A | ╱ ╲ | ╱ ╲
╱ ╱ A | ╱ A | ╱ C
╱ ╱ ╱ A | A ╱ A | C ╱ A
A A B B A | A A B B A | A A B B A
Working with Data¶
Harmonic Annotations¶
The Annotated Beethoven Corpus (ABC) is a dataset with expert harmonic analyses of all Beethoven string quartets. The harmonic labels contain more information and a broader variety of chords than what was possible to cover in the lectures. The following code loads data from one of the files (change file_idx to change the file) and extracts the basic numeral annotations. As you can see, these are still somewhat richer and more diverse than what we have covered.
In [13]:
from muprocdurham import dcml_harmony_regex as regex
import corpusinterface as ci
import pandas
ci.reset_config('ABC_corpus.ini')
corpus = ci.load("ABC_harmonies_tsv", download=True)
file_name = 'n06op18-6_01.harmonies.tsv'
for idx, file in enumerate(corpus.files()):
this_file_name = str(file).split("/")[-1]
if this_file_name != file_name:
continue
print(this_file_name)
data = pandas.read_csv(file, sep='\t')
harmonies = list(data['label'])
cleaned_harmonies = []
for h in harmonies:
match = regex.match(h)
# print(f"Full: {h}, Chord: {match['chord']}, numeral: {match['numeral']}") # uncomment for more info
cleaned_harmonies.append(match['numeral'])
print(cleaned_harmonies)
n06op18-6_01.harmonies.tsv ['I', 'V', 'I', 'I', 'V', 'I', 'V', 'I', 'I', 'vi', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'I', 'V', 'I', 'V', 'I', 'V', 'I', 'I', 'vi', 'vii', '#vii', 'iii', 'ii', 'ii', 'V', 'I', 'I', 'V', 'I', 'V', 'V', 'V', 'V', 'I', 'V', 'I', 'V', 'I', 'V', 'I', 'V', 'I', 'V', 'I', 'V', 'I', 'I', 'V', 'I', 'V', 'I', 'V', 'I', 'V', 'i', '#vii', 'i', '#vii', 'i', 'V', 'V', 'i', 'V', 'iv', 'III', 'V', 'III', 'VI', 'bII', 'V', 'V', 'i', 'ii', 'i', 'V', 'I', 'ii', 'V', 'V', 'I', 'V', 'I', 'vi', 'ii', 'V', 'I', 'V', 'I', 'V', 'vi', 'V', 'vi', 'V', 'IV', 'V', 'V', '#vii', 'vi', 'ii', 'vii', 'V', 'V', 'I', 'V', 'V', 'V', 'V', 'I', 'I', 'V', 'I', 'I', 'V', 'I', 'I', 'V', 'I', 'V', 'I', 'I', 'V', 'I', 'I', 'I', 'V', 'I', 'I', 'I', 'V', 'I', 'V', 'I', '#vii', 'i', 'V', 'i', 'i', 'V', 'i', 'i', 'V', 'V', 'I', 'I', 'V', 'V', 'I', 'I', 'V', 'V', 'i', 'i', 'V', 'V', 'I', 'V', 'V', 'I', 'I', 'V', 'V', 'i', 'i', 'V', 'V', 'V', 'I', 'I', 'V', 'V', 'V', 'V', 'V', 'i', 'V', 'V', 'I', 'V', 'I', 'V', 'I', 'V', 'I', 'iv', 'vii', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'vii', 'vii', 'V', 'vii', 'vii', 'V', 'vii', 'vii', 'vii', 'vii', 'vii', 'vii', '@none', 'vii', 'V', 'I', 'V', 'I', 'I', 'V', 'I', 'V', 'I', 'vi', 'vi', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'I', 'V', 'I', 'V', 'I', 'V', 'I', 'vii', 'I', 'vii', 'I', 'vii', 'I', 'vii', 'I', 'vii', 'I', 'V', 'I', 'ii', 'V', 'i', 'V', 'i', 'iv', 'Ger', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'I', 'V', 'I', 'V', 'I', 'V', 'i', '#vii', 'i', '#vii', 'i', 'V', 'V', 'i', 'V', 'iv', 'iv', 'III', 'V', 'III', 'VI', 'ii', 'bII', 'V', 'V', 'i', 'bII', 'V', 'V', 'I', 'ii', 'V', 'V', 'I', 'V', 'I', 'vi', 'ii', 'V', 'I', 'V', 'I', 'V', 'vi', 'V', 'vi', 'V', 'IV', 'V', 'V', '#vii', 'vi', 'ii', 'vii', 'V', 'V', 'I', 'I', 'I', 'V', 'V', 'V', 'V', 'I', 'I', 'V', 'V', 'V', 'I', 'I', 'V', 'V', 'V', 'V', 'I', 'I', 'V', 'I', 'V', 'I', 'I']
Exercise: Use one of the following grammars (similar to those from the lecture slides) to parse the first couple of harmonies (try out different pieces) and check how many possible parse trees there are.
In [14]:
major_grammar = TreeCFG(
non_terminal_rules=[('I', 'V', 'I'),
('IV', 'I', 'IV'),
('vii0', 'IV', 'vii0'),
('iii', 'vii0', 'iii'),
('vi', 'iii', 'vi'),
('ii', 'vi', 'ii'),
('V', 'ii', 'V'),
('I', 'I', 'I')],
# relative
terminal_rules=[('I', 'I'),
('IV', 'IV'),
('vii0', 'vii0'),
('iii', 'iii'),
('vi', 'vi'),
('ii', 'ii'),
('V', 'V')],
# C Major
# terminal_rules=[('I', 'C'),
# ('IV', 'F'),
# ('vii0', 'B0'),
# ('iii', 'Em'),
# ('vi', 'Am'),
# ('ii', 'Dm'),
# ('V', 'G')],
start_symbol='I'
)
minor_grammar = TreeCFG(
non_terminal_rules=[('i', 'v', 'i'),
('i', 'V', 'i'),
('iv', 'i', 'iv'),
('VII', 'iv', 'VII'),
('III', 'VII', 'III'),
('VI', 'III', 'VI'),
('ii0', 'VI', 'ii0'),
('v', 'ii0', 'v'),
('V', 'ii0', 'V'),
('i', 'i', 'i')],
# relative
terminal_rules=[('i', 'i'),
('iv', 'iv'),
('VII', 'VII'),
('III', 'III'),
('VI', 'VI'),
('ii0', 'ii0'),
('V', 'V'),
('v', 'v')],
# A Minor
# terminal_rules=[('i', 'Am'),
# ('iv', 'Dm'),
# ('VII', 'G'),
# ('III', 'C'),
# ('VI', 'F'),
# ('ii0', 'B0'),
# ('V', 'E'),
# ('v', 'Em')],
start_symbol='i'
)
In [15]:
grammar = major_grammar
# grammar = minor_grammar
grammar.parse(cleaned_harmonies[:8])
print(grammar.chart.pretty())
╱╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ {I:{('I', 'I', 4),('I', 'I', 6),('I', 'I', 1),('I', 'I', 3)}}╲
╱╲ ╱╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ {}╲╱ {I:{('I', 'I', 4),('I', 'I', 6),('I', 'I', 3),('V', 'I', 2)}}╲
╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲
╱ {I:{('I', 'I', 4),('I', 'I', 1),('I', 'I', 3)}}╲╱ {}╲╱ {I:{('I', 'I', 4),('I', 'I', 6),('I', 'I', 3)}}╲
╱╲ ╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ {}╲╱ {I:{('I', 'I', 4),('I', 'I', 3),('V', 'I', 2)}}╲╱ {}╲╱ {I:{('I', 'I', 4),('I', 'I', 6)}}╲
╱╲ ╱╲ ╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ {I:{('I', 'I', 1),('I', 'I', 3)}}╲╱ {}╲╱ {I:{('I', 'I', 4),('I', 'I', 3)}}╲╱ {}╲╱ {I:{('I', 'I', 6),('V', 'I', 5)}}╲
╱╲ ╱╲ ╱╲ ╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ {I:{('I', 'I', 1)}}╲╱ {I:{('I', 'I', 3),('V', 'I', 2)}}╲╱ {}╲╱ {I:{('I', 'I', 4)}}╲╱ {}╲╱ {I:{('I', 'I', 6)}}╲
╱╲ ╱╲ ╱╲ ╱╲ ╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ {}╲╱ {I:{('V', 'I', 2)}}╲╱ {I:{('I', 'I', 3)}}╲╱ {}╲╱ {I:{('V', 'I', 5)}}╲╱ {}╲╱ {I:{('V', 'I', 7)}}╲
╱╲ ╱╲ ╱╲ ╱╲ ╱╲ ╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲
╱ {I:∅}╲╱ {V:∅}╲╱ {I:∅}╲╱ {I:∅}╲╱ {V:∅}╲╱ {I:∅}╲╱ {V:∅}╲╱ {I:∅}╲
In [16]:
trees = grammar.get_trees()
print(f"{len(trees)} possible parse trees")
print(cat_pretty(trees, crosses=True, grid_off=True))
37 possible parse trees
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I | I
╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ I | ╱ ╲ | ╱ ╲ | ╱ ╲
╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | I ╲ | I ╲ | I ╲ | I ╲ | I ╲ | I ╲ | I ╲ | I ╲ | I ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ I | ╱ ╱ I | ╱ ╱ I | ╱ ╱ I | ╱ ╱ I | ╱ ╱ I | ╱ ╱ I | ╱ ╲ | ╱ ╲ | ╱ ╲
╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ | ╱ ╲ ╲ | ╱ ╲ ╲ | ╱ ╲ ╲ | ╱ I ╲ | ╱ I ╲ | ╱ I ╲ | ╱ I ╲ | ╱ I ╲ | ╱ ╲ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ ╱ ╲ | ╱ I ╲ | ╱ I ╲ | ╱ I ╲ | ╱ I ╲ | ╱ I ╲ | ╱ ╱ I | ╱ ╱ I | ╱ ╱ I | ╱ ╱ ╱ ╲ | ╱ ╱ ╱ ╲ | ╱ ╱ ╱ ╲ | ╱ ╱ ╱ ╲ | ╱ ╱ ╱ I | ╱ ╱ ╱ I | ╱ ╱ ╱ I | ╱ I | ╱ I | ╱ I
I I | I I | I I | I I | I I | I I | I ╲ ╲ | I ╲ ╲ | I ╲ ╲ | ╱ ╱ ╲ ╲ | ╱ ╱ ╲ ╲ | ╱ ╱ ╲ ╲ | ╱ ╱ I ╲ | ╱ ╱ I ╲ | ╱ ╲ ╲ | ╱ ╱ I | ╱ ╱ I | ╱ ╱ I | ╱ ╱ I | ╱ ╱ ╲ ╲ | ╱ ╱ ╲ ╲ | ╱ ╱ ╲ ╲ | ╱ ╱ I ╲ | ╱ ╱ I ╲ | ╱ ╱ ╱ I | ╱ ╱ ╱ I | ╱ ╱ ╱ ╲ | ╱ ╱ ╱ I | ╱ ╱ ╱ I | ╱ ╱ I ╲ | ╱ ╱ I ╲ | ╱ ╱ ╱ ╱ I | ╱ ╱ ╱ ╱ I | ╱ ╱ ╱ ╱ ╲ | ╱ ╱ I | ╱ ╱ I | ╱ ╱ ╲
╱ I ╱ ╲ | ╱ I ╱ I | ╱ I ╱ ╲ | ╱ I ╱ I | I ╲ ╱ ╲ | I ╲ ╱ I | ╱ I ╲ ╲ | ╱ I ╲ ╲ | I ╲ ╲ ╲ | ╱ I ╲ ╲ | ╱ I ╲ ╲ | ╱ ╱ I ╲ | ╱ ╱ ╱ ╲ ╲ | ╱ ╱ ╱ I ╲ | I I ╲ | ╱ I ╱ ╲ | ╱ I ╱ I | ╱ I ╱ ╲ | ╱ I ╱ I | ╱ I ╲ ╲ | ╱ I ╲ ╲ | ╱ ╱ I ╲ | ╱ ╱ ╱ ╲ ╲ | ╱ ╱ ╱ I ╲ | ╱ ╱ ╱ ╱ ╲ | ╱ ╱ ╱ ╱ I | ╱ ╱ I ╲ | ╱ ╱ ╱ ╱ ╲ | ╱ ╱ ╱ ╱ I | ╱ ╱ ╱ ╲ ╲ | ╱ ╱ ╱ I ╲ | ╱ ╱ ╱ ╱ ╱ ╲ | ╱ ╱ ╱ ╱ ╱ I | ╱ ╱ ╱ I ╲ | I ╱ ╱ ╲ | I ╱ ╱ I | I I ╲
╱ I ╲ I I | ╱ I ╲ ╱ ╱ I | ╱ ╱ I I I | ╱ ╱ I ╱ ╱ I | ╱ I ╲ I I | ╱ I ╲ ╱ ╱ I | ╱ I ╲ I I | ╱ ╱ I I I | ╱ I ╲ I I | ╱ I ╲ I I | ╱ ╱ I I I | ╱ I ╱ I I | ╱ ╱ I I I | ╱ ╱ ╱ ╱ I I | ╱ I ╱ I I | ╱ I ╲ I I | ╱ I ╲ ╱ ╱ I | ╱ ╱ I I I | ╱ ╱ I ╱ ╱ I | ╱ I ╲ I I | ╱ ╱ I I I | ╱ I ╱ I I | ╱ ╱ I I I | ╱ ╱ ╱ ╱ I I | ╱ I ╱ I I | ╱ I ╱ ╱ ╱ I | ╱ I ╱ I I | ╱ ╱ I I I | ╱ ╱ I ╱ ╱ I | ╱ ╱ I I I | ╱ ╱ ╱ ╱ I I | ╱ ╱ ╱ ╱ I I | ╱ ╱ ╱ ╱ ╱ ╱ I | ╱ ╱ ╱ ╱ I I | ╱ I ╱ I I | ╱ I ╱ ╱ ╱ I | ╱ I ╱ I I
I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I | I V I I V I V I