PLC Laboratory 5

Recursive Descent Parser

Using recursive descent, implement a parser of arithmetic expressions. These expressions contain +, -, *, / operators (with common priorities and left associativity) and parentheses. To simplify the task, consider we have only binary operators. There are no unary operators in our language. Moreover, we can use only positive integers in our expressions.

For the recursive descent use following grammar:

  E  :  T E1;        (1)
  E1 :  '+' T E1     (2)
     |  '-' T E1     (3)
     |  {e};         (4)
  T  :  F T1;        (5)
  T1 :  '*' F T1     (6)
     |  '/' F T1     (7)
     |  {e}          (8)
  F  :  '(' E ')'    (9)
     |  num          (10)

To simplify the solution you can use the lexical analyzer from Laboratory 2

Input specification

The first line of the input contains a number N. It defines the number of expressions your program should evaluate. These expressions are on next N lines. Each line contains exactly one expression.

Output specification

For each expression write one line containing numbers of grammar rules, that are used for parsing during the recursive descent. If there is any error in the input, write text ERROR instead.

Example

• Input

2
2 * (3+5)
15 - 2**7

• Output

1 5 10 6 9 1 5 10 8 2 5 10 8 4 8 4
ERROR