Skip to content

Instantly share code, notes, and snippets.

@nikhil-RGB
Last active April 20, 2024 06:26
Show Gist options
  • Save nikhil-RGB/aa5b9bb1f478423680180c9baa61e3af to your computer and use it in GitHub Desktop.
Save nikhil-RGB/aa5b9bb1f478423680180c9baa61e3af to your computer and use it in GitHub Desktop.
This script will calculate the first and follow of a symbol for a given context free grammar. This currently does not handle left recursion and left factoring. Epsilon is not handled yet.
package compiler_design;
import java.util.*;
public class FirstAndFollow {
public static void main(String[] args)
{
System.out.println("Input number of production rules");
Scanner reader=new Scanner(System.in);
int count=Integer.parseInt(reader.nextLine());
LinkedHashMap<String,String[]> table=new LinkedHashMap<>();
for(int i=0;i<count;++i) {
System.out.println("Input your production rule(RHS->LHS)");
String input=reader.nextLine();
String key=input.split("->")[0];
String[] value=input.split("->")[1].split("\\|");
table.put(key, value);
}
FirstAndFollow.printTable(table);
System.out.println("First for?");
String input=reader.nextLine();
for(String s:first(input,table))
{
System.out.print(s+" ");
}
System.out.println("Follow for?");
String input1=reader.nextLine();
HashSet<String> follows=follow(input1,table);
// follows.add("$");
for(String s:follows)
{
System.out.print(s+" ");
}
reader.close();
}
//Compute first for a context-free grammar
public static HashSet<String> first(String key,LinkedHashMap<String,String[]> table)
{
String[] rules=table.get(key);
if(rules==null)
{
HashSet<String> arrs= new HashSet<String>(0);
arrs.add(key);
return arrs;
}
else
{
HashSet<String> symbols=new HashSet<String>(0);
for(String rule:rules)
{
symbols.addAll(first(rule.toCharArray()[0]+"",table));
}
return symbols;
}
}
//For debugging purposes.
public static void printTable(LinkedHashMap<String,String[]> table)
{
Set<Map.Entry<String, String[]>> entries=table.entrySet();
for(Map.Entry<String, String[]> entry:entries)
{
System.out.println(entry.getKey()+" -> ");
for(String production:entry.getValue())
{
System.out.println(production+", ");
}
}
}
//Follow calculated via this function.
public static HashSet<String> follow(String key,LinkedHashMap<String,String[]> table)
{
if(table.get(key)==null)
{
return null;
}
HashSet<String> symbols=new HashSet<>(0);
Set<Map.Entry<String, String[]>> entries=table.entrySet();
for(Map.Entry<String, String[]> entry:entries)
{
char rhs=entry.getKey().charAt(0);
String[] productions=entry.getValue();
for(String production:productions)
{
for(int i=0;i<production.length();++i)
{
if(key.charAt(0)==production.charAt(i))
{
//statements for moving right here.
if(i==(production.length()-1))
{
//Exception case find follow for RHS of current production
if(rhs!=key.charAt(0))
{symbols.addAll(FirstAndFollow.follow(rhs+"", table));}
else
{
symbols.add("$");
}
}
else
{
String right=production.charAt(i+1)+"";
symbols.addAll(FirstAndFollow.first(right,table));
}
}
}
}
}
// symbols.add("$"); Add this before printing the follow output
return symbols;
}
}
@nikhil-RGB
Copy link
Author

I won't handle epsilon.
I'd rather kill myself.
Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment