Last active
April 20, 2024 06:26
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I won't handle epsilon.
I'd rather kill myself.
Thanks!