Theory: Count the parse trees

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 ambiguous if N > 1, unambiguous if N = 1, or not in the language if 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

Example 1 · Input
E
1
E -> E+E | x
x+x+x
Expected output
trees 2
ambiguous
Example 2 · Input
E
2
E -> E+T | T
T -> x
x+x+x
Expected output
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")

Lesson: Context-free grammars →