Descent Parser to check for Valid Grammer
Project Overview
This project was part of my Operating Systems course at Oakland University. The objective of the assignment was to develop an object-oriented program capable of verifying the validity of an expression. For this purpose, JFlex (www.jflex.de) was utilized to create a lexical analyzer. This analyzer processes input, evaluates it against the regular expressions defined in the specifications, and performs corresponding actions based on the results. JFlex generates the Lexer class according to the required specifications. Additionally, an interface was created to allow users to open a text input file, read the expression, and execute the parser
Valid members for this grammer include:
- Variables (alphanumeric)
- Integers
- + Addition
- - Subtraction
- * Multiplication
- / Division
- ( ) Parenthesis Left and Right
The parser ensures that every component of the expression is a valid part of the grammar. It also verifies that left and right parentheses are correctly paired. Additionally, it enforces rules such as disallowing consecutive operators (e.g., */ is not permitted).
| Expression | Result after Parsing |
|---|---|
| variable + (23 + Ant) / Dog * 1234 | Valid |
| ((This + 12345) + (5/Test)) * 12 - 12 + (2/2) | Valid: Grammar and parenthesis match in pairs. |
| (A + Elephant * CAT / 232323) - (1 + A - 3 * (C / (Z + Z))) | Valid |
| (12 / B) + * (C + 12) | Invalid: Addition and Multiplication cannot be next to each other. |
| (A + B) > C | Invalid: > is not defined |
| 1244 / (A + B) * C & F | Invalid: & is not defined |
Output after running the expressions from the table above:
Enter the path to your input file and hit enter:
C:\\Input Data\\Input1.txt
File located at:
C:\\Input Data\\Input1.txt
Result from parsing is:
true
If you would like to run again enter Y:
Y
Enter the path to your input file and hit enter:
C:\\Input Data\\Input2.txt
File located at:
C:\\Input Data\\Input2.txt
Result from parsing is:
true
If you would like to run again enter Y:
Y
Enter the path to your input file and hit enter:
C:\\Input Data\\Input3.txt
File located at:
C:\\Input Data\\Input3.txt
Result from parsing is:
true
If you would like to run again enter Y:
Y
Enter the path to your input file and hit enter:
C:\\Input Data\\Input4.txt
File located at:
C:\\Input Data\\Input4.txt
Result from parsing is:
false
If you would like to run again enter Y:
Y
Enter the path to your input file and hit enter:
C:\\Input Data\\Input5.txt
File located at:
C:\\Input Data\\Input5.txt
Result from parsing is:
false
If you would like to run again enter Y:
Y
Enter the path to your input file and hit enter:
C:\\Input Data\\Input6.txt
File located at:
C:\\Input Data\\Input6.txt
Result from parsing is: false
If you would like to run again enter Y:
n
C:\\Input Data\\Input1.txt
File located at:
C:\\Input Data\\Input1.txt
Result from parsing is:
true
If you would like to run again enter Y:
Y
Enter the path to your input file and hit enter:
C:\\Input Data\\Input2.txt
File located at:
C:\\Input Data\\Input2.txt
Result from parsing is:
true
If you would like to run again enter Y:
Y
Enter the path to your input file and hit enter:
C:\\Input Data\\Input3.txt
File located at:
C:\\Input Data\\Input3.txt
Result from parsing is:
true
If you would like to run again enter Y:
Y
Enter the path to your input file and hit enter:
C:\\Input Data\\Input4.txt
File located at:
C:\\Input Data\\Input4.txt
Result from parsing is:
false
If you would like to run again enter Y:
Y
Enter the path to your input file and hit enter:
C:\\Input Data\\Input5.txt
File located at:
C:\\Input Data\\Input5.txt
Result from parsing is:
false
If you would like to run again enter Y:
Y
Enter the path to your input file and hit enter:
C:\\Input Data\\Input6.txt
File located at:
C:\\Input Data\\Input6.txt
Result from parsing is: false
If you would like to run again enter Y:
n
Description
Tom DesRosiers
This project was part of my Operating Systems course at Oakland University. The objective of the assignment was to develop an object-oriented program capable of verifying the validity of an expression.
javaApplication1.java
package javaapplication1;
/**
* This file utilizes and tests the descent parser class.
* The first task is to create an instance of the Descent Parser class.
* The user is then prompted for the path to the input file.
* The input file is opened and the Parsing process begins.
* Once parsing is completed the result is displayed and the user is asked if they
* want to run the program again.
*/
import java.io.*;
public class JavaApplication1 {
public static void main(String args[]) throws Exception
{
String filename = null;
//Create Descent Parser Object
DescentParser DParser;
//Boolean to store result
boolean ParsingResult;
//String done
String done = null;
//Open up standard input.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
do
{
//Prompt User to enter the Path for the INput file
System.out.print("\nEnter the path to your input file and hit enter: ");
//Read the path from the command line use catch & try
try
{
filename = br.readLine();
}
catch (IOException ioe)
{
System.out.println("\n\nIO error reading the filename Now exiting!");
System.exit(1);
}
System.out.println("\n\n File located at: " + filename);
//Create Parser
DParser = new DescentParser(filename);
//Run Parser
ParsingResult = DParser.StartParse();
//Print out Results
System.out.println("\n Result from parsing is: " + ParsingResult);
//Print out prompt to try again.
System.out.println("\nIf you would like to run again enter Y: ");
try
{
done = br.readLine();
}
catch (IOException ioe)
{
System.out.println("\n\nIO error reading your choice Now exiting!");
System.exit(1);
}
}while(done.equals("Y"));
}
}
javaApplication1.java
package javaapplication1;
/*******************************
*Class: DescentParser
*This class examines whether or not a grammer is valid.
*********************************************************/
import java.io.File;
import java.io.FileReader;
import java.io.BufferedReader;
public class DescentParser {
//Constants
/* Token Values */
private static final int VAR = 1;
private static final int INT = 2;
private static final int PLUS = 3;
private static final int MINUS = 4;
private static final int MULT = 5;
private static final int DIV = 6;
private static final int LPAR = 7;
private static final int RPAR = 8;
private static final int INVALID = -2;
private static final int END = -1;
//Member Variables.
private int CurrentToken = 0;
private boolean VallidExpression = false;
private Lexer Lex;
//Constructor
DescentParser(String Fname) throws Exception
{
//Create Lexer
Lex = new Lexer(new FileReader(Fname));
}//End of Contructor
/*############Function StartParse############
This function start the parsing process and
*return the result. true if it's a valid
*expression, false if not.
*#######################################*/
public boolean StartParse() throws Exception
{
//Get first token
CurrentToken = Lex.yylex();
//Start Parsing Process and return result
return Exp();
} // END of Function StartParse
/*************Function Match***********************
Input: Integer Representing the Token to be matched
Return: True if matches, False if not
If True then Read in the next Token
*****************************************************/
private boolean match(int Token) throws Exception
{
//Check
if(CurrentToken == Token)
{
//Advance to the next token
CurrentToken = Lex.yylex();
//Return True
return true;
}
else
{
return false;
}
}/*****************End of Function Match********************/
// @@@@@@@@@@@@@@@@@@@@@Parsing Functions@@@@@@@@@@@@@@@@@@@
//@@@@@@@@@@@@@@@@Function: Parse EXP@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
private boolean Exp() throws Exception
{
//Enter Switch Statement for checking Values
switch (CurrentToken)
{
case VAR:
case INT:
case LPAR:
return ((Term()) && (RestExp()));
default:
//None Return False
return false;
}//end of switch statement
}//@@@@@@@@@@@@@@@@@@@@@@@@end of Function EXP@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//@@@@@@@@@@@@@@@@@@@@Function: Parse RestExp@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
private boolean RestExp() throws Exception
{
//Enter Switch Statement for checking Values
switch (CurrentToken)
{
case RPAR:
//Do nothing just return true
return true;
case PLUS:
return ( (match(PLUS)) && ((Term()) && (RestExp()) ) );
case MINUS:
return ( (match(MINUS)) && ((Term()) && (RestExp()) ) );
case END:
return true;
default:
//SOMETHING ELSE
return false;
}//end of switch statement
}//@@@@@@@@@@@@@@@@@@@@@@end of Function RestExp@@@@@@@@@@@@@@@@@@@@@@
//@@@@@@@@@@@@@@@@@@Function: Parse Term@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
private boolean Term() throws Exception
{
//Enter Switch Statement for checking Values
switch (CurrentToken)
{
case VAR:
case INT:
case LPAR:
return ((Factor()) && (RestTerm()));
default:
//None Return False
return false;
}//end of switch statement
}//@@@@@@@@@@@@@@@@@@@@@end of Function Term@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//@@@@@@@@@@@@@@@@@@@@@@Function: Parse RestTerm@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
private boolean RestTerm() throws Exception
{
//Enter Switch Statement for checking Values
switch (CurrentToken)
{
case RPAR:
case PLUS:
case MINUS:
return true;
case MULT:
return ((match(MULT)) && (Factor()) && (RestTerm()));
case DIV:
return ((match(DIV)) && (Factor()) && (RestTerm()));
case END:
//Do Nothing
return true;
default:
//None Return False
return false;
}//end of switch statement
}//@@@@@@@@@@@@@@@end of Function RestTerm@@@@@@@@@@@@@@@@@@@@@
//@@@@@@@@@@@@@@@@@@Function: Parse Factor@@@@@@@@@@@@@@@@@@@@@@@@@@
private boolean Factor() throws Exception
{
//Enter Switch Statement for checking Values
switch (CurrentToken)
{
case VAR:
return (match(VAR));
case INT:
return (match(INT));
case LPAR:
return (match(LPAR) && Exp() && match(RPAR));
default:
//None Return False
return false;
}//end of switch statement
}//@@@@@@@@@@@@@@@@@@@@@@end of Function Factor@@@@@@@@@@@@@@@@@@@@@@@@@@
}//%%%%%%%%%%%%%%%%%%%%%%%%%end of class Descent Parser%%%%%%%%%%%%%%%%%%%%%%%%%
lexer.java
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package javaapplication1;
/* The following code was generated by JFlex 1.4 on 5/22/04 3:36 PM */
import java.lang.*;
/**
* This class is a scanner generated by
* JFlex 1.4
* on 5/22/04 3:36 PM from the specification file
* C:/Documents and Settings/mike/Desktop/Assignment2/CSE335Assignment2/HM2.flex
*/
class Lexer {
/** This character denotes the end of file */
public static final int YYEOF = -1;
/** initial size of the lookahead buffer */
private static final int ZZ_BUFFERSIZE = 16384;
/** lexical states */
public static final int YYINITIAL = 0;
/**
* Translates characters to character classes
*/
private static final char [] ZZ_CMAP = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 10, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0, 8, 9, 6, 4, 0, 5, 0, 7,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0,
0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0,
0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0
};
/**
* Translates DFA states to action switch labels.
*/
private static final int [] ZZ_ACTION = zzUnpackAction();
private static final String ZZ_ACTION_PACKED_0 =
"\1\0\1\1\1\2\1\3\1\4\1\5\1\6\1\7"+
"\1\10\1\11\1\12";
private static int [] zzUnpackAction() {
int [] result = new int[11];
int offset = 0;
offset = zzUnpackAction(ZZ_ACTION_PACKED_0, offset, result);
return result;
}
private static int zzUnpackAction(String packed, int offset, int [] result) {
int i = 0; /* index in packed string */
int j = offset; /* index in unpacked array */
int l = packed.length();
while (i < l) {
int count = packed.charAt(i++);
int value = packed.charAt(i++);
do result[j++] = value; while (--count > 0);
}
return j;
}
/**
* Translates a state to a row index in the transition table
*/
private static final int [] ZZ_ROWMAP = zzUnpackRowMap();
private static final String ZZ_ROWMAP_PACKED_0 =
"\0\0\0\13\0\13\0\26\0\41\0\13\0\13\0\13"+
"\0\13\0\13\0\13";
private static int [] zzUnpackRowMap() {
int [] result = new int[11];
int offset = 0;
offset = zzUnpackRowMap(ZZ_ROWMAP_PACKED_0, offset, result);
return result;
}
private static int zzUnpackRowMap(String packed, int offset, int [] result) {
int i = 0; /* index in packed string */
int j = offset; /* index in unpacked array */
int l = packed.length();
while (i < l) {
int high = packed.charAt(i++) << 16;
result[j++] = high | packed.charAt(i++);
}
return j;
}
/**
* The transition table of the DFA
*/
private static final int [] ZZ_TRANS = zzUnpackTrans();
private static final String ZZ_TRANS_PACKED_0 =
"\1\2\1\3\1\4\1\5\1\6\1\7\1\10\1\11"+
"\1\12\1\13\16\0\1\4\12\0\2\5\7\0";
private static int [] zzUnpackTrans() {
int [] result = new int[44];
int offset = 0;
offset = zzUnpackTrans(ZZ_TRANS_PACKED_0, offset, result);
return result;
}
private static int zzUnpackTrans(String packed, int offset, int [] result) {
int i = 0; /* index in packed string */
int j = offset; /* index in unpacked array */
int l = packed.length();
while (i < l) {
int count = packed.charAt(i++);
int value = packed.charAt(i++);
value--;
do result[j++] = value; while (--count > 0);
}
return j;
}
/* error codes */
private static final int ZZ_UNKNOWN_ERROR = 0;
private static final int ZZ_NO_MATCH = 1;
private static final int ZZ_PUSHBACK_2BIG = 2;
/* error messages for the codes above */
private static final String ZZ_ERROR_MSG[] = {
"Unkown internal scanner error",
"Error: could not match input",
"Error: pushback value was too large"
};
/**
* ZZ_ATTRIBUTE[aState] contains the attributes of state aState
*/
private static final int [] ZZ_ATTRIBUTE = zzUnpackAttribute();
private static final String ZZ_ATTRIBUTE_PACKED_0 =
"\1\0\2\11\2\1\6\11";
private static int [] zzUnpackAttribute() {
int [] result = new int[11];
int offset = 0;
offset = zzUnpackAttribute(ZZ_ATTRIBUTE_PACKED_0, offset, result);
return result;
}
private static int zzUnpackAttribute(String packed, int offset, int [] result) {
int i = 0; /* index in packed string */
int j = offset; /* index in unpacked array */
int l = packed.length();
while (i < l) {
int count = packed.charAt(i++);
int value = packed.charAt(i++);
do result[j++] = value; while (--count > 0);
}
return j;
}
/** the input device */
private java.io.Reader zzReader;
/** the current state of the DFA */
private int zzState;
/** the current lexical state */
private int zzLexicalState = YYINITIAL;
/** this buffer contains the current text to be matched and is
the source of the yytext() string */
private char zzBuffer[] = new char[ZZ_BUFFERSIZE];
/** the textposition at the last accepting state */
private int zzMarkedPos;
/** the textposition at the last state to be included in yytext */
private int zzPushbackPos;
/** the current text position in the buffer */
private int zzCurrentPos;
/** startRead marks the beginning of the yytext() string in the buffer */
private int zzStartRead;
/** endRead marks the last character in the buffer, that has been read
from input */
private int zzEndRead;
/** number of newlines encountered up to the start of the matched text */
private int yyline;
/** the number of characters up to the start of the matched text */
private int yychar;
/**
* the number of characters from the last newline up to the start of the
* matched text
*/
private int yycolumn;
/**
* zzAtBOL == true <=> the scanner is currently at the beginning of a line
*/
private boolean zzAtBOL = true;
/** zzAtEOF == true <=> the scanner is at the EOF */
private boolean zzAtEOF;
/* user code: */
/* Token Values */
private static final int VAR = 1;
private static final int INT = 2;
private static final int PLUS = 3;
private static final int MINUS = 4;
private static final int MULT = 5;
private static final int DIV = 6;
private static final int LPAR = 7;
private static final int RPAR = 8;
private static final int INVALID = -2;
/**
* Creates a new scanner
* There is also a java.io.InputStream version of this constructor.
*
* @param in the java.io.Reader to read input from.
*/
Lexer(java.io.Reader in) {
this.zzReader = in;
}
/**
* Creates a new scanner.
* There is also java.io.Reader version of this constructor.
*
* @param in the java.io.Inputstream to read input from.
*/
Lexer(java.io.InputStream in) {
this(new java.io.InputStreamReader(in));
}
/**
* Refills the input buffer.
*
* @return false, iff there was new input.
*
* @exception java.io.IOException if any I/O-Error occurs
*/
private boolean zzRefill() throws java.io.IOException {
/* first: make room (if you can) */
if (zzStartRead > 0) {
System.arraycopy(zzBuffer, zzStartRead,
zzBuffer, 0,
zzEndRead-zzStartRead);
/* translate stored positions */
zzEndRead-= zzStartRead;
zzCurrentPos-= zzStartRead;
zzMarkedPos-= zzStartRead;
zzPushbackPos-= zzStartRead;
zzStartRead = 0;
}
/* is the buffer big enough? */
if (zzCurrentPos >= zzBuffer.length) {
/* if not: blow it up */
char newBuffer[] = new char[zzCurrentPos*2];
System.arraycopy(zzBuffer, 0, newBuffer, 0, zzBuffer.length);
zzBuffer = newBuffer;
}
/* finally: fill the buffer with new input */
int numRead = zzReader.read(zzBuffer, zzEndRead,
zzBuffer.length-zzEndRead);
if (numRead < 0) {
return true;
}
else {
zzEndRead+= numRead;
return false;
}
}
/**
* Closes the input stream.
*/
public final void yyclose() throws java.io.IOException {
zzAtEOF = true; /* indicate end of file */
zzEndRead = zzStartRead; /* invalidate buffer */
if (zzReader != null)
zzReader.close();
}
/**
* Resets the scanner to read from a new input stream.
* Does not close the old reader.
*
* All internal variables are reset, the old input stream
* cannot be reused (internal buffer is discarded and lost).
* Lexical state is set to ZZ_INITIAL.
*
* @param reader the new input stream
*/
public final void yyreset(java.io.Reader reader) {
zzReader = reader;
zzAtBOL = true;
zzAtEOF = false;
zzEndRead = zzStartRead = 0;
zzCurrentPos = zzMarkedPos = zzPushbackPos = 0;
yyline = yychar = yycolumn = 0;
zzLexicalState = YYINITIAL;
}
/**
* Returns the current lexical state.
*/
public final int yystate() {
return zzLexicalState;
}
/**
* Enters a new lexical state
*
* @param newState the new lexical state
*/
public final void yybegin(int newState) {
zzLexicalState = newState;
}
/**
* Returns the text matched by the current regular expression.
*/
public final String yytext() {
return new String( zzBuffer, zzStartRead, zzMarkedPos-zzStartRead );
}
/**
* Returns the character at position pos from the
* matched text.
*
* It is equivalent to yytext().charAt(pos), but faster
*
* @param pos the position of the character to fetch.
* A value from 0 to yylength()-1.
*
* @return the character at position pos
*/
public final char yycharat(int pos) {
return zzBuffer[zzStartRead+pos];
}
/**
* Returns the length of the matched text region.
*/
public final int yylength() {
return zzMarkedPos-zzStartRead;
}
/**
* Reports an error that occured while scanning.
*
* In a wellformed scanner (no or only correct usage of
* yypushback(int) and a match-all fallback rule) this method
* will only be called with things that "Can't Possibly Happen".
* If this method is called, something is seriously wrong
* (e.g. a JFlex bug producing a faulty scanner etc.).
*
* Usual syntax/scanner level error handling should be done
* in error fallback rules.
*
* @param errorCode the code of the errormessage to display
*/
private void zzScanError(int errorCode) {
String message;
try {
message = ZZ_ERROR_MSG[errorCode];
}
catch (ArrayIndexOutOfBoundsException e) {
message = ZZ_ERROR_MSG[ZZ_UNKNOWN_ERROR];
}
throw new Error(message);
}
/**
* Pushes the specified amount of characters back into the input stream.
*
* They will be read again by then next call of the scanning method
*
* @param number the number of characters to be read again.
* This number must not be greater than yylength()!
*/
public void yypushback(int number) {
if ( number > yylength() )
zzScanError(ZZ_PUSHBACK_2BIG);
zzMarkedPos -= number;
}
/**
* Resumes scanning until the next regular expression is matched,
* the end of input is encountered or an I/O-Error occurs.
*
* @return the next token
* @exception java.io.IOException if any I/O-Error occurs
*/
public int yylex() throws java.io.IOException {
int zzInput;
int zzAction;
// cached fields:
int zzCurrentPosL;
int zzMarkedPosL;
int zzEndReadL = zzEndRead;
char [] zzBufferL = zzBuffer;
char [] zzCMapL = ZZ_CMAP;
int [] zzTransL = ZZ_TRANS;
int [] zzRowMapL = ZZ_ROWMAP;
int [] zzAttrL = ZZ_ATTRIBUTE;
while (true) {
zzMarkedPosL = zzMarkedPos;
zzAction = -1;
zzCurrentPosL = zzCurrentPos = zzStartRead = zzMarkedPosL;
zzState = zzLexicalState;
zzForAction: {
while (true) {
if (zzCurrentPosL < zzEndReadL)
zzInput = zzBufferL[zzCurrentPosL++];
else if (zzAtEOF) {
zzInput = YYEOF;
break zzForAction;
}
else {
// store back cached positions
zzCurrentPos = zzCurrentPosL;
zzMarkedPos = zzMarkedPosL;
boolean eof = zzRefill();
// get translated positions and possibly new buffer
zzCurrentPosL = zzCurrentPos;
zzMarkedPosL = zzMarkedPos;
zzBufferL = zzBuffer;
zzEndReadL = zzEndRead;
if (eof) {
zzInput = YYEOF;
break zzForAction;
}
else {
zzInput = zzBufferL[zzCurrentPosL++];
}
}
int zzNext = zzTransL[ zzRowMapL[zzState] + zzCMapL[zzInput] ];
if (zzNext == -1) break zzForAction;
zzState = zzNext;
int zzAttributes = zzAttrL[zzState];
if ( (zzAttributes & 1) == 1 ) {
zzAction = zzState;
zzMarkedPosL = zzCurrentPosL;
if ( (zzAttributes & 8) == 8 ) break zzForAction;
}
}
}
// store back cached position
zzMarkedPos = zzMarkedPosL;
switch (zzAction < 0 ? zzAction : ZZ_ACTION[zzAction]) {
case 9:
{ return LPAR;
}
case 11: break;
case 4:
{ return VAR;
}
case 12: break;
case 8:
{ return DIV;
}
case 13: break;
case 1:
{ return INVALID;
}
case 14: break;
case 6:
{ return MINUS;
}
case 15: break;
case 7:
{ return MULT;
}
case 16: break;
case 2:
{ /* just skip what was found, do nothing */
}
case 17: break;
case 10:
{ return RPAR;
}
case 18: break;
case 3:
{ return INT;
}
case 19: break;
case 5:
{ return PLUS;
}
case 20: break;
default:
if (zzInput == YYEOF && zzStartRead == zzCurrentPos) {
zzAtEOF = true;
return YYEOF;
}
else {
zzScanError(ZZ_NO_MATCH);
}
}
}
}
}