私は、2 つの部分 (I、II): (I) で構成されるチョムスキー標準形 (CNF) 動的計画法割り当てに取り組んでいます。ユーザーに文法を入力させ、それが有効な CNF 形式である場合は (チェック、受け入れ)、または無効な CNF 形式である場合は (チェック、拒否)、次に (II)。文字列の派生を表示する 2D 配列を生成するために、ユーザーに文字列を入力してもらいます。文字列が文法のメンバーであるかどうかに関係なく、テーブルを表示する必要があります。
以下は、これをコンテキストに入れるのに役立つサンプル出力です。今のところ、文字列に対するユーザー入力の要求と受信までは完了していますが、派生テーブルを出力する時点で、5 つの NPE がスローされます:(
****サンプル出力開始*
文脈自由文法を CNF に入力してください: <- /**パート (I) の開始。*/
S:AB、A:BB、B:BA、A:a、B:b
================ あなたの文法 ================
S -> AB
A -> BB
B -> BA
あ -> あ
B -> b
============================================ <- /* *パート(I)の終わり。*/
テーブルを生成する文字列を入力してください: </-/*パート (II) の開始。/
あばあああ
========== あなたのCNF生産表 =========
| | あ | さ | さ | さ | さ | さ |
| | | | ビ | ビ | ビ | ビ | ビ |
| | | | | | あ | | | | | | |
| | | | | | | | あ | | | | |
| | | | | | | | | | あ | | |
| | | | | | | | | | | | あ | </-/** パート (II) の終わり。*/
** * ****サンプル出力の終了* ***
コード全体の長さをご容赦ください。しかし、これを読んでコンパイルしようとした人がいる場合に備えて、3 つのクラスすべてを投稿する必要があると考えました。
GenerateRules.java の開始
import java.util.Arrays;
import java.util.Scanner;
public class GenerateRules
{
ProduceTable dyTab;
public final String NT1 = "A";
public final String NT2 = "B";
public final String NT3 = "C";
public final String terminal1 = "a";
public final String terminal2 = "b";
public final String terminal3 = "c";
//to store each rule and not overrwrite
//and infinitely loop per the initial
//problem on 7/31/2012's original submission
private String startingRule;
private String secondRule;
private String thirdRule;
private String fourthRule;
private String fifthRule;
private String grammarRules;
private String[] rulesArray;
private String[] alphaArray;
private String[][] rulesTable;
private String ruleSeparator = ",";
private String ruleDenoter = ">";
private String start = "S";
private String blank = " ";
private String epsilon = "e";
public GenerateRules()
{
readStartingCNFRule();
readSecondCNFRule();
readThirdCNFRule();
readFourthCNFRule();
readFifthCNFRule();
forgeGrammar();
//readGrammarInput();
}
protected void readStartingCNFRule()
{
Scanner in = new Scanner(System.in);
//null condition for UI's first(starting) CNF rule
String rules_input = null;
//if rules are valid CNF form or not, default case
//set to null
boolean is_validRules = false;
//condition to hold since input is volatile
while (!is_validRules)
{
try
{
//user prompt for entering starting CNF rule
System.out.println("enter starting CNF rule in " +
" regex format: S>AB, or S> e,");
rules_input = in.nextLine();
//so compiler knows to split each rule by ',' indicator
String[] rules = rules_input.split(",");
//iterate through the length of the rule
for (int i = 0; i < rules.length; i++)
{
String parts[] = rules[i].split(">");
//provided format for delineating LHS from RHS
String format = String.format("Rule: '%s', Yield: " +
"'%s'", parts[0], parts[1]);
System.out.println(format);
//conditions for ACCEPTING the starting rule
if(rules_input.startsWith(start)&&rules_input.substring(1).equals(ruleDenoter)
&&rules_input.substring(2).contains(NT1)||rules_input.substring(2).contains(NT2)
||rules_input.substring(2).contains(blank)&&rules_input.substring(3).contains(NT1)
||rules_input.substring(3).contains(NT2)||rules_input.substring(3).contains(epsilon)
&&rules_input.substring(4).contains(ruleSeparator))
{
System.out.println("success! S>AA, S>AB, S>BA, S>BB, or S> e, are" +
" ALL acceptable regexes for starting rule");
//stores the input of starting rule for upcoming use
startingRule = new String(rules_input);
is_validRules = true;
}
//conditions for REJECTING the starting rule
else if(!rules_input.startsWith(start)&&!rules_input.substring(1).equals(ruleDenoter)
&&!rules_input.substring(2).contains(NT1)||!rules_input.substring(2).contains(NT2)
&&!rules_input.substring(3).contains(NT1)||!rules_input.substring(3).contains(NT2)
||!rules_input.substring(3).contains(blank)&&rules_input.substring(4).contains(ruleSeparator))
{
System.out.println("starting rule MUST match regex" +
"of form S>AA, S>AB, S>BA, S>BB, or S> e, . Please re-enter.");
is_validRules = false;
rules_input = in.nextLine();
}
}//end of for-loop
}//end of try-loop
catch (Exception ex)
{
System.out.println(ex.getMessage());
}
}//end of while-loop
}//end of readStartingCNFRule method
protected void readSecondCNFRule()
{
Scanner in = new Scanner(System.in);
String rules_input = null;
//if rules are valid CNF form or not, default case
//set to null
boolean is_validRules = false;
//condition to hold since input is volatile
while (!is_validRules)
{
try
{
//user prompt for entering 2nd CNF rule
System.out.println("enter 2nd CNF rule in regex " +
"A>AA, or B>BB,");
rules_input = in.nextLine();
//so compiler knows to split each rule by ',' indicator
String[] rules = rules_input.split(",");
//iterate through the length of the rule
for (int i = 0; i < rules.length; i++)
{
String parts[] = rules[i].split(">");
//provided format for delineating LHS from RHS
String format = String.format("Rule: '%s', Yield: " +
"'%s'", parts[0], parts[1]);
System.out.println(format);
//conditions for ACCEPTING the second rule
if(rules_input.startsWith(NT1)||rules_input.startsWith(NT2)&&rules_input.substring(1).equals(ruleDenoter)
&&rules_input.substring(2).contains(NT1)||rules_input.substring(2).contains(NT2)
&&rules_input.substring(3).contains(NT1)||rules_input.substring(3).contains(NT2)
&&rules_input.substring(4).contains(ruleSeparator))
{
System.out.println("success! A>AA, A>AB, B>BB, or B>BA are " +
"ALL acceptable regex for 2nd rule ");
//stores the input of 2nd CNF rule for upcoming use
secondRule = new String(rules_input);
is_validRules = true;
}
//conditions for REJECTING the 2nd CNF production
else if(!rules_input.startsWith(NT1)||!rules_input.startsWith(NT2)&&!rules_input.substring(1).equals(ruleDenoter)
&&!rules_input.substring(2).contains(NT1)||!rules_input.substring(2).contains(NT2)
&&!rules_input.substring(3).contains(NT1)||!rules_input.substring(3).contains(NT2)
&&!rules_input.substring(4).contains(ruleSeparator))
{
System.out.println("2nd CNF rule MUST match regex" +
"of either A>AA, A>AB, B>BB, or B>BA. Please re-enter.");
is_validRules = false;
rules_input = in.nextLine();
}
}//end of for-loop
}//end of try-loop
catch (Exception ex)
{
System.out.println(ex.getMessage());
}
}//end of while-loop
}//end of readSecondCNFRule method
protected void readThirdCNFRule()
{
Scanner in = new Scanner(System.in);
String rules_input = null;
//if rules are valid CNF form or not, default case
//set to null
boolean is_validRules = false;
//condition to hold since input is volatile
while (!is_validRules)
{
try
{
//user prompt for entering 3rd CNF rule
System.out.println("enter 3rd CNF rule in regex " +
"A>AA, or B>BB,");
rules_input = in.nextLine();
//so compiler knows to split each rule by ',' indicator
String[] rules = rules_input.split(",");
//iterate through the length of the rule
for (int i = 0; i < rules.length; i++)
{
String parts[] = rules[i].split(">");
//provided format for delineating LHS from RHS
String format = String.format("Rule: '%s', Yield: " +
"'%s'", parts[0], parts[1]);
System.out.println(format);
//conditions for ACCEPTING the 3rd rule
if(rules_input.startsWith(NT1)||rules_input.startsWith(NT2)&&rules_input.substring(1).equals(ruleDenoter)
&&rules_input.substring(2).contains(NT1)||rules_input.substring(2).contains(NT2)
&&rules_input.substring(3).contains(NT1)||rules_input.substring(3).contains(NT2)
&&rules_input.substring(4).contains(ruleSeparator))
{
System.out.println("success! A>AA, A>AB, B>BB, or B>BA are " +
"ALL acceptable regexes for 3rd rule ");
//stores the input of 3rd CNF rule for upcoming use
thirdRule = new String(rules_input);
is_validRules = true;
}
//conditions for REJECTING the 3rd CNF production
else if(!rules_input.startsWith(NT1)||!rules_input.startsWith(NT2)&&!rules_input.substring(1).equals(ruleDenoter)
&&!rules_input.substring(2).contains(NT1)||!rules_input.substring(2).contains(NT2)
&&!rules_input.substring(3).contains(NT1)||!rules_input.substring(3).contains(NT2)
&&!rules_input.substring(4).contains(ruleSeparator))
{
System.out.println("3rd CNF rule MUST match regex" +
"of either A>AA, A>AB, B>BB, or B>BA. Please re-enter.");
is_validRules = false;
rules_input = in.nextLine();
}
}//end of for-loop
}//end of try-loop
catch (Exception ex)
{
System.out.println(ex.getMessage());
}
}//end of while-loop
}//end of readThirdCNFRule method
protected void readFourthCNFRule()
{
Scanner in = new Scanner(System.in);
String rules_input = null;
//if rules are valid CNF form or not, default case
//set to null
boolean is_validRules = false;
//condition to hold since input is volatile
while (!is_validRules)
{
try
{
//user prompt for entering 4th CNF rule
System.out.println("enter 4th CNF rule in regex " +
"A>a, or B>b,");
rules_input = in.nextLine();
//so compiler knows to split each rule by ',' indicator
String[] rules = rules_input.split(",");
//iterate through the length of the rule
for (int i = 0; i < rules.length; i++)
{
String parts[] = rules[i].split(">");
//provided format for delineating LHS from RHS
String format = String.format("Rule: '%s', Yield: " +
"'%s'", parts[0], parts[1]);
System.out.println(format);
//conditions for ACCEPTING the 4th rule
if(rules_input.startsWith(NT1)||rules_input.startsWith(NT2)&&rules_input.substring(1).equals(ruleDenoter)
&&rules_input.substring(2).contains(terminal1)||rules_input.substring(2).contains(terminal2)
&&rules_input.substring(3).contains(ruleSeparator))
{
System.out.println("success! A>a, or B>b are " +
"ALL acceptable regexes for 4th rule ");
//stores the input of 4th CNF rule for upcoming use
fourthRule = new String(rules_input);
is_validRules = true;
}
//conditions for REJECTING the 4th CNF rule
else if(!rules_input.startsWith(NT1)||!rules_input.startsWith(NT2)&&!rules_input.substring(1).equals(ruleDenoter)
&&!rules_input.substring(2).contains(terminal1)||!rules_input.substring(2).contains(terminal2)
&&!rules_input.substring(3).contains(ruleSeparator))
{
System.out.println("4th CNF rule MUST match regex" +
"of either A>a, or B>b, . Please re-enter.");
is_validRules = false;
rules_input = in.nextLine();
}
}//end of for-loop
}//end of try-loop
catch (Exception ex)
{
System.out.println(ex.getMessage());
}
}//end of while-loop
}//end of readFourthCNFRule method
protected void readFifthCNFRule()
{
Scanner in = new Scanner(System.in);
String rules_input = null;
//if rules are valid CNF form or not, default case
//set to null
boolean is_validRules = false;
//condition to hold since input is volatile
while (!is_validRules)
{
try
{
//user prompt for entering 5th CNF rule
System.out.println("enter 5th CNF rule in regex " +
"A>a, or B>b,");
rules_input = in.nextLine();
//so compiler knows to split each rule by ',' indicator
String[] rules = rules_input.split(",");
//iterate through the length of the rule
for (int i = 0; i < rules.length; i++)
{
String parts[] = rules[i].split(">");
//provided format for delineating LHS from RHS
String format = String.format("Rule: '%s', Yield: " +
"'%s'", parts[0], parts[1]);
System.out.println(format);
//conditions for ACCEPTING the 5th rule
if(rules_input.startsWith(NT1)||rules_input.startsWith(NT2)&&rules_input.substring(1).equals(ruleDenoter)
&&rules_input.substring(2).contains(terminal1)||rules_input.substring(2).contains(terminal2)
&&rules_input.substring(3).contains(ruleSeparator))
{
System.out.println("success! A>a, or B>b are " +
"ALL acceptable regexes for 5th rule ");
//stores the input of 5th CNF rule for upcoming use
fifthRule = new String(rules_input);
is_validRules = true;
}
//conditions for REJECTING the 5th CNF rule
else if(!rules_input.startsWith(NT1)||!rules_input.startsWith(NT2)&&!rules_input.substring(1).equals(ruleDenoter)
&&!rules_input.substring(2).contains(terminal1)||!rules_input.substring(2).contains(terminal2)
&&!rules_input.substring(3).contains(ruleSeparator))
{
System.out.println("5th CNF rule MUST match regex" +
"of either A>a, or B>b, . Please re-enter.");
is_validRules = false;
rules_input = in.nextLine();
}
}//end of for-loop
}//end of try-loop
catch (Exception ex)
{
System.out.println(ex.getMessage());
}
}//end of while-loop
}//end of readFifthCNFRule method
/**
* my protected void forgeGrammar() method
* description: aggregates all CNF rules into one
* string and removes the commas before converting
* the rules(grammar) into a 2D array. then, takes
* ui from user (alphaString) so can pass by reference
* to ProduceTable.java
* @param - no-arg
* @return - n/a
*/
protected void forgeGrammar()
{
//this verifies that all 5 rules displayed in the console are valid
grammarRules = new String(startingRule + secondRule + thirdRule + fourthRule + fifthRule);
rulesArray = new String[grammarRules.length()];
//remove the commas from the grammar
rulesArray = grammarRules.split("[,]");
//convert the grammar to a 2D String array
rulesTable = new String[rulesArray.length][5];
for (int i = 0; i < rulesTable.length; i++)
{
String[] rulesMatrix = rulesArray[i].split(blank);
for(int j = 0; j < rulesMatrix.length; j++)
{
rulesTable[i][j] = rulesMatrix[j];
}
}
for(int i = 0; i < rulesTable.length; i++)
{
/**intermittent print out, compilation checkpoint*/
System.out.println(Arrays.toString(rulesTable[i]));
}
//new Scanner instance to receive the alpha string
Scanner in = new Scanner(System.in);
String alpha_input = null;
//the printout prompt for user to enter the grammar
//string
System.out.println("enter a string please using only " +
"terminals a or b with no whitespaces");
alpha_input = in.nextLine();
//initialize alphaArray
alphaArray = new String[alpha_input.length()];
//check for valid string entry
for(int i = 0; i < alpha_input.length(); i++)
{
String temp = Character.toString(alpha_input.charAt(i));
if(alphaStringTest(temp))
{
alphaArray[i] = temp;
}
else
{
System.out.println("alpha string must contain only" +
"a or b . please re-enter.");
alpha_input = in.nextLine();
}
}
dyTab = new ProduceTable(rulesTable, alphaArray);
}//end of forgeGrammar method
/**
* my public Boolean alphaStringTest method
* @param String ui - the input string to test
* (pass by 'reference')
* @return - (Boolean) whether user input
*/
public Boolean alphaStringTest(String ui)
{
String a = "a";
String b = "b";
if(ui.equals(a)||ui.equals(b))
{
return true;
}
return false;
}//end of alphaStringTest method
//end of GenerateRules.java
}
GenerateRules.java の終わり
次は ProduceTable クラスです。
ProduceTable.java の開始
public class ProduceTable
{
private String[][] dynamicTable;
private String[][] rulesTable;
private String[] alphaArray;
/**
* my ProduceTable class constructor
* @param rt - pass by reference from GR.java (line 573)
* @param alph - pass by reference from GR.java (line 573)
*/
public ProduceTable(String[][] rt, String[] alph)
{
//'re'-initializing the rulesTable and the
//ui alpha string
rulesTable = new String[rt.length][rt[0].length];
for(int i = 0; i <rt.length; i++)
{
for(int j = 0; j <rt[0].length; j++)
{
rulesTable[i][j] = rt[i][j];
}
}
try
{
alphaArray = new String[alph.length];
System.arraycopy(alph, 0, alphaArray, 0, alph.length);
}
catch(Exception ex)
{
System.out.println("null input string" + ex);
}
run716();
}//end of class constructor
/**
* my public void run716 method
* description: algo which implements the proof idea of a context-free grammar
* in CNF (G) generating the context-free lang. L . in other words,
* this algo generates a table for L(G) and lets the user know if their alphaString
* is/is not a member of L(G).
* @param - no -arg
* @return - n/a
*
*/
public void run716()
{
//the dynamic table created as a new string[][] with the
//length of the String[] alphaArray, as previously received,
//as its defaulted input
dynamicTable = new String[alphaArray.length][alphaArray.length];
//call to external method to prevent the word 'null' from printing
//out in dynamicTable and instead insert blank spaces.
trim();
//2,3.iterate through each variable A (we are examining
//each substring of length 1
for(int i =0; i < alphaArray.length; i++)
{
//4.test if A-->b is
//a valid rule at b = wi (where wi.length = 1)
for(int a=0;a<rulesTable[0].length;a++)
{
// boolean condition for wi = 1
if(alphaArray[i].equals(rulesTable[1][a]))
{
//5. if A-->b is a rule, place A in the table
dynamicTable[i][i] = rulesTable [0][a];
}
}
}
//6. for l = 2 to n where l = length of substring
//this is for iterating upon substrings of min. len. 2
for(int l=1; l<alphaArray.length;l++)
{
//7. i = starting position of substring, i.e. for i = 1
//to n - l + 1
for(int i=0; i<rulesTable.length-l; i++)
{
//8. let j = i + l - 1, (technically, the -1 is covered
//in (7, above), where i is iterated until < rulesTable.length - 1,
//i.e., wherein j = end position of substring. Hence, j = i + l.
int j = i+l;
//9. for k = i to j - 1, k < j , where k is the
//'split' position 'declaration' BEFORE the
//A-->BC rule form cases are examined
for(int k=i; k<j ;k++)
{
//where substring_marker is used as the
//split marker for each rule A-->BC
for(int substring_marker=0; substring_marker<rulesTable[0].length; substring_marker++)
{
//conditions for where the substring length
//is greater than or equal to 2, pivoting from
//the second row onward
if(rulesTable[1][substring_marker].length() >= 2)
{
//allows a printout for a blank above the diagonal;
//i.e., a blank occurs in the table iff the 2 terminals
//below it cannot be produced in any one step by any
//available rule in the grammar
if(!dynamicTable[i][k].equals(" ") && !dynamicTable
[k+1][j].equals(" "))
{
//10 for each rule A--> BC, if table(i,k)
//contains B and table(k+1,j) contains
//C, put A in table(i,j),
if(dynamicTable[i][k].equals(rulesTable[1][substring_marker].substring(0,1))
&&dynamicTable[k+1][j].equals(rulesTable[1][substring_marker].substring(1,2)))
{
//11.if table(i,k) contains B and table(k+1,j)
//contains C, put A in table(i,j)
dynamicTable[i][j]= rulesTable[0][substring_marker];
}
}
}
}
}
}
}
print7162D();
grammarMember();
}//end of run716 method
/**
* my public static void printAlgo2d()
* description: provides some printout formatting
* for the table to make it more grid-like and
* readable
* @param - no-arg
* @return - none
*/
public void print7162D()
{
//row iterator for alphaString
for(int k=0;k<dynamicTable.length;k++)
{
//col iterator for alphaString
for(int j=0; j<dynamicTable[0].length; j++)
{
//prints out vertical line to create a 'grid'-like
//structure for the table, help with readability,
//and delineate between variables
System.out.print(dynamicTable[k][j] + "|");
}
//prints out a space between each row
System.out.println();
//prints horizontal line-dash to help with
//readability and aesthetic structure between rows
System.out.println("-----");
}
}//end of print7162D
/**
* my public void trim() method
* description: compensates for variation in ui
* alphaString input length, supplanting the word
* 'null' with blank whitespace
* @param - no-arg
* @return - n/a
*/
public void trim()
{
for(int k=0;k<dynamicTable.length;k++)
{
for(int j=0; j<dynamicTable[0].length; j++)
{
dynamicTable[k][j]= " ";
}
}
}
/**
* my public void grammarMember method
* description: provides the printout for the table
* @param - no-arg
* @return - n/a
*/
public void grammarMember()
{
if (dynamicTable[0][alphaArray.length - 1].indexOf("S") == -1)
{
System.out.println("alphaString is not a member of L(G)");
}
else
{
System.out.println("alphaString is a member of L(G)");
}
}//end of grammarMember method
//end of ProduceTable.java
}
ProduceTable.java の終わり
そして最後に、すべてをまとめる簡単な TestHarness クラス
TestHarness.java
public class TestHarness
{
public static void main(String args[])
{
String[][] p = null;
GenerateRules grrr = new GenerateRules ();
grrr.readStartingCNFRule();
grrr.readSecondCNFRule();
grrr.readThirdCNFRule();
grrr.readFourthCNFRule();
grrr.readFifthCNFRule();
grrr.forgeGrammar();
ProduceTable pt = new ProduceTable(p, args);
pt.run716();
pt.print7162D();
pt.grammarMember();
pt.trim();
}
}
たまたまこれをコンパイルしてくださった場合は、私のプログラムに文法を入力する方法の簡単なデモを次に示します。
enter starting CNF rule in regex format: S>AB, or S> e,
S>AB,
Rule: 'S', Yield: 'AB'
yes! S>AA, S>AB, S>BA, S>BB, or S> e, are valid 1st regexes
enter 2nd CNF rule in regex A>AA, or B>BB,
A>AA,
Rule: 'A', Yield: 'AA'
success! A>AA, A>AB, B>BB, or B>BA are ALL valid 2nd regexes
enter 3rd CNF rule in regex A>AA, or B>BB,
B>BB,
Rule: 'B', Yield: 'BB'
yes! A>AA, A>AB, B>BB, or B>BA are ALL valid 3rd regexes
enter 4th CNF rule in regex A>a, or B>b,
A>a,
Rule: 'A', Yield: 'a'
success! A>a, or B>b are ALL valid regexes for 4th rule
enter 5th CNF rule in regex A>a, or B>b,
B>b,
Rule: 'B', Yield: 'b'
success! A>a, or B>b are ALL acceptable regexes for 5th rule
==========Your Grammar:======
Rule: 'S', Yield: 'AB'
Rule: 'A', Yield: 'AA'
Rule: 'B', Yield: 'BB'
Rule: 'A', Yield: 'a'
Rule: 'B', Yield: 'b'
誰かアドバイスがあれば、大歓迎です。ありがとうございました。5 つの NPE は、リターンを押して文法文字列を入力した直後に生成されます。