Compiler Design

Important Topics that you have to go through before Appearing in the Final Exam.

1. Ambiguous Grammar

A grammar is said to be ambiguous if there exists more than one left most derivation or more than one right most derivation or more than one parse tree for a given input string. If the grammar is not ambiguous then we call it unambiguous grammar. If the grammar has ambiguity then it is good for compiler construction.

2. Parse Generator

In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine. The most common type of compiler-compiler is more precisely called a parser generator

3. SLR

SLR represents "Simple LR Parser". It is very simple and economical to execute. But it fails to make a parsing table for some class of grammars, i.e., why CLR and LALR are used which implements mainly all class or type of grammars.

4. What is Parsing in Compiler Design?

The process of transforming the data from one format to another is called Parsing. This process can be accomplished by the parser. The parser is a component of the translator that helps to organise linear text structure following the set of defined rules which is known as grammar.

5. Translator

A translator is a programming language processor that modifies a computer program from one language to another. It takes a program written in the source program and modifies it into a machine program. It can find and detect the error during translation.

There are various types of a translator which are as follows −

Compiler − A compiler is a program that translates a high-level language (for example, C, C++, and Java) into a low-level language (object program or machine program). The compiler converts high-level language into the low-level language using various phases. A character stream inputted by the customer goes through multiple stages of compilation which at last will provide target language.

Pre-Processor − Pre-Processor is a program that processes the source code before it passes through the compiler. It can perform under the control of what is referred to as pre-processor command lines or directives.

Assembler − An assembler is a translator which translates an assembly language program into an equivalent machine language program of the computer. Assembler provides a friendlier representation than a computer 0’s and 1’s that simplifies writing and reading programs.

An assembler reads a single assembly language source document and creates an object document including machine instructions and bookkeeping data that supports to merge of various object files into a program.

Interpreter − An interpreter is a program that executes the programming code directly rather than only translating it into another format. It translates and executes programming language statements one by one.

Macros − Many assembly languages support a “macro” facility whereby a macro statement will translate into a sequence of assembly language statements and possibly other macro statements before being translated into machine code. Therefore, a macro facility is a text replacement efficiency.

Linker − Linker is a computer program that connects and combines multiple object files to create an executable file. All these files might have been compiled by a separate assembler. The function of a linker is to inspect and find referenced module/routines in a program and to decide the memory location where these codes will be loaded creating the program instruction have an absolute reference.

Loader − The loader is an element of the operating framework and is liable for loading executable files into memory and implement them. It can compute the size of a program (instructions and data) and generate memory space for it. It can initialize several registers to start execution.

It creates a new address space for the program. This address space is huge to influence the text and data segments, along with a stack segment. It can repeat instructions and data from the executable file into the new address space.

6. Error

An Error is the blank entries in the symbol table. Errors in the program should be detected and reported by the parser. Whenever an error occurs, the parser can handle it and continue to parse the rest of the input.

7. Code Generator

A code generator is a compiler that translates the intermediate representation of the source program into the target program. In other words, a code generator translates an abstract syntax tree into machine-dependent executable code.

8. Context free grammar

Context free grammar is a formal grammar which is used to generate all possible strings in a given formal language.

Context free grammar G can be defined by four tuples as:

G= (V, T, P, S)  

Where,

G describes the grammar

T describes a finite set of terminal symbols.

V describes a finite set of non-terminal symbols

P describes a set of production rules

S is the start symbol.

In CFG, the start symbol is used to derive the string. You can derive the string by repeatedly replacing a non-terminal by the right hand side of the production, until all non-terminal have been replaced by terminal symbols.

9. Role of Parser

The parser obtains a string of tokens from the lexical analyzer and verifies that the string can be the grammar for the source language. It detects and reports any syntax errors and produces a parse tree from which intermediate code can be generated.

10. What is Parsing in Compiler Design?

The process of transforming the data from one format to another is called Parsing. This process can be accomplished by the parser. The parser is a component of the translator that helps to organise linear text structure following the set of defined rules which is known as grammar.

11. Finite Automata

Finite automata is a state machine that takes a string of symbols as input and changes its state accordingly. Finite automata is a recognizer for regular expressions. When a regular expression string is fed into finite automata, it changes its state for each literal

12. Regular Expression

Regular expression is an important notation for specifying patterns. Each pattern matches a set of strings, so regular expressions serve as names for a set of strings. Programming language tokens can be described by regular languages. The specification of regular expressions is an example of a recursive definition.

13. Scanner Generator

It generates lexical analyzers from the input that consists of regular expression description based on tokens of a language. It generates a finite automaton to recognize the regular expression

14. Syntex Tree

Tree in which each leaf node describes an operand & each interior node an operator. The syntax tree is shortened form of the Parse Tree

15. Parameter Parsing

The communication among procedures or functions or methods is known as parameter parsing. The values of a variable procedure are transferred to the called procedure by some mechanism

16. Memory Allocation

In this allocation scheme, the compilation data is bound to a fixed location in the memory and it does not change when the program executes. As the memory requirement and storage locations are known in advance, runtime support package for memory allocation and de-allocation is not required

17. Directed Acyclic Graph

Directed Acyclic Graph (DAG) is a tool that depicts the structure of basic blocks, helps to see the flow of values flowing among the basic blocks, and offers optimization too. DAG provides easy transformation on basic blocks. DAG can be understood here:

Leaf nodes represent identifiers, names or constants.

Interior nodes represent operators.

Interior nodes also represent the results of expressions or the identifiers/name where the values are to be stored or assigned.

18. Compiler

A compiler is a computer program that helps in translating the computer code from one programming language into another language. Basically, it translates the program written in the source language to the machine language. The compiling process contains an essential translation operation and error detection.

19. Grammar Rules

The productions of a grammar specify the manner in which the terminals and non-terminals can be combined to form strings. Each production consists of a non-terminal called the left side of the production, an arrow, and a sequence of tokens and/or on- terminals, called the right side of the production.

20. Local optimization

It involves finding the optimal solution for a specific region of the search space, or the global optima for problems with no local optima. Global optimization involves finding the optimal solution on problems that contain local optima.

21. Loop Optimization

It is the process of increasing execution speed and reducing the overheads associated with loops. It plays an important role in improving cache performance and making effective use of parallel processing capabilities. Most execution time of a scientific program is spent on loops.

Loop Optimization is a machine independent optimization.

22. Control Flow

In computer science, control flow is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an imperative programming language from a declarative programming language.

23. Data Flow

Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program's control-flow graph is used to determine those parts of a program to which a particular value assigned to a variable might propagate.

24. Instruction Scheduling

In computer science, instruction scheduling is a compiler optimization used to improve instruction-level parallelism, which improves performance on machines with instruction pipelines.

25. Target Machine

A target machine is a system (or systems) that runs the 4Test Agent, which is the software process that translates the commands in your scripts into GUI-specific commands, in essence, driving and monitoring your applications under test.

26. Compiler Optimization

In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers. Register allocation can happen over a basic block, over a whole function/procedure, or across function boundaries traversed via call-graph

27. Syntax Analysis

When an input string (source code or a program in some language) is given to a compiler, the compiler processes it in several phases, starting from lexical analysis (scans the input and divides it into tokens) to target code generation.

Syntax Analysis or Parsing is the second phase, i.e. after lexical analysis. It checks the syntactical structure of the given input, i.e. whether the given input is in the correct syntax (of the language in which the input has been written) or not. It does so by building a data structure, called a Parse tree or Syntax tree. The parse tree is constructed by using the pre-defined Grammar of the language and the input string. If the given input string can be produced with the help of the syntax tree (in the derivation process), the input string is found to be in the correct syntax. if not, the error is reported by the syntax analyzer.

The pushdown automata (PDA) is used to design the syntax analysis phase.

28. Pushdown Automata

In the theory of computation, a branch of theoretical computer science, a pushdown automaton is a type of automaton that employs a stack. Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines

29. Top-down parsing

 In computer science it is a parsing strategy where one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar. LL parsers are a type of parser that uses a top-down parsing strategy

30. Operator Grammar

A grammar that is used to define mathematical operators is called an operator grammar or operator precedence grammar. Such grammars have the restriction that no production has either an empty right-hand side (null productions) or two adjacent non-terminals in its right-hand side.