FIRST AND FOLLOWS

FIRST: 

If α is any string of grammar symbols, the FIRST (α) be the set of terminals that begins strings derived from α.

                 If αà€, then € is also in FIRST (α).

To compute FIRST (α) for all grammar symbols ’X’, apply the following rules until no more terminals or € can be added to any FIRST set.

     1)    If x is terminal ,the FIRST(x)={x}

     2)    If x is non terminal and xà aα is a production, then add a to FIRST(x), If xà€ is a production, then add € to FIRST(x).

     3)    If xày₁,y₂,y₃,…….y_k is a production ,then for all i such that of all y₁……y_i-1 are non terminals and FIRST(y_i) contains € for j=1,2,3….i-1 (i.e.,y_i,y₂,…..y_i-1à€) add every non-€ symbol in FIRST(y_i) to FIRST(x).

FOLLOW:    For a non terminal A, FOLLOW (A) to de the set of terminal a, that can appear immediately to the right of A in some sentential form i.e., sàαAaβ for some α and β.

      To compute FOLLOW (A) for all non-terminals A, apply the following rules until nothing can be added to any follow set.

1)      $ is in FOLLOW(S), where S is the start symbol.

2)      If there is a production Aàαbβ, then everything in FIRST (β) except for € is in FOLLOW (B).

Example :

Construct the predictive parser for the following grammar

        Sà(L)/a

        LàL,S/S

Sol: We have to eliminate left recursion LàL,S/S.

After eliminating the left recursion we obtain

           Sà(L)/a

           LàSL¹

           L¹à, SL¹/€

Then FIRST

FIRST (S) = { ( , a} by rule (2)

FIRST (L) = { ( ,a} by rule (3) and (1)

FIRST (L¹) = {, ,€} by rule (2)

FOLLOW

FOLLOW(S) = { $ , ) , ,}    =FIRST(L¹) U FOLLOW(L)

FOLLOW (L) = { )  ,}

FOLLOW (L¹) = { ) }

The parsing table

	(	)	a	,	$
S	Sà(L)		Sàa
L	LàSL1		LàSL1
L1		L1 à€		L1 à,SL1	L1  à€

Read More

Classification of parsing Techniques

There are two parsing techniques, these parsing techniques work on the following principle

1. The parser scans the input string from left to right and identifiers that the derivation is leftmost or rightmost.

2. The parser makes use of production rules for choosing the appropriate derivation. The different parsing techniques use different approaches in selecting the appropriate rules for derivation and finally a parse tree is constructed.

When the parse tree can be constructed from root and expanded to leaves, then such type of parse is called top-down parser. The name itself tells us that the parse tree can be built from top to bottom.

When the parse tree can be constructed from leaves to root, then such type of parse is called as bottom–up parse. Thus the parse tree is built in bottom up manner.

Read More

The Role of a Parser

 In this process of compilation the parser and lexical analyzer work together. That means, when parser required string of tokens it invokes lexical analyzer .In turn, the lexical analyzer supplies tokens to syntax analyzer (parser).

 The parser collects sufficient number of tokens and builds a parse tree. Then by building the parse tree, parse smartly finds the syntactical errors if any. It is also necessary that the parse should recover from commonly occurring errors so that remaining task of process the input can be continued.

Read More

Syntax Analysis

 The parser or syntax analysis checks for whether the string given can be generated from the given grammar.

 A parser for grammar G is a program that takes as input a string w and produces as output either a parser tree for w, if w is a sentences of G, or an end message indicating that w is not a sentence of G. 

Read More

Aho Alfred V. Pearson Education India, 1999 - 796 pages

Read More

A.A.Puntambekar Technical Publications, 01-Jan-2009 - 540 pages

Read More

compiler design by A.A.Putambekar

A.A.Puntambekar Technical Publications, 01-Jan-2010 - Compilers (Computer programs) - 461 pages Overview of Compilation : Phases of compilation - Lexical analysis, Regular grammar and regular expression for common programming language features, Pass and phases of translation, Interpretation, Bootstrapping, Data structures in compilation - LEX lexical analyzer generator.Top Down Parsing : Context free grammars, Top down parsing, Backtracking, LL (1), Recursive descent parsing, Predictive parsing, Preprocessing steps required for predictive parsing.Bottom up Parsing : Shift reduce parsing, LR and LALR parsing, Error recovery in parsing, Handling ambiguous grammar, YACC - automatic parser generator.Semantic Analysis : Intermediate forms of source programs - abstract syntax tree, Polish notation and three address codes. Attributed grammars, Syntax directed translation, Conversion of popular programming languages language constructs into intermediate code forms, Type checker.Symbol Tables : Symbol table format, Organization for block structures languages, Hashing, Tree structures representation of scope information. Block structures and non block structure storage allocation : Static, Runtime stack and heap storage allocation, Storage allocation for arrays, strings and records.Code Optimization : Consideration for optimization, Scope of optimization, Local optimization, Loop optimization, Frequency reduction, Folding, DAG representation.Data Flow Analysis : Flow graph, Data flow equation, Global optimization, Redundant subexpression elimination, Induction variable elements, Live variable analysis, Copy propagation.Object Code Generation : Object code forms, Machine dependent code optimization, Register allocation and assignment generic code generation algorithms, DAG for register allocation.

Read More