Skip to main content

Syntax Trees

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
  1. Parse tree
  2. Syntax tree
  3. Directed Acyclic Graph (DAG)

Solution-

Parse Tree-


 





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

Grammar in Automata | Types of Grammar

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