Skip to main content

Parse Tree | Derivations

Parse Tree-

  • The process of deriving a string is called as derivation.
  • The geometrical representation of a derivation is called as a parse tree or derivation tree.
Example-


Let us consider a string w = aaabbabbba
Now, let us derive the string w using leftmost derivation.

Leftmost Derivation-

S   → aB
→  aaBB                   (Using B → aBB)

→ aaaBBB                (Using B → aBB)
→ aaabBB                (Using B → b)
→ aaabbB                (Using B → b)
→ aaabbaBB            (Using B → aBB)
→ aaabbabB            (Using B → b)
→ aaabbabbS          (Using B → bS)
→ aaabbabbbA        (Using S → bA)
→ aaabbabbba         (Using A → a)

2. Rightmost Derivation-

  • The process of deriving a string by expanding the rightmost non-terminal at each step is called as rightmost derivation.
  • The geometrical representation of rightmost derivation is called as a rightmost derivation tree.

Example-

Consider the following grammar-
S → aB / bA
S → aS / bAA / a
B → bS / aBB / b
(Unambiguous Grammar)
Let us consider a string w = aaabbabbba
Now, let us derive the string w using rightmost derivation.

Rightmost Derivation-

S   → aB
→  aaBB                    (Using B → aBB)
→ aaBaBB                 (Using B → aBB)
→ aaBaBbS               (Using B → bS)
→ aaBaBbbA             (Using S → bA)
→ aaBaBbba              (Using A → a)
→ aaBabbba              (Using B → b)
→ aaaBBabbba          (Using B → aBB)
→ aaaBbabbba          (Using B → b)
→ aaabbabbba           (Using B → b)


Properties Of Parse Tree-

  • Root node of a parse tree is the start symbol of the grammar.
  • Each leaf node of a parse tree represents a terminal symbol.
  • Each interior node of a parse tree represents a non-terminal symbol.
  • Parse tree is independent of the order in which the productions are used during derivations.

Yield Of Parse Tree-

  • Concatenating the leaves of a parse tree from the left produces a string of terminals.
  • This string of terminals is called as yield of a parse tree.

PRACTICE PROBLEMS BASED ON DERIVATIONS AND PARSE TREE-

Problem-01:

Consider the grammar-
S → bB / aA
A → b / bS / aAA
B → a / aS / bBB
For the string w = bbaababa, find-
  1. Leftmost derivation
  2. Rightmost derivation
  3. Parse Tree

Solution-

1. Leftmost Derivation-

S   → bB
→ bbBB              (Using B → bBB)
→ bbaB              (Using B → a)
→ bbaaS            (Using B → aS)
→ bbaabB          (Using S → bB)
→ bbaabaS        (Using B → aS)
→ bbaababB      (Using S → bB)
→ bbaababa       (Using B → a)

2. Rightmost Derivation-

S   → bB
→ bbBB                (Using B → bBB)
→ bbBaS              (Using B → aS)
→ bbBabB            (Using S → bB)
→ bbBabaS          (Using B → aS)
→ bbBababB        (Using S → bB)
→ bbBababa        (Using B → a)
→ bbaababa         (Using B → a)

3. Parse Tree-

 

  • Whether we consider the leftmost derivation or rightmost derivation, we get the above parse tree.
  • The reason is given grammar is unambiguous.

Problem-02:

Consider the grammar-
S → A1B
A → 0A / ∈
B → 0B / 1B / ∈
For the string w = 00101, find-
  1. Leftmost derivation
  2. Rightmost derivation
  3. Parse Tree

Solution-

1. Leftmost Derivation-

S   → A1B
→ 0A1B              (Using A → 0A)
→ 00A1B            (Using A → 0A)
→ 001B              (Using A → ∈)
→ 0010B            (Using B → 0B)
→ 00101B          (Using B → 1B)
→ 00101             (Using B → ∈)

2. Rightmost Derivation-

S   → A1B
→ A10B                (Using B → 0B)
→ A101B              (Using B → 1B)
→ A101                (Using B → ∈)
→ 0A101              (Using A → 0A)
→ 00A101            (Using A → 0A)

→ 00101               (Using A → ∈)

3. Parse Tree-

Whether we consider the leftmost derivation or rightmost derivation, we get the above parse tree.
  • The reason is given grammar is unambiguous.






Comments

Post a Comment

Popular posts from this blog

Code Optimization | Code Optimization Techniques

Code Optimization- Code Optimization is an approach to enhance the performance of the code. The process of code optimization involves- Eliminating the unwanted code lines Rearranging the statements of the code Advantages- The optimized code has the following advantages- Optimized code has faster execution speed. Optimized code utilizes the memory efficiently. Optimized code gives better performance. Code Optimization Techniques- Important code optimization techniques are- Compile Time Evaluation Common sub-expression elimination Dead Code Elimination Code Movement Strength Reduction 1. Compile Time Evaluation- Two techniques that falls under compile time evaluation are- A) Constant Folding- In this technique, As the name suggests, it involves folding the constants. The expressions that contain the operands having constant values at compile time are evaluated. Those express...
Post a Comment
Read more

Elimination of Left Factoring

In left factoring, We make one production for each common prefixes. The common prefix may be a terminal or a non-terminal or a combination of both. Rest of the derivation is added by new productions. The grammar obtained after the process of left factoring is called as Left Factored Grammar . Example-   PRACTICE PROBLEMS BASED ON LEFT FACTORING- Problem-01: Do left factoring in the following grammar- S → iEtS / iEtSeS / a E → b Solution- The left factored grammar is- S → iEtSS’ / a S’ → eS / ∈ E → b Problem-02: Do left factoring in the following grammar- A → aAB / aBc / aAc Solution- Step-01: A → aA’ A’ → AB / Bc / Ac Again, this is a grammar with common prefixes. Step-02: A → aA’ A’ → AD / Bc D → B / c This is a left factored grammar. Problem-03: Do left factoring in the following grammar- S → bSSaaS / bSSaSb / bSb / a Solution- ...
Post a Comment
Read more

FIRST & FOLLOW Calculation

First Function- First(α) is a set of terminal symbols that begin in strings derived from α. Example- Consider the production rule- A → abc / def / ghi Then, we have- First(A) = { a , d , g } Rules For Calculating First Function- Rule-01: For a production rule X → ∈, First(X) = { ∈ } Rule-02: For any terminal symbol ‘a’, First(a) = { a } Rule-03: For a production rule X → Y1Y2Y3, Calculating First(X) If ∈ ∉ First(Y1), then First(X) = First(Y1) If ∈ ∈ First(Y1), then First(X) = { First(Y1) – ∈ } ∪ First(Y2Y3) Calculating First(Y2Y3) If ∈ ∉ First(Y2), then First(Y2Y3) = First(Y2) If ∈ ∈ First(Y2), then First(Y2Y3) = { First(Y2) – ∈ } ∪ First(Y3) Similarly, we can make expansion for any production rule X → Y1Y2Y3…..Yn. Follow Function- Follow(α) is a set of terminal symbols that appear immediately to the right of...
Post a Comment
Read more