I am writing a simple recursive decent parser in Java that uses a lexical analyzer to split source code from a hypothetical imperative programming language (looks kinda like pseudocode) from a text file into individual tokens which are then examined to see if they follow the rules of an EBNF grammar. If the rules are not followed, the program outputs that a syntax error is present (not what it is or where it occurs).
Here is the EBNF grammar:
<program> -> program begin <statement_list> end
<statement_list> -> <statement> {;<statement>}
<statement> -> <assignment_statement> | <if_statement> | <loop_statement>
<assignment_statement> -> <variable> = <expression>
<variable> -> identifier (An identifier is a string that begins with a letter followed by 0 or more letters and/or digits)
<expression> -> <term> {(+|-) <term>}
<term> -> <factor> {(* | /) <factor>}
<factor> -> identifier | int_constant | (<expr>)
<if_statement> -> if (<logic_expression>) then <statement>
<logic_expression> -> <variable> (< | >) <variable> (Assume logic expressions have only less than or greater than operators)
<loop_statement> -> loop (<logic_expression>) <statement>
And here is a sample program in the pseudolanguage without any syntax errors:
program
begin
sum1 = var1 + var2;
sum2 = var3 + var2 * 90;
sum3 = (var2 + var1) * var3;
if (sum1 < sum2) then
if (var1 > var2) then
var4 = sum2 - sum1;
loop (var1 < var2)
var5 = var4/45
end
As you can see, every program must follow the program begin <statement_list> end format. Only the last statement does not require a semicolon at the end.
Right now, I have a basic program working. The lexical analyzer part has no issues since the output of the tokens for debugging purposes shows that they are all examined, but as for the EBNF parsing I only have it recognizing a statement as a simple variable (start small). I am unable to go any further because I don't know how to implement rules involving curly braces such as <statement_list> -> <statement> {;<statement>} (see above).
According to the Wikipedia page on Extended Backus-Naur form, curly braces indicate that repetition is optional. So in the case of this grammar, a <statement_list>, for example, is at least one <statement> optionally followed by any number of semicolon + <statement>. So if multiple <statement>s are present, all but the last have a semicolon at the end.
I am just unsure how to implement it based on my code. I know that you have to check if the token after a statement is a semicolon followed by another statement, but since this is a recursive decent parser and I have the methods returning a boolean, recursion would not work here which leaves iteration. However, since I implemented the lexical analyzer to delete the token from the buffer after it has been examined, this makes checking by iteration very difficult. Is there a better way to go about doing this?
Here is my Java program so far:
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.StringTokenizer;
public class SyntacticAnalysis {
private static class Parser {
// Parser has buffer -- which contains the source code as text -- it must read from
private StringBuilder buffer;
public Parser(File file) {
// Reading from text file using simple scanner
Scanner sc = null;
try {
sc = new Scanner(file);
// Define buffer length as file length
buffer = new StringBuilder((int)file.length());
// Stops reading when no more text
while(sc.hasNext()) {
// Token will be sequence of characters
String token = sc.next();
// Since token character sequence may contain characters such as ()+-*/=;
// We need to further break down token to separate special character and rest
// E.g. if(sum1<sum2) token will be further tokenized into: if ( sum1 < sum2 )
// This way spacing doesn't matter
StringTokenizer tokens = new StringTokenizer(token, "()+-*/=;", true);
// Add tokens to buffer
while (tokens.hasMoreTokens())
buffer.append(tokens.nextToken() + " ");
}
} catch (FileNotFoundException fnfe) {
System.out.print("File not found.");
fnfe.printStackTrace();
} finally {
sc.close();
}
}
private String lexicalAnalyzer() {
int i = buffer.indexOf(" ");
// Lexeme will be from beginning of buffer (location of current token) to where whitespace is
String lexeme = buffer.substring(0, i);
// Delete lexeme from buffer since now stored in variable
buffer.delete(0, i + 1);
// Print what tokens are read for debugging purposes
System.out.println(lexeme);
return lexeme;
}
// Method for main
// Returns program() since <program> -> program begin <statement_list> end is checked first
public boolean analyzeCode() {
return program();
}
private boolean program() {
// Every program must have program followed by begin
if (!lexicalAnalyzer().toLowerCase().equals("program")) return false;
if (!lexicalAnalyzer().toLowerCase().equals("begin")) return false;
if (!statementList()) return false;
// Every program must finish with end keyword
if (!lexicalAnalyzer().equals("end")) return false;
return true;
}
private boolean statementList() {
if (!statement()) return false;
/* Repetition to check further statements goes here -- how to implement? */
return true;
}
private boolean statement() {
// Define statement as variable for now just as a test
if (!variable()) return false;
return true;
}
private boolean variable() {
// Regular expression to determine valid identifier
// [a-zA-Z] means starts with any letter
// [a-zA-Z0-9]* means any amount of alphanumeric characters (0 - infinity)
if (!lexicalAnalyzer().matches("[a-zA-Z][a-zA-Z0-9]*")) return false;
return true;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter file name: ");
String name = sc.next();
File file = new File(name);
Parser parser = new Parser(file);
if (parser.analyzeCode())
System.out.print("There are no syntax errors in the program.");
else
System.out.print("The program contains one or more syntax errors.");
}
}
Any help would be kindly appreciated.
Scannerhere is completely pointless, a waste of both time and space. lexer has nothing to do with your question. Repetition is simply s matter of looping in recursive descent. Unclear what you're asking. - user207421