time limit per test: 0.25
sec.
memory limit per test: 262144
KB
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.
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 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.
Note that this parser and this grammar correspond to arithmetic expressions involving binary numbers and two constants 'PE'
and 'PI'
.