COMPILER DESIGN CS 654
DOP: Practical No. 5 DOS:
Aim: Program to implement bottom-up parsing.
Input:
1. Set of production rules
2. String to be parsed
Expected Output:
1. Table representing Bottom up parsing.
2. Determine whether the string is parsed or not.
Theory : Bottom-up parsing is a fundamental parsing technique used in compiler design. It
starts from the leaf nodes of a parse tree and works its way up to the root node, which represents
the start symbol of the grammar. Unlike top-down parsing, which begins with the start symbol
and derives the input string, bottom-up parsing works in reverse it starts with the input string
and applies production rules in a backward manner until it reduces the string to the start symbol.
In this program, the input consists of a grammar and an input string that needs to be parsed.
The grammar is defined using a set of production rules, where each rule specifies how a non-
terminal symbol can be replaced by a sequence of terminal and/or non-terminal symbols. The
parsing process begins by shifting symbols from the input onto a stack, and then attempting to
reduce them using the given production rules. This process continues until either the input
string is fully reduced to the start symbol, indicating successful parsing, or no further reductions
are possible, meaning the string is not valid under the given grammar.The output of this
program provides a step-by-step trace of the parsing process. At each step, the current stack
content, the remaining input, and the action performed (shift or reduce) are displayed.
Algorithm:
1. Begin
2. Store the production rules of grammar.
3. Input the string to be parsed.
4. Calculate its length and store first element in stack.
5. Do steps 6-12 while the length of stack !=1 && stacktop == input length.
6. Print the current stack elements and current input string.
7. According to the action print Reduced or Shifted.
8. If reduce is possible then goto 9 else goto 5.
9. Pop first element from stack.
10. Compare with each production rule and if matched goto 11 else goto 5.
11. Pop matched part from stack.
12. Push LHS of that rule in stack.
13. If length(stack) == 1 then goto 14 else goto 15.
14. Print string can be parsed.
15. End.
44
CO22329
Flowchart:
45
CO22329
Source Code:
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <fstream>
using namespace std;
struct Production {
string lhs;
string rhs;
};
bool reduceStack(string &stack, vector<Production> &productions,
string &action) {
for (const auto &prod : productions) {
size_t pos = stack.rfind(prod.rhs);
if (pos != string::npos && pos + prod.rhs.length() ==
stack.length()) {
stack.erase(pos, prod.rhs.length());
stack += prod.lhs;
action = "Reduced (" + prod.lhs + "->" + prod.rhs + ")";
return true;
}
}
return false;
}
int main() {
int numProductions;
vector<Production> productions;
string input, choice, fileName;
cout << "BOTTOM UP PARSING\n";
cout << "Read input from (console/file)? ";
cin >> choice;
if (choice == "file") {
cout << "Enter file name: ";
cin >> fileName;
ifstream file(fileName);
if (!file) {
cerr << "Error: Unable to open file.\n";
return 1;
}
file >> numProductions;
productions.resize(numProductions);
46
CO22329
for (int i = 0; i < numProductions; i++) {
string production;
file >> production;
productions[i].lhs = production.substr(0, 1);
productions[i].rhs = production.substr(3);
}
file >> input;
file.close();
} else {
cout << "Enter total no. of productions: ";
cin >> numProductions;
productions.resize(numProductions);
cout << "Enter the set of productions:\n";
for (int i = 0; i < numProductions; i++) {
string production;
cin >> production;
productions[i].lhs = production.substr(0, 1);
productions[i].rhs = production.substr(3);
}
cout << "Enter input string: ";
cin >> input;
}
string stack;
size_t i = 0;
cout << "\n" << left << setw(15) << "Stack" << setw(15) <<
"Input" << "Action" << endl;
cout << "-----------------------------------------------------";
while (i < input.length() || !stack.empty()) {
string action = "Shifted";
cout << "\n" << left << setw(15) << stack << setw(15) <<
input.substr(i) << action;
if (i < input.length()) {
stack += input[i++];
}
while (reduceStack(stack, productions, action)) {
cout << "\n" << left << setw(15) << stack << setw(15) <<
input.substr(i) << action;
}
if (stack == productions[0].lhs && i == input.length()) {
break;
}
}
47
CO22329
if (stack == productions[0].lhs) {
cout << "\n\nString Accepted";
} else {
cout << "\n\nString Rejected";
}
return 0;
}
Output:
48
CO22329
Frequently Asked Questions (FAQs):
1. What is bottom-up parsing?
Ans Bottom-up parsing is a syntax analysis technique that starts from the input string and
applies production rules in reverse to reach the start symbol.
2. How does bottom-up parsing differ from top-down parsing?
Ans Bottom-up parsing starts from the input and moves towards the start symbol, whereas top-
down parsing begins with the start symbol and derives the input.
3. What are the key types of bottom-up parsers?
• Shift-Reduce Parser
• LR Parser (Simple LR, Canonical LR, LALR)
4. What is the main advantage of bottom-up parsing?
Ans It can handle left-recursive and ambiguous grammars more efficiently.
5. What is the purpose of the stack in bottom-up parsing?
Ans The stack stores symbols and helps in reducing them using grammar rules.
49
CO22329
