Notes

Program
import java.util.*;
public class LL1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of non terminals: ");
int n_nt = sc.nextInt();
sc.nextLine();
Map<String, List<String>> productions = new LinkedHashMap<>();
System.out.println("Enter the productions for each non-terminal:");
for (int i = 0; i < n_nt; i++) {
System.out.println("Enter non-terminal " + (i + 1) + ":");
String nonTerminal = sc.nextLine();
System.out.println("Enter number of productions for " +
nonTerminal + ":");
int numProductions = sc.nextInt();
sc.nextLine();
List<String> productionList = new ArrayList<>();
for (int j = 0; j < numProductions; j++) {
System.out.println("Enter production " + (j + 1) + " for " +
nonTerminal + ":");
String production = sc.nextLine();
productionList.add(production);
}
productions.put(nonTerminal, productionList);
}
// Printing the stored productions
System.out.println("nProductions:");
for (Map.Entry<String, List<String>> entry : productions.entrySet()) {
System.out.println(entry.getKey() + " -> " + entry.getValue());
}
// Calculate FIRST sets
Map<String, Set<Character>> firstSets =
calculateFirstSets(productions);
// Printing FIRST sets
System.out.println("nFIRST sets:");
System.out.println("Non-terminaltSet");
printTable(firstSets);
// Calculate FOLLOW sets
Map<String, Set<Character>> followSets =
calculateFollowSets(productions, firstSets);
// Printing FOLLOW sets
System.out.println("nFOLLOW sets:");
printTable(followSets);
// Calculate LL(1) Parsing Table
Map<String, Map<Character, String>> ll1ParsingTable =
calculateLL1ParsingTable(productions, firstSets, followSets);
// Printing LL(1) Parsing Table
System.out.println("nLL(1) Parsing Table:");
printLL1ParsingTable(ll1ParsingTable);
}
// Function to calculate FIRST sets
public static Map<String, Set<Character>> calculateFirstSets(Map<String,
List<String>> productions) {
Map<String, Set<Character>> firstSets = new LinkedHashMap<>();
// Initialize FIRST sets with empty sets for each non-terminal
for (String nonTerminal : productions.keySet()) {
firstSets.put(nonTerminal, new HashSet<>());
}
boolean changed;
do {
changed = false;
for (Map.Entry<String, List<String>> entry :
productions.entrySet()) {
String nonTerminal = entry.getKey();
List<String> productionList = entry.getValue();
for (String production : productionList) {
char[] symbols = production.toCharArray();
int i = 0;
while (i < symbols.length) {
char symbol = symbols[i];
if (Character.isUpperCase(symbol)) {
// Non-terminal
if
(!firstSets.containsKey(Character.toString(symbol))) {
// Initialize FIRST set if not already
initialized
firstSets.put(Character.toString(symbol), new
HashSet<>());
}
Set<Character> firstOfSymbol =
firstSets.get(Character.toString(symbol));
if (firstOfSymbol.contains('&')) {
// If symbol can derive epsilon, continue to
next symbol
firstOfSymbol.remove('&');
if
(firstSets.get(nonTerminal).addAll(firstOfSymbol)) {
changed = true; // Set changed
}
i++;
} else {
// Symbol cannot derive epsilon, break loop
if
(firstSets.get(nonTerminal).addAll(firstOfSymbol)) {
changed = true; // Set changed
}
break;
}
} else if (symbol != '&') {
// Terminal
if (firstSets.get(nonTerminal).add(symbol)) {
changed = true; // Set changed
}
break;
} else {
// Epsilon
if (firstSets.get(nonTerminal).add('&')) {
changed = true; // Set changed
}
break;
}
i++;
}
// If all symbols derive epsilon, add epsilon to FIRST(S)
if (i == symbols.length &&
firstSets.get(nonTerminal).add('&')) {
changed = true; // Set changed
}
}
}
} while (changed);
return firstSets;
}
// Function to calculate FOLLOW sets
public static Map<String, Set<Character>> calculateFollowSets(Map<String,
List<String>> productions,
Map<String, Set<Character>> firstSets) {
Map<String, Set<Character>> followSets = new LinkedHashMap<>();
// Initialize FOLLOW sets with empty sets for each non-terminal
for (String nonTerminal : productions.keySet()) {
followSets.put(nonTerminal, new HashSet<>());
}
// Add $ to FOLLOW(S), where S is the start symbol
String startSymbol = productions.keySet().iterator().next();
followSets.get(startSymbol).add('$');
boolean changed;
do {
changed = false;
for (Map.Entry<String, List<String>> entry :
productions.entrySet()) {
String nonTerminal = entry.getKey();
List<String> productionList = entry.getValue();
for (String production : productionList) {
char[] symbols = production.toCharArray();
for (int i = 0; i < symbols.length; i++) {
char symbol = symbols[i];
if (Character.isUpperCase(symbol)) {
if (i < symbols.length - 1) {
for (int j = i + 1; j < symbols.length; j++) {
char nextSymbol = symbols[j];
if (Character.isUpperCase(nextSymbol)) {
String nextSymbolStr =
Character.toString(nextSymbol);
if
(!followSets.containsKey(nextSymbolStr)) {
followSets.put(nextSymbolStr, new
HashSet<>());
}
if
(followSets.get(Character.toString(symbol)).addAll(firstSets.get(nextSymbolStr
))) {
changed = true;
}
if
(!firstSets.get(nextSymbolStr).contains('&')) {
break;
}
} else if (nextSymbol != '&') {
if
(followSets.get(Character.toString(symbol)).add(nextSymbol)) {
changed = true;
}
break;
}
}
} else {
if
(followSets.get(Character.toString(symbol)).addAll(followSets.get(nonTerminal)
)) {
changed = true;
}
}
}
}
}
}
} while (changed);
return followSets;
}
// Function to calculate LL(1) Parsing Table
public static Map<String, Map<Character, String>>
calculateLL1ParsingTable(
Map<String, List<String>> productions, Map<String, Set<Character>>
firstSets,
Map<String, Set<Character>> followSets) {
Map<String, Map<Character, String>> parsingTable = new
LinkedHashMap<>();
for (Map.Entry<String, List<String>> entry : productions.entrySet()) {
String nonTerminal = entry.getKey();
List<String> productionList = entry.getValue();
Map<Character, String> row = new HashMap<>();
for (String production : productionList) {
Set<Character> firstSetOfProduction =
calculateFirstOfProduction(production, firstSets);
for (Character terminal : firstSetOfProduction) {
if (terminal != '&') {
row.put(terminal, production);
} else {
Set<Character> followSetOfNonTerminal =
followSets.get(nonTerminal);
for (Character followTerminal :
followSetOfNonTerminal) {
row.put(followTerminal, production);
}
}
}
}
parsingTable.put(nonTerminal, row);
}
return parsingTable;
}
// Helper function to calculate FIRST set of a production
public static Set<Character> calculateFirstOfProduction(String production,
Map<String, Set<Character>> firstSets) {
Set<Character> firstSet = new HashSet<>();
char[] symbols = production.toCharArray();
for (char symbol : symbols) {
if (Character.isUpperCase(symbol)) {
firstSet.addAll(firstSets.get(Character.toString(symbol)));
if (!firstSets.get(Character.toString(symbol)).contains('&'))
{
break;
}
} else if (symbol != '&') {
firstSet.add(symbol);
break;
} else {
firstSet.add('&');
break;
}
}
return firstSet;
}
// Function to print the table of sets
public static void printTable(Map<String, Set<Character>> sets) {
System.out.println("Non-terminaltSet");
for (Map.Entry<String, Set<Character>> entry : sets.entrySet()) {
System.out.print(entry.getKey() + "tt{ ");
for (char c : entry.getValue()) {
System.out.print(c + " ");
}
System.out.println("}");
}
}
// Function to print the LL(1) parsing table
public static void printLL1ParsingTable(Map<String, Map<Character,
String>> ll1ParsingTable) {
// Find all terminals
Set<Character> terminals = new HashSet<>();
for (Map<Character, String> row : ll1ParsingTable.values()) {
terminals.addAll(row.keySet());
}
// Include '$' symbol
terminals.add('$');
// Print header row
System.out.print("Non-terminalt|");
for (char terminal : terminals) {
System.out.print("t" + terminal + "t|");
}
System.out.println();
// Print LL(1) parsing table
for (Map.Entry<String, Map<Character, String>> entry :
ll1ParsingTable.entrySet()) {
System.out.print(entry.getKey() + "tt|");
Map<Character, String> row = entry.getValue();
for (char terminal : terminals) {
System.out.print("t" + row.getOrDefault(terminal, "") +
"t|");
}
System.out.println();
}
}
}
Output