Studyledge

Advanced System Software and Security: Question 9

Syllabus 16.2

Structured A2 8 marks

A grammar for a simplified <identifier> used by a compiler's syntax analysis stage is defined by the following BNF rules:

<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
<letter> ::= "a" | "b" | "c" | ... | "z"
<digit> ::= "0" | "1" | ... | "9"

(a) State what is meant by a grammar in the context of a compiler, and state one way (other than BNF) that a grammar can be expressed. [2]

(b) Using this grammar, state, with a reason, whether each of the following is a valid <identifier>: (i) x9 (ii) 9x (iii) total2 [3]

(c) A compiler may include an optimisation stage in addition to syntax analysis and code generation. State at which point in the compilation process optimisation typically takes place, and give one example of a technique it might use to improve the object code produced. [3]

Show worked solution Hide worked solution

Worked solution

Part (a): What a grammar is

A grammar is a set of rules that defines which sequences of tokens are considered syntactically valid in a language. It specifies exactly how valid statements, expressions or constructs (such as the <identifier> here) may legally be built up. The syntax analysis stage of compilation uses the grammar to check the tokens already produced by lexical analysis against these rules, typically building a parse tree if the tokens are found to be valid.

Besides BNF, a grammar can also be expressed as a syntax diagram (sometimes called a railroad diagram), a visual representation of the same rules, using boxes and arrows instead of written production rules. [2 marks]: [1] for the definition of a grammar, [1] for naming syntax diagrams as an alternative way to express one.

Part (b): Testing strings against the grammar

The grammar has one base case, <identifier> ::= <letter>, meaning every valid identifier must start life as a single letter. From there, <identifier> ::= <identifier> <letter> or <identifier> ::= <identifier> <digit> can be applied repeatedly to append further letters or digits, one at a time, to the end of an already-valid identifier.

  • (i) x9. Valid. x is generated directly as <letter> (the base case), giving the identifier x. Then <identifier> <digit> is applied once, appending 9, to give x9.
  • (ii) 9x, not valid. The only base case for <identifier> is <letter>, there is no rule that lets an identifier begin with a <digit>. Since 9x would have to start with the digit 9, it can never be derived from this grammar.
  • (iii) total2. Valid. t is generated as the base <letter>. Then <identifier> <letter> is applied in turn to append o, t, a and l, building up total. Finally, <identifier> <digit> is applied once to append 2, giving total2.

[3 marks]: [1] each for a correct valid/not-valid judgement with correct reasoning for (i), (ii) and (iii).

Part (c): When optimisation happens and what it does

Optimisation typically takes place after code generation has already produced an initial version of the object code, and before that object code is finalised and output. It works on code that has already been shown to be syntactically valid and already translated, improving it without changing what the program actually does.

One example technique is removing redundant code: for instance, deleting an instruction that assigns a value to a variable that is never subsequently read anywhere in the program, or removing code that can never be reached during execution. (Another possible example is replacing a calculation that produces the same result every time a loop repeats with a single calculation performed once, outside the loop.)

[3 marks]: [1] for stating optimisation happens after code generation and before the final object code is output, [1] for stating it improves the code without changing its behaviour, [1] for a valid example technique.

Final answers

  • (a) A grammar defines which token sequences are syntactically valid, used by syntax analysis; it can also be expressed as a syntax diagram.
  • (b) (i) x9, valid. (ii) 9x, not valid (identifiers must start with a letter). (iii) total2, valid.
  • (c) Optimisation happens after code generation, improving the object code without changing its behaviour, e.g. by removing redundant code.