2.2 SYNTAX TREES:
Parse tree can be presented in a simplified form with only the relevant structure information by:
Syntax Error Handling: If a compiler had to process only correct programs, its design & implementation would be greatly simplified. But programmers frequently write incorrect programs, and a good compiler should assist the programmer in identifying and locating errors.The programs contain errors at many different levels. For example, errors can be:
1) Lexical – such as misspelling an identifier, keyword or operator
2) Syntactic – such as an arithmetic expression with un-balanced parentheses.
3) Semantic – such as an operator applied to an incompatible operand.
4) Logical – such as an infinitely recursive call.
Much of error detection and recovery in a compiler is centered around the syntax analysis phase. The goals of error handler in a parser are:
|(i) A → B | AA|| Lists of one or more B’s|
C → A | E
|(A → BC|
|(ii) A → B | A;A||Lists of one or more B’s with punctuation|
C → ;A | E
|A → BC|
|(iii) A → B | AA | E||lists of zero or more B’s||A → BA | E|
Any sentence with more than two variables, such as (arg, arg, arg) will have multiple parse trees
2.4 Left Recursion:
If there is any non terminal A, such that there is a derivation A The A ⇒α for some string⇒, then the grammar is left recursive.
Algorithm for eliminating left Recursion:
1. Group all the A productions together like this: A ⇒ A α1 | A α2 | - - - | A αm | β1 | β2 | - - - | βn
A is the left recursive non-terminal,
αis any string of terminals and
β is any string of terminals and non terminals that does not begin with A.
2. Replace the above A productions by the following: A ⇒ β1 A I |β2 A I | - - - |βn A I A I ⇒ ⇒1 A I | ⇒2 A I | - - - |⇒m A I | ∈ Where, AI is a new non terminal. Top down parsers cannot handle left recursive grammars.
If our expression grammar is left recursive: