Some Related Terms asked in Gate Exam

Lexical Anaysis                -->      Finite Automata / DFA mimization

Code optimization        -->      DAG(subtree minimization)

Code generation            -->      Syntax tree(parse tree)

Abelian Groups              -->       Push Down Automata

Parsing                              -->       Production tree

Data Flow Analysis       -->       Code Optimization

Register Allocation       -->      Graph coloring / Code generation 

Regular Grammer         -->      Lexical Analysis

Backus Normal Form   -->     Context free Grammar

YAcc                                    -->      LALR(1)




First and Follow Examples(1)

The construction of a predictive parser is aided by two functions associated with a grammar G. These functions, FIRST and FOLLOW, allow us to fill in the entries of a predictive parsing table for G, whenever possible. Sets of tokens yielded by the FOLLOW function can also be used as synchronizing tokens during panic-mode error recovery.

1. FIRST(a)

First(a) = set of terminals that start a string of terminals derived from a.

Apply following rules until no terminal or ε can be added

1. If t  ∈ T, then First( t ) = { t }.  

2. If X ∈ N and X → ε exists (nullable), then add ε to First( X ).

3. If X ∈ N and X →  Y1Y2Y3… Ym, where Y1, Y2, Y3, ... Ym are non‐terminals, then:     for each, I from 1 to m     if Y1 … Yi‐1 are all nullable (or if i = 1)      First( X ) = First( X ) ∪ First( Yi )

2. FOLLOW (a) 

Apply the following rules until no terminal or e can be added

1. $  ∈ Follow( S ), where S is the start symbol.

2. Look at the occurrence of a non‐terminal on the right-hand side of a production which is followed by something If A → a B b, then First( b ) ‐ {e} ⊆ Follow( B )

3. Look at N on the RHS that is not followed by anything, if (A → a B) or (A → a B b and ε  First( b )), then Follow( A ) ⊆  Follow( B )