Compiler Design - Definitions

Compiler Design - Definitions

  5:16 PM    mayuravaani

---

Lexical analysis
Lexical analyzer reads the source program character by character and returns the tokens of the source program. The tokens represent pattern of characters which have the same meaning such as identifiers, operators, numbers and etc.

Syntax analysis
Syntax analyzer re-combine the tokens and create a graphical representation of the syntactic structure (syntax tree). In addition to that, it rejects the invalid string by reporting the syntax error.
In syntax tree the terminals are at the leave nodes and the inner nodes are non-terminals

Context-free grammar
Context-free grammar is a set of rules for putting strings together and so correspondent to a language.

Parse tree
Parse tree is a ordered rooted tree that graphically represents the semantic of a string derived from a context free grammar.

Top-Down approach
It starts from the start symbol(root) and goes down to leaves using production rules.

Bottom-Up approach
It starts from the leave and proceeds upwards to the root which is  a starting symbol.

Left most derivation
A left most derivation is obtained by applying the production to the left most variable or left most non terminal in each step.

Right most derivation
A right most derivation is obtained by applying the production to the right most variable or right most non terminal in each step.

Ambiguous grammar
A grammar is said to be ambiguous if any string generated by it has more than one parse tree or derivation tree or syntax tree or left most derivation or right most derivation.

Unambiguous grammar
A grammar is said to be unambiguous if a string generated by it has exactly one parse tree or derivation tree or syntax tree or left most derivation or right most derivation.

Left recursion
A production of a grammar is said to have left recursion if the left most variable or non-terminal of the right hand side is same as the variable or non-terminal of the left hand side.

Right recursion
A production of a grammar is said to have right recursion if the right most variable or non-terminal of the right hand side is same as the non-terminal or variable of left hand side.

Associativity
If an operand has operators on both side, then the side on which the operator takes the operand is associativity of that operator.

Precedence
Precedence determines which part operator is performed first in an expression with more than one operators with different precedence level.

Left factorization
In left factorizing, it is not clear that which of the two alternative production to use expand a non-terminal that is A -> ab/ac.

Read More

BST - Binary Search Tree

BST - Binary Search Tree

  12:31 PM    mayuravaani

---

For any node x,
    the keys in left sub tree of x are at most x.key and
    the keys in right sub tree of x are at least x.key.

Here the fisrt is BST but in the second 11 should not be in the left side of 10.

Binary Search Tree Property
   Let x be a node in BST.
   Let y be a node in left sub tree of x and
   Let z be a node in the right sub tree of y then
   y.key <= x.key and z.key > = x,key
Binary search average case-> O(lg n)
                       worst case -> O(n)
                       best case -> O(1)

Inorder tree walk
left --- root --- right

INORDER-TREE-WALK(x)
if(x ≠  NIL)
       INORDER-TREE-WALK(x.left)
       print x.key
       INORDER-TREE-WALK(x.right)

Preorder tree walk
root --- left --- right

PREORDER-TREE-WALK(x)
if(x ≠  NIL)
       print x.key
       PREORDER-TREE-WALK(x.left)
       PREORDER-TREE-WALK(x.right)

Postorder tree walk
left --- right --- root

POSTORDER-TREE-WALK(x)
if(x ≠  NILL)
       POSTORDER-TREE-WALK(x.left)
       POSTORDER-TREE-WALK(x.right)
       print x.key

INORDER TRAVERSAL
P, H, A, K, C, T, Q, M, R

PREORDER TRAVERSAL
C, H, P, K, A, M, T, Q,  R

POSTORDER TRAVERSAL
P,A, K, H, Q, T, R, M, C

If x is root of an n-node subtree, then the call INORDER-TREE-WALK(x) takes time O(n)

Searching

x- current node , k- search key

TREE-SEARCH(x, k)
if ( x == NIL or k == x.key)
       return x
if( k < x.key)
       return TREE-SEARCH(x.left, k)
else
       return TREE-SEARCH(x.right, k)

ITERATIVE TREE-SEARCH(x, k)
while( x ≠ NIL or k ≠ x.key)
         if( k < x.key)
                x = x.left
          else
                 x = x.right           return x

The running time of tree-search is O(h),  where h is height of tree.

Minimum


TREE-MINIMUM(x)
while(x.left ≠ NIL)
      x = x.left
return x

Maximum
     
TREE-MAXIMUM(x)
while(x.right ≠ NIL)
      x  =  x.right
return x

The running time of minimum and maximum is O(h),  where h is height of tree.

Successor

TREE-SUCCESSOR(x)
if(x.right ≠ NIL)
      return TREE-MINIMUM(x.right)
y = x.p
while( y  ≠  NIL and x == y.right)
       x = y
       y = y.p
return y

Maximum
   
TREE-PREDECESSOR(x)
if(x.left  ≠  NIL)
       return TREE-PREDECESSOR(x.left)
y = x.p
while( y  ≠  NIL and x == y.left)
        x = y
        y = y.p
return y

Simply, Inorder successor of the node x is the smallest value node of its right subtree and the inorder predecessor of the node x is the largest value of its right subtree.

INORDER SUCCESSOR OF C -> T

INORDER PREDECESSOR OF C -> K

Insertion

The new element will be inserted by considering left and right subtree values. 
T- binary tree, z-new node

TREE-INSERT(T, z)
y = NIL
x = T.root
while( x ≠ NIL)
       y = x
       if( z.key < x.key)
              x = x.left
        else
              x = x.right
z.p = y
if( y == NIL)
    T.root = z
else if( z.key < y.key)
     y.left = z
else
     y.right = z

Deletion

Deleting a node z from a binary search tree T has 3 cases:
If z has no children, then simply remove it by replacing with NIL
If z has only one child, then remove the z by replacing the child node of z with the z.
If z has two children then find the successor(y) and replace it with z. Original right and left subtrees of z becomes y's new subtrees.

TRANSPLANT(T, u, v)
if (u.p == NIL)
     T.root = v
else if (u == u.p.left)
      p.p.left = c
else if (u == u.p.right)
      u.p.right == v
if (v ≠ NIL)
      v.p = u.p

TREE-DELETE(T, z)
if (z.left == NIL)
       TRANSPLANT(T, z, z.right)
else if(z.right == NIL)
       TRANSPLANT(T, z, z.left)
else
       y = TREE-MINIMUM(z.right)
       if (y.p ≠ z)
             TRANSPLANT(T, y, y.right)
              y.right = z.right
              y.right.p = y
       TRANSPLANT(T, z, y)
        y.left = z.left
        y.left.p = y

Randomly build binary search tree

Read More