Translation Software (Cambridge (CIE) A Level Computer Science): Exam Questions

Several syntax diagrams are shown.

State why each number is invalid for the given syntax diagrams.

21

Reason ..................................................

123

Reason ..................................................

Complete the Backus‑Naur Form (BNF) for the given syntax diagrams

<symbol> ::= ....................................

<number> ::= ....................................

A new syntax rule, code, is required. It must begin with a letter, followed by one or two numbers, and end with a symbol.

(i) Draw a syntax diagram for code.

(3)

(ii) Write the BNF for code.

(2)

Write this Reverse Polish Notation (RPN) in infix form:

5 2 + 9 3 - / 3 *

Write this infix expression in RPN:

((7 + 3) - (2 * 8)) / 6

Evaluate this RPN expression:

a b - c d + * e /

when

a = 17, b = 5, c = 7, d = 3 and e = 10

Show the changing contents of the stack as the RPN expression is evaluated.

Write this infix expression in Reverse Polish Notation (RPN):

(7 – 2 + 8) / (9 – 5)

Evaluate this RPN expression:

a d + a b + c - *

when

a = 6, b = 3, c = 7 and d = 9

Show the changing contents of the stack as the RPN expression is evaluated.

Write this RPN expression in infix form:

b a c - + d b + * c /

Write the infix expression for this Reverse Polish Notation (RPN) expression:

5 2 – 5 4 + * 9 /

Explain how an expression stored in RPN can be evaluated.