Program to find out FIRST () and FOLLOW() from given set of production rules. - Java program

Dharmik 9:39 PM , No comments
Write a program to find out FIRST () and FOLLOW() from given set of production rules.

S→ABa|bcA
A→cBc|є
B →cdA| ad

Program:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package prac_5cd;
import java.io.*;
public class Prac_5CD {
    static char nonterminal[],terminal[];
    static int ntlen,tlen;
    static String grammar[][],first[],follow[];

    public static void main(String[] args) throws IOException {
            String nt,t;
    int i,j,n;
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    System.out.println("Enter the non-terminals");
    nt=br.readLine();
    ntlen=nt.length();
    nonterminal=new char[ntlen];
    nonterminal=nt.toCharArray();
   
    System.out.println("Enter the terminals");
    t=br.readLine();
    tlen=t.length();
    terminal=new char[tlen];
    terminal=t.toCharArray();
   
    System.out.println("Specify the grammar(Enter 9 for epsilon production)");
    grammar=new String[ntlen][];
    for(i=0;i<ntlen;i++)
    {
        System.out.println("Enter the number of productions for "+nonterminal[i]);
        n=Integer.parseInt(br.readLine());
        grammar[i]=new String[n];
        System.out.println("Enter the productions");

        for(j=0;j<n;j++)
            grammar[i][j]=br.readLine();
    }
    first=new String[ntlen];
   
    for(i=0;i<ntlen;i++)
        first[i]=first(i); //calling  first funcction for every non-terminal

    System.out.println("First Set");

    for(i=0;i<ntlen;i++)
        System.out.println(removeDuplicates(first[i]));
        follow=new String[ntlen];

    for(i=0;i<ntlen;i++)
        follow[i]=follow(i); //calling follow function for every non -terminal


    System.out.println("Follow Set");

    for(i=0;i<ntlen;i++)
        System.out.println(removeDuplicates(follow[i]));
}
static String first(int i)
{
    int j,k,l=0,found=0;
    String temp="",str="";

    for(j=0;j<grammar[i].length;j++) //number of productions
    {
        for(k=0;k<grammar[i][j].length();k++,found=0) //when nonterminal has epsilon production
        {
            for(l=0;l<ntlen;l++) //finding nonterminal
            {
                if(grammar[i][j].charAt(k)==nonterminal[l]) //for nonterminal in first set
                {
                    str=first(l);
                    if(!(str.length()==1 && str.charAt(0)=='9')) //when epsilon production is the only nonterminal production
                        temp=temp+str;
                        found=1;
                        //str.replace("9", "");
                        
                        break;
                }
            }
            if(found==1)
            {
                if(str.contains("9")) //here epsilon will lead to next nonterminal’s first set
                    continue;
            }
            else //if first set includes terminal
                temp=temp+grammar[i][j].charAt(k);
                break;
        }
    }
    return temp;
}
static String follow(int i)
{
    char pro[],chr[];
    String temp="";
    int j,k,l,m,n,found=0;
    if(i==0)
    temp="$";
   
    for(j=0;j<ntlen;j++)
    {
        for(k=0;k<grammar[j].length;k++) //entering grammar matrix
        {
            pro=new char[grammar[j][k].length()];
            pro=grammar[j][k].toCharArray();

            for(l=0;l<pro.length;l++) //entering each production
            {              
                if(pro[l]==nonterminal[i]) //finding the nonterminal whose follow set is to be found
                {
                    if(l==pro.length-1) //if it is the last terminal/non-terminal then follow of current non-terminal
                    {
                        if(j<i)
                            temp=temp+follow[j];
                    }
                    else
                    {
                        for(m=0;m<ntlen;m++)
                        {
                            if(pro[l+1]==nonterminal[m]) //first of next non-terminal otherwise (else later…)
                            {
                                chr=new char[first[m].length()];
                                chr=first[m].toCharArray();

                                for(n=0;n<chr.length;n++)
                                {
                                    if(chr[n]=='9') //if first includes epsilon
                                    {
                                        if(l+1==pro.length-1)
                                            temp=temp+follow(j); //when non-terminal is second last
                                        else
                                            temp=temp+follow(m);
                                    }  
                                    else
                                    temp=temp+chr[n]; //include whole first set except epsilon
                                }
                                found=1;
                            }                              
                        }
                    if(found!=1)
                        temp=temp+pro[l+1]; //follow set will include terminal(else is here)
                    }
                }
            }
        }
    }  
    return temp;
}
static String removeDuplicates(String str)
{
    int i;
    char ch;
    boolean seen[] = new boolean[256];
    StringBuilder sb = new StringBuilder(seen.length);
        for(i=0;i<str.length();i++)
        {
            ch=str.charAt(i);
            if (!seen[ch])
            {
                seen[ch] = true;
                sb.append(ch);
            }
            if(str.contains("9"))
            {
                str.replace("9", "");
            }
          
        }
        return sb.toString();

    }
   

}

Output:


No comments :

Post a Comment

Subscribe to: Post Comments ( Atom )