Scribd
Upload
9 views

Compiler Lab Assignment-4

The document describes a shift reduce parser program that parses input strings based on a given grammar. The program takes grammar rules and an input string as input and performs shift and reduce operations on a stack to check if the string is accepted by the grammar.

Uploaded by

Viswanath Chowdary
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views

Compiler Lab Assignment-4

The document describes a shift reduce parser program that parses input strings based on a given grammar. The program takes grammar rules and an input string as input and performs shift and reduce operations on a stack to check if the string is accepted by the grammar.

Uploaded by

Viswanath Chowdary
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

ASSIGNMENT-4

AIM:
Performing SHIFT REDUCE PARSER for the given input string considering the given
grammer.

Grammer:
S->S+S
S->S*S
S->id (we considering id as i)

CODE:
import java.util.Scanner;
class ProductionRule {
String left;
String right;
ProductionRule(String left, String right) {
this.left = left;
this.right = right;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String input, stack = "", temp, ch, token1, token2, substring;
int i, j, stackLength, substringLength, stackTop, ruleCount;
ProductionRule[] rules;
System.out.println("Enter the number of production rules: ");
ruleCount = scanner.nextInt();
scanner.nextLine(); // Consume newline character
rules = new ProductionRule[ruleCount];
System.out.println("Enter the production rules (in the form 'left->right'): ");
for (i = 0; i < ruleCount; i++) {
temp = scanner.nextLine();
token1 = temp.split("->")[0];
token2 = temp.split("->")[1];
rules[i] = new ProductionRule(token1, token2);
}
System.out.println("Enter the input string: ");
input = scanner.nextLine();
i = 0;
while (true) {
if (i < input.length()) {
ch = Character.toString(input.charAt(i));
i++;
stack += ch;
System.out.print(stack + "\t");
for (int k = i; k < input.length(); k++) {
System.out.print(input.charAt(k));
}
System.out.println("\tShift " + ch);
}
for (j = 0; j < ruleCount; j++) {
substring = stack.contains(rules[j].right) ? rules[j].right : null;
if (substring != null) {
stackLength = stack.length();
substringLength = substring.length();
stackTop = stackLength - substringLength;
stack = stack.substring(0, stackTop);
stack += rules[j].left;
System.out.print(stack + "\t");
for (int k = i; k < input.length(); k++) {
System.out.print(input.charAt(k));
}
System.out.println("\tReduce " + rules[j].left + "->" + rules[j].right);
j = -1;
}
}
if (stack.equals(rules[0].left) && i == input.length()) {
System.out.println("\nAccepted");
break;
}
if (i == input.length()) {
System.out.println("\nNot Accepted");
break;
}
}
}
}

OUTPUT:

Name:
VISWANATH
Reg No:
21BRS1675

You might also like