{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv align\u003d\"left\"\u003eA typical top-down parser is a very simple application. We will consider parsers written in Pascal that obey the following structure: \u003cbr\u003e\u003cpre\u003e\u003cbr\u003eProgram Parser;\u003cbr\u003eProcedure Skip; Forward;\u003cbr\u003eFunction Peek:Char; Forward;\u003cbr\u003eProcedure Error; Forward;\n\u003cbr\u003e\u0026lt;parsing routines forward-declarations\u0026gt;\u003cbr\u003e\u0026lt;parsing routines\u0026gt;\n\u003cbr\u003eVar\u003cbr\u003e St:String;\u003cbr\u003e Pos:Integer;\u003cbr\u003eProcedure Error;\u003cbr\u003eBegin\u003cbr\u003e WriteLn(\u0027NO\u0027);\u003cbr\u003e Halt;\u003cbr\u003eEnd;\u003cbr\u003eProcedure Skip;\u003cbr\u003eBegin\u003cbr\u003e Inc(Pos);\u003cbr\u003e If Pos\u0026gt;Length(St) Then Error;\u003cbr\u003eEnd;\u003cbr\u003eFunction Peek:Char;\u003cbr\u003eBegin\u003cbr\u003e Peek:\u003dSt[Pos];\u003cbr\u003eEnd;\u003cbr\u003eBegin\u003cbr\u003e ReadLn(St);\u003cbr\u003e St:\u003dSt+\u0027#\u0027;\u003cbr\u003e Pos:\u003d1;\u003cbr\u003e Parse;\u003cbr\u003e If Pos\u003dLength(St) Then WriteLn(\u0027YES\u0027) Else WriteLn(\u0027NO\u0027);\u003cbr\u003eEnd.\u003c/pre\u003e \u003cbr\u003eThe part labeled \u003ccode\u003e\u0026lt;parsing routines forward-declarations\u0026gt;\u003c/code\u003e contains a definition for each of the parsing functions, followed by \u003ccode\u003eForward;\u003c/code\u003e. The part labeled \u003ccode\u003e\u0026lt;parsing routines\u0026gt;\u003c/code\u003e contains a definition followed by a body for each of the parsing routines. \u003cbr\u003e \u003cbr\u003eA definition of a parsing routine is: \u003cbr\u003e\u003cpre\u003e\u003cbr\u003eProcedure \u0026lt;name\u0026gt;;\u003c/pre\u003e \u003cbr\u003eThe 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\u0027s internal functions (\u003ccode\u003eSkip\u003c/code\u003e, \u003ccode\u003ePeek\u003c/code\u003e or \u003ccode\u003eError\u003c/code\u003e). A body of a parsing routine is: \u003cbr\u003e\u003cpre\u003e\u003cbr\u003eBegin\u003cbr\u003e \u0026lt;segment\u0026gt;\u003cbr\u003e \u0026lt;segment\u0026gt;\u003cbr\u003e ...\u003cbr\u003e \u0026lt;segment\u0026gt;\u003cbr\u003eEnd;\u003c/pre\u003e \u003cbr\u003eThere must be at least one segment. Each segment is either an unconditional segment, or a conditional segment. \u003cbr\u003e \u003cbr\u003eAn unconditional segment is a routine call: \u003ccode\u003e\u0026lt;name\u0026gt;;\u003c/code\u003e, where \u003ccode\u003e\u0026lt;name\u0026gt;\u003c/code\u003e is a name of some parsing routine. \u003cbr\u003e \u003cbr\u003eA conditional segment has the following structure: \u003cbr\u003e\u003cpre\u003e\u003cbr\u003eIf Peek\u003d\u0026lt;character\u0026gt; Then Begin\u003cbr\u003e Skip;\u003cbr\u003e \u0026lt;segment\u0026gt;\u003cbr\u003e \u0026lt;segment\u0026gt;\u003cbr\u003e ...\u003cbr\u003e \u0026lt;segment\u0026gt;\u003cbr\u003eEnd Else If Peek\u003d\u0026lt;character\u0026gt; Then Begin\u003cbr\u003e Skip;\u003cbr\u003e \u0026lt;segment\u0026gt;\u003cbr\u003e \u0026lt;segment\u0026gt;\u003cbr\u003e ...\u003cbr\u003e \u0026lt;segment\u0026gt;\u003cbr\u003eEnd Else If Peek\u003d\u0026lt;character\u0026gt; Then Begin\u003cbr\u003e...\u003cbr\u003eEnd Else If Peek\u003d\u0026lt;character\u0026gt; Then Begin\u003cbr\u003eEnd;\u003c/pre\u003e \u003cbr\u003eWhere each \u003ccode\u003e\u0026lt;segment\u0026gt;\u003c/code\u003e is again either unconditional or conditional. The simplest form of a conditional segment has only one \u003ccode\u003eIf\u003c/code\u003e and no \u003ccode\u003eElse\u003c/code\u003e. Note that we always skip a character after guessing it right, and that\u0027s the only case where we invoke \u003ccode\u003eSkip;\u003c/code\u003e. Each \u003ccode\u003e\u0026lt;character\u0026gt;\u003c/code\u003e is a non-apostrophe character with ASCII code between 33 and 126 wrapped in apostrophes, like \u003ccode\u003e\u0027a\u0027\u003c/code\u003e. It is not necessary to have at least one \u003ccode\u003e\u0026lt;segment\u0026gt;\u003c/code\u003e after \u003ccode\u003eSkip;\u003c/code\u003e in the \u003ccode\u003eIf\u003c/code\u003e body. The last \u003ccode\u003eEnd;\u003c/code\u003e can also be written as \u003ccode\u003eEnd Else Error;\u003c/code\u003e, meaning that all other peek outcomes are unacceptable. \u003cbr\u003e \u003cbr\u003eThe 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 \u003ccode\u003eParse\u003c/code\u003e. \u003cbr\u003e \u003cbr\u003eSuch 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\u0027t care about it, just blindly apply the rules): \u003cbr\u003e\u003cul\u003e \u003cbr\u003e\u003cli\u003eThe set of nonterminal symbols of the grammar is the same as the set of parsing routine names in the parser.\u003c/li\u003e \u003cbr\u003e\u003cli\u003eThe set of terminal symbols of the grammar is the set of characters with ASCII codes between 33 and 126, except apostrophe.\u003c/li\u003e \u003cbr\u003e\u003cli\u003eFor each (even seemingly impossible, like duplicate \u003ccode\u003ePeek\u003d...\u003c/code\u003e conditions) way of evaluating all \u003ccode\u003eIf\u003c/code\u003e\u0027s in the body of some routine that do not result in a call to \u003ccode\u003eError;\u003c/code\u003e, there should be one production rule concatenating the corresponding nonterminals and terminals (see example for further clarification).\u003c/li\u003e \u003cbr\u003e\u003cli\u003eThe starting symbol should be \u003ccode\u003eParse\u003c/code\u003e.\u003c/li\u003e \u003cbr\u003e\u003c/ul\u003eYour 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 \u003ccode\u003e\u0027AB\u0027\u003c/code\u003e instead of \u003ccode\u003e\u0027A\u0027\u0027B\u0027\u003c/code\u003e. Your output should contain exactly \u003ci\u003en\u003c/i\u003e lines, where \u003ci\u003en\u003c/i\u003e is the number of parsing routines in the input. \u003cbr\u003e \u003cbr\u003eThe nonterminals must be written in lowercase. The production rules inside a line must be sorted lexicographically, and the lines must be sorted lexicographically, too. \u003cbr\u003e \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eThe 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. \u003cbr\u003e \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eOutput 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. \u003cbr\u003e \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eSample test(s)\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eInput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003cbr\u003eProgram Parser;\u003cbr\u003eProcedure Skip; Forward;\u003cbr\u003eFunction Peek:Char; Forward;\u003cbr\u003eProcedure Error; Forward;\n\u003cbr\u003eProcedure Parse; Forward;\u003cbr\u003eProcedure Addend; Forward;\u003cbr\u003eProcedure Term; Forward;\u003cbr\u003eProcedure Number; Forward;\n\u003cbr\u003eProcedure Term;\u003cbr\u003eBegin\u003cbr\u003e If Peek\u003d\u00270\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e Number;\u003cbr\u003e End Else If Peek\u003d\u00271\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e Number;\u003cbr\u003e End Else If Peek\u003d\u0027(\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e Parse;\u003cbr\u003e If Peek\u003d\u0027)\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e End Else Error;\u003cbr\u003e End Else If Peek\u003d\u0027P\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e If Peek\u003d\u0027I\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e End Else If Peek\u003d\u0027E\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e End Else Error; \u003cbr\u003e End Else Error;\u003cbr\u003eEnd;\n\u003cbr\u003eProcedure Number;\u003cbr\u003eBegin\u003cbr\u003e If Peek\u003d\u00270\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e Number;\u003cbr\u003e End Else If Peek\u003d\u00271\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e Number;\u003cbr\u003e End;\u003cbr\u003eEnd;\n\u003cbr\u003eProcedure Addend;\u003cbr\u003eBegin\u003cbr\u003e Term;\u003cbr\u003e If Peek\u003d\u0027*\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e Addend;\u003cbr\u003e End Else If Peek\u003d\u0027/\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e Addend;\u003cbr\u003e End;\u003cbr\u003eEnd;\n\u003cbr\u003eProcedure Parse;\u003cbr\u003eBegin\u003cbr\u003e Addend;\u003cbr\u003e If Peek\u003d\u0027+\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e Parse;\u003cbr\u003e End Else If Peek\u003d\u0027-\u0027 Then Begin\u003cbr\u003e Skip;\u003cbr\u003e Parse;\u003cbr\u003e End;\u003cbr\u003eEnd;\n\u003cbr\u003eVar\u003cbr\u003e St:String;\u003cbr\u003e Pos:Integer;\n\u003cbr\u003eProcedure Error;\u003cbr\u003eBegin\u003cbr\u003e WriteLn(\u0027NO\u0027);\u003cbr\u003e Halt;\u003cbr\u003eEnd;\n\u003cbr\u003eProcedure Skip;\u003cbr\u003eBegin\u003cbr\u003e Inc(Pos);\u003cbr\u003e If Pos\u0026gt;Length(St) Then Error;\u003cbr\u003eEnd;\n\u003cbr\u003eFunction Peek:Char;\u003cbr\u003eBegin\u003cbr\u003e Peek:\u003dSt[Pos];\u003cbr\u003eEnd;\u003cbr\u003eBegin\u003cbr\u003e ReadLn(St);\u003cbr\u003e St:\u003dSt+\u0027#\u0027;\u003cbr\u003e Pos:\u003d1;\u003cbr\u003e Parse;\u003cbr\u003e If Pos\u003dLength(St) Then WriteLn(\u0027YES\u0027) Else WriteLn(\u0027NO\u0027);\u003cbr\u003eEnd.\u003c/pre\u003e \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eOutput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003cbr\u003e\u0026lt;addend\u0026gt;::\u003d\u0026lt;term\u0026gt;|\u0026lt;term\u0026gt;\u0027*\u0027\u0026lt;addend\u0026gt;|\u0026lt;term\u0026gt;\u0027/\u0027\u0026lt;addend\u0026gt;\u003cbr\u003e\u0026lt;number\u0026gt;::\u003d|\u00270\u0027\u0026lt;number\u0026gt;|\u00271\u0027\u0026lt;number\u0026gt;\u003cbr\u003e\u0026lt;parse\u0026gt;::\u003d\u0026lt;addend\u0026gt;|\u0026lt;addend\u0026gt;\u0027+\u0027\u0026lt;parse\u0026gt;|\u0026lt;addend\u0026gt;\u0027-\u0027\u0026lt;parse\u0026gt;\u003cbr\u003e\u0026lt;term\u0026gt;::\u003d\u0027(\u0027\u0026lt;parse\u0026gt;\u0027)\u0027|\u00270\u0027\u0026lt;number\u0026gt;|\u00271\u0027\u0026lt;number\u0026gt;|\u0027PE\u0027|\u0027PI\u0027\u003c/pre\u003e \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eNote\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eNote that this parser and this grammar correspond to arithmetic expressions involving binary numbers and two constants \u003ccode\u003e\u0027PE\u0027\u003c/code\u003e and \u003ccode\u003e\u0027PI\u0027\u003c/code\u003e. \u003cbr\u003e \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003chr\u003e\u003c/div\u003e\u003ctable align\u003d\"left\" cellspacing\u003d\"7\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd\u003eAuthor:\u003c/td\u003e\u003ctd\u003ePetr Mitrichev \u003cbr\u003e \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eResource:\u003c/td\u003e\u003ctd\u003ePetr Mitrichev Contest 3 \u003cbr\u003e \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eDate:\u003c/td\u003e\u003ctd\u003eSeptember 01, 2007 \u003cbr\u003e \u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e \u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\r\n\u003c/div\u003e"}}]}