Advanced System Software and Security: Question 8

Worked solution

Part (a): What lexical analysis does

Lexical analysis is the stage of compilation that scans the source code character by character and groups those characters into meaningful tokens. Such as identifiers, keywords, operators and literals. Ready for the syntax analysis stage that follows it.

Besides producing tokens themselves, two further tasks it typically carries out are:

• Removing whitespace, layout characters and comments from the source code, since these are needed for the programmer to read the code but carry no meaning for later compiler stages.
• Detecting illegal symbols. Characters or character sequences that are not valid in the language at all, and reporting these as errors, rather than passing them on as tokens.

[3 marks]: [1] for the definition (scanning source code and grouping characters into tokens), [1] for removing whitespace/layout characters/comments, [1] for detecting illegal symbols/characters.

Part (b): Classifying the tokens

Working through the line Total ← Count * 2 + 5 token by token:

Total and Count are identifiers, since they are names chosen by the programmer for variables. ←, * and + are operators, ← performs assignment, while * and + perform arithmetic. 2 and 5 are literals: fixed numeric constants written directly in the code, rather than named variables.

[3 marks]: [1] for correctly classifying both identifiers (Total, Count), [1] for correctly classifying all three operators (←, *, +), [1] for correctly classifying both literals (2, 5).

Part (c): The role of the symbol table

As lexical analysis encounters each new identifier (here, Total and Count) it records information about that identifier in a symbol table: typically its name, its data type, and (later, once allocated) its memory location. This means the identifier’s full name does not need to be stored or compared repeatedly throughout the rest of compilation. Later stages such as syntax analysis and code generation can instead look up the identifier’s details in the symbol table using a much shorter reference.

The symbol table is also what allows the compiler to catch certain errors, such as an identifier being referenced (as Count is here) before it has ever been declared, or being declared more than once. [2 marks]: [1] for stating that the symbol table stores information about identifiers (name/type/location) as they are first encountered, [1] for explaining how this is used by later stages (lookup instead of re-deriving information, and/or detecting errors such as undeclared identifiers).

Final answers

• (a) Lexical analysis scans source code and groups characters into tokens; it also removes whitespace/comments and detects illegal symbols.
• (b) Total and Count are identifiers; ←, *, + are operators; 2 and 5 are literals.
• (c) The symbol table records each identifier’s name, type and memory location so later compiler stages can look it up rather than re-deriving this information, and so undeclared identifiers can be detected.