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

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...

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- ...

Testing a Program – An Example

Question: Write a set of test cases – specific set of data – to properly test a relatively Simple program. Create a set of test data for the program - data the program must handle correctly to be considered a successful program. Here’s a description of the program: “The program reads three integer values from an input dialog. The three values represent the lengths of the sides of a triangle. The program displays a message that states whether the triangle is scalene, isosceles, or equilateral”. Code: The function triangle takes three integer parameters that are interpreted as the lengths of the sides of a triangle. It returns whether the triangle is equilateral (three lengths equal), isosceles (two lengths equal), scalene (no lengths equal), or invalid (impossible lengths). Evaluate your test cases: Evaluate your set of test cases by using it to answer the following questions. Give yourself one point for each “YES” answer. Do you have a test case that represents a ...