Python · A Level 15

Grammars, Parsing and Compilers

Section A: 10 multiple choice questions, 10 marks. Section B: 5 written questions, 21 marks. Total 31 marks.

Name

Class

Date

Mark / 31

Section A

Circle the letter of the correct answer. One mark each.

1In BNF, what does ::= mean?1
1. AIs greater than or equal to
2. BIs equal to
3. CIs assigned the value
4. DIs defined as
2In the rule <integer> ::= <digit> | <digit> <integer>, how is repetition shown?1
1. ABy a loop symbol
2. BBy the angle brackets
3. CBy the rule referring to itself
4. DBy the | symbol
3What is a terminal in a BNF grammar?1
1. AA symbol defined by another rule
2. BA symbol that appears in the language exactly as written
3. CA rule that can never be used
4. DThe last rule in the grammar
4What is the output of the lexical analysis stage?1
1. AA list of syntax errors only
2. BMachine code
3. CA sequence of tokens
4. DA syntax tree
5Which stage checks that the tokens follow the rules of the grammar?1
1. ACode generation
2. BOptimisation
3. CLexical analysis
4. DSyntax analysis
6Which of these is found by the syntax analysis stage?1
1. AA missing closing bracket
2. BA division by zero
3. CA wrong answer from a correct looking formula
4. DA file that does not exist
7What is constant folding?1
1. AStoring constants in a table
2. BConverting text to tokens
3. CWorking out an expression made only of numbers once, at compile time
4. DRemoving comments from the code
8What is one advantage of a compiler over an interpreter?1
1. AIt reports errors only when each line runs
2. BThe compiled program usually runs faster
3. CIt needs no translator at all
4. DIt can run on any type of computer without changes
9What is one advantage of an interpreter?1
1. AIt produces a standalone executable
2. BIt can run and test one line at a time, so errors are easy to find while developing
3. CIt produces faster code
4. DIt checks the whole program before running
10Python translates source code into bytecode, which a virtual machine then runs. What does that make Python?1
1. ABoth compiled and interpreted
2. BOnly interpreted
3. COnly compiled
4. DNeither

Section B

Answer in the space provided. The number of marks tells you how many separate points to make.

1WriteThe grammar for a variable name states that it must start with a letter, followed by any number of letters or digits. Write a BNF definition for a variable name, including definitions for a letter and for a digit. You may use ... to shorten a list of alternatives.4
2StateThe line of a program shown is passed to the lexical analysis stage of a compiler. State the tokens that are produced, and state what the lexical analyser does with the spaces.3
```
total = price * 2 + 1
```
3DescribeDescribe the purpose of two stages in the compilation of a high-level language program.4
4ShowA stack machine evaluates the expression 2 + 3 * 4. Show the instructions that would be generated, using PUSH, ADD and MUL, and state the value left on the stack.4
5DiscussA software company is deciding whether to supply a program as compiled code or to supply the source code to be run with an interpreter. Discuss which it should choose.6

Mark scheme

Section A

1D2C3B4C5D6A7C8B9B10A

Section B

1 The grammar for a variable name states that it must start with a letter, followed by any number of letters or digits. Write a BNF definition for a variable name, including definitions for a letter and for a digit. You may use ... to shorten a list of alternatives. 4

One mark for each of the following, to a maximum of 4.

A definition of <letter> as a | b | ... | z (and capitals) and <digit> as 0 | ... | 9
Uses ::= and | correctly and the angle brackets for non-terminals
A rule where a name can be just a letter (a non-recursive base case)
A recursive rule that extends a name by a letter or digit

Model answer.

<letter>   ::= a | b | c | ... | z | A | B | ... | Z
<digit>    ::= 0 | 1 | 2 | ... | 9
<variable> ::= <letter> | <variable> <letter> | <variable> <digit>

A variable is either a single letter, or a variable followed by a letter, or a variable followed by a digit. The recursion allows names of any length, and the first alternative gives it a place to start, so the rule can end.

2 The line of a program shown is passed to the lexical analysis stage of a compiler. State the tokens that are produced, and state what the lexical analyser does with the spaces. 3

One mark for each of the following, to a maximum of 3.

Identifies the names and operators as separate tokens: total, =, price, *, 2, +, 1
Identifies the numbers 2 and 1 as number tokens
White space is removed (ignored) and does not produce a token

Model answer. The tokens are the name total, the operator =, the name price, the operator *, the number 2, the operator + and the number 1. The spaces are removed by the lexical analyser, and do not produce any tokens.

3 Describe the purpose of two stages in the compilation of a high-level language program. 4

One mark for each of the following, to a maximum of 4.

Lexical analysis: splits the source code into tokens
and removes spaces and comments (or reports invalid symbols)
Syntax analysis: checks the tokens follow the rules (grammar) of the language, reporting syntax errors
Code generation: produces the machine code (or bytecode); optimisation makes it smaller or faster

Model answer. In lexical analysis the source code is split into tokens such as names, numbers and operators, and spaces and comments are removed. In syntax analysis the tokens are checked against the grammar rules of the language, any syntax errors are reported, and a syntax tree is usually built. In code generation the tree is translated into machine code or bytecode, and optimisation then changes it so that it is smaller or runs faster without changing what it does.

4 A stack machine evaluates the expression 2 + 3 * 4. Show the instructions that would be generated, using PUSH, ADD and MUL, and state the value left on the stack. 4

One mark for each of the following, to a maximum of 4.

Recognises that 3 4 is done first because has higher precedence
Instructions PUSH 2, PUSH 3, PUSH 4 in that order
Followed by MUL and then ADD
The value left on the stack is 14

Model answer. Multiplication has higher precedence, so 3 4 is calculated before the addition. The instructions are PUSH 2, PUSH 3, PUSH 4, MUL, ADD. MUL takes 3 and 4 off the stack and pushes 12, then ADD takes 2 and 12 off the stack and pushes 14. The value left on the stack is 14. This order is the Reverse Polish form 2 3 4 +.

5 A software company is deciding whether to supply a program as compiled code or to supply the source code to be run with an interpreter. Discuss which it should choose. 6

One mark for each of the following, to a maximum of 6.

Compiled code is already translated, so it runs faster
The compiled program does not need a translator on the user's computer
Compiled code hides the source code, protecting the company's work
But the compiled code only runs on one type of processor or operating system, so versions are needed for each
An interpreted program runs on any computer that has the interpreter, but is slower and exposes the source code
A reasoned conclusion

Model answer. Compiled code has already been translated into machine code, so it runs faster and the user does not need a translator installed. It also keeps the company's source code hidden, which protects its work from being copied. However, it will only run on one type of processor and operating system, so the company must produce and support a different version for each. Supplying source code to be interpreted lets the same program run on any computer that has the interpreter, but it will run more slowly and the source code is exposed. For a commercial program that has to be quick and where the source code is valuable, the company should supply compiled code, producing a version for each of the systems it wants to support.