A LevelComputer ScienceCambridge (CIE)Exam Questions16. System SoftwareTranslation Software

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

Exam code: 9618

1 hour18 questions
1a
4 marks

Several syntax diagrams are shown.

Flowchart with categories: letter (A, E, I, O, U, Y), symbol (#, $, ?, &, @), operator (+, -, *, /), digit (0-9); label and equation processes.

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

<operator> ::= ..................................................

<label> ::= ........................................................

<equation> ::= ..................................................

How did you do?

1b
5 marks

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

(i) Draw a syntax diagram for password.

(3)

(ii) Write the BNF for password.

(2)

How did you do?

2a
2 marks

Several syntax diagrams are shown.

Flowchart illustrating categorisation of odd, even, symbols, and letters with arrows indicating progression. Second diagram classifies numbers by odd and even.

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

21

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

123

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

How did you do?

2b
2 marks

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

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

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

How did you do?

2c
5 marks

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)

How did you do?

3a
3 marks

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

5 2 + 9 3 - / 3 *

How did you do?

3b
2 marks

Write this infix expression in RPN:

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

How did you do?

3c
4 marks

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.

Twelve columns of identical vertical grids, each divided into four equal rectangles, aligned in a row against a plain background.

How did you do?

4a
2 marks

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

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

How did you do?

4b
4 marks

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.

Thirteen vertical columns of equal-sized rectangles, each containing four stacked smaller rectangles, evenly spaced in rows.

How did you do?

4c
3 marks

Write this RPN expression in infix form:

b a c - + d b + * c /

How did you do?

5
2 marks

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

5 2 – 5 4 + * 9 /

How did you do?

6
3 marks

Explain how an expression stored in RPN can be evaluated.

How did you do?

7
2 marks

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

(p - q) / r + s * 3

How did you do?

8
2 marks

A program written in a high-level language is run using an interpreter.

Tick (✓) one box in each row to show whether each statement about how the interpreter executes the program is true or false.

Statement

True

False

The interpreter checks each statement for errors before it executes that statement.

The interpreter translates the whole program into an executable file before it executes any statement.

The statements inside a loop are interpreted again on every iteration of the loop.

After the program has been run once, it can be run again without being interpreted again.

How did you do?

9
3 marks

A program that is run using an interpreter contains this loop.

FOR Index ← 1 TO 1000

    Total ← Total + Reading[Index]

NEXT Index

A student makes this claim:

"The interpreter translates the statement inside the loop once. It stores the translated version and reuses it on each pass of the loop. When the program is run again next week, the stored version is used again."

Explain why the student's claim is wrong.

How did you do?

10
3 marks

Write this Reverse Polish Notation (RPN) expression in infix form.

a b c * + d a - /

How did you do?

11
4 marks

A program is run using an interpreter. The line numbers are for reference only and are not part of the program. Variable declarations are not shown.

01  Total ← 0

02  FOR Count ← 1 TO 3

03      OUTPUT "Pass ", Count

04      Total ← Total + Count

05  NEXT Count

06  OUTPUT "Total is ", Total

07  Average ← Total /

08  OUTPUT Average

Line 07 contains a syntax error. There are no other errors in the program.

Describe what happens when the program is run using the interpreter.

How did you do?

12
2 marks

The compilation of a program takes place in stages.

Name the stage of compilation described by each statement.

(i) The source code is converted from a sequence of characters into a sequence of tokens.

(1)

(ii) The program is changed to minimise its execution time and its memory requirement.

(1)

How did you do?

13
2 marks

A game uses a short code to unlock each level. The Backus-Naur Form (BNF) for a code is shown.

<letter> ::= A | B | C | D

<digit> ::= 1 | 2 | 3 | 4 | 5

<symbol> ::= # | @ | %

<code> ::= <letter><digit><digit> | <letter><digit><symbol>

State whether each of the following codes is valid or invalid for <code>. Give a reason for your choice in each case.

C4%

B6@

How did you do?

14
3 marks

A program contains this statement.

Cost ← Price + * Quantity

The statement contains an error. The program is compiled.

Identify the stage of compilation at which this error is reported, and explain why the error is not reported during lexical analysis.

How did you do?

15
4 marks

A program contains this statement.

Area ← Length * Width + 10

The statement contains no errors. The program is compiled.

Describe what happens to this statement at each stage of compilation.

How did you do?

16
4 marks

The Reverse Polish Notation (RPN) expression:

a b c d + * - e /

is to be evaluated when a = 40, b = 3, c = 2, d = 4 and e = 11.

Show the changing contents of the stack as the RPN expression is evaluated. Complete the table. Each column shows the stack after one more item has been read. Fill each column from the bottom row upwards.

Item read

a

b

c

d

+

*

-

e

/

Bottom of stack

How did you do?

17
3 marks

A parcel locker is opened with a code. The Backus-Naur Form (BNF) for some parts of the code is shown.

<letter> ::= P | Q | R | S | T

<digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<symbol> ::= # | @ | %

A new syntax rule, <locker>, is required. A locker code must begin with two letters, followed by one digit or one symbol, and end with one or two digits.

Write the BNF for <locker>.

How did you do?

18
5 marks

A weather station sends its temperature readings to a computer as text. The Backus-Naur Form (BNF) for some parts of the text is shown.

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<sign> ::= + | -

The following rules are also needed.

  • An integer contains one or more digits.

  • A reading is an integer that may have one sign in front of it.

  • A message contains one or more readings. When a message has more than one reading, a comma separates each reading from the next one.

For example, 25 and 12,-3,+40 are both valid messages.

Write the BNF for <integer>, <reading> and <message>.

How did you do?