Theory: Follow a derivation

Apply grammar rules one at a time and print each step.

What to build

A program that applies a list of rules, each to the leftmost variable, and prints the sentential form after each step.

Requirements

  • Print the start variable first, then the form after each rule.
  • The token ε as a body means the empty string; print ε when the form is empty.

Input

Line 1: the start variable. Line 2: n. Then n rules A -> body; each rule's A is the leftmost variable at that point.

Output

n + 1 lines.

Constraints

n ≤ 10; forms stay under 40 symbols.

Example

Input:

S
3
S -> aSb
S -> aSb
S -> ε

Output:

S
aSb
aaSbb
aabb

Why it works

A leftmost derivation always rewrites the leftmost variable, so the steps are fixed by the list of rules.

Examples

Example 1 · Input
S
3
S -> aSb
S -> aSb
S -> ε
Expected output
S
aSb
aaSbb
aabb
Example 2 · Input
S
2
S -> AB
A -> a
Expected output
S
AB
aB

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Variables are capital letters; find the leftmost one with a loop or next(...).

Hint 2

Replace only that one occurrence: form[:i] + body + form[i + 1:].

Solution

Show one correct solution (try it yourself first)
form = input().strip()
print(form)
for _ in range(int(input())):
    head, body = input().split(" -> ")
    body = "" if body == "ε" else body
    i = next(k for k, c in enumerate(form) if c.isupper())
    form = form[:i] + body + form[i + 1:]
    print(form or "ε")

Lesson: Context-free grammars →