Я пишу простой рекурсивный синтаксический анализатор в Java, который использует лексический анализатор для разделения исходного кода из гипотетического императивного языка программирования (выглядит как псевдокод) из текстового файла на отдельные токены, которые затем проверяются, чтобы выяснить, они следуют правилам грамматики EBNF. Если правила не соблюдаются, программа выводит, что присутствует синтаксическая ошибка (а не то, чем она является или где она возникает).
Вот грамматика EBNF:
<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>
И здесь это пример программы в псевдоязыке без синтаксических ошибок:
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
Как видите, каждая программа должна соответствовать формату program begin <statement_list> end. Только последнее утверждение не требует точки с запятой в конце.
Сейчас у меня работает базовая c программа. В части лексического анализатора проблем нет, поскольку вывод токенов для целей отладки показывает, что все они проверяются, но что касается синтаксического анализа EBNF, он только распознает оператор как простую переменную (начните с малого). Я не могу go дальше, потому что я не знаю, как реализовать правила с фигурными скобками, такие как <statement_list> -> <statement> {;<statement>} (см. Выше).
Согласно странице Википедии в расширенной форме Бэкуса-Наура, фигурные скобки указывают, что повторение не является обязательным. Так, в случае этой грамматики, например, <statement_list> - это, по крайней мере, один <statement>, за которым может следовать любое число точек с запятой + <statement>. Поэтому, если присутствует несколько <statement> с, все, кроме последнего, имеют точку с запятой в конце.
Я просто не уверен, как реализовать это на основе моего кода. Я знаю, что вы должны проверить, является ли токен после оператора точкой с запятой, за которым следует другой оператор, но так как это рекурсивный приличный синтаксический анализатор, и у меня есть методы, возвращающие boolean, рекурсия здесь не будет работать, что оставляет итерацию. Однако, поскольку я реализовал лексический анализатор для удаления токена из буфера после его проверки, это делает проверку итерацией очень сложной. Есть ли лучший способ go сделать это?
Вот моя Java программа на данный момент:
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.");
}
}
Любая помощь будет любезно оценена.