问如何编写上下文无关文法？
EN

Stack Overflow用户

提问于 2021-06-29 21:15:02

回答 2查看 53关注 0票数 0

我这里有两节课。

CFG类在其定义上下文无关语法的构造函数中接受一个字符串数组。SampleTest类用于测试CFG类，方法是将语法(C)输入到类中，然后由用户输入一个字符串，并查看该字符串是否可以由上下文无关文法生成。

我遇到的问题是堆栈溢出(很明显)。我假设我刚刚创建了一个永无止境的递归函数。

谁能看一下processData()函数，并帮我弄清楚如何正确地配置它。我基本上是使用递归来生成CFG可以创建的字符串的所有可能性，然后如果生成的可能性之一与用户的输入(inString)匹配，则返回true。哦，wkString参数就是语法在每次递归迭代中生成的字符串。

public class SampleTest {
  public static void main(String[] args) {
    // Language: strings that contain 0+ b's, followed by 2+ a's,
    // followed by 1 b, and ending with 2+ a's.
    String[] C = { "S=>bS", "S=>aaT", "T=>aT", "T=>bU", "U=>Ua", "U=>aa" };
    String inString, startWkString;
    boolean accept1;
    CFG CFG1 = new CFG(C);
    if (args.length >= 1) {
      // Input string is command line parameter
      inString = args[0];
      char[] startNonTerm = new char[1];
      startNonTerm[0] = CFG1.getStartNT();
      startWkString = new String(startNonTerm);
      accept1 = CFG1.processData(inString, startWkString);
      System.out.println(" Accept String? " + accept1);
    }
  } // end main
} // end class


public class CFG {

  private String[] code;
  private char startNT;

  CFG(String[] c) {
    this.code = c;
    setStartNT(c[0].charAt(0));
  }

  void setStartNT(char startNT) {
    this.startNT = startNT;
  }

  char getStartNT() {
    return this.startNT;
  }

  boolean processData(String inString, String wkString) {
    if (inString.equals(wkString)) {
      return true;
    } else if (wkString.length() > inString.length()) {
      return false;
    }

    // search for non-terminal in the working string
    boolean containsNT = false;
    for (int i = 0; i < wkString.length(); i++) {
      // if one of the characters in the working string is a non-terminal
      if (Character.isUpperCase(wkString.charAt(i))) {
        // mark containsNT as true, and exit the for loop
        containsNT = true;
        break;
      }
    }
    // if there isn't a non-terminal in the working string
    if (containsNT == false) {
      return false;
    }

    // for each production rule
    for (int i = 0; i < this.code.length; i++) {
      // for each character on the RHS of the production rule
      for (int j = 0; j <= this.code[i].length() - 3; j++) {
        if (Character.isUpperCase(this.code[i].charAt(j))) {
          // make substitution for non-terminal, creating a new working string
          String newWk = wkString.replaceFirst(Character.toString(this.code[i].charAt(0)), this.code[i].substring(3));
          if (processData(inString, newWk) == true) {
            return true;
          }
        }

      }
    } // end for loop
    return false;
  } // end processData
} // end class