Discussion
A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet {a,b,c}.
\(T_{1}:\ a?\,(b|c)^{*}a\)
\(T_{2}:\ b?\,(a|c)^{*}b\)
\(T_{3}:\ c?\,(b|a)^{*}c\)
Note that 'x?' means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix.
If the string \(bbaacabc\) is processed by the analyzer, which one of the following is the sequence of tokens it outputs?
Answer: D
The analyzer outputs \(T_{3}T_{3}\).
It always takes the longest prefix any pattern matches. On bbaacabc:
- \(T_{1}\) can match bba (no leading a, then bb, then a): 3 characters.
- \(T_{2}\) can match only bb, since \((a|c)^{*}\) cannot absorb the second b: 2 characters.
- \(T_{3}\) can match bbaac (no leading c, then bbaa from \((b|a)^{*}\), then c): 5 characters.
So the first token is \(T_{3}\), for bbaac. The rest is abc: \(T_{3}\) matches all of it (ab, then c), while \(T_{1}\) matches only a and \(T_{2}\) only ab. So the second token is \(T_{3}\) too.
The options starting with \(T_{1}\) or \(T_{2}\) take a shorter prefix than the longest-match rule allows.
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