<|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

You are given the source code of a specially structured Pascal top-down parser. Its parsing routines consist only of:

- calls to other parsing routines, and
- `If Peek='c' Then Begin Skip; ... End ...` conditional chains, optionally ending with `Else Error;`.

From this parser, reconstruct the formal grammar it encodes.

Rules:

- Each parsing routine is a nonterminal, printed lowercase as `<name>`.
- Each successful way through a routine body gives one production.
- A condition `Peek='c'` followed by `Skip;` contributes terminal `'c'`.
- A routine call contributes the corresponding nonterminal.
- If a conditional chain has no final `Else Error`, then "do nothing" is also a valid alternative.
- Output one BNF line per routine, sorted lexicographically.
- Alternatives inside each line must also be sorted lexicographically.
- Adjacent terminals must be merged, e.g. output `'AB'`, not `'A''B'`.

Input size is at most 10000 bytes.

---

## 2. Detailed editorial

### Observations

The Pascal parser has a very restricted structure. We do not need to understand arbitrary Pascal. We only need to recognize:

1. Procedure definitions of parsing routines.
2. Procedure bodies containing segments.
3. Conditional chains of the form:

```pascal
If Peek='x' Then Begin
  Skip;
  ...
End Else If Peek='y' Then Begin
  Skip;
  ...
End Else Error;
```

or without the final `Else Error`.

Every non-error execution path through a routine body becomes a production rule.

For example:

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

There are three successful paths:

1. First branch: consume `'0'`, call `Number`.
2. Second branch: consume `'1'`, call `Number`.
3. No branch matches, because there is no `Else Error`.

So the grammar is:

```text
<number>::=|'0'<number>|'1'<number>
```

The empty alternative appears first because alternatives are sorted lexicographically.

---

### Step 1: Tokenization

Whitespace and letter case are irrelevant in most places, so the first step is to convert the entire Pascal program into tokens.

We use three token types:

```cpp
enum tok_kind {
    word_tok,
    str_tok,
    punct_tok
};
```

- A `word_tok` is a maximal sequence of English letters, converted to lowercase.
- A `str_tok` is a Pascal string literal, preserving its contents.
- A `punct_tok` is any other single character, such as `;`, `=`, `(`, `)`.

For example:

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

becomes roughly:

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

Because the input is guaranteed to be valid, the parser can consume expected tokens without extensive error checking.

---

### Step 2: Parse routine bodies into an AST-like structure

Each routine body is a list of segments.

A segment is either:

1. An unconditional call:

```pascal
Number;
```

represented as:

```cpp
conditional = false
call_name = "number"
```

2. A conditional chain:

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

represented as a list of branches:

```text
branch '0' -> [call Number]
branch '1' -> [call Number]
else_error = true
```

If there is no final `Else Error`, then `else_error = false`, which means the conditional also has an empty alternative.

---

### Step 3: Find parsing routine definitions

Forward declarations look like:

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

Real definitions look like:

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

So we scan the token list and look for:

```text
procedure <name> ; begin
```

We ignore internal procedures `Skip` and `Error`.

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

For each real parsing routine, we parse its body into a vector of segments.

---

### Step 4: Expand a segment into productions

Each segment expands into a list of possible symbol sequences.

Symbols are either:

- terminal characters, e.g. `'0'`
- nonterminals, e.g. `<number>`

#### Unconditional call

```pascal
Number;
```

expands to:

```text
<number>
```

#### Conditional segment

For each branch:

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

we produce:

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

If the conditional chain does not end with `Else Error`, we also add the empty sequence.

---

### Step 5: Expand a list of segments

A routine body is a sequence of segments, so the production alternatives are the Cartesian product of all segment expansions.

For example:

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

First segment:

```text
<term>
```

Second segment:

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

Combined result:

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

---

### Step 6: Render and sort

A production is rendered by printing:

- terminals inside apostrophes,
- adjacent terminals as one string literal,
- nonterminals inside angle brackets.

For example, terminal `P` followed by terminal `I` becomes:

```text
'PI'
```

Finally:

- sort alternatives within each nonterminal line,
- sort all lines lexicographically,
- print exactly one line per parsing routine.

---

### Complexity

The input and output are both limited to 10000 bytes. The algorithm is linear in the input size for tokenization and parsing, plus the size of the expanded output. Since the output size is guaranteed not to exceed 10000 bytes, this is easily fast enough.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

string src;

enum tok_kind { word_tok, str_tok, punct_tok };

struct token {
    tok_kind kind;
    string val;
};

struct symbol {
    bool terminal;
    char ch;
    string name;
};

struct segment {
    bool conditional;
    string call_name;
    vector<pair<char, vector<segment>>> branches;
    bool else_error;
};

vector<token> toks;
size_t pos;

void tokenize() {
    size_t i = 0, n = src.size();
    while(i < n) {
        char c = src[i];
        if(isspace((unsigned char)c)) {
            i++;
            continue;
        }

        if(isalpha((unsigned char)c)) {
            string w;
            while(i < n && isalpha((unsigned char)src[i])) {
                w += (char)tolower((unsigned char)src[i]);
                i++;
            }
            toks.push_back({word_tok, w});
        } else if(c == '\'') {
            i++;
            string content;
            while(i < n) {
                if(src[i] == '\'') {
                    if(i + 1 < n && src[i + 1] == '\'') {
                        content += '\'';
                        i += 2;
                    } else {
                        i++;
                        break;
                    }
                } else {
                    content += src[i];
                    i++;
                }
            }
            toks.push_back({str_tok, content});
        } else {
            toks.push_back({punct_tok, string(1, c)});
            i++;
        }
    }
}

bool at_word(const string& w) {
    return toks[pos].kind == word_tok && toks[pos].val == w;
}

vector<segment> parse_segments();

segment parse_conditional() {
    segment s;
    s.conditional = true;
    s.else_error = false;
    pos++;  // if
    while(true) {
        pos++;  // peek
        pos++;  // =
        char c = toks[pos].val[0];
        pos++;  // character literal
        pos++;  // then
        pos++;  // begin
        pos++;  // skip
        pos++;  // ;
        vector<segment> inner = parse_segments();
        pos++;  // end
        s.branches.push_back({c, std::move(inner)});

        if(at_word("else")) {
            pos++;  // else
            if(at_word("if")) {
                pos++;  // if
                continue;
            }
            pos++;  // error
            pos++;  // ;
            s.else_error = true;
            break;
        }

        pos++;  // ;
        break;
    }

    return s;
}

vector<segment> parse_segments() {
    vector<segment> segs;
    while(!at_word("end")) {
        if(at_word("if")) {
            segs.push_back(parse_conditional());
        } else {
            segment s;
            s.conditional = false;
            s.call_name = toks[pos].val;
            pos++;  // name
            pos++;  // ;
            segs.push_back(std::move(s));
        }
    }

    return segs;
}

vector<vector<symbol>> expand_segments(const vector<segment>& segs);

vector<vector<symbol>> expand_segment(const segment& s) {
    if(!s.conditional) {
        symbol sym{false, 0, s.call_name};
        return {{sym}};
    }

    vector<vector<symbol>> out;
    for(const auto& br: s.branches) {
        symbol t{true, br.first, ""};
        for(auto& inner: expand_segments(br.second)) {
            vector<symbol> prod{t};
            prod.insert(prod.end(), inner.begin(), inner.end());
            out.push_back(std::move(prod));
        }
    }
    if(!s.else_error) {
        out.push_back({});
    }

    return out;
}

vector<vector<symbol>> expand_segments(const vector<segment>& segs) {
    vector<vector<symbol>> result = {{}};
    for(const auto& s: segs) {
        vector<vector<symbol>> seg_prods = expand_segment(s);
        vector<vector<symbol>> next;
        for(auto& a: result) {
            for(auto& b: seg_prods) {
                vector<symbol> c = a;
                c.insert(c.end(), b.begin(), b.end());
                next.push_back(std::move(c));
            }
        }
        result = std::move(next);
    }

    return result;
}

string render(const vector<symbol>& prod) {
    string out;
    size_t i = 0;
    while(i < prod.size()) {
        if(prod[i].terminal) {
            out += '\'';
            while(i < prod.size() && prod[i].terminal) {
                out += prod[i].ch;
                i++;
            }
            out += '\'';
        } else {
            out += '<';
            out += prod[i].name;
            out += '>';
            i++;
        }
    }

    return out;
}

void read() {
    stringstream ss;
    ss << cin.rdbuf();
    src = ss.str();
}

void solve() {
    // This is a pure parsing/implementation problem: read the Pascal source,
    // recover each parsing routine's body, and emit the grammar it encodes.
    //
    // The standard way to handle a task like this is to split it into two
    // stages. First a tokenizer walks the raw text once and turns it into a
    // flat list of tokens, collapsing all the optional whitespace away: a
    // maximal run of letters becomes one case-folded word token, a run wrapped
    // in apostrophes becomes a string token, and every other byte is its own
    // punctuation token. After this stage the language is regular in the
    // tokens, so the messy "whitespace may appear anywhere between words" rule
    // never has to be thought about again.
    //
    // The second stage is a recursive-descent parser over that token list. A
    // single cursor (pos) scans forward and each grammar construct gets one
    // function that consumes exactly its tokens and advances the cursor:
    // parse_segments reads a run of segments until the closing End, and
    // parse_conditional reads an If / Else-If / Else chain, recursing back into
    // parse_segments for each branch body. Because the input is guaranteed
    // well-formed we advance the cursor positionally instead of validating.
    //
    // A parsing routine is any "Procedure <name>; Begin ..." with Skip and
    // Error excluded and Peek being a Function, so a linear scan over the
    // tokens finds every definition and parses its body.
    //
    // Finally each body is expanded into productions. Evaluating the If's of a
    // routine in every non-Error way is just a cartesian product: a segment
    // list expands to the concatenation of its segments' expansions, an
    // unconditional call contributes its nonterminal, and a conditional
    // contributes, per branch, the guessed character (a terminal, since Skip
    // consumes it) followed by that branch's body, plus the empty alternative
    // when there is no trailing Else Error. Rendering merges adjacent terminals
    // into one quoted literal, and both the alternatives on a line and the
    // lines themselves are sorted lexicographically.

    tokenize();

    vector<pair<string, vector<segment>>> routines;
    pos = 0;
    while(pos < toks.size()) {
        bool is_def =
            toks[pos].kind == word_tok && toks[pos].val == "procedure" &&
            pos + 3 < toks.size() && toks[pos + 1].kind == word_tok &&
            toks[pos + 3].kind == word_tok && toks[pos + 3].val == "begin" &&
            toks[pos + 1].val != "skip" && toks[pos + 1].val != "error";
        if(is_def) {
            string name = toks[pos + 1].val;
            pos += 4;  // procedure name ; begin
            vector<segment> body = parse_segments();
            pos++;  // end
            pos++;  // ;
            routines.push_back({name, std::move(body)});
        } else {
            pos++;
        }
    }

    vector<string> lines;
    for(auto& [name, body]: routines) {
        vector<string> rendered;
        for(auto& prod: expand_segments(body)) {
            rendered.push_back(render(prod));
        }
        sort(rendered.begin(), rendered.end());

        string line = "<" + name + ">::=";
        for(size_t i = 0; i < rendered.size(); i++) {
            if(i) {
                line += '|';
            }
            line += rendered[i];
        }
        lines.push_back(line);
    }

    sort(lines.begin(), lines.end());
    for(auto& line: lines) {
        cout << line << "\n";
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python solution with detailed comments

```python
import sys


# Token kinds.
WORD = "word"      # Sequence of letters, converted to lowercase.
STRING = "string"  # Pascal string literal without surrounding apostrophes.
PUNCT = "punct"    # Single punctuation character.


def tokenize(src):
    """
    Convert the whole Pascal source into tokens.

    Each token is represented as a pair:
        (kind, value)
    """
    tokens = []             # Result token list.
    i = 0                   # Current source index.
    n = len(src)            # Source length.

    while i < n:
        c = src[i]          # Current character.

        # Whitespace is irrelevant.
        if c.isspace():
            i += 1
            continue

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

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

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

        # Pascal string literal.
        if c == "'":
            i += 1          # Skip opening apostrophe.
            content = []    # Literal contents.

            while i < n:
                if src[i] == "'":
                    # Pascal escapes an apostrophe as two apostrophes.
                    if i + 1 < n and src[i + 1] == "'":
                        content.append("'")
                        i += 2
                    else:
                        i += 1      # Closing apostrophe.
                        break
                else:
                    content.append(src[i])
                    i += 1

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

        # Everything else is punctuation.
        tokens.append((PUNCT, c))
        i += 1

    return tokens


class ParserExtractor:
    """
    Parses the restricted Pascal parser and extracts grammar productions.
    """

    def __init__(self, tokens):
        self.tokens = tokens    # Full token list.
        self.pos = 0            # Current token pointer.

    def at_word(self, word):
        """
        Return True if 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 current token value.
        """
        return self.tokens[self.pos][1]

    def parse_segments(self):
        """
        Parse a list of segments until the matching 'end'.

        Segment representation:
        - unconditional call:
              ("call", routine_name)
        - conditional:
              ("if", branches, else_error)

          where branches is a list of:
              (terminal_character, inner_segments)
        """
        segments = []

        while not self.at_word("end"):
            if self.at_word("if"):
                segments.append(self.parse_conditional())
            else:
                # Unconditional 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 = []              # Successful branches.
        else_error = False         # Whether the chain ends with Else Error.

        self.pos += 1              # Consume initial "if".

        while True:
            self.pos += 1          # Consume "peek".
            self.pos += 1          # Consume "=".

            ch = self.current_value()[0]  # Character literal content.
            self.pos += 1          # Consume string literal.

            self.pos += 1          # Consume "then".
            self.pos += 1          # Consume "begin".
            self.pos += 1          # Consume "skip".
            self.pos += 1          # Consume ";".

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

            self.pos += 1          # Consume "end".

            branches.append((ch, inner))

            if self.at_word("else"):
                self.pos += 1      # Consume "else".

                if self.at_word("if"):
                    self.pos += 1  # Consume "if".
                    continue       # Parse next branch.

                # Otherwise this is Else Error ;
                self.pos += 1      # Consume "error".
                self.pos += 1      # Consume ";".
                else_error = True
                break

            # No Else, so the End is followed by semicolon.
            self.pos += 1          # Consume ";".
            break

        return ("if", branches, else_error)

    def find_routines(self):
        """
        Scan the token list and parse every real parsing routine definition.

        A real definition has the token pattern:
            procedure name ; begin

        Forward declarations have:
            procedure name ; forward

        Internal procedures 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 + 3][0] == WORD
                and self.tokens[self.pos + 3][1] == "begin"
                and self.tokens[self.pos + 1][1] not in ("skip", "error")
            )

            if is_definition:
                name = self.tokens[self.pos + 1][1]
                self.pos += 4       # Consume procedure name ; begin.

                body = self.parse_segments()

                self.pos += 1       # Consume end.
                self.pos += 1       # Consume semicolon.

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

        return routines


def expand_segment(segment):
    """
    Expand one segment into a list of possible productions.

    A production is represented as a list of symbols:
    - terminal:    ("terminal", character)
    - nonterminal: ("nonterminal", name)
    """
    kind = segment[0]

    # Unconditional call contributes one nonterminal.
    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_prod in expand_segments(inner_segments):
            result.append([terminal_symbol] + inner_prod)

    # 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.

    Since segments are executed sequentially, alternatives are combined
    by Cartesian product and concatenation.
    """
    result = [[]]                  # One empty prefix initially.

    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(prod):
    """
    Convert a production into required BNF text.

    Adjacent terminal characters are merged into one quoted literal.
    """
    out = []
    i = 0

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

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

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

            out.append("'" + "".join(chars) + "'")
        else:
            out.append("<" + value + ">")
            i += 1

    return "".join(out)


def solve():
    src = sys.stdin.read()             # Read entire Pascal program.
    tokens = tokenize(src)             # Tokenize it.

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

    lines = []

    for name, body in routines:
        alternatives = []

        for prod in expand_segments(body):
            alternatives.append(render_production(prod))

        alternatives.sort()

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

    lines.sort()

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


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

---

## 5. Compressed editorial

Tokenize the whole Pascal program into lowercase words, string literals, and punctuation, ignoring whitespace. Scan tokens for real parsing routine definitions of the form `Procedure name ; Begin`, excluding internal `Skip` and `Error`.

Parse each routine body as a sequence of segments until `End`. A segment is either a routine call `name;` or an `If Peek='c' Then Begin Skip; ... End` chain. Store conditional chains as branches `(c, inner_body)` plus a flag saying whether the chain ends with `Else Error`.

To generate grammar productions, expand each routine body. A routine call expands to one nonterminal. A conditional branch expands to terminal `c` followed by all expansions of its inner body. If the conditional has no final `Else Error`, also add the empty expansion. A sequence of segments is expanded by Cartesian product concatenation.

Render productions by writing nonterminals as `<name>` and terminals in quotes, merging adjacent terminals. Sort alternatives in each line, sort all lines, and print them.
