We have discussed following topics on Syntax Analysis.

Introduction to Syntax Analysis

Why FIRST and FOLLOW?

FIRST Set in Syntax Analysis

In this post, FOLLOW Set is discussed.

**Follow(X)** to be the set of terminals that can appear immediately to the right of Non-Terminal X in some sentential form.

Example:

S ->Aa | Ac A ->b S S / / A a A C | | b b Here, FOLLOW (A) = {a, c}

Rules to compute FOLLOW set:

1) FOLLOW(S) = { $ } // where S is the starting Non-Terminal 2) If A -> pBq is a production, where p, B and q are any grammar symbols, then everything in FIRST(q) except ? is in FOLLOW(B. 3) If A->pB is a production, then everything in FOLLOW(A) is in FOLLOW(B). 4) If A->pBq is a production and FIRST(q) contains ?, then FOLLOW(B) contains { FIRST(q) – ? } U FOLLOW(A)

**Example 1:**

Production Rules:E -> TE’ E’ -> +T E’|? T -> F T’ T’ -> *F T’ | ? F -> (E) | idFIRST setFIRST(E) = FIRST(T) = { ( , id } FIRST(E’) = { +, ? } FIRST(T) = FIRST(F) = { ( , id } FIRST(T’) = { *, ? } FIRST(F) = { ( , id }FOLLOW SetFOLLOW(E) = { $ , ) } // Note ')' is there because of 5th rule FOLLOW(E’) = FOLLOW(E) = { $, ) } // See 1st production rule FOLLOW(T) = { FIRST(E’) – ? } U FOLLOW(E’) U FOLLOW(E) = { + , $ , ) } FOLLOW(T’) = FOLLOW(T) = { + , $ , ) } FOLLOW(F) = { FIRST(T’) – ? } U FOLLOW(T’) U FOLLOW(T) = { *, +, $, ) }

Example 2:

Production Rules:S -> ACB|Cbb|Ba A -> da|BC B-> g|? C-> h| ?FIRST setFIRST(S) = FIRST(A) U FIRST(B) U FIRST(C) = { d, g, h, ?, b, a} FIRST(A) = { d } U FIRST(B) = { d, g, h, ? } FIRST(B) = { g, ? } FIRST(C) = { h, ? }FOLLOW SetFOLLOW(S) = { $ } FOLLOW(A) = { h, g, $ } FOLLOW(B) = { a, $, h, g } FOLLOW(C) = { b, g, $, h }

Note :

- ? as a FOLLOW doesn’t mean anything (? is an empty string).
- $ is called end-marker, which represents the end of the input string, hence used while parsing to indicate that the input string has been completely processed.
- The grammar used above is Context-Free Grammar (CFG). The syntax of a programming language can be specified using CFG.
- CFG is of the form A -> B , where A is a single Non-Terminal, and B can be a set of grammar symbols ( i.e. Terminals as well as Non-Terminals)

This article is compiled by Vaibhav Bajpai. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

## leave a comment

## 1 Comments