Syntax Trees | Compiler Design - Computer Science Engineering (CSE) PDF Download

2.2 SYNTAX TREES: 

Parse tree can be presented in a simplified form with only the relevant structure information by:

•  Leaving out chains of derivations (whose sole purpose is to give operators difference precedence).
• Labeling the nodes with the operators in question rather than a non-terminal. The simplified Parse tree is sometimes called as structural tree or syntax tree.
   

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:

• It should report the presence of errors clearly and accurately.
•  It should recover from each error quickly enough to be able to detect subsequent errors.
•  It should not significantly slow down the processing of correct programs.
  
  2.3 Ambiguity:
  Several derivations will generate the same sentence, perhaps by applying the same productions in a different order. This alone is fine, but a problem arises if the same sentence has two distinct parse trees. A grammar is ambiguous if there is any sentence with more than one parse tree.
  
  Any parses for an ambiguous grammar has to choose somehow which tree to return. There are a number of solutions to this; the parser could pick one arbitrarily, or we can provide some hints about which to choose. Best of all is to rewrite the grammar so that it is not ambiguous. There is no general method for removing ambiguity. Ambiguity is acceptable in spoken languages. Ambiguous programming languages are useless unless the ambiguity can be resolved.
  
  Fixing some simple ambiguities in a grammar:
  Ambiguous language unambiguous (i) A → B | AA Lists of one or more B’s A → BC C → A | E (ii) A → B | A;A Lists of one or more B’s with punctuation A → BC C → ;A | E (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.

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
Where,
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:

•  This can lead to non termination in a top-down parser.
•  for a top-down parser, any recursion must be right recursion.
•  we would like to convert the left recursion to right recursion.