java - 如何将 EBNF 重复实现为 Java 代码？

问题描述

我正在用 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格式。只有最后一条语句的末尾不需要分号。

现在，我有一个基本程序正在运行。词法分析器部分没有问题，因为用于调试目的的标记输出表明它们都已被检查，但至于 EBNF 解析，我只有将语句识别为简单变量（从小处开始）。我无法再进一步，因为我不知道如何实施涉及花括号的规则，例如<statement_list> -> <statement> {;<statement>}（见上文）。

根据扩展巴科斯-瑙尔形式的维基百科页面，花括号表示重复是可选的。因此，在这种语法的情况下，<statement_list>例如，a 至少是一个<statement>可选的后跟任意数量的分号 + <statement>。因此，如果<statement>存在多个 s，则除最后一个之外的所有 s 都在末尾有一个分号。

我只是不确定如何根据我的代码实现它。我知道您必须检查语句后的标记是否是分号后跟另一个语句，但是由于这是一个递归的体面解析器，并且我有返回 a 的方法boolean，因此递归在这里不起作用，这会导致迭代。然而，由于我实现了词法分析器以在检查后从缓冲区中删除标记，这使得通过迭代进行检查非常困难。有没有更好的方法来做到这一点？

到目前为止，这是我的 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.");

    }

}

任何帮助将不胜感激。

标签： javaparsingbnfebnf

解决方案

花括号的作用是接受它们所包含的序列的 0 个或多个项目。这通常被实现为循环，即，当当前令牌是可以启动当前序列的令牌时，处理该序列。（注意，前面的伪代码）中的一些东西：

    while(FIRSTS contain lookAhead()){
      processCurrentBlock()
    }

这是什么' FIRSTS'？它是预先计算的一组标记，可以开始您当前正在分析的序列。例如，FIRSTS(;<statement>)是“;”。

lookAhead是您的词法分析器/扫描器中的一个函数，它返回当前令牌（不使用它）。

一般而言，序列的 FIRSTS 集不得包含该序列的 FOLLOW 集中存在的任何标记。FOLLOW 是可能出现在该序列之后的标记集。

幸运的是，语法中三个重复块的 FIRSTS 集与它们的 FOLLOW 集不同。即，序列的 FIRSTS 是，序列的 FIRSTS是;<statement>，[';']序列的FIRSTS是。(+|-) <term>['+', '-'](* | /) <factor>['*', '/']

这只是为每个块实现该算法的问题。

java - 如何将 EBNF 重复实现为 Java 代码？

问题描述

解决方案

推荐阅读