Decide whether a word shows that a grammar is ambiguous.
What to build
A program that counts the parse trees of a word in a grammar and says whether the word is ambiguous.
Requirements
- Print
trees N. - Then print
ambiguousif N > 1,unambiguousif N = 1, ornot in the languageif N = 0.
Input
Line 1: the start variable. Line 2: r. Then r lines A -> body | body. Last line: the word.
Output
Two lines.
Constraints
No ε-rules and no cycles of single-variable rules; the word has at most 12 symbols.
Example
Input:
E
1
E -> E+E | x
x+x+x
Output:
trees 2
ambiguous
Why it works
Each parse tree is one way of splitting the word among the parts of the rules; counting all splits counts all trees.
Examples
E 1 E -> E+E | x x+x+x
trees 2 ambiguous
E 2 E -> E+T | T T -> x x+x+x
trees 1 unambiguous
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Count trees for a variable over a piece of the word, w[i:j], and remember the answers (memoise).
Hint 2
For a body X1…Xk, try every way of splitting w[i:j] into k non-empty parts, multiplying the counts of the parts.
Solution
Show one correct solution (try it yourself first)
from functools import lru_cache
start = input().strip()
grammar = {}
for _ in range(int(input())):
head, bodies = input().split(" -> ")
for body in bodies.split(" | "):
grammar.setdefault(head, []).append(tuple(body))
word = input().strip()
@lru_cache(maxsize=None)
def trees(symbol, i, j):
if symbol not in grammar:
return 1 if word[i:j] == symbol else 0
return sum(ways(body, i, j) for body in grammar[symbol])
@lru_cache(maxsize=None)
def ways(body, i, j):
if len(body) == 1:
return trees(body[0], i, j)
total = 0
for k in range(i + 1, j - len(body) + 2):
left = trees(body[0], i, k)
if left:
total += left * ways(body[1:], k, j)
return total
n = trees(start, 0, len(word))
print("trees", n)
print("ambiguous" if n > 1 else "unambiguous" if n == 1 else "not in the language")