Mindspark

Syntax trees are abstract or compact representation of parse trees. They are also called as Abstract Syntax Trees . Example- Problem-01: Considering the following grammar- E → E + T | T T → T x F | F F → ( E ) | id Generate the following for the string id + id x id Parse tree Syntax tree Directed Acyclic Graph (DAG) Solution- Parse Tree-  

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   → a B →  aa B B                   (Using B → aBB) → aaa B BB                (Using B → aBB) → aaab B B                (Using B → b) → aaabb B                 (Using B → b) → aaabba B B            (Using B → aBB) → aaabbab B             (Using B → b) → aaabbabb S           (Using B → bS) → aaabbabbb A       ...

Grammar in Automata- Formal Definition- A Grammar is a 4-tuple such that G = (V , T , P , S) where- V = Finite non-empty set of non-terminal symbols T = Finite set of terminal symbols P = Finite non-empty set of production rules S = Start symbol Grammar Constituents- A Grammar is mainly composed of two basic elements- 1. Terminal symbols 2. Non-terminal symbols 1. Terminal Symbols- Terminal symbols are those which are the constituents of the sentence generated using a grammar. Terminal symbols are denoted by using small case letters such as a, b, c etc. 2. Non-Terminal Symbols- Non-Terminal symbols are those which take part in the generation of the sentence but are not part of it. Non-Terminal symbols are also called as auxiliary symbols or variables . Non-Terminal symbols are denoted by using capital letters such as A, B, C etc. Examples of Grammar- Example-01: Consider a grammar G = (V ...

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

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