Compiler design lab file
Practical No: 1
Aim: -The program in Java that verifies the s->as/bs/a pattern in compiler design with user input
Program: import java.util.Scanner;
public class PatternMatcher {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("Enter a string: ");
String str = input.nextLine();
if (isMatchingPattern(str)) {
System.out.println("The string matches the pattern."); } else {
System.out.println("The string does not match the pattern."); } }
public static boolean isMatchingPattern(String str) {
int n = str.length();
if (n == 0) { return false;
} else if (str.charAt(0) != 'a') {
return false; } int i = 1;
while (i < n && str.charAt(i) == 'a') { i++; }
if (i == n) { return true;
} else if (str.charAt(i) == 'b') { i++;
while (i < n && str.charAt(i) == 's') { i++; }
if (i == n || str.charAt(i) != 'a') { return false; } i++;
while (i < n && str.charAt(i) == 's') { i++; }
if (i == n) { return true;
} else {
return false; }
} else if (str.charAt(i) == 'a') { i++;
while (i < n && str.charAt(i) == 's') { i++; }
if (i == n) {
return true; } else {
return false; } } else { return false; } }}
Algorithm:-
The string must start with the letter ‘a’.
After the first ‘a’, there can be any number of consecutive ‘a’s.
If there is a ‘b’ after the ‘a’s, it must be followed by any number of consecutive ‘s’s.
After the ‘s’s (if any), there must be another ‘a’.
After the second ‘a’, there can again be any number of consecutive ‘s’s.
The string must end after the second group of ‘s’s (if any).
The main method of the program prompts the user to enter a string and then calls the isMatchingPattern method to check if the string matches the pattern. If the string matches the pattern, it prints “The string matches the pattern.” Otherwise, it prints “The string does not match the pattern.”
The IsMatchingPattern method takes a string as input and returns a boolean value indicating whether the string matches the pattern or not. It first checks if the string is empty or if the first character is not ‘a’. If either of these conditions is true, it returns false.
If the first character is ‘a’, it checks for any consecutive ‘a’s and counts them. Then, it checks the next character. If it is ‘b’, it checks for any consecutive ‘s’s after the ‘b’, and then checks for the second ‘a’ and any consecutive ‘s’s after that. If the next character is ‘a’, it checks for any consecutive ‘s’s after that.
If the string matches the pattern, the method returns true. Otherwise, it returns false.
Input/output
Practical No: 2
Aim:- The program in Java that verifies the s->a^n b^n c^n pattern in compiler design with user input
Code: import java.util.Scanner;
public class StringPatternVerifier {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("Enter a string to check: ");
String s = input.nextLine();
if (checkStringPattern(s)) {
System.out.println("The string matches the pattern.");
} else {
System.out.println("The string does not match the pattern."); } }
public static boolean checkStringPattern(String s) {
int aCount = 0;
int bCount = 0;
int cCount = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == 'a') {
aCount++;
} else if (c == 'b') {
bCount++;
} else if (c == 'c') {
cCount++;
} else {
// If there are any other characters in the string, it doesn't match the pattern.
return false; }
// If b or c counts ever exceed a count, the string doesn't match the pattern.
if (bCount > aCount || cCount > aCount) {
return false; } }
// If all three counts are equal, the string matches the pattern.
return aCount == bCount && bCount == cCount; }}
Algorithm :- 1.The checkStringPattern method takes a string as input and returns true if the string matches the pattern S -> a^n b^n c^n, and false otherwise. It does this by iterating over the characters in 2.the string and keeping track of the counts of a, b, and c characters. If there are any characters in the string that are not a, b, or c, or if the count of b or c characters ever exceeds the count of a characters, 3.the string doesn't match the pattern and the method returns false. If the counts of a, b, and c characters are all equal at the end of the loop, the string matches the pattern and the method returns true.
4.The main method prompts the user to enter a string and then calls the checkStringPattern method to check if the string matches the pattern. It then prints a message indicating whether the string matches the pattern or not.
Input/output
Practical No : 3
Aim: Firstset program in compiler design grammar
import java.util.*;
public class FirstAlgorithm {
static Map<Character, List<String>> productions = new HashMap<>();
static Map<Character, Set<Character>> firstSets = new HashMap<>();
public static void main(String[] args) {
// Define the grammar productions
productions.put('S', Arrays.asList("aB", "bA"));
productions.put('A', Arrays.asList("a", "bA"));
productions.put('B', Arrays.asList("b", "aB"));
// Calculate the First sets
for (Character nonTerminal : productions.keySet()) {
calculateFirst(nonTerminal); }
// Print the First sets
for (Map.Entry<Character, Set<Character>> entry : firstSets.entrySet()) {
System.out.println("First(" + entry.getKey() + "): " + entry.getValue()); } }
private static void calculateFirst(Character nonTerminal) {
Set<Character> first = new HashSet<>();
for (String production : productions.get(nonTerminal)) {
char symbol = production.charAt(0);
if (symbol >= 'A' && symbol <= 'Z') {
calculateFirst(symbol);
first.addAll(firstSets.get(symbol));
} else {
first.add(symbol); } }
firstSets.put(nonTerminal, first); }}
Algorithm Step1 .The program defines a Map called "productions" that stores the productions of the grammar. Each non-terminal symbol is mapped to a list of production rules. For example, 'S' is mapped to the list {"aB", "bA"}.
Step 2.The program defines a Map called “firstSets” that will store the First sets for each non-terminal symbol.
Step 3.The main method of the program first defines the grammar productions using the “productions” Map.
Step 4. Then, for each non-terminal symbol in the grammar, the “calculateFirst” method is called to calculate its First set.
Step 5. The “calculateFirst” method takes a non-terminal symbol as input and calculates its First set by iterating over its production rules. For each rule, it looks at the first symbol in the rule. If it is a non-terminal symbol, the “calculateFirst” method is recursively called for that symbol. If it is a terminal symbol, it is added to the First set. This process continues until all possible productions for the non-terminal symbol have been considered.
Step 6. Once the First set has been calculated for the non-terminal symbol, it is stored in the “firstSets” Map.
Step 7. Finally, the program prints out the First sets for each non-terminal symbol in the grammar.
Input/output
Practical No:4
Aim: followset program in compiler design
Program
Import java.util.*;
Public class FollowSet {
Public static void main(String[] args) {
// Define the grammar
Map<Character, List<String>> grammar = new HashMap<>();
Grammar.put(‘S’, Arrays.asList(“AaB”, “b”));
Grammar.put(‘A’, Arrays.asList(“aA”, “c”));
Grammar.put(‘B’, Arrays.asList(“bB”, “c”));
// Define the non-terminal symbol whose Follow set we want to find
Char nonTerminal = ‘A’;
// Calculate the Follow set
Set<Character> followSet = calculateFollowSet(grammar, nonTerminal);
// Print the result
System.out.println(“Follow(“ + nonTerminal + “) = “ + followSet); }
Private static Set<Character> calculateFollowSet(Map<Character, List<String>> grammar, char nonTerminal) {
Set<Character> followSet = new HashSet<>();
followSet.add(‘$’); // Add the end-of-input symbol to the Follow set
// Iterate over all the productions in the grammar
For (Map.Entry<Character, List<String>> entry : grammar.entrySet()) {
Char leftHandSide = entry.getKey();
List<String> rightHandSide = entry.getValue();
// Iterate over all the symbols in the right-hand side of each production
For (String rhs : rightHandSide) {
Int index = rhs.indexOf(nonTerminal);
While (index != -1) {
// If the non-terminal is at the end of the production, add the Follow set of the left-hand side
If (index == rhs.length() – 1) {
If (leftHandSide != nonTerminal) { // To avoid infinite loop
followSet.addAll(calculateFollowSet(grammar, leftHandSide));} }
// Otherwise, add the First set of the symbol immediately after the non-terminal
Else {
Char nextSymbol = rhs.charAt(index + 1);
followSet.addAll(calculateFirstSet(grammar, nextSymbol));
// If the First set of the next symbol contains epsilon, also add the Follow set of the left-hand side
If (calculateFirstSet(grammar, nextSymbol).contains(‘ε’)) {
If (leftHandSide != nonTerminal) { // To avoid infinite loop
followSet.addAll(calculateFollowSet(grammar, leftHandSide));}}}
// Move to the next occurrence of the non-terminal in the same production
Index = rhs.indexOf(nonTerminal, index + 1); }}}
Return followSet;}
Private static Set<Character> calculateFirstSet(Map<Character, List<String>> grammar, char symbol) {
Set<Character> firstSet = new HashSet<>();
// If the symbol is a terminal, add it to the First set
If (!grammar.containsKey(symbol)) {
firstSet.add(symbol);
return firstSet;}
// If the symbol is a non-terminal, add the First set of all its productions
For (String production : grammar.get(symbol)) {
Set<Character> productionFirstSet = calculateFirstSet(grammar, production.charAt(0));
firstSet.addAll(productionFirstSet);
// If the First set of the first symbol in the production contains epsilon, also add the First set of the next symbol
If (productionFirstSet.contains(‘ε’) && production.length() > 1) {
firstSet.addAll(calculateFirstSet(grammar, production.charAt(1)));} }
Return firstSet;}}
Algorithm step1. Initialize an empty set for the Follow set of the non-terminal symbol.
Step2. Add the end-of-input symbol ($) to the Follow set.
Step3. For each production rule in the grammar, iterate through the symbols in the right-hand side of the rule.
Step4. If the non-terminal symbol is found in the middle of the right-hand side, add the First set of the symbol immediately after it to the Follow set.
Step5. If the non-terminal symbol is found at the end of the right-hand side, recursively calculate the Follow set of the left-hand side non-terminal symbol (excluding the current non-terminal symbol) and add it to the Follow set.
Step6. If the right-hand side of a production rule contains a chain of non-terminals that can derive the empty string (epsilon), add the Follow set of the left-hand side non-terminal symbol to the Follow set of each non-terminal in the chain.
Step7. Steps 4-6 may need to be repeated until no new symbols are added to the Follow set. This ensures that all possible symbols are included in the Follow set.
Step 8. Return the Follow set of the non-terminal symbol.
Input/output
Practical No: 5
Aim: oprator precedence parser program in compiler design
Program
Import java.util.*;
Public class OperatorPrecedenceParser {
Private static final Map<Character, Integer> PRECEDENCE_MAP = new HashMap<>();
Static {
PRECEDENCE_MAP.put(‘+’, 1);
PRECEDENCE_MAP.put(‘*’, 2);}
Public static void main(String[] args) {
String input = “id+id*id”; // Input expression
System.out.println(“Input: “ + input);
Stack<Character> operators = new Stack<>();
Stack<String> operands = new Stack<>();
For (int I = 0; I < input.length(); i++) {
Char ch = input.charAt(i);
If (ch == ‘ ‘) {Continue;
} else if (ch == ‘+’ || ch == ‘*’) {
While (!operators.empty() && PRECEDENCE_MAP.get(ch) <= PRECEDENCE_MAP.get(operators.peek())) {
Char op = operators.pop();
String b = operands.pop();
String a = operands.pop();
Operands.push(“(“ + a + op + b + “)”);
} Operators.push(ch);} else {
// Read the entire operand
StringBuilder operand = new StringBuilder();
While (I < input.length() && Character.isLetterOrDigit(input.charAt(i))) {
Operand.append(input.charAt(i));
I++;} i--;
operands.push(operand.toString());}}
While (!operators.empty()) {
Char op = operators.pop();
String b = operands.pop();
String a = operands.pop();
Operands.push(“(“ + a + op + b + “)”);}
System.out.println(“Result: “ + operands.pop());}}
Algorithm Step1 Create a stack for operators and a stack for operands.
Step2. Read the input expression character by character from left to right.
Step 3. If the character is a whitespace, ignore it and move on to the next character.
Step4.If the character is an operand (a variable or a constant), push it onto the operand stack.
Step5.If the character is an operator (+ or * in this example), compare its precedence to the precedence of the operator at the top of the operator stack.
Step6.If the operator stack is empty or the new operator has higher precedence than the operator at the top of the stack, push the new operator onto the stack.
Step7. If the new operator has lower or equal precedence to the operator at the top of the stack, pop the operator off the stack and evaluate it with the two operands on top of the operand stack.
Step8.Push the result of the evaluation onto the operand stack.
Step9.Once the new operator has been pushed onto the operator stack, move on to the next character.
Step10.If the end of the input expression is reached, pop all remaining operators off the operator stack and evaluate them with the operands on top of the operand stack.
Step11.The result of the evaluation is the fully parenthesized expression.
Input/output
Practical No: 6
Aim:- remove left recursion in java
Algorithm:-step1 Read the input CFG production rule as a string
Step2 Split the rule into its left-hand side (lhs) and right-hand side (rhs)
Step3 Split the rhs into individual productions using the pipe character (|)
Step3 Check if any of the productions in the rhs start with the lhs (left recursion)
Step4 If the rule has left recursion, do the following:
a. Create a new non-terminal symbol by appending a prime (‘) to the lhs
b. Create two new rhs lists: newRhs1 and newRhs2
c. For each production in the rhs:
i. If it starts with the lhs, remove the lhs prefix and add the rest of the production to newRhs2, followed by the new non-terminal symbol and a pipe (|)
ii. Otherwise, add the production to newRhs1, followed by the new non-terminal symbol and a pipe (|)
d. Remove the last pipe (|) from both newRhs1 and newRhs2
e. Add epsilon to the end of newRhs2
f. Print the new production rule with the non-terminal symbol and new rhs lists
Step6 If the rule does not have left recursion, simply print it as is
And that’s it! This algorithm effectively applies the left-factoring technique to eliminate left recursion from a CFG production rule.
Step7 stop
Source code: import java.util.*;
public class LeftRecursionElimination {
public static void main(String[] args) {
// Example CFG production rule with left recursion
String rule = "A -> A alpha | beta";
// Split the rule into left-hand side and right-hand side
String[] parts = rule.split("->");
String lhs = parts[0].trim();
String[] rhs = parts[1].trim().split("\\|");
// Check if the rule has left recursion
boolean hasLeftRecursion = false;
for (String prod : rhs) {
if (prod.trim().startsWith(lhs)) {
hasLeftRecursion = true;
break;} }
if (hasLeftRecursion) {
// Apply left-factoring to eliminate left recursion
String newLhs = lhs + "'";
String newRhs1 = "";
String newRhs2 = "";
for (String prod : rhs) {
if (prod.trim().startsWith(lhs)) {
String suffix = prod.trim().substring(lhs.length()).trim();
if (suffix.isEmpty()) { suffix = "epsilon";}
newRhs2 += " " + suffix + " " + newLhs + " |";} else {
newRhs1 += " " + prod.trim() + " " + newLhs + " |";}}
newRhs1 = newRhs1.substring(0, newRhs1.length() - 1);
newRhs2 = newRhs2.substring(0, newRhs2.length() - 1) + "/ epsilon";
// Print the new production rule without left recursion
System.out.println(newLhs + " ->" + newRhs1);
System.out.println(newLhs + " ->" + newRhs2);} else {
// The rule does not have left recursion
System.out.println(rule);}}}
Output/input
Practical No: 7
Aim: LL(1) parser in compiler design
Algorithm:-
1. Initialize the FIRST sets, FOLLOW sets, and parsing table for the grammar.
2. Append the end-of-input symbol ('$') to the end of the input string.
3. Push the end-of-stack symbol ('$') and the start symbol ('S') onto the stack.
4. Initialize a variable i to 0.
5. While the stack is not empty:
a. Pop the top symbol from the stack.
b. If the top symbol is a terminal:
i. If the top symbol matches the next input symbol (input[i]), increment i.
ii. Otherwise, the input string is not in the language of the grammar. Return false.
c. If the top symbol is a nonterminal:
i. Look up the appropriate entry in the parsing table for the nonterminal and the next input symbol.
ii. If there is no entry, the input string is not in the language of the grammar. Return false.
iii. If the entry is empty, do nothing.
iv. If the entry contains a production, push its symbols onto the stack in reverse order.
6. If the input string has been fully consumed (i.e., i == length of input string) and the stack is empty, return true. Otherwise, the input string is not in the language of the grammar. Return false.Source code:-
import java.util.*;
public class LL1Parser {
private static final Map<String, Set<String>> FIRST_SETS = new HashMap<>();
private static final Map<String, Set<String>> FOLLOW_SETS = new HashMap<>();
private static final Map<String, Map<String, String>> PARSING_TABLE = new HashMap<>();
static {
// initialize FIRST sets
FIRST_SETS.put("S", new HashSet<>(Arrays.asList("id")));
FIRST_SETS.put("A", new HashSet<>(Arrays.asList("+", "")));
// initialize FOLLOW sets
FOLLOW_SETS.put("S", new HashSet<>(Arrays.asList("$")));
FOLLOW_SETS.put("A", new HashSet<>(Arrays.asList("id")));
// initialize parsing table
Map<String, String> sTable = new HashMap<>();
sTable.put("id", "idA");
PARSING_TABLE.put("S", sTable);
Map<String, String> aTable = new HashMap<>();
aTable.put("+", "+id");
aTable.put("id", "");
PARSING_TABLE.put("A", aTable);}
public static boolean parse(String input) {
input += "$"; // add end-of-input symbol
Stack<String> stack = new Stack<>();
stack.push("$"); // push end-of-stack symbol onto stack
stack.push("S"); // push start symbol onto stack
int i = 0;
while (!stack.empty()) {
String top = stack.pop();
String nextInput = input.substring(i, i+1);
if (isTerminal(top)) { if (top.equals(nextInput)) { i++;} else {
// error: mismatched terminal
return false;} } else {
Map<String, String> tableEntry = PARSING_TABLE.get(top);
if (tableEntry.containsKey(nextInput)) {
String production = tableEntry.get(nextInput);
if (!production.isEmpty()) {
String[] symbols = production.split("");
for (int j = symbols.length - 1; j >= 0; j--) {
stack.push(symbols[j]);}} } else {
// error: invalid input
return false;}}}return true;}
private static boolean isTerminal(String symbol) {
return !FIRST_SETS.containsKey(symbol); }
public static void main(String[] args) {
String input = "id+id";
if (parse(input)) { System.out.println("Accepted"); } else {
System.out.println("Rejected");}}}
Output/input
Practical No: 8
Aim LR(0) program in compiler design using java
Algorithm:
To help you understand the step-by-step algorithm of the LR(0) parser implemented in the code, here is a breakdown of the process:
1. Initialize the necessary constants, grammar, input string, terminals, non-terminals, and data structures such as `firstSets`, `followSets`, and `parsingTable`.
2. `computeFirstSets()`: Calculate the FIRST sets for all non-terminals in the grammar. Iterate through the grammar rules and update the FIRST sets based on the symbols on the right-hand side of each rule.
3. `computeFollowSets()`: Calculate the FOLLOW sets for all non-terminals in the grammar. Iterate through the grammar rules and update the FOLLOW sets based on the symbols on the right-hand side of each rule.
4. `buildParsingTable()`: Construct the parsing table using the calculated FIRST and FOLLOW sets. Iterate through the grammar rules and populate the parsing table with the appropriate rule index for each non-terminal and terminal combination.
5. `parseInputString()`: Perform the LR(0) parsing of the input string using the constructed parsing table. Initialize a stack with the starting state. Iterate through the input string and perform shift and reduce operations based on the actions in the parsing table until the stack is empty or an acceptance state is reached.
6. If the parsing process completes with an acceptance state, return `true` indicating that the input string is acceptable; otherwise, return `false`.
The code you provided implements these steps to perform LR(0) parsing. However, there are a few issues with the code, such as the incorrect logic in the `parseInputString()` method. I have made corrections to the code and provided an updated version in the previous response. Please refer to that response for the corrected code.
Source code:
import java.util.*;
Public class LR0Parser {
Private static final int ACCEPT_STATE = -1;
Private static final String[] grammar = {
“S -> AA”,
“A -> AA”,
“A -> ab” };
Private static final String inputString = “aabb$”;
Private static final String[] terminals = {“a”, “b”, “$”};
Private static final String[] nonTerminals = {“S”, “A”};
Private static final Map<String, Set<String>> firstSets = new HashMap<>();
Private static final Map<String, Set<String>> followSets = new HashMap<>();
Private static final Map<String, Map<String, String>> parsingTable = new HashMap<>();
Public static void main(String[] args) {
computeFirstSets();
computeFollowSets();
buildParsingTable();
boolean acceptable = parseInputString();
System.out.println(“Input String is “ + (acceptable ? “Not Acceptable” : “Acceptable”)); }
Private static void computeFirstSets() {
For (String nonTerminal : nonTerminals) {
firstSets.put(nonTerminal, new HashSet<>()); }
Boolean changed;
Do {
Changed = false;
For (String rule : grammar) {
String[] parts = rule.split(“ -> “);
String leftSide = parts[0];
String[] rightSideSymbols = parts[1].split(\\s+);
Int I = 0;
While (I < rightSideSymbols.length) {
String symbol = rightSideSymbols[i];
If (!nonTerminalsContains(symbol)) {
Changed |= firstSets.get(leftSide).add(symbol);
Break; }
Set<String> symbolFirstSet = firstSets.get(symbol);
If (!symbolFirstSet.contains(“”)) {
Changed |= firstSets.get(leftSide).addAll(symbolFirstSet);
Break; }
Changed |= firstSets.get(leftSide).addAll(symbolFirstSet);
I++; }
If (I == rightSideSymbols.length) {
Changed |= firstSets.get(leftSide).add(“”); } }
} while (changed); }
Private static void computeFollowSets() {
For (String nonTerminal : nonTerminals) {
followSets.put(nonTerminal, new HashSet<>()); }
followSets.get(“S”).add(“$”); // Add $ to the follow set of the start symbol
boolean changed;
do {
changed = false;
for (String rule : grammar) {
String[] parts = rule.split(“ -> “);
String leftSide = parts[0];
String[] rightSideSymbols = parts[1].split(\\s+);
For (int I = 0; I < rightSideSymbols.length; i++) {
String symbol = rightSideSymbols[i];
If (nonTerminalsContains(symbol)) {
Set<String> symbolFollowSet = followSets.get(symbol);
If (I < rightSideSymbols.length – 1) {
// Add all symbols in the first set of the next symbol
String nextSymbol = rightSideSymbols[I + 1];
Set<String> nextSymbolFirstSet = firstSets.get(nextSymbol);
Changed |= symbolFollowSet.addAll(nextSymbolFirstSet);
If (nextSymbolFirstSet.contains(“”)) {
// Remove epsilon from the follow set
Changed |= symbolFollowSet.remove(“”);
// Add all symbols in the follow set of the left side
Changed |= symbolFollowSet.addAll(followSets.get(leftSide)); }
} else {
// Add all symbols in the follow set of the left side
Changed |= symbolFollowSet.addAll(followSets.get(leftSide)); } } }}
} while (changed); }
Private static void buildParsingTable() {
For (String nonTerminal : nonTerminals) {
parsingTable.put(nonTerminal, new HashMap<>());
for (String terminal : terminals) {
parsingTable.get(nonTerminal).put(terminal, “”);
} }
For (int I = 0; I < grammar.length; i++) {
String[] parts = grammar[i].split(“ -> “);
String leftSide = parts[0];
String[] rightSideSymbols = parts[1].split(\\s+);
For (String terminal : followSets.get(leftSide)) {
parsingTable.get(leftSide).put(terminal, String.valueOf(i)); }
If (rightSideSymbols.length == 1 && rightSideSymbols[0].equals(“”)) {
For (String terminal : terminals) {
parsingTable.get(leftSide).put(terminal, String.valueOf(i)); }
} else {
For (String symbol : rightSideSymbols) {
If (!symbol.equals(“”)) {
parsingTable.get(leftSide).put(symbol, String.valueOf(i)); } } } } }
Private static boolean parseInputString() {
Stack<String> stack = new Stack<>();
Stack.push(“0”);
Int inputIndex = 0;
While (!stack.isEmpty()) {
String currentState = stack.peek();
String currentInputSymbol = inputString.charAt(inputIndex) + “”;
If (!parsingTable.containsKey(currentState) || !parsingTable.get(currentState).containsKey(currentInputSymbol)) {
Return false; }
String action = parsingTable.get(currentState).get(currentInputSymbol);
If (action.equals(“”)) {
Return false; }
If (action.equals(String.valueOf(ACCEPT_STATE))) {
Return true; }
If (action.charAt(0) == ‘s’) {
// Shift operation
Stack.push(currentInputSymbol);
Stack.push(action.substring(1));
inputIndex++;
} else if (action.charAt(0) == ‘r’) {
// Reduce operation
String productionRule = grammar[Integer.parseInt(action.substring(1))];
String[] parts = productionRule.split(“ -> “);
String leftSide = parts[0];
String rightSide = parts[1];
For (int I = 0; I < rightSide.length() * 2; i++) {
Stack.pop(); }
Int newState = Integer.parseInt(stack.peek());
Stack.push(leftSide);
Stack.push(parsingTable.get(leftSide).get(String.valueOf(newState)));
} else {
Return false;} }
Return false; }
Private static boolean nonTerminalsContains(String symbol) {
For (String nonTerminal : nonTerminals) {
If (nonTerminal.equals(symbol)) {
Return true;} }
Return false;}}
Output
Practical No: 9
Aim :Java program that demonstrates how to check if a given grammar is ambiguous
Source code:
Import java.util.*;
Public class AmbiguityChecker {
Private Map<String, Set<String>> productions;
Public AmbiguityChecker() {
Productions = new HashMap<>(); }
Public void addProduction(String nonTerminal, String production) {
Productions.computeIfAbsent(nonTerminal, k -> new HashSet<>()).add(production); }
Public boolean isAmbiguous() {
For (String nonTerminal : productions.keySet()) {
Set<String> productionSet = productions.get(nonTerminal);
If (productionSet.size() > 1) {
Return true; } }
Return false; }
Public static void main(String[] args) {
AmbiguityChecker checker = new AmbiguityChecker();
// Add productions to the grammar
Checker.addProduction(“E”, “E + E”);
Checker.addProduction(“E”, “E * E”);
// Check if the grammar is ambiguous
Boolean isAmbiguous = checker.isAmbiguous();
If (isAmbiguous) {
System.out.println(“The grammar is ambiguous.”);} else {
System.out.println(“The grammar is not ambiguous.”);
}}}
Output
Comments
Post a Comment