Compiler Design Project 1: Implement a predictive parser for the example express
ID: 3703672 • Letter: C
Question
Compiler Design Project 1: Implement a predictive parser for the example expression grammar
1. Introduction
Implement a predictive parser for the example expression grammar. You need to construct
an abstract syntax tree for input expressions. Emit the abstract syntax tree for an input
expression in preorder.
<goal> ::= <expr>
<expr> ::= <term> + <expr>
| <term> - <expr>
| <term>
<term> ::= <factor> * <term>
| <factor> / <term>
| <factor>
<factor> ::= number
| id
2. Input-Output specification
Input : "input.txt" file that contains expressions
- Input expressions only contain variables with a single character alphabet
(like a, b, c, x, y, not like var1, length)
- Input expressions may contain multiple digit number
(like 150, 20, 293...)
- Input expression may contains empty spaces within an expression
(like 5 +10-x...)
- Input expression does not contain brackets
- Each expression is separated with a new line character (' ')
Output : "output.txt" file that should contain results for each expression in the input file
- For a syntactically incorrect expression, print "incorrect syntax"
- For a syntactically correct expression, print the syntax tree for the expression in preorder
(ex. *+234)
Input, output file example
[input.txt]
x-2*y
a + 35 - b
10+*5
[output.txt]
-x*2y
-+a35b
incorrect syntax
C/C++, or Java are all receivable.
Please help!!!
Thanks a lot!!!
Explanation / Answer
Answer: See the code below:
1. TreeNode class: TreeNode.java
------------------------------------------------
package expressiontreedemo;
/**
* TreeNode class
*
*/
public class TreeNode {
private String data; // data item on node
private TreeNode left; // reference to LST
private TreeNode right; // reference to RST
/**
* Constructor
*/
public TreeNode() {
this(null);
}
/**
* Parameterized constructor
*
* @param newData
*/
public TreeNode(String newData) {
this.data = newData;
this.left = this.right = null;
}
/**
* @return the data
*/
public String getData() {
return data;
}
/**
* @param data
* the data to set
*/
public void setData(String data) {
this.data = data;
}
/**
* @return the left
*/
public TreeNode getLeft() {
return left;
}
/**
* @param left
* the left to set
*/
public void setLeft(TreeNode left) {
this.left = left;
}
/**
* @return the right
*/
public TreeNode getRight() {
return right;
}
/**
* @param right
* the right to set
*/
public void setRight(TreeNode right) {
this.right = right;
}
}
---------------------------------------------------
2. ExpressionTreeDemo class: ExpressionTreeDemo.java
----------------------------------------------
/**
*
*/
package expressiontreedemo;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
/**
* ExpressionTreeDemo class
*
*/
public class ExpressionTreeDemo {
private String[] expressions; // array to store expressions
private int numExpressions; // number of expressions in file
final int MAX_SIZE = 100; // maximum number of expressions
private TreeNode[] expressionTrees;
private int numExprTrees; // number of trees
private String[] outputExpressions;
private int numOutputExpressions; // number of output expressions
/**
* Constructor
*
* @param numExpressions
*/
public ExpressionTreeDemo() {
this.numExpressions = 0;
this.expressions = new String[MAX_SIZE];
this.expressionTrees = new TreeNode[MAX_SIZE];
this.outputExpressions = new String[MAX_SIZE];
this.numExprTrees = 0;
this.numOutputExpressions = 0;
}
// function to read expressions from file
public void readExpressionsFromFile(String filename) {
File file = new File(filename);
try {
BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file)));
String line;
while ((line = reader.readLine()) != null) {
expressions[numExpressions] = line;
numExpressions++;
}
reader.close();
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
// function to process expressions
public void processExpressions() {
for (int i = 0; i < numExpressions; i++) {
String[] expression = new String[10];
int numTerms = 0;
String term = "";
String expr = expressions[i];
for (int j = 0; j < expr.length(); j++) {
char ch = expr.charAt(j);
if (ch != ' ') {
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || Character.isLetter(ch)) {
if (!term.equals("")) {
expression[numTerms] = term;
numTerms++;
term = "";
}
expression[numTerms] = String.valueOf(ch);
numTerms++;
} else if (Character.isDigit(ch)) {
term += String.valueOf(ch);
}
}
}
expressionTrees[numExprTrees] = createExprTree(expression, 0);
numExprTrees++;
}
}
// function to create expression tree
public TreeNode createExprTree(String[] expr, int pos) {
TreeNode root = null;
String term = expr[pos];
while (pos != expr.length - 1) {
if (term.equals("+") || term.equals("-") || term.equals("*") || term.equals("/")) {
root = new TreeNode(term);
root.setLeft(createExprTree(expr, pos++));
root.setRight(createExprTree(expr, pos++));
} else {
return new TreeNode(term);
}
}
return root;
}
// function to traverse expression tree in preorder
public String traverseExpressionTree(TreeNode root) {
String str = null;
if (root == null) {
str = "";
} else {
str += root.getData();
traverseExpressionTree(root.getLeft());
traverseExpressionTree(root.getRight());
}
return str;
}
// function to generate output
public void generateOutput() {
for (int i = 0; i < numExprTrees; i++) {
TreeNode root = expressionTrees[i];
outputExpressions[numOutputExpressions] = traverseExpressionTree(root);
numOutputExpressions++;
}
}
// function to write output to file
public void writeOutputToFile() {
String outputFileName = "./output.txt";
File outputFile = new File(outputFileName);
try {
BufferedWriter writer = new BufferedWriter(new FileWriter(outputFile));
for (int i = 0; i < numOutputExpressions; i++) {
writer.write(outputExpressions[i]);
writer.newLine();
}
writer.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
/**
* main() function
*
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String filename = "./input.txt";
ExpressionTreeDemo treeDemo = new ExpressionTreeDemo();
treeDemo.readExpressionsFromFile(filename);
treeDemo.processExpressions();
treeDemo.generateOutput();
treeDemo.writeOutputToFile();
}
}
----------------------------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.