MCQs on Compiler Design

Normally programmers use high-level languages since they are easier to read, write, debug and maintain.

A compiler is a program that accepts code written in a high-level language such as Java, C/C++ and transforms it into assembly code which are instructions that can be executed by a computer processor.

An assembler emits object code. These usually have a .obj or .o file extension.

A scanner takes a sequence of characters from the source code and produces a sequence of tokens that are fed to the compiler's parser.

These are *top-down* and *bottom-up* parsing. The former looks at the top level of the parse tree and works it way down the parse tree using the grammar rules. The latter does the same except that it starts from the bottom of the parse tree.

A canonical LR parser is an LR(k) parser for k=1, i.e. with a single lookahead terminal. It is the most powerful among the rest.

Lexical analysis takes source code and breaks them down into tokens/syntactic classes.

A bottom-up parser results in the right-most derivation in reverse. An example of a bottom-up parser is the LR parser

Shift-reduce parsing involves two steps for bottom-up parsing. These are the shift-step and the reduce-step.

A hash table has a constant time access O(1) and thus very efficient for implementing a symbol table.

The result of top-down parsing is the left-most derivation. An example of a top-down parser is the LL Parser

A CFG specifies the syntax of a programming language.

Back tracking mean that if one derivation of a production fails, the syntax analyzer restarts the process using different rules of same production. Both recursive-descent parsing and predictive parsing avoid backtracking, this is why they are efficient.

This means that in a given interval of time, only a smaller subset of the list is probabilistically most likely to be accessed. This is improves the efficiency of a linear search and thus achieves a near constant time access in the best case.

Among the above, the compiler can only detect syntax and semantic errors in the code.

We check the grammar of the programming language during the second phase in compiler design which is syntax analysis.

Type checking involves verifying that each operation executed in a program is in accordance with the type system of the programming language.

A parse tree is a hierarchical representation of terminals and non-terminals. Interior nodes indicate non-terminals while leaf nodes are terminals.

explain here

In the lexical analysis phase, the lexical analyzer breaks programming language syntax into tokens, by removing any whitespace or comments in the source code. It is also referred to as the scanner.

Syntax analysis is also referred to as parsing. The syntax analyzer checks the syntactical structure of the input and verifies its correctness. This is done by building a Parse tree or Syntax tree.

There are two major compiler optimizations, the first if machine-dependent and the second if machine-independent.

Peephole optimizations involve improving the performance of the target program by examining short sequences of target instructions and replacing them with shorter/faster sequences. This includes reducing multiple jumps.

Three-address code is an intermediate code representation used by optimizing compilers to aid in the implementation of code-improving transformations.

A CFG consists of start symbol, a set of terminals and non-terminals and a set of productions.

A cross compiler is capable of creating executables for different platforms other than the one on which the compiler is running.

A shift-reduce parser has shift, reduce, error and accept actions.

Ambiguous grammar is CFG that produces multiple leftmost or rightmost derivations for the same specified string.

Loop fusion also called loop jamming is a compiler optimization and loop transformation where by multiple loops are replaced with a single loop.

Right linear grammar is a grammar whereby the non-terminal symbol is at the right side of the production.

When there are issues with the source code either syntactic or semantic errors, the compiler completes reading the program but wont produce machine code.

When there are issues with the source code, the interpreter will immediately stop before proceeding to the next instruction.

For example in C/C++, a pre-processor will remove all #include directives and #define directives. Generally if function entail, file inclusion, augmentation, macro-processing etc.

This is code that links, merges object files together to make an executable file.

A Java compiler compiles Java high-level code into platform-neutral Java bytecode that can run anywhere.

explain here

Left recursion is a problem during parsing. It can either leads to an infinite recursion. We solve this by parsing grammar that is preprocessed to eliminate the left recursion.

A loader is responsible for loading an executable into main memory for execution. It does this by calculating the size of a program the creating the needed space in memory for it.

The purpose of predictive parsing is to build top-down parser that never backtracks. For this, we transform a grammar by eliminating left recursion, and performing left factoring.

explain here

A DAG(Directed Acyclic Graph) is a tool used to determine the structure of basic blocks. It allows us see the flow of values flowing among the basic blocks. It is also useful for optimization.

During compilation, we have expressions that consume more system resources such as CPU cycles, time, and memory. We replace such expressions with cheaper expressions without compromising the output of expression. This is referred to as strength reduction

This is a parse tree with the attribute values at each node for given input string. It is also referred to as a decorated parse tree.

In a Directed Acyclic Graph(DAG), leaf nodes represent identifiers, names or constants while interior nodes represent operators.

A recursive descent parser is a top-down parser built from a set of mutually recursive procedures whereby each procedure implements a non-terminal of the given grammar.

To convert an arbitrary CFG into an LL(1) grammar we first remove ambiguity, then remove left recursion and finally make the grammar deterministic using left factoring. If the grammar is ambiguous, left recursive and has left factoring, it is not an LL(1) since for LL(1) all three are removed.

We say a grammar is an LL(1) if the associated LL(1) parsing table has at most a single production for each table entry.

During a bottom-up evaluation of a syntax directed definition, inherited attributes can be evaluated only if the definition if L-attributed.

We say a grammar is ambiguous if there is a string s such that the grammar has more than one left-most derivations for s. We can also come up with multiple right-most derivations for a string to prove the statement but not both right-most and left-most.

– has a higher precedence than *

All of the above checks are included during static checking.

Type checking is done in the syntax analysis phase of compiler design while type checking is done in the semantic analysis phase.

References are resolved at link time by a linker. The linker extracts object modules from libraries and adds them to the executable.

They allow for portability for other target processors. Intermediate code is machine independent and at the same time close to machine code.

SLR is the easiest to implement while Canonical LR is the most powerful.