Recently Updated Compiler Design Interview Questions Part – 2
Define Compiler-compiler.
Systems to help with the compiler-writing process are often been referred to as compiler-compilers, compiler-generators or translator-writing systems.
Largely they are oriented around a particular model of languages , and they are suitable for generating compilers of languages similar model.
List The Various Compiler Construction Tools.
The following is a list of some compiler construction tools:
Parser generators
Scanner generators
Syntax-directed translation engines
Automatic code generators
Data-flow engines
Differentiate Tokens, Patterns, Lexeme.
Tokens-
Sequence of characters that have a collective meaning.
Patterns-
There is a set of strings in the input for which the same token is produced as output. This set of strings is described by a rule called a pattern associated with the token
Lexeme-
A sequence of characters in the source program that is matched by the pattern for a token.
List The Operations On Languages.
Union –
L U M ={s | s is in L or s is in M}
Concatenation –
LM ={st | s is in L and t is in M}
Kleene Closure –
L* (zero or more concatenations of L)
Positive Closure –
L+ ( one or more concatenations of L)
Write A Regular Expression For An Identifier.
An identifier is defined as a letter followed by zero or more letters or digits.
The regular expression for an identifier is given as
letter (letter | digit)*
Mention The Various Notational Short Hands For Representing Regular Expressions.
One or more instances (+)
Zero or one instance (?)
Character classes ([abc] where a,b,c are alphabet symbols denotes the regular expressions a | b | c.)
Non regular sets
What Is The Function Of A Hierarchical Analysis?
Hierarchical analysis is one in which the tokens are grouped hierarchically into nested collections with collective meaning.Also termed as Parsing.
What Does A Semantic Analysis Do?
Semantic analysis is one in which certain checks are performed to ensure that components of a program fit together meaningfully.Mainly performs type checking.
List The Various Error Recovery Strategies For A Lexical Analysis.
Possible error recovery actions are:
Panic mode recovery
Deleting an extraneous character
Inserting a missing character
Replacing an incorrect character by a correct character
Transposing two adjacent characters
Mention The Basic Issues In Parsing.
There are two important issues in parsing.
Specification of syntax
Representation of input after parsing.
Why Lexical And Syntax Analysers Are Separated Out?
Reasons for separating the analysis phase into lexical and syntax analyzers:
Simpler design.
Compiler efficiency is improved.
Compiler portability is enhanced.
Define A Context Free Grammar.
A context free grammar G is a collection of the following
· V is a set of non terminals
· T is a set of terminals
· S is a start symbol
· P is a set of production rules
G can be represented as G = (V,T,S,P)
Production rules are given in the following form
Non terminal → (V U T)*
Briefly Explain The Concept Of Derivation.
Derivation from S means generation of string w from S. For constructing derivation two things are important.
i) Choice of non terminal from several others.
ii) Choice of rule from production rules for corresponding non terminal.
Instead of choosing the arbitrary non terminal one can choose
i) either leftmost derivation – leftmost non terminal in a sentinel form.
ii) or rightmost derivation – rightmost non terminal in a sentinel form.
Define Ambiguous Grammar.
A grammar G is said to be ambiguous if it generates more than one parse tree for some sentence of language L(G).
i.e. both leftmost and rightmost derivations are same for the given sentence.
What Is A Operator Precedence Parser?
A grammar is said to be operator precedence if it possess the following properties:
1. No production on the right side is ε.
2. There should not be any production rule possessing two adjacent non terminals at the right hand side.
List The Properties Of Lr Parser.
1. LR parsers can be constructed to recognize most of the programming languages for which the context free grammar can be written.
2. The class of grammar that can be parsed by LR parser is a superset of class of grammars that can be parsed using predictive parsers.
3. LR parsers work using non backtracking shift reduce technique yet it is efficient one.
Mention The Types Of Lr Parser.
· SLR parser- simple LR parser
· LALR parser- lookahead LR parser
· Canonical LR parser
What Are The Problems With Top Down Parsing?
The following are the problems associated with top down parsing:
· Backtracking
· Left recursion
· Left factoring
· Ambiguity