import re
type StringVariable = int | str
type StringVariables = tuple[StringVariable, ...]
class MCFGRuleElement:
"""A multiple context free grammar rule element.
Parameters
----------
variable : str
The nonterminal variable name.
string_variables : StringVariables
Variable number of string variable tuples.
Attributes
----------
variable : str
The nonterminal variable name.
string_variables : tuple[StringVariables, ...]
The string variable tuples.
"""
def __init__(self, variable: str, *string_variables: StringVariables) -> None:
self._variable = variable
self._string_variables = string_variables
def __str__(self) -> str:
strvars = ", ".join(
"".join(str(v) for v in vtup) for vtup in self._string_variables
)
return f"{self._variable}({strvars})"
def __eq__(self, other: object) -> bool:
if not isinstance(other, MCFGRuleElement):
return NotImplemented
vareq = self._variable == other._variable
strvareq = self._string_variables == other._string_variables
return vareq and strvareq
def to_tuple(self) -> tuple[str, tuple[StringVariables, ...]]:
"""Convert to a hashable tuple representation.
Returns
-------
tuple[str, tuple[StringVariables, ...]]
The (variable, string_variables) tuple.
"""
return (self._variable, self._string_variables)
def __hash__(self) -> int:
return hash(self.to_tuple())
@property
def variable(self) -> str:
"""The nonterminal variable name."""
return self._variable
@property
def string_variables(self) -> tuple[StringVariables, ...]:
"""The string variable tuples."""
return self._string_variables
@property
def unique_string_variables(self) -> set[int]:
"""The unique string variable indices across all tuples."""
return {
variable
for component in self.string_variables
for variable in component
if isinstance(variable, int)
}Final Project
What are we building in the final project? You will develop a package for parsing with multiple context-free grammars (MCFGs). The package must implement an agenda-based parser as described in Shieber et al. 1995, using the inference rules laid out in Kallmeyer 2013.
In addition to a working agenda-based parser, the package must use the standard directory structure for a Python package, including a full test suite implemented in pytest. If you have not written a Python package before, I encourage you to read this tutorial and use the directory structure they discuss:
PACKAGE_NAME/
├── LICENSE
├── pyproject.toml
├── README.md
├── src/
│ └── PACKAGE_NAME/
│ ├── __init__.py
│ └── example.py
└── tests/Test Grammar
In writing tests, it will be useful to have a grammar to test your parser against. Rather than have you write your own, you might find it useful to use the one below.
S(uv) -> NP(u) VP(v)
S(uv) -> NPwh(u) VP(v)
S(vuw) -> Aux(u) Swhmain(v, w)
S(uwv) -> NPdisloc(u, v) VP(w)
S(uwv) -> NPwhdisloc(u, v) VP(w)
Sbar(uv) -> C(u) S(v)
Sbarwh(v, uw) -> C(u) Swhemb(v, w)
Sbarwh(u, v) -> NPwh(u) VP(v)
Swhmain(v, uw) -> NP(u) VPwhmain(v, w)
Swhmain(w, uxv) -> NPdisloc(u, v) VPwhmain(w, x)
Swhemb(v, uw) -> NP(u) VPwhemb(v, w)
Swhemb(w, uxv) -> NPdisloc(u, v) VPwhemb(w, x)
Src(v, uw) -> NP(u) VPrc(v, w)
Src(w, uxv) -> NPdisloc(u, v) VPrc(w, x)
Src(u, v) -> N(u) VP(v)
Swhrc(u, v) -> Nwh(u) VP(v)
Swhrc(v, uw) -> NP(u) VPwhrc(v, w)
Sbarwhrc(v, uw) -> C(u) Swhrc(v, w)
VP(uv) -> Vpres(u) NP(v)
VP(uv) -> Vpres(u) Sbar(v)
VPwhmain(u, v) -> NPwh(u) Vroot(v)
VPwhmain(u, wv) -> NPwhdisloc(u, v) Vroot(w)
VPwhmain(v, uw) -> Vroot(u) Sbarwh(v, w)
VPwhemb(u, v) -> NPwh(u) Vpres(v)
VPwhemb(u, wv) -> NPwhdisloc(u, v) Vpres(w)
VPwhemb(v, uw) -> Vpres(u) Sbarwh(v, w)
VPrc(u, v) -> N(u) Vpres(v)
VPrc(v, uw) -> Vpres(u) Nrc(v, w)
VPwhrc(u, v) -> Nwh(u) Vpres(v)
VPwhrc(v, uw) -> Vpres(u) Sbarwhrc(v, w)
NP(uv) -> D(u) N(v)
NP(uvw) -> D(u) Nrc(v, w)
NPdisloc(uv, w) -> D(u) Nrc(v, w)
NPwh(uv) -> Dwh(u) N(v)
NPwh(uvw) -> Dwh(u) Nrc(v, w)
NPwhdisloc(uv, w) -> Dwh(u) Nrc(v, w)
Nrc(v, uw) -> C(u) Src(v, w)
Nrc(u, vw) -> N(u) Swhrc(v, w)
Nrc(u, vwx) -> Nrc(u, v) Swhrc(w, x)
Dwh(which)
Nwh(who)
D(the)
D(a)
N(greyhound)
N(human)
Vpres(believes)
Vroot(believe)
Aux(does)
C(that)Whichever test grammar you use, load it as a pytest.fixture so that the tests can share one checked grammar object.
Rules
We begin with the rule representation. A context-free Rule from Assignments 9 and 10 has a string-valued left side and a tuple-valued right side. Here, an MCFGRule instead has one MCFGRuleElement on the left and a tuple of MCFGRuleElement objects on the right. Each element records both a nonterminal—e.g. S, NP, or VP—and its string component variables.
An MCFGRuleElement wraps a nonterminal name and its string components. In a nonterminal rule, the components contain integer indices. For instance, VPwhemb(u, v) -> NPwh(u) Vpres(v) may represent u and v by the singleton tuples (0,) and (1,). A terminal rule such as Dwh(which) uses the same representation with the constant string "which"; MCFGRule.string_yield exposes that constant. This starter representation is deliberately nonerasing: every nonterminal has at least one nonempty component, and every terminal rule yields exactly one nonempty token. The supplied grammar satisfies those restrictions.
print(
MCFGRuleElement("VPwhemb", (0,), (1,)),
"->",
MCFGRuleElement("NPwh", (0,)),
MCFGRuleElement("Vpres", (1,)),
)Why is one component represented by a tuple rather than one integer? A left-side component may concatenate several right-side variables. In VPwhemb(u, wv) -> NPwhdisloc(u, v) Vpres(w), the second output component contains w followed by v. Its index tuple must thus contain both variables in that order.
print(
MCFGRuleElement("VPwhemb", (0,), (2, 1)),
"->",
MCFGRuleElement("NPwhdisloc", (0,), (1,)),
MCFGRuleElement("Vpres", (2,)),
)What must a recognizer record for each component? It must track the component’s span. In who does the greyhound believe, u and v in VPwhmain(u, v) -> NPwh(u) Vroot(v) are instantiated by who at \([0,1)\) and believe at \([4,5)\), respectively. We use half-open spans throughout: the left endpoint is included and the right endpoint is excluded.
type SpanIndices = tuple[int, int]
class MCFGRuleElementInstance:
"""An instantiated multiple context free grammar rule element.
Parameters
----------
variable : str
The nonterminal variable name.
string_spans : SpanIndices
Variable number of span index tuples.
Attributes
----------
variable : str
The nonterminal variable name.
string_spans : tuple[SpanIndices, ...]
The span index tuples.
"""
def __init__(self, variable: str, *string_spans: SpanIndices) -> None:
self._variable = variable
self._string_spans = string_spans
def __eq__(self, other: object) -> bool:
if not isinstance(other, MCFGRuleElementInstance):
return NotImplemented
vareq = self._variable == other._variable
strspaneq = self._string_spans == other._string_spans
return vareq and strspaneq
def to_tuple(self) -> tuple[str, tuple[SpanIndices, ...]]:
"""Convert to a hashable tuple representation.
Returns
-------
tuple[str, tuple[SpanIndices, ...]]
The (variable, string_spans) tuple.
"""
return (self._variable, self._string_spans)
def __hash__(self) -> int:
return hash(self.to_tuple())
def __str__(self) -> str:
strspans = ", ".join(str(list(stup)) for stup in self._string_spans)
return f"{self._variable}({strspans})"
def __repr__(self) -> str:
return self.__str__()
@property
def variable(self) -> str:
"""The nonterminal variable name."""
return self._variable
@property
def string_spans(self) -> tuple[SpanIndices, ...]:
"""The span index tuples."""
return self._string_spansWe now have enough structure to define the full MCFGRule implementation.
type SpanMap = dict[int, SpanIndices]
class MCFGRule:
"""A linear multiple context free grammar rule.
Parameters
----------
left_side : MCFGRuleElement
The left side of the rule.
right_side : MCFGRuleElement
Variable number of right side elements.
Attributes
----------
left_side : MCFGRuleElement
The left side of the rule.
right_side : tuple[MCFGRuleElement, ...]
The right side elements.
"""
def __init__(
self, left_side: MCFGRuleElement, *right_side: MCFGRuleElement
) -> None:
self._left_side = left_side
self._right_side = right_side
self._validate()
def to_tuple(self) -> tuple[MCFGRuleElement, tuple[MCFGRuleElement, ...]]:
"""Convert to a hashable tuple representation.
Returns
-------
tuple[MCFGRuleElement, tuple[MCFGRuleElement, ...]]
The (left_side, right_side) tuple.
"""
return (self._left_side, self._right_side)
def __hash__(self) -> int:
return hash(self.to_tuple())
def __repr__(self) -> str:
return "<Rule: " + str(self) + ">"
def __str__(self) -> str:
if self.is_terminal:
return str(self._left_side)
else:
return (
str(self._left_side)
+ " -> "
+ " ".join(str(el) for el in self._right_side)
)
def __eq__(self, other: object) -> bool:
if not isinstance(other, MCFGRule):
return NotImplemented
left_side_equal = self._left_side == other._left_side
right_side_equal = self._right_side == other._right_side
return left_side_equal and right_side_equal
def _validate(self) -> None:
vs = [el.unique_string_variables for el in self.right_side]
sharing = any(
vs1.intersection(vs2)
for i, vs1 in enumerate(vs)
for j, vs2 in enumerate(vs)
if i < j
)
if sharing:
raise ValueError("right side variables cannot share string variables")
if self.is_terminal:
components = self.left_side.string_variables
if (
len(components) != 1
or len(components[0]) != 1
or not isinstance(components[0][0], str)
):
raise ValueError(
"a terminal rule must contain exactly one string yield"
)
return
if any(
not component for component in self.left_side.string_variables
) or any(
not element.string_variables
or any(not component for component in element.string_variables)
for element in self.right_side
):
raise ValueError(
"this representation requires nonempty string components"
)
left_atoms = [
variable
for component in self.left_side.string_variables
for variable in component
]
right_components = [
component
for element in self.right_side
for component in element.string_variables
]
if any(not isinstance(variable, int) for variable in left_atoms) or any(
len(component) != 1 or not isinstance(component[0], int)
for component in right_components
):
raise TypeError(
"nonterminal rules must use integer string-variable indices"
)
right_vars = [component[0] for component in right_components]
if len(right_vars) != len(set(right_vars)):
raise ValueError(
"each right-side string variable must occur exactly once"
)
if len(left_atoms) != len(set(left_atoms)):
raise ValueError("a linear rule cannot copy a string variable")
if set(left_atoms) != set(right_vars):
raise ValueError(
"the left and right sides must use the same string variables"
)
@property
def left_side(self) -> MCFGRuleElement:
"""The left side of the rule."""
return self._left_side
@property
def right_side(self) -> tuple[MCFGRuleElement, ...]:
"""The right side elements."""
return self._right_side
@property
def is_terminal(self) -> bool:
"""Whether this rule has a constant terminal yield."""
return len(self._right_side) == 0
@property
def unique_variables(self) -> set[str]:
"""The set of unique variable names across both sides."""
return {el.variable for el in [self._left_side] + list(self._right_side)}
def instantiate_left_side(
self, *right_side: MCFGRuleElementInstance
) -> MCFGRuleElementInstance:
"""Instantiate the left side of the rule given an instantiated right side.
Parameters
----------
right_side : MCFGRuleElementInstance
The instantiated right side elements.
Returns
-------
MCFGRuleElementInstance
The instantiated left side element.
Raises
------
ValueError
If spans are not adjacent as required by the rule.
"""
if self.is_terminal:
raise ValueError(
"a terminal rule is instantiated directly from an input token"
)
integer_components: list[tuple[int, ...]] = []
for component in self._left_side.string_variables:
if not all(isinstance(variable, int) for variable in component):
raise TypeError("nonterminal rules require integer string variables")
integer_components.append(
tuple(variable for variable in component if isinstance(variable, int))
)
new_spans = []
span_map = self._build_span_map(right_side)
for vs in integer_components:
for i in range(1, len(vs)):
end_prev = span_map[vs[i - 1]][1]
begin_curr = span_map[vs[i]][0]
if end_prev != begin_curr:
raise ValueError(
f"Spans {span_map[vs[i - 1]]} and {span_map[vs[i]]} "
f"must be adjacent according to {self} but they "
"are not."
)
begin_span = span_map[vs[0]][0]
end_span = span_map[vs[-1]][1]
new_spans.append((begin_span, end_span))
return MCFGRuleElementInstance(self._left_side.variable, *new_spans)
def _build_span_map(
self, right_side: tuple[MCFGRuleElementInstance, ...]
) -> SpanMap:
"""Construct a mapping from string variables to string spans.
Parameters
----------
right_side : tuple[MCFGRuleElementInstance, ...]
The instantiated right side elements.
Returns
-------
SpanMap
Mapping from string variable indices to span tuples.
Raises
------
ValueError
If the instantiated right side does not align with the rule.
"""
if self._right_side_aligns(right_side):
span_map: SpanMap = {}
for element, instance in zip(self._right_side, right_side):
for component, span in zip(
element.string_variables,
instance.string_spans,
):
variable = component[0]
if not isinstance(variable, int):
raise TypeError(
"a span variable must be represented by an integer"
)
span_map[variable] = span
return span_map
else:
raise ValueError(
f"Instantiated right side {right_side} do not "
f"align with rule's right side {self._right_side}"
)
def _right_side_aligns(
self, right_side: tuple[MCFGRuleElementInstance, ...]
) -> bool:
"""Check whether the instantiated right side aligns with the rule.
Parameters
----------
right_side : tuple[MCFGRuleElementInstance, ...]
The instantiated right side elements.
Returns
-------
bool
Whether the right side aligns.
"""
if len(right_side) == len(self._right_side):
vars_match = all(
elem.variable == eleminst.variable
for elem, eleminst in zip(self._right_side, right_side)
)
strvars_match = all(
len(elem.string_variables) == len(eleminst.string_spans)
for elem, eleminst in zip(self._right_side, right_side)
)
return vars_match and strvars_match
else:
return False
@classmethod
def from_string(cls, rule_string: str) -> MCFGRule:
"""Parse an MCFG rule from a string representation.
Parameters
----------
rule_string : str
The rule string to parse, e.g. ``'A(uv) -> B(u) C(v)'``.
Returns
-------
MCFGRule
The parsed rule.
"""
elem_strs = re.findall(r"(\w+)\(((?:\w+,? ?)+?)\)", rule_string)
elem_tuples = [
(var, [v.strip() for v in svs.split(",")]) for var, svs in elem_strs
]
if len(elem_tuples) == 1:
return cls(
MCFGRuleElement(elem_tuples[0][0], tuple(w for w in elem_tuples[0][1]))
)
else:
strvars = [v for _, sv in elem_tuples[1:] for v in sv]
if len(strvars) != len(set(strvars)):
raise ValueError("variables duplicated on right side of " + rule_string)
elem_left = MCFGRuleElement(
elem_tuples[0][0],
*[
tuple(
[
strvars.index(v)
for v in re.findall(
"|".join(
re.escape(variable)
for variable in sorted(
strvars, key=len, reverse=True
)
),
vs,
)
]
)
for vs in elem_tuples[0][1]
],
)
elems_right = [
MCFGRuleElement(var, *[(strvars.index(sv),) for sv in svs])
for var, svs in elem_tuples[1:]
]
return cls(elem_left, *elems_right)
def string_yield(self) -> str:
"""Return the constant yielded by a terminal rule.
Raises
------
ValueError
If this is not a terminal rule.
"""
if not self.is_terminal:
raise ValueError("string_yield is only defined for terminal rules")
string_yield = self._left_side.string_variables[0][0]
if not isinstance(string_yield, str):
raise TypeError("a terminal yield must be a string")
return string_yieldNow we need to load a grammar. The provided class method reads rules from strings.
rule = MCFGRule.from_string("A(w1u, x1v) -> B(w1, x1) C(u, v)")
rule
terminal_rule = MCFGRule.from_string("Dwh(which)")
assert terminal_rule.is_terminal
assert terminal_rule.string_yield() == "which"
try:
MCFGRule.from_string("A(uu) -> B(u)")
except ValueError:
pass
else:
raise AssertionError("a linear MCFG rule cannot copy a string variable")
try:
MCFGRule(
MCFGRuleElement("A", (0,)),
MCFGRuleElement("B", (0,), (0,)),
)
except ValueError:
pass
else:
raise AssertionError(
"a right-side string variable cannot be reused within one element"
)
try:
MCFGRule(
MCFGRuleElement("A", ()),
MCFGRuleElement("B", (0,)),
)
except ValueError:
pass
else:
raise AssertionError(
"the starter representation excludes empty components"
)
overlapping_names = MCFGRule.from_string("A(u1u) -> B(u) C(u1)")
assert overlapping_names.left_side.string_variables == ((1, 0),)Before implementing an inference rule, work through MCFGRule.instantiate_left_side. What must this method verify? It receives instantiated right-side elements, checks their nonterminal names and fan-outs, verifies every required adjacency, and constructs the left-side spans. The example below shows each record explicitly.
rule.instantiate_left_side(
MCFGRuleElementInstance("B", (1, 2), (5, 7)),
MCFGRuleElementInstance("C", (2, 4), (7, 8)),
)With this method supplied, your implementation can focus on deductive parsing and agenda control. The parser must still decide which antecedent items to combine, call the rule on them, avoid duplicate chart work, record backpointers, and identify the goal item.