Discussion
Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals \(\{S, A\}\) and terminals \(\{a, b\}\).
\(S \rightarrow aA\) { print 1 }
\(S \rightarrow a\) { print 2 }
\(A \rightarrow Sb\) { print 3 }
Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:
Answer: C
The output is 2 3 1.
The input aab is derived as \(S \Rightarrow aA \Rightarrow aSb \Rightarrow aab\). A bottom-up parser performs the reductions in the reverse of this rightmost derivation, printing as each rule is reduced:
- Shift a, shift a; reduce the second a to \(S\) by \(S \rightarrow a\): print 2.
- Shift b; reduce \(Sb\) to \(A\) by \(A \rightarrow Sb\): print 3.
- Reduce \(aA\) to \(S\) by \(S \rightarrow aA\): print 1.
1 3 2 is the top-down (preorder) order of the same rules, and 2 2 3 would need two reductions by \(S \rightarrow a\), but the first a is never reduced on its own. The input is in the language, so there is no syntax error.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development