Problem 118: PASIC

Description

PASIC is a simple programming language, as its name suggests, it is a cross between PAScal and baSIC. The entire language is defined by the following BNF specification.

In this version of BNF,

the symbol == means is defined to be
the vertical bar symbol | represents a choice
enclosure inside { curly brackets } indicates an optional item (or items)
a word inside " quotes " is a reserved word or symbol of the language
a word not in quotes is replaced by that word's definition according to the BNF.

PASIC Syntax

      program == "PROGRAM" block

      block == "BEGIN" statementlist "END"

      statementlist == statement { ";" statementlist }

      statement == block | assign | output | conditional | loop

      assign == variable ":=" expression

      expression == variable | constant | "(" expression operator expression ")"

      operator == "+" | "-" | "*" | "/" | "=" | "<" | ">"

      output == "PRINT" outputitemlist

      outputitemlist == outputitem { "," outputitemlist }

      outputitem == expression | string | "NEWLINE"

      conditional == "IF" expression "THEN" statement

      loop == "WHILE" expression "DO" statement

      variable: see lexical rules

      constant: see lexical rules

      string: see lexical rules

Lexical Rules

case (capital vs. little) is always irrelevant except inside a string.
a string begins with a single quote ', and consists of all characters up to the next single quote. A string may not contain newlines or single quotes. A string will contain at least one character.
a variable is either a single letter or a single letter followed by a single digit.
a constant is any non-empty sequence of digits.
white-space is allowed and completely ignored between lexical elements.
no lexeme (symbol, string, word, etc) may be more than 100 characters long

So, a program in PASIC consists of the word "program" followed by a block. A block consists of the words "begin" and "end" surrounding a statement-list. A statement-list always consists of at least one statement; after that one statement there may be a semicolon followed by a further statement-list. This has the overall effect of saying that a statement-list consists of any (non-zero) number of statements separated by semicolons. Each statement is either another block, and assignment statement, an output statement, a conditional statement, or a loop statement.

The Problem

You must write a program that reads a PASIC program as input, and runs it. The output from your program should be exactly the output that the PASIC program would produce if it were run.

You may safely assume that the input will be a single, perfectly correct, PASIC program, immediately followed by the end-of-file. The syntax and lexical rules will be followed exactly. Execution of the program will never result in a division by zero, and no numeric results or intermediate results will be less than 2^-31 or greater than or equal to 2³¹. The program will not contain any infinite loops. You will ceratinly not be required to perform any "optimisations" on the PASIC program to get the desired results.

Semantics

There are only 270 different variables available in a PASIC program; each of them is predeclared as a global integer variable, and initialised to zero.
All variables are integers, all computations produce integer results.
The seven operators have their normal programming language meanings; the = operator is an equality test, not an assignment.
The three relational operators =, <, and > return 1 for true, and 0 for false.
Expressions have their obvious meanings.
The five kinds of statement each have their obvious meanings.
- A block is just a sequence of statements that are executed one-by-one in turn.
- An assignment first computes the value of its expression, then sets the variable to that value.
- An output statement evaluates each of its items, and prints them one-by-one in turn. No spaces or newlines are printed unless they explicitly appear in a print statement. Numbers are printed in decimal without leading zeros (except of course that the number 0 is printed as 0). A - sign is printed before a number if it is negative. Printing "newline" starts a new line of output.
- A conditional statement evaluates its expression, and if the value of the expression is non-zero, its statement is executed. A conditional statement has no effect if its condition is false (zero).
- A while statement is best understood in terms of an equivalence: WHILE C DO S is equivalent to IF C THEN BEGIN S; WHILE C DO S END.

Input Format

The input will be a single perfectly correct PASIC program. It may occupy more than one line. No line will contain more than 100 characters.

Output Format

The output should be exactly the output that would be produced by running the PASIC program. Only print statements produce any output. Print an extra newline after the PASIC program terminates, so that all output lines will be properly terminated even if the PASIC program afils to print a newline, and there will be an extra blank line at the end if the PASIC program does print a final newline.

Sample Input 1

program begin
  x:=12;
  y:=34;
  z:=((x*2)+y);
  print z    
end

Sample Output 1

Sample Input 2

PROGRAM
  BEGIN
    n:=7;
    f:=1;
    n1:=n;
    WHILE (n1>0) DO
      BEGIN
        f:=(f*n1);
        n1:=(n1-1)
      END;
    PRINT n, '! = ', f, NEWLINE
  END

Sample Output 2

7! = 5040

Sample Input 3

program begin
  i:=1;
  while (i<10) do begin
    j:=1;
    while (j<10) do begin
      p:=(i*j);
      if (p<10) then print ' ';
      print ' ', p;
      j:=(j+1) end;
    print newline;
    i:=(i+1) end end

Sample Output 3

  1  2  3  4  5  6  7  8  9
  2  4  6  8 10 12 14 16 18
  3  6  9 12 15 18 21 24 27
  4  8 12 16 20 24 28 32 36
  5 10 15 20 25 30 35 40 45
  6 12 18 24 30 36 42 48 54
  7 14 21 28 35 42 49 56 63
  8 16 24 32 40 48 56 64 72
  9 18 27 36 45 54 63 72 81