16.2 Translation Software
A Level · 34 questions found
What this topic covers
Section titled “What this topic covers”- How an interpreter executes programs without a translated version
- Compilation stages: lexical analysis, syntax analysis, code generation, optimisation
- Grammar notation: syntax diagrams and Backus-Naur Form (BNF)
- Reverse Polish Notation (RPN) for expression evaluation
Past paper questions
Section titled “Past paper questions”(a) Outline the purpose of lexical analysis during the compilation of a program. 2 marks
(b) Write the Reverse Polish Notation (RPN) for the given infix expression: 2 marks
(2 – 6) * (13 + 7) / 5
(c) The RPN expression: 4 marks
d a b + * c a ‑ /
is to be evaluated, where:
a = 6, b = 12, c = 15 and d = 5.
Show the changing contents of the stack as the RPN expression is evaluated.
Show mark scheme
8(a) [2 marks]
One mark per mark point ( Max 2 ) MP1 To convert the high-level source code / program into a sequence of tokens MP2 … that can be sent to the parser for syntax analysis MP3 To create a symbol table MP4 To remove the unnecessary white space and comments from the code
8(b) [2 marks]
One mark 2 6 – One mark 13 7 + * 5 / Complete answer 2 6 – 13 7 + * 5 /
8(c) [4 marks]
One mark per ring ( Max 4 ) 12 6 6 6 18 15 15 9 5 5 5 5 90 90 90 90 10
(a) A stack has been implemented using pseudocode to store a maximum of 100 string items using the global variables in the following table:
| Identifier | Data type | Description | Initialisation value |
|---|---|---|---|
| Base | INTEGER | pointer for the bottom of the stack | 0 |
| Top | INTEGER | pointer for the top of the stack | ‑1 |
| StackArray | STRING | 1D array to implement the stack | [0:99] |
| Max | INTEGER | maximum number of items in the stack | 100 |
The value of Top is incremented each time a data item is added to the stack and decremented every time a data item is removed.
(i) Complete the pseudocode for the function to remove a data item from the stack. 5 marks
FUNCTION Pop() DECLARE DataItem : STRING DataItem ""
IF ______ THEN
DataItem
Top ELSE DataItem "You cannot remove data; the stack is empty" ENDIF
ENDFUNCTION
(ii) Write the pseudocode to output the data item removed from the stack with an appropriate message. 1 mark
(b) A stack is used to implement recursion. 3 marks
State the three essential features of recursion.
1
2
3
Show mark scheme
9(a)(i) [5 marks]
One mark for each correctly completed line ( Max 5 ) FUNCTION Pop() RETURNS STRING DECLARE DataItem : STRING DataItem "" // IF Top > –1 Top >= Base THEN DataItem StackArray[Top] Top Top – 1 ELSE DataItem "You cannot remove data; the stack is empty" ENDIF // RETURN DataItem StackArray[Top + 1] ENDFUNCTION
9(a)(ii) [1 mark]
OUTPUT "The data removed from the stack is ", Pop()
9(b) [3 marks]
One mark per mark point ( Max 3 ) MP1 A recursive algorithm must call itself / have a general case MP2 It must have a base case / have a stopping condition MP3 It must change its state and move towards the base case
(a) State the purpose of the optimisation stage in the compilation of a program. 1 mark
(b) Convert this Reverse Polish Notation (RPN) back to its original infix form: 3 marks
a b - c + c a - * d /
(c) The RPN expression: 4 marks
c a / b d – * b +
is to be evaluated, where:
a = 3, b = 16, c = 9 and d = 6.
Show the changing contents of the stack as the RPN expression is evaluated.
Show mark scheme
8(a) [1 mark]
To improve the code by making it use minimum resources (CPU, memory/storage, time) // Answer by example: To improve the code by • minimising program storage • minimising CPU time • minimising memory use • minimising program execution time (includes peripheral use as well as CPU)
8(b) [3 marks]
One mark (a – b + c) One mark
- (c - a) One mark / d Complete answer (a – b + c) * (c - a) / d
8(c) [4 marks]
One mark per ring ( Max 4 ) 6 3 16 16 10 16 9 9 3 3 3 3 30 30 46
(a) A stack has been implemented using pseudocode to store a maximum of 100 string items using the global variables in the following table:
| Identifier | Data type | Description | Initialisation value |
|---|---|---|---|
| Base | INTEGER | pointer for the bottom of the stack | 0 |
| Top | INTEGER | pointer for the top of the stack | -1 |
| StackArray | STRING | 1D array to implement the stack | [0:99] |
| Max | INTEGER | maximum number of items in the stack | 100 |
The value of Top is incremented each time a data item is added to the stack and decremented each time a data item is removed. If the stack is full, an appropriate error message is output.
(i) Complete the pseudocode for the procedure to add a data item onto the stack. 4 marks
PROCEDURE Push(______) IF Top < Max – 1 THEN
Top ←
______ ← NewData ELSE
OUTPUT ENDIF ENDPROCEDURE
(ii) Write pseudocode to input a new data item and add it to the stack using Push(). 2 marks
(b) Explain the reasons why a stack is used when a recursive algorithm is executed. 3 marks
Show mark scheme
12(a)(i) [4 marks]
One mark for each correctly completed line ( Max 4 ) PROCEDURE Push( NewData : STRING ) IF Top < Max – 1 THEN Top Top + 1 StackArray[Top] NewData ELSE OUTPUT "Stack full; new data cannot be added" ENDIF ENDPROCEDURE
12(a)(ii) [2 marks]
One mark per mark point ( Max 2 ) MP1 Input with variable, with or without prompt MP2 Procedure call for Push with parameter used matching input variable Example answer INPUT MyData CALL Push(MyData)
12(b) [3 marks]
One mark per mark point ( Max 3 ) MP1 Stacks store data in Last In First Out (LIFO) / First In Last Out (FILO) order MP2 Each time a recursive algorithm calls itself data is pushed onto the stack MP3 When the recursive algorithm reaches its base case / starts to unwind MP4 … data is popped from the stack in the reverse order to which it was pushed onto it.
(a) Outline the process of optimisation during the compilation of a program. 2 marks
(b) Write the Reverse Polish Notation (RPN) for the given infix expression: 3 marks
((6 + 12) / (16 – 10)) * 18
(c) The RPN expression c a – b d + * b c + / is to be evaluated, where: 4 marks
a = 4, b = 12, c = 24 and d = 6.
Show the changing contents of the stack as the RPN expression is evaluated.
Show mark scheme
7(a) [2 marks]
One mark per mark point ( Max 2 ) MP1 To identify and remove redundant code / To simplify expressions / To reorder the code MP2 … so that storage size/memory use/power consumption/program execution time/CPU time is minimized.
7(b) [3 marks]
One mark per mark point ( Max 2 ) MP1 6 12 + MP2 16 10 – / MP3 18 * Final correct expression 6 12 + 16 10 – / 18 *
7(c) [4 marks]
One mark per ring ( Max 3 ) One mark for the interim total (360) and the final total (10). 6 24 4 12 12 18 12 12 36 24 24 20 20 20 20 360 360 360 360 10
Describe the process of executing a program using an interpreter. 4 marks
Show mark scheme
6 [4 marks]
One mark for each mark point ( Max 4 ) MP1 The interpreter translates the source code one line at a time MP2 If the line is syntax error free it is executed MP3 It is not stored in executable format MP4 If an error is found, the program halts with an error message MP5 Each line must be translated every time it is run, including lines running multiple times for example in loops
Several syntax diagrams are shown.
Show mark scheme
7(a) [2 marks]
One mark for each correct answer – must begin with a member of the group uppercase // cannot begin with a symbol #Jd7 – the fourth character cannot be a member of the group uppercase // the fourth character must be either a symbol, C%6A digit or lowercase
7(b) [4 marks]
One
mark
per
mark point
::= ||
Explain what is meant by lexical analysis during program compilation. 4 marks
Show mark scheme
8 [4 marks]
One mark per mark point ( Max 4 ) MP1 It is the first stage of compilation MP2 White space and comments are removed MP3 It takes modified source code and breaks it into a series of tokens MP4 Each token is categorised and assigned types MP5 Identifiers are stored in a symbol table MP6 If the lexical analyser finds invalid tokens, it generates an error MP7 Acceptable data from the lexical analyser passes to the syntax analyser
(a) State why 9K is not a valid variable for the given syntax diagrams. 1 mark
(b) Complete the Backus-Naur Form (BNF) for . 1 mark
(c) An expression is defined as follows: 3 marks
A variable is assigned to a variable followed by an operator followed by another variable.
The operator and final variable stage can be repeated as many times as necessary.
Complete the syntax diagram for an expression.
(d) A character can be a letter or a digit. 1 mark
An additional constraint has been applied to the definition of variable. It must comply with the given syntax diagram, but it will only pass validation if it has at least four characters.
State one example of a valid variable.
Show mark scheme
9(a) [1 mark]
Variables must begin with a letter / not a digit
9(c) [3 marks]
One mark per mark point MP1 Two variable boxes added to diagram MP2 One operator box added to diagram and all boxes in correct order MP3 Connections, arrows and return loop correctly added and no additional boxes or connections expression variable variable operator variable
9(d) [1 mark]
Answer must begin with a valid letter. It can then be followed by any number of valid digits and/or letters, as long as it is at least four characters in length. Example answer AC768
Explain the process of syntax analysis during program compilation. 4 marks
Show mark scheme
8 [4 marks]
One mark per mark point ( Max 4 ) MP1 It is the second stage of compilation // It’s the compilation stage after lexical analysis. MP2 It takes input from the lexical analyser in the form of token streams. MP3 The source code is analysed / parsed against the rules of the language to detect any errors in the code. MP4 The output from this phase is a parse tree. MP5 Syntax errors are reported.
Several syntax diagrams are shown.
passcode
| upper | ||
|---|---|---|
| upper | upper | upper |
| upper |
(a) State why JJ90 is not a valid passcode for the given syntax diagrams. 1 mark
Show mark scheme
9(a) [1 mark]
The second character must come from either lower or digit. It can’t be upper.
9(b) [3 marks]
Max 3
One
mark
MP1
9(c) [2 marks]
One mark per mark point MP1 Box for upper in correct place with correct connections MP2 Correct repetition arrow for final digit lower lower passcode digit upper digit digit upper
Several syntax diagrams are shown.
Show mark scheme
10(a) [4 marks]
One
mark per mark point (
Max 4
)
•
10(b)(i) [3 marks]
One mark per mark point ( Max 3) MP1 begin with either a letter or a symbol MP2 end with either one or two symbols MP3 digit and all other connections and label correct. password letter digit symbol symbol symbol
10(b)(ii) [2 marks]
One
mark per mark point (
Max 2)
•
Several syntax diagrams are shown.
Show mark scheme
7(a) [2 marks]
One mark per mark point ( Max 2) MP1 21 - a number must begin with an odd digit, 2 is even MP2 123 - a number can only be one or two digits in length not three
7(b) [2 marks]
One
mark per mark point (
Max 2)
MP1
7(c)(i) [3 marks]
One mark per mark point ( Max 3) MP1 letter, number and symbol all included in correct order: letter first, followed by number, finishing with symbol MP2 provision for one or two numbers including relevant connectors MP3 all other connections and label correct and no additional data Example answer code number letter number symbol
7(c)(ii) [2 marks]
One
mark per correct line (
Max 2)
::= ::= ::=
Several syntax diagrams are shown.
Show mark scheme
10(a) [4 marks]
One
mark per mark point (
Max 4
)
•
10(b)(i) [3 marks]
One mark per mark point ( Max 3) MP1 begin with either a letter or a symbol MP2 end with either one or two symbols MP3 digit and all other connections and label correct. password letter digit symbol symbol symbol
10(b)(ii) [2 marks]
One
mark per mark point (
Max 2)
•
(a) Write this Reverse Polish Notation (RPN) in infix form: 3 marks
5 2 + 9 3 - / 3 *
(b) Write this infix expression in RPN: 2 marks
((7 + 3) - (2 * 8)) / 6
(c) Evaluate this RPN expression: 4 marks
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.
Show mark scheme
5(a) [3 marks]
mark per correct term ( Max 3) (5 + 2) / (9 – 3) Complete correct answer ((5 + 2) / (9 - 3)) * 3
5(b) [2 marks]
mark 7 3 + mark 2 8 * - 6 / Complete answer 7 3 + 2 8 * - 6 /
5(c) [4 marks]
mark per ring ( Max 4) 3 5 7 7 10 10 17 17 12 12 12 12 120 120 12
(a) Write this infix expression in Reverse Polish Notation (RPN): 2 marks
(7 – 2 + 8) / (9 – 5)
(b) Evaluate this RPN expression: 4 marks
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.
(c) Write this RPN expression in infix form: 3 marks
b a c - + d b + * c /
Show mark scheme
5(a) [2 marks]
mark 7 2 – 8 + mark 9 5 - / Complete answer 7 2 – 8 + 9 5 - /
5(b) [4 marks]
mark per ring ( Max 4) 3 7 9 6 6 9 9 2 6 6 15 15 15 15 15 15 30
5(c) [3 marks]
mark per correct term ( Max 3) (a – c + b)
- (d + b) Complete correct answer (((a – c) + b) * (d + b))/c (a – c + b) * (d + b)/c
(a) Write this Reverse Polish Notation (RPN) in infix form: 3 marks
5 2 + 9 3 - / 3 *
(b) Write this infix expression in RPN: 2 marks
((7 + 3) - (2 * 8)) / 6
(c) Evaluate this RPN expression: 4 marks
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.
Show mark scheme
5(a) [3 marks]
mark per correct term ( Max 3) (5 + 2) / (9 – 3) Complete correct answer ((5 + 2) / (9 - 3)) * 3
5(b) [2 marks]
mark 7 3 + mark 2 8 * - 6 / Complete answer 7 3 + 2 8 * - 6 /
5(c) [4 marks]
mark per ring ( Max 4) 3 5 7 7 10 10 17 17 12 12 12 12 120 120 12
9 (a) (i) Write the infix expression for this Reverse Polish Notation (RPN) expression:
5 2 – 5 4 + * 9 /
2 marks
(ii) Show how the contents of the following stack will change as the RPN expression in part (a)(i) is evaluated. 4 marks
(b) Explain how a stack can be used to evaluate RPN expressions. 3 marks
Show mark scheme
9(a)(i) [2 marks]
One mark per mark point ( Max 2 ) • (5 – 2) •
- (5 + 4) / 9 Final correct expression (5 – 2) * (5 + 4) / 9
9(a)(ii) [4 marks]
One mark per ring ( Max 4 ) 4 2 5 5 9 9 5 5 3 3 3 3 27 27 3 OR 5 2 3 5 4 9 27 9 3 5 3 5 3 27 3
9(b) [3 marks]
One mark per mark point ( Max 3 ) MP1 Evaluate the RPN expression from left to right MP2 Push each element of the RPN expression onto the stack in order until an operator is reached MP3 Pop the last two elements from the stack and apply the operator MP4 Push the result of the operation onto the stack MP5 Repeat the process until the whole expression is evaluated.
Show mark scheme
7(a) [1 mark]
0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0
7(b) [1 mark]
X= A.B.C
7(c) [3 marks]
(Max 2) for correct working from points shown (T =) X.Y.Z + X.Y.Z + X Distributive law (T=) X.Z.(Y + Y) + X Complement law (T=) X.Z.(1) + X Identity law (T=) X.Z + X Redundancy law (to get final answer) One mark for correct answer (T=) X + Z
9 (a) (i) Write the infix expression for this Reverse Polish Notation (RPN) expression:
5 2 – 5 4 + * 9 /
2 marks
(ii) Show how the contents of the following stack will change as the RPN expression in part (a)(i) is evaluated. 4 marks
(b) Explain how a stack can be used to evaluate RPN expressions. 3 marks
Show mark scheme
9(a)(i) [2 marks]
One mark per mark point ( Max 2 ) • (5 – 2) •
- (5 + 4) / 9 Final correct expression (5 – 2) * (5 + 4) / 9
9(a)(ii) [4 marks]
One mark per ring ( Max 4 ) 4 2 5 5 9 9 5 5 3 3 3 3 27 27 3 OR 5 2 3 5 4 9 27 9 3 5 3 5 3 27 3
9(b) [3 marks]
One mark per mark point ( Max 3 ) MP1 Evaluate the RPN expression from left to right MP2 Push each element of the RPN expression onto the stack in order until an operator is reached MP3 Pop the last two elements from the stack and apply the operator MP4 Push the result of the operation onto the stack MP5 Repeat the process until the whole expression is evaluated.
Several syntax diagrams are shown.
Show mark scheme
6(a)
One
mark per correct valid/invalid and reason combination (
Max 3
)
– Valid
DPAD99$
Reason – 4/multiple letters followed by 2/multiple digits followed by a symbol.
– Invalid
DAD#95
Reason – The symbol comes before the digits – it should be after.
– Invalid
ADY123?
Reason – The ? is not a valid symbol.
6(b) [4 marks]
6(c) [2 marks]
One mark per mark point ( Max 4 ) begins with a letter letter can repeat and digit present digit can repeat or can be bypassed correct structure – name, boxes and arrows (in and out). Example answers: identifier letter digit identifier letter digit letter
Several syntax diagrams are shown.
Show mark scheme
3(a) [2 marks]
One mark per correct valid/invalid and reason combination ( Max 2 ) – Invalid 9SW Reason - This begins with a digit and a variable must begin with a letter – Valid UWY Reason – This begins with a letter and is followed by two other letters.
3(b) [3 marks]
One
mark per mark point (
Max 3
)
3(c)(i) [3 marks]
Answer must be two letters followed by one, two or three digits using the letters and digits on the syntax diagram. Example answer AC768
3(c)(ii) [4 marks]
One mark per mark point ( Max 3 ) always has only two letters one, two or three digits possible correct arrows, boxes and name of syntax diagram Example answer Vehicle registration letter digit letter digit digit
Several syntax diagrams are shown.
Show mark scheme
6(a)
One
mark per correct valid/invalid and reason combination (
Max 3
)
– Valid
DPAD99$
Reason – 4/multiple letters followed by 2/multiple digits followed by a symbol.
– Invalid
DAD#95
Reason – The symbol comes before the digits – it should be after.
– Invalid
ADY123?
Reason – The ? is not a valid symbol.
6(b) [4 marks]
6(c) [2 marks]
One mark per mark point ( Max 4 ) begins with a letter letter can repeat and digit present digit can repeat or can be bypassed correct structure – name, boxes and arrows (in and out). Example answers: identifier letter digit identifier letter digit letter
Draw one line to connect each stage of compilation to its most appropriate description.
Stage of compilation Description
minimising a program’s execution time and memory requirement
Lexical analysis
converting an intermediate representation of source code into an executable form
Syntax analysis
converting a sequence of characters into a sequence of tokens
Code generation
directly executing instructions written in a scripting language
Optimisation
using parsing algorithms to interpret the meaning of a sequence of tokens 4 marks
Show mark scheme
4 [4 marks]
One mark for each correct line connecting one stage of compilation to a description a b * b + d - 15 +
A program to manage regular flight details at an airport requires some user-defined data types.
(a) Write pseudocode statements to declare the enumerated data type Aircraft to hold data about the types of aircraft used for a flight. 2 marks
These types of aircraft are: C300, C350, D242, E757, X380.
(b) Write pseudocode statements to declare the composite data type Flight to hold data about flights to a specific destination. These include: 4 marks
flight number, which could be any combination of letters and numbers
destination
date of departure
type of aircraft used.
Use the enumerated data type you created in part (a) .
(c) (i) Write the pseudocode statement to set up a variable for one record of the composite 1 mark
data type Flight .
Show mark scheme
4(a) [2 marks]
Marks as shown in the square brackets: TYPE Aircraft = (C300, C350, D242, E757, X380) [1] TYPE Aircraft = [1] (C300, C350, D242, E757, X380)
4(b) [4 marks]
One mark for each point ( Max 4 ) • and correct TYPE Flight ENDTYPE • and as DECLARE FlightNumber DECLARE Destination STRING • as DECLARE DepartureDate DATE • as (correct data type from part 4(a) DECLARE AircraftType Aircraft Example answer: TYPE Flight DECLARE FlightNumber : STRING DECLARE Destination : STRING DECLARE DepartureDate : DATE DECLARE AircraftType : Aircraft ENDTYPE
4(c)(i) [1 mark]
Example answer: DECLARE Flight1 : Flight
4(c)(ii) [3 marks]
One mark for each point ( Max 3 ) • Correct assignments of both string data values • Correct assignments of date data value • Correct assignments of enumerated data value Example answer: Flight1.FlightNumber "XA782" Flight1.Destination "Cambridge" Flight1.DepartureDate 12/12/2022 Flight1.AircraftType C350
Draw one line to connect each stage of compilation to its most appropriate description.
Stage of compilation Description
minimising a program’s execution time and memory requirement
Lexical analysis
converting an intermediate representation of source code into an executable form
Syntax analysis
converting a sequence of characters into a sequence of tokens
Code generation
directly executing instructions written in a scripting language
Optimisation
using parsing algorithms to interpret the meaning of a sequence of tokens 4 marks
Show mark scheme
4 [4 marks]
One mark for each correct line connecting one stage of compilation to a description a b * b + d - 15 +
Part of a program’s calculations uses the integer variables j, k, m, n and p .
j = 3
k = 2
m = 10
n = (j + k)/(j - k)
p = m * (m - j * k)
(a) Write the Reverse Polish Notation (RPN) for the expression: 2 marks
(j + k)/(j - k)
(b) (i) Show the changing contents of the stack as the value for p is calculated from its RPN 4 marks
expression:
m m j k * - *
(ii) Describe the main steps in the evaluation of this RPN expression using a stack. 4 marks
Show mark scheme
5(a) [2 marks]
One mark for each in order jk+jk-/
5(b)(i) [4 marks]
1 mark per ring Do not allow operators in stacks 2 3 3 6 10 10 10 10 4 10 10 10 10 10 10 40
5(b)(ii) [4 marks]
four from Max 4 Max 3 generic answer only Working from left to right in the expression PUSH 10/m onto the stack PUSH the following numbers (10/m, 3/j, 2/k) onto the stack When the first operator ,*, is reached … POP the top two numbers, 2/k and 3/j … apply the operation PUSH result back onto stack Continue to the end of the expression
5(c) [2 marks]
two from recursion implementation of ADTs e.g. linked lists procedure calls interrupt handling (storing contents of registers etc)
The following syntax diagrams show the syntax of:
a variable
an unsigned integer
a letter
a digit
an operator
an assignment statement.
unsigned integer
| digit digit | ||
|---|---|---|
| digit | digit | digit |
| digit | digit |
assignment
(a) The following assignment statements are invalid. State the reason in each case. 2 marks
X1 = Y2 – 12
Reason
Z = Y12 + Z1
Reason
Show mark scheme
4(a) [2 marks]
An unsigned integer, 12 , is used instead of the last variable 12 is not a valid variable The variable Z is not a valid variable / missing an unsigned integer after the Z
4(b) [5 marks]
mark
per bullet point
4(c)(i) [3 marks]
mark adding both boxes… mark for correct position(s) and connector(s) … mark … rest correct (assignment statement) variable
operator unsigned integer variable variable unsigned integer unsigned integer unsigned integer
4(c)(ii) [3 marks]
Max three
mark for
Part of a program’s calculations uses the integer variables j, k, m, n and p .
j = 3
k = 2
m = 10
n = (j + k)/(j - k)
p = m * (m - j * k)
(a) Write the Reverse Polish Notation (RPN) for the expression: 2 marks
(j + k)/(j - k)
(b) (i) Show the changing contents of the stack as the value for p is calculated from its RPN 4 marks
expression:
m m j k * - *
(ii) Describe the main steps in the evaluation of this RPN expression using a stack. 4 marks
Show mark scheme
5(a) [2 marks]
One mark for each in order jk+jk-/
5(b)(i) [4 marks]
1 mark per ring Do not allow operators in stacks 2 3 3 6 10 10 10 10 4 10 10 10 10 10 10 40
5(b)(ii) [4 marks]
four from Max 4 Max 3 generic answer only Working from left to right in the expression PUSH 10/m onto the stack PUSH the following numbers (10/m, 3/j, 2/k) onto the stack When the first operator ,*, is reached … POP the top two numbers, 2/k and 3/j … apply the operation PUSH result back onto stack Continue to the end of the expression
5(c) [2 marks]
two from recursion implementation of ADTs e.g. linked lists procedure calls interrupt handling (storing contents of registers etc)
The following syntax diagrams for a particular programming language show the syntax of:
a digit
a capital letter
a character.
(a) Write the Backus-Naur Form (BNF) notation of the syntax diagram for character. 2 marks
Show mark scheme
4(a) [2 marks]
One
mark for each marking point (
Max 2
)
•
4(b)(i) [1 mark]
For example: $A9E3
4(b)(ii) [4 marks]
One
mark for each marking point (
Max 4
)
•
•
::= …
•
… |
Complete answer
::=|
The following syntax diagrams for a particular programming language show the syntax of:
a digit
a capital letter
a character.
(a) Write the Backus-Naur Form (BNF) notation of the syntax diagram for character. 2 marks
Show mark scheme
4(a) [2 marks]
One
mark for each marking point (
Max 2
)
•
4(b)(i) [1 mark]
For example: $A9E3
4(b)(ii) [4 marks]
One
mark for each marking point (
Max 4
)
•
•
::= …
•
… |
Complete answer
::=|
Show mark scheme
4(a)(i) [2 marks]
One mark for each correct marking point (Max 2) Reverse Polish Notation provides an unambiguous method of • representing an expression … reading from left to right • …without the need to use brackets • …with no need for rules of precedence / BODMAS •
4(a)(ii) [2 marks]
One mark for identification of the data structure, One mark for a sensible reason Either: Structure: stack The operands are popped from the stack in the reverse order to how they were pushed Or: Structure: Binary tree A (binary) tree allows both infix and postfix to be evaluated (tree traversal)
4(b) [1 mark]
a b - a c + * 7 /
4(c) [2 marks]
a / b * 4 – (a + b)
4(d)
1 mark for correct structure 1 mark for correct substitution (a + b) / (c / d) (17 + 3) / (48 / 12)
Show mark scheme
4(a)(i) [2 marks]
One mark for each correct marking point (Max 2) Reverse Polish Notation provides an unambiguous method of • representing an expression … reading from left to right • …without the need to use brackets • …with no need for rules of precedence / BODMAS •
4(a)(ii) [2 marks]
One mark for identification of the data structure, One mark for a sensible reason Either: Structure: stack The operands are popped from the stack in the reverse order to how they were pushed Or: Structure: Binary tree A (binary) tree allows both infix and postfix to be evaluated (tree traversal)
4(b) [1 mark]
a b - a c + * 7 /
4(c) [2 marks]
a / b * 4 – (a + b)
4(d)
1 mark for correct structure 1 mark for correct substitution (a + b) / (c / d) (17 + 3) / (48 / 12)
Show mark scheme
4(a)(i) [2 marks]
One mark for each correct marking point (Max 2) Reverse Polish Notation provides an unambiguous method of • representing an expression … reading from left to right • …without the need to use brackets • …with no need for rules of precedence / BODMAS •
4(a)(ii) [2 marks]
One mark for identification of the data structure, One mark for a sensible reason Either: Structure: stack The operands are popped from the stack in the reverse order to how they were pushed Or: Structure: Binary tree A (binary) tree allows both infix and postfix to be evaluated (tree traversal)
4(b) [1 mark]
a b - a c + * 7 /
4(c) [2 marks]
a / b * 4 – (a + b)
4(d)
1 mark for correct structure 1 mark for correct substitution (a + b) / (c / d) (17 + 3) / (48 / 12)