Compiler Design Gate Questions
(a) Leftmost derivation
(b) Leftmost derivation traced out in reverse
(c) Rightmost derivation
(d) Rightmost derivation traced out in reverse
Answer (a)
Top-down parsing (LL)
In top down parsing, we just start with the start symbol and compare the right side of the different productions against the first piece of input to see which of the productions should be used.
A top down parser is called LL parser because it parses the input from Left to right, and constructs a Leftmost derivation of the sentence.
Algorithm (Top Down Parsing)
a) In the current string, choose leftmost nonterminal.
b) Choose a production for the chosen nonterminal.
c) In the string, replace the nonterminal by the right-hand-side
of the rule.
d) Repeat until no more nonterminals.
LL grammars are often classified by numbers, such as LL(1), LL(0) and
so on. The number in the parenthesis tells the maximum number of
terminals we may have to look at at a time to choose the right
production at any point in the grammar. The most common (and useful) kind of LL grammar is LL(1) where you can always choose the right production by looking at only the first terminal on the input at any given time. With LL(2) you have to look at two symbols, and so on. There exist grammars that are not LL(k) grammars for any fixed value of k at all, and they are sadly quite common.
Let us see an example of top down parsing for following grammar. Let input string be ax.
S -> Ax
A -> a
A -> b
An LL(1) parser starts with S and asks “which production should I
attempt?” Naturally, it predicts the only alternative of S. From there
it tries to match A by calling method A (in a recursive-descent parser).
Lookahead a predicts productionA -> aThe parser matches a, returns to S and matches x. Done. The derivation tree is:
S
/ \
A x
|
a
References:http://www.garshol.priv.no/download/text/bnf.html
http://en.wikipedia.org/wiki/Top-down_parsing
http://www.cs.wm.edu/~noonan/animations/lderive.html
http://en.wikipedia.org/wiki/LL_parser
2. The process of assigning load addresses to the various parts of the program and adjusting the code and data in the program to reflect the assigned addresses is called (GATE CS 2001)
a) Assembly
b) Parsing
c) Relocation
d) Symbol resolution
Answer: (c)
Relocation is the process of replacing symbolic references or names of libraries with actual usable addresses in memory before running a program. It is typically done by the linker during compilation (at compile time), although it can be done at runtime by a relocating loader. Compilers or assemblers typically generate the executable with zero as the lower-most starting address. Before the execution of object code, these addresses should be adjusted so that they denote the correct runtime addresses.
Relocation is typically done in two steps:
1. Each object code has various sections like code, data, .bss etc. To combine all the objects to a single executable, the linker merges all sections of similar type into a single section of that type. The linker then assigns runtime addresses to each section and each symbol. At this point, the code (functions) and data (global variables) will have unique runtime addresses.
2. Each section refers to one or more symbols which should be modified so that they point to the correct runtime addresses.
References:
http://en.wikipedia.org/wiki/Relocation_(computer_science)
3. Which of the following statements is false? (GATE CS 2001)
a) An unambiguous grammar has same leftmost and rightmost derivation
b) An LL(1) parser is a top-down parser
c) LALR is more powerful than SLR
d) An ambiguous grammar can never be LR(k) for any k
Answer: (a)
If a grammar has more than one leftmost (or rightmost) derivation for a single sentential form, the grammar is ambiguous. The leftmost and rightmost derivations for a sentential form may differ, even in an unambiguous grammar
4. Which of the following grammar rules violate the requirements of an operator grammar? P, Q, R are nonterminals, and r,s,t are terminals (GATE CS 2004).
(i) P -> QR
(ii) P -> QsR
(iii) P ->
(iV) P -> QtRr
a) (i) only
b) (i) and (iii) only
c) (ii) and (iii) only
d) (iii) and (iv) only
Answer: (b)
Explanation:
An operator precedence parser is a bottom-up parser that interprets an operator-precedence grammar. For example, most calculators use operator precedence parsers to convert from the human-readable infix notation with order of operations format into an internally optimized computer-readable format like Reverse Polish notation (RPN).
An operator precedence grammar is a kind of context-free grammar that can be parsed with an operator-precedence parser. It has the property that no production has either an empty (
)
right-hand side or two adjacent nonterminals in its right-hand side.
These properties allow the terminals of the grammar to be described by a
precedence relation, and the a parser that exploits that relation is
considerably simpler than more general-purpose parsers such as LALR
parsers.References:
http://en.wikipedia.org/wiki/Operator-precedence_grammar
http://en.wikipedia.org/wiki/Operator-precedence_parser
5. Consider the grammar with the following translation rules and E as the start symbol.
E -> E1 #T {E.value = E1.value * T.value}
| T {E.value = T.value}
T -> T1 & F {T.value = T1.value + F.value}
|F {T.value= F.value}
F -> num {F.value = num.value}
Compute E.value for the root of the parse tree for the expression:2 # 3 & 5 # 6 &4. (GATE CS 2004)
a) 200
b) 180
c) 160
d) 40
Answer: (c)
Explanation:
We can calculate the value by constructing the parse tree for the expression 2 # 3 & 5 # 6 &4.
Alternatively, we can calculate by considering following precedence and associativity rules.
Precedence in a grammar is enforced by making sure that a production rule with higher precedence operator will never produce an expression with operator with lower precedence.
In the given grammar ‘&’ has higher precedence than ‘#’.
Left associativity for operator * in a grammar is enforced by making sure that for a production rule like S -> S1 * S2 in grammar, S2 should never produce an expression with *. On the other hand, to ensure right associativity, S1 should never produce an expression with *.
In the given grammar, both ‘#’ and & are left-associative.
So expression 2 # 3 & 5 # 6 &4 will become
((2 # (3 & 5)) # (6 & 4))
Let us apply translation rules, we get
((2 * (3 + 5)) * (6 + 4)) = 160.
6. Given the following expression grammar:
E -> E * F | F+E | F
F -> F-F | id
which of the following is true? (GATE CS 2000)
(a) * has higher precedence than +
(b) – has higher precedence than *
(c) + and — have same precedence
(d) + has higher precedence than *
Answer(b)
Precedence in a grammar is enforced by making sure that a production rule with higher precedence operator will never produce an expression with operator with lower precedence.
In the given grammar ‘-’ has higher precedence than ‘*’
7. Consider a program P that consists of two source modules M1 and M2 contained in two different files. If M1 contains a reference to a function defined in M2 the reference will be resolved at (GATE CS 2004)
a) Edit time
b) Compile time
c) Link time
d) Load time
Answer (c)
Compiler transforms source code into the target language. The target language is generally in binary form known as object code. Typically, an object file can contain three kinds of symbols:
* defined symbols, which allow it to be called by other modules,
* undefined symbols, which call the other modules where these symbols are defined, and
* local symbols, used internally within the object file to facilitate relocation.
When a program comprises multiple object files, the linker combines these files into a unified executable program, resolving the symbols as it goes along.
http://en.wikipedia.org/wiki/Compiler
http://en.wikipedia.org/wiki/Linker_%28computing%29
8. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar? (GATE CS )
(a) Removing left recursion alone
(b) Factoring the grammar alone
(c) Removing left recursion and factoring the grammar
(d) None of the above
Answer(d)
Removing left recursion and factoring the grammar do not suffice to convert an arbitrary CFG to LL(1) grammar.
http://pages.cpsc.ucalgary.ca/~robin/class/411/LL1.3.html
9. Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between nl and n2 is (GATE CS 2003)
(a) n1 is necessarily less than n2
(b) n1 is necessarily equal to n2
(c) n1 is necessarily greater than n2
(d) none of the above
Answer (b)
http://parasol.tamu.edu/people/rwerger/Courses/434/lec10.pdf
http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/11-LALR-Parsing.pdf
No comments:
Post a Comment