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