<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

418. Deducing Grammar
time limit per test: 0.25 sec.
memory limit per test: 262144 KB
input: standard
output: standard



A typical top-down parser is a very simple application. We will consider parsers written in Pascal that obey the following structure:

Program Parser;
Procedure Skip; Forward;
Function Peek:Char; Forward;
Procedure Error; Forward;

<parsing routines forward-declarations>
<parsing routines>

Var
  St:String;
  Pos:Integer;
Procedure Error;
Begin
  WriteLn('NO');
  Halt;
End;
Procedure Skip;
Begin
  Inc(Pos);
  If Pos>Length(St) Then Error;
End;
Function Peek:Char;
Begin
  Peek:=St[Pos];
End;
Begin
  ReadLn(St);
  St:=St+'#';
  Pos:=1;
  Parse;
  If Pos=Length(St) Then WriteLn('YES') Else WriteLn('NO');
End.

The part labeled <parsing routines forward-declarations> contains a definition for each of the parsing functions, followed by Forward;. The part labeled <parsing routines> contains a definition followed by a body for each of the parsing routines.

A definition of a parsing routine is:

Procedure <name>;

The name is a case-insensitive sequence of English letters. Names of different routines should be different. A routine name cannot coincide with a keyword, nor can it coincide with the names of parser's internal functions (Skip, Peek or Error). A body of a parsing routine is:

Begin
  <segment>
  <segment>
  ...
  <segment>
End;

There must be at least one segment. Each segment is either an unconditional segment, or a conditional segment.

An unconditional segment is a routine call: <name>;, where <name> is a name of some parsing routine.

A conditional segment has the following structure:

If Peek=<character> Then Begin
  Skip;
  <segment>
  <segment>
  ...
  <segment>
End Else If Peek=<character> Then Begin
  Skip;
  <segment>
  <segment>
  ...
  <segment>
End Else If Peek=<character> Then Begin
...
End Else If Peek=<character> Then Begin
End;

Where each <segment> is again either unconditional or conditional. The simplest form of a conditional segment has only one If and no Else. Note that we always skip a character after guessing it right, and that's the only case where we invoke Skip;. Each <character> is a non-apostrophe character with ASCII code between 33 and 126 wrapped in apostrophes, like 'a'. It is not necessary to have at least one <segment> after Skip; in the If body. The last End; can also be written as End Else Error;, meaning that all other peek outcomes are unacceptable.

The case of the letters in the identifiers and keywords can be arbitrary, and whitespace may be inserted and/or omitted everywhere except it must be present between two words and it must not be present inside a word or string literal (something wrapped in apostrophes). One of the parsing routines must be named Parse.

Such a top-down parser is usually based on some formal grammar. Your task is to find which grammar the given parser is based on. To do so, you should apply the following rules (note that the resulting grammar may not necessarily define the same language as the language accepted by the parser — you shouldn't care about it, just blindly apply the rules):

The set of nonterminal symbols of the grammar is the same as the set of parsing routine names in the parser.

The set of terminal symbols of the grammar is the set of characters with ASCII codes between 33 and 126, except apostrophe.

For each (even seemingly impossible, like duplicate Peek=... conditions) way of evaluating all If's in the body of some routine that do not result in a call to Error;, there should be one production rule concatenating the corresponding nonterminals and terminals (see example for further clarification).

The starting symbol should be Parse.

Your program should input the top-down parser code in Pascal, and output the grammar in the Backus-Naur form. See example for more information on how to output the grammar. Two adjacent string literals should be concatenated, i.e., you should write 'AB' instead of 'A''B'. Your output should contain exactly n lines, where n is the number of parsing routines in the input.

The nonterminals must be written in lowercase. The production rules inside a line must be sorted lexicographically, and the lines must be sorted lexicographically, too.

Input
The input file contains a top-down parser in Pascal. The size of the input file does not exceed 10000 bytes, and each word is at most 20 characters long.

Output
Output the Backus-Naur form of the underlying grammar. The only whitespace in output should be line breaks after each line (including the last line), as the output will be checked for exact equality with the reference answer. The output is guaranteed not to exceed 10000 bytes.

Sample test(s)

Input

Program Parser;
Procedure Skip; Forward;
Function Peek:Char; Forward;
Procedure Error; Forward;

Procedure Parse; Forward;
Procedure Addend; Forward;
Procedure Term; Forward;
Procedure Number; Forward;

Procedure Term;
Begin
  If Peek='0' Then Begin
    Skip;
    Number;
  End Else If Peek='1' Then Begin
    Skip;
    Number;
  End Else If Peek='(' Then Begin
    Skip;
    Parse;
    If Peek=')' Then Begin
      Skip;
    End Else Error;
  End Else If Peek='P' Then Begin
    Skip;
    If Peek='I' Then Begin
      Skip;
    End Else If Peek='E' Then Begin
      Skip;
    End Else Error;        
  End Else Error;
End;

Procedure Number;
Begin
  If Peek='0' Then Begin
    Skip;
    Number;
  End Else If Peek='1' Then Begin
    Skip;
    Number;
  End;
End;

Procedure Addend;
Begin
  Term;
  If Peek='*' Then Begin
    Skip;
    Addend;
  End Else If Peek='/' Then Begin
    Skip;
    Addend;
  End;
End;

Procedure Parse;
Begin
  Addend;
  If Peek='+' Then Begin
    Skip;
    Parse;
  End Else If Peek='-' Then Begin
    Skip;
    Parse;
  End;
End;

Var
  St:String;
  Pos:Integer;

Procedure Error;
Begin
  WriteLn('NO');
  Halt;
End;

Procedure Skip;
Begin
  Inc(Pos);
  If Pos>Length(St) Then Error;
End;

Function Peek:Char;
Begin
  Peek:=St[Pos];
End;
Begin
  ReadLn(St);
  St:=St+'#';
  Pos:=1;
  Parse;
  If Pos=Length(St) Then WriteLn('YES') Else WriteLn('NO');
End.

Output

<addend>::=<term>|<term>'*'<addend>|<term>'/'<addend>
<number>::=|'0'<number>|'1'<number>
<parse>::=<addend>|<addend>'+'<parse>|<addend>'-'<parse>
<term>::='('<parse>')'|'0'<number>|'1'<number>|'PE'|'PI'

Note
Note that this parser and this grammar correspond to arithmetic expressions involving binary numbers and two constants 'PE' and 'PI'.
Author:	Petr Mitrichev
Resource:	Petr Mitrichev Contest 3
Date:	September 01, 2007

<|response|>
## 1. Abridged problem statement

We are given the source code of a specially restricted Pascal top-down parser.

Parsing routines contain only:

- unconditional calls to other parsing routines: `Name;`
- conditional chains of the form:

```pascal
If Peek='c' Then Begin
  Skip;
  ...
End Else If Peek='d' Then Begin
  Skip;
  ...
End Else Error;
```

or the same structure without the final `Else Error`.

We must reconstruct the formal grammar encoded by the parser:

- each parsing routine is a nonterminal;
- each consumed character after `Peek='c'` and `Skip;` is a terminal;
- each successful execution path through a routine body gives one production;
- if a conditional does not end with `Else Error`, then doing nothing is also a valid path;
- nonterminals and keywords are case-insensitive, output nonterminals in lowercase;
- alternatives and output lines must be sorted lexicographically;
- adjacent terminals must be merged, e.g. output `'AB'`, not `'A''B'`.

---

## 2. Key observations

### Observation 1: We do not need to parse full Pascal

The input program has a fixed structure. We only need to recognize:

- words, like `Procedure`, `Begin`, `If`, routine names;
- string literals, like `'a'`, `'+'`;
- punctuation, like `;`, `=`, `:`.

So the first step should be tokenization.

All words can be lowercased because Pascal identifiers and keywords are case-insensitive.

---

### Observation 2: Routine bodies form a small recursive language

Each routine body is:

```pascal
Begin
  segment
  segment
  ...
End;
```

A segment is either:

1. a routine call:

```pascal
Name;
```

2. a conditional chain:

```pascal
If Peek='c' Then Begin
  Skip;
  ...
End Else If Peek='d' Then Begin
  Skip;
  ...
End Else Error;
```

Conditional branch bodies may contain nested segments, so recursive parsing is natural.

---

### Observation 3: Grammar production generation is a Cartesian product

A routine body is a sequence of segments.

For example:

```pascal
Term;
If Peek='*' Then Begin
  Skip;
  Addend;
End Else If Peek='/' Then Begin
  Skip;
  Addend;
End;
```

The first segment produces:

```text
<term>
```

The second segment produces:

```text
empty
'*'<addend>
'/'<addend>
```

Combining them gives:

```text
<term>
<term>'*'<addend>
<term>'/'<addend>
```

So expansion of a list of segments is done by Cartesian-product concatenation.

---

### Observation 4: Missing `Else Error` means empty alternative

A conditional without final `Else Error` allows the parser to simply skip the entire conditional if no branch matches.

Therefore, such conditionals add an empty production alternative.

Example:

```pascal
If Peek='0' Then Begin
  Skip;
  Number;
End;
```

produces:

```text
empty
'0'<number>
```

---

### Observation 5: Do not remove duplicates

The statement says every way of evaluating `If`s gives a production, even if it looks impossible. If two different paths result in identical text, they are still separate production rules. Therefore, sort alternatives but do not deduplicate them.

---

## 3. Full solution approach

### Step 1: Tokenize the input

Read the entire source code as one string.

Produce tokens:

- `WORD`: maximal sequence of letters, converted to lowercase;
- `STRING`: contents inside apostrophes;
- `PUNCT`: every other non-whitespace character.

For example:

```pascal
If Peek='0' Then Begin
```

becomes:

```text
word(if), word(peek), punct(=), string(0), word(then), word(begin)
```

---

### Step 2: Find real parsing routine definitions

Forward declarations look like:

```pascal
Procedure Parse; Forward;
```

Real definitions look like:

```pascal
Procedure Parse;
Begin
  ...
End;
```

After tokenization, a real definition has the pattern:

```text
procedure name ; begin
```

We ignore the internal procedures:

```text
skip
error
```

`Peek` is a function, not a parsing routine.

---

### Step 3: Parse routine bodies

Represent each body as a list of segments.

A segment can be:

```text
call(name)
```

or

```text
conditional(branches, else_error)
```

where each branch stores:

```text
character, nested_segment_list
```

For a conditional:

```pascal
If Peek='a' Then Begin
  Skip;
  ...
End Else If Peek='b' Then Begin
  Skip;
  ...
End Else Error;
```

we store:

```text
branches = [
  ('a', body_of_first_branch),
  ('b', body_of_second_branch)
]
else_error = true
```

If there is no final `Else Error`, then:

```text
else_error = false
```

---

### Step 4: Expand segments into grammar productions

Use a symbol representation:

```text
terminal character
nonterminal name
```

Expansion rules:

#### Routine call

```pascal
Number;
```

expands to:

```text
<number>
```

#### Conditional branch

```pascal
If Peek='c' Then Begin
  Skip;
  body
End
```

expands to:

```text
'c' + expansion(body)
```

If there is no final `Else Error`, also add:

```text
empty
```

#### Sequence of segments

Expand each segment and concatenate all possibilities.

---

### Step 5: Render productions

When rendering:

- nonterminals are written as `<name>`;
- terminals are written in apostrophes;
- consecutive terminals are merged into one string literal.

Example:

```text
terminal 'P', terminal 'I'
```

renders as:

```text
'PI'
```

An empty production renders as an empty string.

---

### Step 6: Sort and output

For each routine:

1. expand its body;
2. render all alternatives;
3. sort alternatives lexicographically;
4. output:

```text
<name>::=alt1|alt2|alt3
```

Finally, sort all lines lexicographically and print them.

Complexity is easily sufficient because both input and output are at most about `10000` bytes.

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

// -------------------- Tokenization --------------------

enum TokenKind {
    WORD,
    STRING,
    PUNCT
};

struct Token {
    TokenKind kind;
    string value;
};

vector<Token> tokens;
string source;

// Convert the whole input program into tokens.
void tokenize() {
    int n = (int)source.size();

    for (int i = 0; i < n; ) {
        char c = source[i];

        // Ignore whitespace.
        if (isspace((unsigned char)c)) {
            i++;
            continue;
        }

        // A word is a maximal sequence of English letters.
        // We lowercase it because Pascal is case-insensitive here.
        if (isalpha((unsigned char)c)) {
            string word;

            while (i < n && isalpha((unsigned char)source[i])) {
                word.push_back((char)tolower((unsigned char)source[i]));
                i++;
            }

            tokens.push_back({WORD, word});
            continue;
        }

        // String literal, for example: 'a', '+', 'NO'
        if (c == '\'') {
            i++; // Skip opening apostrophe.

            string value;

            while (i < n && source[i] != '\'') {
                value.push_back(source[i]);
                i++;
            }

            i++; // Skip closing apostrophe.

            tokens.push_back({STRING, value});
            continue;
        }

        // Every other non-whitespace character is punctuation.
        tokens.push_back({PUNCT, string(1, c)});
        i++;
    }
}

// -------------------- Parser data structures --------------------

struct Segment {
    // false: unconditional routine call
    // true: conditional If / Else If / Else Error chain
    bool is_conditional;

    // Used for unconditional calls.
    string call_name;

    // Used for conditional chains.
    // Each branch is: consumed character, nested body.
    vector<pair<char, vector<Segment>>> branches;

    // True iff the conditional chain ends with "Else Error;"
    bool else_error = false;
};

int pos_token = 0;

// Check if the current token is a given word.
bool at_word(const string& word) {
    return pos_token < (int)tokens.size()
        && tokens[pos_token].kind == WORD
        && tokens[pos_token].value == word;
}

vector<Segment> parse_segments();

// Parse one conditional segment.
Segment parse_conditional() {
    Segment seg;
    seg.is_conditional = true;
    seg.else_error = false;

    // Current token is "if".
    pos_token++;

    while (true) {
        // We are now at:
        // Peek = 'c' Then Begin Skip ; ...

        pos_token++; // consume "peek"
        pos_token++; // consume "="

        char ch = tokens[pos_token].value[0]; // consume character literal
        pos_token++;

        pos_token++; // consume "then"
        pos_token++; // consume "begin"

        pos_token++; // consume "skip"
        pos_token++; // consume ";"

        // Parse nested segments until corresponding End.
        vector<Segment> inner = parse_segments();

        pos_token++; // consume "end"

        seg.branches.push_back({ch, inner});

        // After End, we may have:
        // - Else If ...
        // - Else Error ;
        // - ; meaning the conditional chain is finished.
        if (at_word("else")) {
            pos_token++; // consume "else"

            if (at_word("if")) {
                pos_token++; // consume "if"
                continue;    // parse next branch
            }

            // Otherwise it must be "Error;"
            pos_token++; // consume "error"
            pos_token++; // consume ";"

            seg.else_error = true;
            break;
        } else {
            // No Else: there is a semicolon after End.
            pos_token++; // consume ";"
            break;
        }
    }

    return seg;
}

// Parse a list of segments until the matching "End".
vector<Segment> parse_segments() {
    vector<Segment> result;

    while (!at_word("end")) {
        if (at_word("if")) {
            result.push_back(parse_conditional());
        } else {
            // Unconditional call:
            // Name ;
            Segment seg;
            seg.is_conditional = false;
            seg.call_name = tokens[pos_token].value;

            pos_token++; // consume name
            pos_token++; // consume ";"

            result.push_back(seg);
        }
    }

    return result;
}

// -------------------- Grammar expansion --------------------

struct Symbol {
    bool terminal;

    // Used if terminal == true.
    char ch;

    // Used if terminal == false.
    string name;
};

vector<vector<Symbol>> expand_segments(const vector<Segment>& segments);

// Expand one segment into possible symbol sequences.
vector<vector<Symbol>> expand_segment(const Segment& seg) {
    vector<vector<Symbol>> result;

    if (!seg.is_conditional) {
        // A routine call contributes one nonterminal.
        Symbol sym;
        sym.terminal = false;
        sym.ch = 0;
        sym.name = seg.call_name;

        result.push_back({sym});
        return result;
    }

    // Conditional segment.
    // Each successful branch contributes:
    // terminal character + expansion of nested body.
    for (const auto& branch : seg.branches) {
        char ch = branch.first;
        const vector<Segment>& inner_body = branch.second;

        Symbol terminal_symbol;
        terminal_symbol.terminal = true;
        terminal_symbol.ch = ch;
        terminal_symbol.name = "";

        vector<vector<Symbol>> inner_expansions = expand_segments(inner_body);

        for (const auto& inner : inner_expansions) {
            vector<Symbol> production;
            production.push_back(terminal_symbol);
            production.insert(production.end(), inner.begin(), inner.end());

            result.push_back(production);
        }
    }

    // If there is no Else Error, doing nothing is also successful.
    if (!seg.else_error) {
        result.push_back({});
    }

    return result;
}

// Expand a sequence of segments using Cartesian product concatenation.
vector<vector<Symbol>> expand_segments(const vector<Segment>& segments) {
    vector<vector<Symbol>> result;
    result.push_back({}); // Start with one empty prefix.

    for (const Segment& seg : segments) {
        vector<vector<Symbol>> alternatives = expand_segment(seg);
        vector<vector<Symbol>> next_result;

        for (const auto& prefix : result) {
            for (const auto& suffix : alternatives) {
                vector<Symbol> combined = prefix;
                combined.insert(combined.end(), suffix.begin(), suffix.end());
                next_result.push_back(combined);
            }
        }

        result = next_result;
    }

    return result;
}

// Render one production into required BNF text.
string render_production(const vector<Symbol>& production) {
    string output;

    int i = 0;
    int n = (int)production.size();

    while (i < n) {
        if (production[i].terminal) {
            // Merge adjacent terminals into one quoted string.
            output.push_back('\'');

            while (i < n && production[i].terminal) {
                output.push_back(production[i].ch);
                i++;
            }

            output.push_back('\'');
        } else {
            output.push_back('<');
            output += production[i].name;
            output.push_back('>');
            i++;
        }
    }

    // Empty production renders as an empty string.
    return output;
}

// -------------------- Main solving logic --------------------

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Read complete input source.
    {
        stringstream buffer;
        buffer << cin.rdbuf();
        source = buffer.str();
    }

    tokenize();

    vector<pair<string, vector<Segment>>> routines;

    pos_token = 0;

    // Scan all tokens and find real parsing routine definitions.
    while (pos_token < (int)tokens.size()) {
        bool is_definition =
            tokens[pos_token].kind == WORD &&
            tokens[pos_token].value == "procedure" &&
            pos_token + 3 < (int)tokens.size() &&
            tokens[pos_token + 1].kind == WORD &&
            tokens[pos_token + 2].kind == PUNCT &&
            tokens[pos_token + 2].value == ";" &&
            tokens[pos_token + 3].kind == WORD &&
            tokens[pos_token + 3].value == "begin";

        if (is_definition) {
            string name = tokens[pos_token + 1].value;

            // Ignore parser's internal procedures.
            if (name != "skip" && name != "error") {
                pos_token += 4; // consume "procedure name ; begin"

                vector<Segment> body = parse_segments();

                pos_token++; // consume "end"
                pos_token++; // consume ";"

                routines.push_back({name, body});
            } else {
                pos_token++;
            }
        } else {
            pos_token++;
        }
    }

    vector<string> lines;

    for (const auto& routine : routines) {
        const string& name = routine.first;
        const vector<Segment>& body = routine.second;

        vector<vector<Symbol>> productions = expand_segments(body);

        vector<string> alternatives;

        for (const auto& production : productions) {
            alternatives.push_back(render_production(production));
        }

        // Sort alternatives lexicographically.
        // Do not remove duplicates.
        sort(alternatives.begin(), alternatives.end());

        string line = "<" + name + ">::=";

        for (int i = 0; i < (int)alternatives.size(); i++) {
            if (i > 0) {
                line.push_back('|');
            }
            line += alternatives[i];
        }

        lines.push_back(line);
    }

    // Sort grammar lines lexicographically.
    sort(lines.begin(), lines.end());

    for (const string& line : lines) {
        cout << line << '\n';
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


# -------------------- Tokenization --------------------

WORD = "word"
STRING = "string"
PUNCT = "punct"


def tokenize(source):
    """
    Convert the Pascal program into a list of tokens.

    Token format:
        (kind, value)

    Words are lowercased because keywords and identifiers are case-insensitive.
    """
    tokens = []
    i = 0
    n = len(source)

    while i < n:
        c = source[i]

        # Ignore whitespace.
        if c.isspace():
            i += 1
            continue

        # Word: maximal sequence of letters.
        if c.isalpha():
            word = []

            while i < n and source[i].isalpha():
                word.append(source[i].lower())
                i += 1

            tokens.append((WORD, "".join(word)))
            continue

        # String literal, for example: 'a', '+', 'NO'
        if c == "'":
            i += 1  # Skip opening apostrophe.

            value = []

            while i < n and source[i] != "'":
                value.append(source[i])
                i += 1

            i += 1  # Skip closing apostrophe.

            tokens.append((STRING, "".join(value)))
            continue

        # Every other character is punctuation.
        tokens.append((PUNCT, c))
        i += 1

    return tokens


# -------------------- Parser for the restricted Pascal structure --------------------

class Extractor:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def at_word(self, word):
        """
        Check whether the current token is the given lowercase word.
        """
        return (
            self.pos < len(self.tokens)
            and self.tokens[self.pos][0] == WORD
            and self.tokens[self.pos][1] == word
        )

    def current_value(self):
        return self.tokens[self.pos][1]

    def parse_segments(self):
        """
        Parse a sequence of segments until the matching End.

        Segment representation:

        1. Unconditional call:
              ("call", name)

        2. Conditional chain:
              ("if", branches, else_error)

           branches is a list of:
              (character, nested_segments)
        """
        segments = []

        while not self.at_word("end"):
            if self.at_word("if"):
                segments.append(self.parse_conditional())
            else:
                # Routine call:
                # Name ;
                name = self.current_value()

                self.pos += 1  # consume name
                self.pos += 1  # consume semicolon

                segments.append(("call", name))

        return segments

    def parse_conditional(self):
        """
        Parse an If / Else If / Else Error conditional chain.
        """
        branches = []
        else_error = False

        # Current token is "if".
        self.pos += 1

        while True:
            # Parse:
            # Peek = 'c' Then Begin Skip ; ...

            self.pos += 1  # consume "peek"
            self.pos += 1  # consume "="

            ch = self.current_value()[0]
            self.pos += 1  # consume character literal

            self.pos += 1  # consume "then"
            self.pos += 1  # consume "begin"

            self.pos += 1  # consume "skip"
            self.pos += 1  # consume ";"

            # Parse nested branch body.
            inner_segments = self.parse_segments()

            self.pos += 1  # consume "end"

            branches.append((ch, inner_segments))

            # After End, either:
            # - Else If ...
            # - Else Error ;
            # - ; and the conditional ends.
            if self.at_word("else"):
                self.pos += 1  # consume "else"

                if self.at_word("if"):
                    self.pos += 1  # consume "if"
                    continue

                # Otherwise this is "Error;"
                self.pos += 1  # consume "error"
                self.pos += 1  # consume ";"

                else_error = True
                break

            else:
                self.pos += 1  # consume ";"
                break

        return ("if", branches, else_error)

    def find_routines(self):
        """
        Scan the token list and extract real parsing routine definitions.

        A real definition has token pattern:
            procedure name ; begin

        Forward declarations have:
            procedure name ; forward

        Internal Skip and Error are ignored.
        """
        routines = []
        self.pos = 0

        while self.pos < len(self.tokens):
            is_definition = (
                self.tokens[self.pos][0] == WORD
                and self.tokens[self.pos][1] == "procedure"
                and self.pos + 3 < len(self.tokens)
                and self.tokens[self.pos + 1][0] == WORD
                and self.tokens[self.pos + 2][0] == PUNCT
                and self.tokens[self.pos + 2][1] == ";"
                and self.tokens[self.pos + 3][0] == WORD
                and self.tokens[self.pos + 3][1] == "begin"
            )

            if is_definition:
                name = self.tokens[self.pos + 1][1]

                if name not in ("skip", "error"):
                    self.pos += 4  # consume "procedure name ; begin"

                    body = self.parse_segments()

                    self.pos += 1  # consume "end"
                    self.pos += 1  # consume ";"

                    routines.append((name, body))
                else:
                    self.pos += 1
            else:
                self.pos += 1

        return routines


# -------------------- Grammar expansion --------------------

def expand_segment(segment):
    """
    Expand one segment into all possible productions.

    A production is represented as a list of symbols.

    Symbol representation:
        ("terminal", character)
        ("nonterminal", name)
    """
    kind = segment[0]

    if kind == "call":
        name = segment[1]
        return [[("nonterminal", name)]]

    # Conditional segment.
    _, branches, else_error = segment

    result = []

    for ch, inner_segments in branches:
        terminal_symbol = ("terminal", ch)

        # Branch contributes the consumed character followed by its body.
        for inner_production in expand_segments(inner_segments):
            result.append([terminal_symbol] + inner_production)

    # If there is no Else Error, doing nothing is also successful.
    if not else_error:
        result.append([])

    return result


def expand_segments(segments):
    """
    Expand a sequence of segments.

    Sequential execution means Cartesian-product concatenation.
    """
    result = [[]]  # One empty prefix.

    for segment in segments:
        alternatives = expand_segment(segment)
        new_result = []

        for prefix in result:
            for suffix in alternatives:
                new_result.append(prefix + suffix)

        result = new_result

    return result


def render_production(production):
    """
    Convert one production into BNF text.

    Adjacent terminals are merged into one quoted string.
    """
    output = []
    i = 0

    while i < len(production):
        typ, value = production[i]

        if typ == "terminal":
            chars = []

            while i < len(production) and production[i][0] == "terminal":
                chars.append(production[i][1])
                i += 1

            output.append("'" + "".join(chars) + "'")

        else:
            output.append("<" + value + ">")
            i += 1

    # Empty production becomes an empty string.
    return "".join(output)


# -------------------- Main solving logic --------------------

def solve():
    source = sys.stdin.read()
    tokens = tokenize(source)

    extractor = Extractor(tokens)
    routines = extractor.find_routines()

    lines = []

    for name, body in routines:
        productions = expand_segments(body)

        alternatives = [
            render_production(production)
            for production in productions
        ]

        # Sort alternatives but do not remove duplicates.
        alternatives.sort()

        line = "<" + name + ">::=" + "|".join(alternatives)
        lines.append(line)

    lines.sort()

    sys.stdout.write("\n".join(lines) + "\n")


if __name__ == "__main__":
    solve()
```