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