Parse Trees in Top Down Parsing

A parsing is a process, which takes the input string w and produces either a parse tree(syntactic structure) or generate syntactic errors

The parser takes the tokens as input, and generates a tree like structure called parse tree

Grammar naturally describes the hierarchical syntactical structure of the sentences of the language they define

These hierarchical structures are called parse trees

A parse tree has

                Terminals at the leaves

                Non-Terminals at the interior nodes

                Sub tree of a parse tree describes an instance of an abstraction of the sentence

Example 1:

Example 2:

E → E + E | E * E | (E) | id

Statement A * B + C

Ambiguity

A Grammar is said to be ambiguous if it produces more than one parse tree for some sentence

Ambiguous  Grammars should be avoided

Example:

The below grammar is ambiguous because there are two distinct parse trees for the statement
A = B + C * A

Example 2:
Let G be a Context Free Grammar for which the production rules are given as below

S → aB | bA

A → a | aS | bAA

B → b | bS | aBB

Derive the string ‘aaabbabbba’ using grammar

This grammar is ambiguous because it allows the expression to grow on the both sides (left and right), rather than allowing the parse tree of an expression to grow only on the right

Syntactic ambiguity is a problem because compilers often base the semantics of structures on their syntactic form

• If a language structure has more than one parse tree, then its meaning cannot be determined uniquely

The other characteristics to determine the ambiguity of the grammar are

•  If the grammar generates more than one leftmost derivation
•  If the grammar generates more than one rightmost derivation

A general way to avoid the ambiguity is rewriting the grammar

Instead of rewriting the grammar to solve ambiguity

• Use more natural grammar along with disambiguating declarations with enforcing operator precedence and associativity

Example:

Find whether the following grammar is ambiguous or not.

S → AB | aaB

A → a | Aa

B → b

Construct parse tree for the string ‘aab’.

There are two different parse trees for deriving string 'aab'. Hence the above given grammar is an ambiguous grammar

Operator Precedence

The order of evaluation is the basic semantic issue when an expression contains more than one operator

Example: A + B + C * A

                In this expression it is add, then multiply or vice versa

This statement issue is addressed by Operator Precedence

A parse tree can support operator precedence by the rule that the Operator Precedence lower in parse trees are evaluated before those generated higher up in the parse tree

                This rule may allow the expression to grow on the both sides (left and right)

                This can be avoided by enforcing the Operator Precedence

Example 1:

Example 2:
Derivation : A + B + C * A <assign> => <id> = <expr>

• Every derivation with an unambiguous grammar has a unique parse tree
• Both of the above derivations are represented by the same parse tree

Associativity of Operators
Associativity is the order of evaluation of operators with the same precedence
When an expression includes two operators that have the same precedence (as * and /), for example A / B * C a semantic rule is required to specify which should have precedence. This rule is named associativity
Consider the following example of an assignment statement of a language which supports power operator (**)
Example: A = 3** 3 ** 4
This execution can be evaluated to A=531441 with left associativity and can be evaluated to A = A will be 262144
To fix this ambiguity, a grammar can define associativity rules to make it left recursive or right recursive

Left Recursive: A grammar rule that has it its LHS also appearing at the beginning of its RHS

                <expr> → <expr> + <term>

                Supports left associativity

Right Recursive: A grammar rule that has its LHS at the rught end of the RHS

Example:

                <factor> → <expr> ** <factor>

                                |<expr>

                <expr> → (<expr>)

                                |id

This can be used to describe exponentiation right associative operator.

Derivations

Home

Parser