java - 通过伪代码解析大O分析的代码

Question

我目前正在尝试编写一个程序，该程序从 txt 文件中读取伪代码并将伪代码的 Big O 表示法输出为新的 txt 文件。我正在努力寻找一种方法来解析 for 循环以获取查找代码时间复杂度所需的关键信息。例如:

"input02.txt"
n m /* The estimate variable */
i j /* The control variable in the for loop */
tmp x j /* Variable(s) appeared in the loop body */
for (i=0; i<n*m; i*=2) {
   for (j=0; j<n; j++) {
      tmp = tmp + 3;
      x--;
      j++;
   }
}
"input02_BigO.txt"
O( n * log(n*m) )

为了尽量简化我的要求，这里是我被分配要做的项目的描述:

描述: 编写一个程序来分析嵌套的 Java“for”循环，并为输入文件中提供的代码提供 Big-O 符号估计。特别是，输入文件包含以适当的 Java 语法嵌套的“for”循环，并且限于 (1) 最多 2 个“for”循环和仅“for”循环(因此没有“while”或“do-while” "循环) (2) 简单操作+(加)、-(减)、*(乘)和/(除)。请注意，也允许使用简写操作“++”、“--”、“+=”、“-=”、“=”和“/=”。为了简单起见，您可以假设输入的代码是Java语言下的，没有语法错误，也不涉及任何方法/函数。

输入/输出: 输入文件“.txt”是一个文本文件，其中前三行描述了不同的变量集。第 1 行描述了应该在 BigO 估计结果中使用的估计变量。第 2 行描述了每个循环中的控制变量。第 3 行描述出现在循环/嵌套循环体中的变量。输出 将名为“.txt”的文件中给出的代码的 Big-O 估计写入文件“_BigO.txt”。如果您无法给出估计值，请在该文件中说明原因。

例子: 如上所示

我目前拥有的:

import java.util.*;
import java.io.*;
public class Big_O_Analysis {
    public static void main(String[] args) throws FileNotFoundException {
        /* ASKS USER TO INPUT NAME OF TXT FILE TO BE READ */
        Scanner keyboard = new Scanner(System.in);
        System.out.println("Enter file name (without '.txt': ");

        /* STORES FILE NAME TO READ INPUT FILE AND CREATE OUTPUT FILE*/
        String fileName = keyboard.nextLine();
        String inputFile = fileName + ".txt";
        String outputFile = fileName + "_BigO.txt";

        /* READS INPUT FILE AND ANALYZES FOR LOOPS AND ASSIGNMENT STATEMENTS */
        File file = new File(inputFile);
        Scanner input = new Scanner(file);
        String line = input.nextLine();
        String[] complexity = new String[10];                                   // Holds time complexity
        while (input.hasNext())                                                 // Search for line with for loop
        {
            while (!line.startsWith("for"))
            {
                line = input.nextLine();
            }

            // PARSE THROUGH LOOP
            String[] forLoop = line.split(";");                                 // Splits loop into 3 parts by the ';', ex: "for (i=0", "i<10","i++)"

            // Keeps control variable part of for loop
            String[] forLoopStart = forLoop[0].split("(");                      // Splits "for (i=0" into "for " and "i=0"
            String initialization = forLoopStart[1];                            // Stores the start of the for loop "i=0"
            char control = initialization.charAt(0);                            // Stores control variable 'i'
            int start = Integer.parseInt(initialization.substring(2));          // Stores start value of control '0'


            // Keeps estimate variables
            String termination = forLoop[1].substring(2);                       // Stores termination of loop. "i<10" -> "10" or "i<n" -> "n" or "i<n*m" -> "n*m"
            int end;                                                            // Initializes termination value for loop 
            int index = 0;
            for (int i = 0; i<termination.length(); i++)                        // Gets termination value when it is a number: "i<10"
            {
                index++;
            }
            end = Integer.parseInt(termination);


            // Keeps increment values
            String increment = forLoop[2].substring(0,forLoop[2].length()-1);   // Stores increment section of loop. "i++)" -> "i++" or "i+=10" or "i*=i"
            String inc = increment.substring(1,3);                              // Stores increment. "++", "*=", etc
            if (inc == "++" || inc == "--")
                complexity[1] = termination;
            else if(inc == "*=" || inc == "/=")                                 // Log
                complexity[1] = "log(" + termination + ")";
            else if (inc == "+=" || inc == "-=")                                // Jump
                complexity[1] = termination + "/" + increment.substring(3);


            String factor = "";                                                 // Stores factor of increment. "2", "10", "n"
            boolean factorDigits = false;                                       // The following boolean values test to see if the factor is just a number, variable by itself, or variable with number
            boolean factorVar = false;
            boolean factorMix = false;
            int fac;                                                            // If factor is just a number
            for (int i = 3; i<increment.length(); i++)
            {
                if (Character.isDigit(increment.charAt(i)))
                    factorDigits = true;
                else if (Character.isLetter(increment.charAt(i)))
                    factorVar = true;
            }
            if (factorDigits == true && factorVar == false)
            {
                factor = factor + increment.substring(3);
                fac = Integer.parseInt(factor);
            }
            else if (factorDigits == false && factorVar == true)
            {
                factor = factor + increment.substring(3);
            }
            else if (factorDigits == true && factorVar == true)
            {
                factorMix = true;
                factor = factor + increment.substring(3);
            }




            // Reads for assignment statements
            line = input.nextLine();
            int assignments = 0;
            while (input.hasNext() && !line.startsWith("for"))
            {
                assignments++;
                line = input.nextLine();
            }
            complexity[0]= Integer.toString(assignments);

            // Analyzes loop


        }

        /* FORMS COMPLEXITY */
        String timeComplexity = "";

        /* FORMS COMPLEXITY INTO BIG O NOTATION */
        String bigO = "O(" + timeComplexity + ")";

        /* CREATES AND WRITES A FILE OF THE BIG O ESTIMATE */
        PrintWriter output = new PrintWriter(outputFile);
        output.print(bigO);
    }
}

Answer 1

这将非常棘手，即使解析已解决 :)

如果您想正确地做到这一点，您可以使用 StreamTokenizer 进行标记化，并在顶部为整个语言构建一个递归下降解析器。

或者，您可以做一些额外的假设并逐行处理 block 。在这种情况下，您可以使用以下代码片段将循环初始值设定项、条件和增量提取到“部分”:

 if (line.startsWith("for") {
   int cut0 = line.indexOf('(');
   int cut1 = line.lastIndexOf(')');
   String parts = line.substring(cut0+1, cut1).split(";");
   ...

根据您想要的复杂程度，您可以在部件上使用现有的表达式解析器——或者只是验证它们是否符合您能够处理的情况的一些假设...