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

Machine - learning methods

Machine - learning methods

  1:50 PM    mayuravaani

---

Classification learning

classification learning is supervised.(Predicting a discrete class)
label is provided with actual outcome.

Association learning

detecting association between features.
it can be applied if no class is specified and any kind of structure is considered as "interesting".

Clustering

Finding group of items that are similar.
It is unsupervised

Numeric prediction

Variant of classification learning where class is numeric

Read More

Visual studio c# example codes - calculator - simple login system

Visual studio c# example codes - calculator - simple login system

  12:23 PM    mayuravaani

---

Click here

Read More

NLP- Natural Language Processing

NLP- Natural Language Processing

  6:59 PM    mayuravaani

---

Natural Language Processing is the technology used to aid computers to understand the human’s natural language.

Different level of analysis for natural language

Prosody: Deals with rhythm and intuition of the language

Phonology: Examined the sound that are combined to from language

Morphology: Concern with the components that make up words 

Syntax: Studies the rules for combining words into legal phrases and sentences

Semantics: Consider the meaning of words

Pragmatics: Study of the ways in which the language is used and its effects on the listener

World knowledge: Include the knowledge of the physical world, interaction and intention in communication

Specification and Parsing using Context-Free Grammar

Phrase structure plays an essential role in semantic interpretation by defining intermediate stages in a derivation at which semantic processing may take place.

Parsing algorithm has 2 types:
 Top-down Parser:
     It begins with a top-level Sentence symbol and expand the tree whose leaves match the target sentence.
 Bottom-up Parser:
     It begins with the word symbols (terminal) attempt to find a series of reductions that leads to the Sentence Symbol.

Sample grammar rules

Sentence <-> noun_phrase verb_phrase
noun_phrase <-> noun
noun_phrase <-> article noun
verb_phrase <-> verb
verb_phrase <-> verb noun_phrase
prep_phrase <-> preposition noun_phrase
noun_phrase <-> noun_phrase prep_phrase
verb_phrase <-> verb prep_phrase
article <-> a/ the
noun <-> cat/ Mango
verb <-> eat/ like
preposition <-> on

Read More

Red Black Tree

Red Black Tree

  8:38 PM    mayuravaani

---

Rules

• Self-balancing Binary Search Tree
• The node color can be either red or black (It is possible to have all black nodes but impossible to have all red nodes)
• The root node must be black
• There is no two red adjacent nodes (It will not have a parent and a child node in red color)
• NULL node is always black
• Every path from root to NULL node should have the same number of black nodes

Insertion

• If tree is empty, create a root node with black color
• If tree node is not empty, create a new child node as leaf node with red color
• If parent of new node is black then do nothing 
• If parent of new node is red then check the color of parent's sibling of new node (uncle of new node)
•      If the sibling node is black or NULL then do suitable rotation and re-color 
•      If the sibling node is red then re-color and check grand parent of new node
•         If grand parent is root then do nothing
•         else change the color of grand parent node and recheck 

Deletion

Read More

Graphics - OPenGL - C++ - Code Examples

Graphics - OPenGL - C++ - Code Examples

  11:02 AM    mayuravaani

---

Click here

Read More