Phases of a Compiler Questions and Answers

Answer: C

Correct answer: regular expressions describing the tokens and produces a scanner

Lex and its successors take a specification pairing regular expressions with actions and generate a scanner - typically as a finite automaton driven by a table.

Regular expressions suffice because token structure is regular: identifiers, numbers and operators can all be described without recursion. Nested structures such as balanced parentheses cannot, which is why the parser needs a context-free grammar and a different generator, and why the two tools are separate.

Answer: D

Correct answer: A-2, B-4, C-1, D-3

Each tool automates one phase from a declarative specification. A scanner generator turns regular expressions into a lexical analyser; a parser generator turns a context-free grammar into a parser.

A syntax directed translation engine turns rules attached to grammar productions into a translator. A data flow engine produces analysis results for the optimiser. Note the pattern: the first three generate code from a specification, while the last generates facts about a particular program.

Answer: A

Correct answer: the decomposition makes a large translation problem tractable

Translating a high-level language to machine code is too large a problem to attack whole. Dividing it into phases with defined inputs and outputs lets each be designed, implemented and tested on its own.

It also creates the interfaces that make front ends and back ends interchangeable. The structure is an engineering convention, not a legal requirement or a standard's prescription, and real compilers merge phases into passes freely - the logical division survives the physical one.

Answer: A

All four statements are true. Assembly languages are tied to the instruction set of a particular processor, so they are machine dependent. A compiler translates a program in a high-level language into machine-level code. An interpreter translates and executes the program one statement at a time. BASIC is an interactive programming language, since statements can be entered and run immediately. The options that mark any of these as false are therefore wrong.

Answer: B

The correct matching is P ↔ iii, Q ↔ i, R ↔ ii, S ↔ iv.

• Lexical analysis recognises tokens, which are specified by regular expressions (P-iii).
• Top-down parsing (recursive descent, LL) builds a leftmost derivation of the input (Q-i).
• Semantic analysis checks meaning beyond syntax, chiefly type checking (R-ii).
• The runtime environment manages procedure calls through activation records on the stack (S-iv).

Each of the other options places at least one of these well-defined pairs wrongly, for instance tying lexical analysis to leftmost derivation or type checking.

Answer: B

The correct match is P - 2; Q - 3; R - 1; S - 4.

1. The lexical analyzer reads characters and produces tokens (P-2).
2. The syntax analyzer checks the token stream against the grammar and builds a parse tree (Q-3).
3. The intermediate code generator works from the abstract syntax tree (R-1), a condensed form of the parse tree.
4. Constant folding, evaluating constant expressions at compile time, is a code optimization (S-4).

The option P - 2; Q - 1; R - 3; S - 4 swaps the parse tree and the abstract syntax tree. Options pairing the lexical analyzer with constant folding misplace both, since a lexer only produces tokens.

Answer: B

The false statement is Type checking is done before parsing.

Type checking is part of semantic analysis, which works on the parse tree or syntax tree. It needs to know the structure of expressions and declarations, so it comes after parsing.

The other statements are true. Regular token patterns are a special case of context-free languages, so a context-free grammar can describe both lexical and syntax rules, even though lexers usually use regular expressions. A program can be translated to several intermediate representations, such as syntax trees, three-address code or SSA form. And the program stack is the usual way to pass arguments in a function call.

Answer: B

The answer is only S1 and S2 are TRUE.

A compiler's front-end (lexical analysis, parsing, semantic analysis and intermediate code generation) works on the source language and produces a machine-independent intermediate representation, so it does not depend on the target hardware (S1). The back-end (machine-dependent optimisation, register allocation, instruction selection and code generation) translates that intermediate form for a particular processor, so it is specific to the target hardware (S2).

S3 is false: it is the front-end that is specific to the programming language. The point of the split is that one back-end can serve several source languages and one front-end several targets. That rules out 'Only S1', 'all three' and 'S1 and S3'.

Answer: D

The true statement is LR(1) parsing is sufficient for deterministic context-free languages.

Every deterministic context-free language has an LR(1) grammar, and the languages accepted by deterministic pushdown automata are exactly those LR(1) parsers recognise, so an LR(1) parser suffices for any of them.

The others are false. LALR(1) is built by merging LR(1) states with the same core, and the merge can create reduce-reduce conflicts that the LR(1) parser did not have (it cannot create new shift-reduce conflicts). The symbol table is used throughout compilation, by the parser, semantic analysis and code generation, not only by the lexer. Data flow analysis is a compile-time technique for optimisation; run-time memory management, such as heap allocation and garbage collection, does not depend on it.

Answer: C

A macroprocessor is an aid to the assembler.

In assembly language programming a macro names a frequently used group of instructions. The macroprocessor expands each macro call into the full instructions before assembly, so a macro assembler can translate the program. Macroprocessors arose as a pre-pass of the assembler, though the C preprocessor shows the same idea used with a compiler.

A linker combines separately translated object modules, a loader places a program in memory for execution, and an interpreter executes source statements directly. None of them needs macro expansion as its aid.