Which of the following is NOT a top-down parsing method?
Answer: A
The first three all build the tree from the root downward. Shift-reduce parsing is the general bottom-up technique of which the LR family are the practical instances. The direction in which the tree is built is what separates the two families.
Please log in or register to report this question.
The following are all reasons to prefer a parser generator over a hand written parser EXCEPT
Answer: B
Correct answer: the generated parser always produces better error messages
Error messages are generally the generated parser’s weakness rather than its strength, since the tool knows only that no action was available and not what the programmer probably meant. That is exactly why many production compilers use hand written recursive descent. The other three are genuine advantages of generation.
Please log in or register to report this question.
Many production compilers use hand written recursive descent parsers because
Answer: C
Correct answer: error messages and recovery can be tailored precisely
A hand written parser knows where it is in the grammar in terms a person can understand, so it can say what was expected and recover in a way suited to the construct. It also gives control over performance and over constructs that fit the LR model awkwardly. The cost is that the grammar and the code must be kept in step by hand.
Please log in or register to report this question.
The parse of a program has succeeded when
Answer: D
Acceptance requires both conditions together. Exhausting the input with symbols left on the stack, or reaching the start symbol with input remaining, are both errors. The end marker in the augmented grammar is what makes the test straightforward.
Please log in or register to report this question.
A parser reading a program that is syntactically correct but semantically meaningless will
Answer: A
The parser judges form alone. A statement adding a string to a function name parses perfectly well and is rejected only when types are checked. Form and meaning are genuinely separate questions and are answered by separate phases.
Please log in or register to report this question.
Assertion (A): Syntax analysis and semantic analysis are kept as separate phases.
Reason (R): Context free grammars can express the form of a program but not the relationships between distant parts of it.
Answer: B
Both are true and the reason gives the mechanism, and the division reflects a genuine limit of the formalism. Attempting to force declaration rules into the grammar would make it enormous and still not cover every case.
Please log in or register to report this question.
The primary output of the syntax analysis phase is
Answer: C
Whether a parse tree or an abstract syntax tree, the structure is what later phases traverse. Some single pass compilers build no tree and act during the parse instead. Whether to build one is a design decision rather than a requirement of the method.
Please log in or register to report this question.
Consider the following grammar \(G\), with \(S\) as the start symbol. The grammar \(G\) has three incomplete productions denoted by (1), (2), and (3).
\(S \to daT\ |\) ___(1)___
\(T \to aS\ |\ bT\ |\) ___(2)___
\(R \to\) ___(3)___ \(|\ \epsilon\)
The set of terminals is \(\{a, b, c, d, f\}\). The FIRST and FOLLOW sets of the different non-terminals are as follows.
FIRST(\(S\)) = \(\{c, d, f\}\), FIRST(\(T\)) = \(\{a, b, \epsilon\}\), FIRST(\(R\)) = \(\{c, \epsilon\}\)
FOLLOW(\(S\)) = FOLLOW(\(T\)) = \(\{c, f, \$\}\), FOLLOW(\(R\)) = \(\{f\}\)
Which one of the following options CORRECTLY fills in the incomplete productions?
GATE CS - 2024,
Answer: A
The productions are (1) \(S \to Rf\) (2) \(T \to \epsilon\) (3) \(R \to cTR\).
Check them against the given sets. FIRST(T) contains \(\epsilon\), so T needs an \(\epsilon\) production: \(T \to \epsilon\), which rules out \(T \to cT\) (that would put c in FIRST(T)). FIRST(S) = {c, d, f}: d comes from daT, and \(S \to Rf\) adds FIRST(R) = {c} plus f because R is nullable. \(S \to fR\) would give only {d, f}.
With \(R \to cTR\): FIRST(R) = {c, \(\epsilon\)}; FOLLOW(R) = {f} from \(S \to Rf\); and FOLLOW(T) gets c from the R after T and, since R is nullable, FOLLOW(R) = {f}, while \(S \to daT\) and \(T \to aS\) make FOLLOW(T) = FOLLOW(S) = {c, f, \$}. Every given set matches, so the first option is the one that fits.
Please log in or register to report this question.
A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example,
int a[10][3];The grammars use \(D\) as the start symbol, and use six terminal symbols int ; id [ ] num.
| Grammar G1 | Grammar G2 |
|---|---|
| D → int L; | D → int L; |
| L → id [E | L → id E |
| E → num] | E → E[num] |
| E → num] [E | E → [num] |
Which of the grammars correctly generate the declaration mentioned above?
GATE CS - 2016,
Answer: A
Both G1 and G2 generate the declaration correctly.
G1 derives int a[10][3]; as D ⇒ int L; ⇒ int id [E; then E ⇒ num] [E ⇒ num] [num], giving int id [num] [num];. The rule E → num] ends the dimensions and E → num] [E adds another, so it generates one or more dimensions.
G2 derives it as D ⇒ int L; ⇒ int id E; with E ⇒ E[num] ⇒ [num][num]. E → [num] is one dimension and the left-recursive E → E[num] appends more, again at least one.
Both grammars produce exactly the declarations with one or more bracketed sizes, so the options claiming only one, or neither, are wrong.
Please log in or register to report this question.
Consider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #.
Which one of the following is correct for the given parse tree?
GATE CS - 2018,
Answer: A
The tree shows that $ has higher precedence and is left associative; # is right associative.
Precedence: the $ operations sit below the # operations, so b$c$d is grouped first and becomes an operand of #. The operator applied first, lower in the tree, binds tighter, so $ has higher precedence.
Associativity of $: in b$c$d the lower $ joins b and c, and the upper $ joins that result with d, giving (b$c)$d, which is left associative.
Associativity of #: the tree reads a # ((b$c$d) # (e#f)), so each # takes everything to its right as its right operand. That is right associative. The options giving # the higher precedence, or calling # left associative, contradict the tree.
Please log in or register to report this question.