Exam Flashcards
What is a compiler?
- A computer program translates one language to another (Source Program to Target Program).
- A compiler is a complex program From 10,000 to 1,000,000 lines of codes.
- Compilers are used in many forms of computing (Command interpreters, interface programs).
Why Compiler ?
Writing machine language-numeric codes is time consuming and tedious.
What are the defects of assembly language ?
– Not easy to write.
– Difficult to read and understand.
What is an Interpreter ?
- Execute the source program immediately rather than generating object code.
- Speed of execution is slower than compiled code by a factor of 10 or more.
- Share many of their operations with compilers.
What are some examples of interpreters ?
BASIC, LISP, used often in educational or development situations.
What is an Assemblers ?
- A translator for the assembly language of a particular computer.
- Assembly language is a symbolic form of one machine language.
- A compiler may generate assembly language as its target language and an assembler finished the translation into object code.
What is a Linker ?
- Collect separate object files into a directly executable file.
- Connect an object program to the code for standard library functions and to resource supplied by OS.
- Becoming one of the principle activities of a compiler, depends on OS and processor.
What is a Loader ?
- Resolve all re-locatable address relative to a given base.
- Make executable code more flexible.
- Often as part of the operating environment, rarely as an actual separate program.
What is a Preprocessor ?
- Delete comments, include other files, and perform macro substitutions.
- Required by a language (as in C) or can be later add-ons that provide additional facilities.
What is an Editor ?
- Compiler have been bundled together with editor and other programs into an interactive development environment (IDE).
- Oriented toward the format or structure of the programming language, called structure based.
- May include some operations of a compiler, informing some errors.
What is a debugger ?
- Used to determine execution error in a compiled program.
- Keep tracks of most or all of the source code information.
- Halt execution at pre-specified locations called breakpoints.
- Must be supplied with appropriate symbolic information by the compiler.
What is a profile ?
- Collect statistics on the behavior of an object program during execution.
– Called Times for each procedures.
– Percentage of execution time Used to improve the execution speed of the program.
What are the six phases of a compiler ?
– Scanner. – Parser. – Semantic Analyzer. – Source code optimizer. – Code generator. – Target Code Optimizer.
What are the three auxiliary components of a compiler ?
– Literal table.
– Symbol table.
– Error Handler.
What does a scanner do ?
- Lexical analysis: it collects sequences of characters into meaningful units called tokens.
- Other operations: it may enter literals into the literal table.
What does a parser do ?
- Syntax analysis: it determines the structure of the program.
- The results of syntax analysis are a parse tree or a syntax tree.
What does a semantic analyzer do ?
- The semantics of a program are its “meaning”, as opposed to its syntax, or structure, that determines some of its running time behaviors prior to execution.
- Static semantics: declarations and type checking.
- Attributes: The extra pieces of information computed by semantic analyzer.
What does a source code optimizer do ?
- The earliest point of most optimization steps is just after semantic analysis.
- The code improvement depends only on the source code, and as a separate phase.
- Individual compilers exhibit a wide variation in optimization kinds as well as placement.
– Constant folding performed directly on annotated tree.
– Using intermediate code: three-address code, p-code.
What does a code generator do ?
- It takes the intermediate code or IR and generates code for target machine.
- The properties of the target machine become the major factor:
– Using instructions and representation of data.
– Code sequence in a hypothetical assembly language.
What does a target code optimizer do ?
- It improves the target code generated by the code generator:
– Address modes choosing.
– Instructions replacing.
– As well as redundant eliminating.
What are tokens ?
– A scanner collects characters into a token, as a value of an enumerated data type for tokens.
– May also preserve the string of characters or other derived information, such as name of identifier, value of a number token.
– A single global variable or an array of tokens.
What are syntax trees ?
– A standard pointer-based structure generated by parser.
– Each node represents information collect by parser or later, which maybe dynamically allocated or stored in symbol table.
– The node requires different attributes depending on kind of language structure, which may be represented as variable record.
What is a symbol table ?
– Keeps information associated with identifiers: function, variable, constants, and data types.
– Interacts with almost every phase of compiler.
– Access operation need to be constant-time.
– One or several hash tables are often used.
What is a lateral table ?
– Stores constants and strings, reducing size of program.
– Quick insertion and lookup are essential.
What are the types of normal forms ?
- Chomsky Normal Form (CNF).
- Greibach Normal Form (GNF).
What are the restriction for normal form ?
- non recursive start symbol.
- elimination of lambda rules.
- elimination of chain rules.
- useless symbols.
describe chomsky normal form
- all the productions must derive either two non-terminals or a single terminal.
- CNF restricts the number of symbols on the right side of a production to be two.
- The two symbols must be non-terminals or a single
terminal. - A context free grammar is said to be in chomsky normal form (CNF) if all its productions are of the form A → BC or A → a
where A, B, C are non-terminals and a is a terminal.
Describe greibach normal form
A context free grammar G= (V,Σ,P,S) is in greidbach normal form if each rule has one of the following forms:
- A → aA1A2…..An
- A → a
- S → λ
