PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q16

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Lexical Analysis with DFA; Top-Down & Bottom-Up Parsing

Question

How syntax analyzer helps to check whether the particular block of code is syntactically correct or not. Explain with suitable example.

Solution

Mechanism of Syntax Checking Using CFG: The syntax analyzer (parser) takes the token stream generated by the lexical analyzer and verifies whether it conforms to the structural rules of the programming language defined by a Context-Free Grammar (CFG):

  1. Grammar Verification: The parser attempts to construct a derivation or parse tree from the grammar's start symbol to the token sequence.
  2. Validation: If a complete parse tree can be successfully built using top-down (e.g., LL) or bottom-up (e.g., LR/LALR) parsing, the code block is deemed syntactically correct.
  3. Error Reporting and Recovery: If an unexpected token occurs that cannot be reduced or expanded according to the parsing table, the parser reports a syntax error with line/column coordinates and applies error recovery strategies (panic mode or phrase-level recovery).

Concrete Example with Expression Grammar: Consider a simple statement grammar:

Case 1: Syntactically Correct Statement ():

Case 2: Syntactically Incorrect Statement ():

Answer:

The syntax analyzer verifies code against a Context-Free Grammar by constructing a parse tree. For valid statements like x = a + b * 2;, complete derivations succeed; for invalid constructs like x = a + * b;, unexpected token transitions trigger syntax error diagnosis.

All past exam questions for Theory of Computation