1 package fri.patterns.interpreter.parsergenerator.parsertables; 2 3 import java.util.*; 4 import fri.patterns.interpreter.parsergenerator.Token; 5 import fri.patterns.interpreter.parsergenerator.syntax.*; 6 7 23 24 class Nullable extends Hashtable 25 { 26 27 public static final String NULL = ""; 28 29 35 public Nullable(Syntax syntax, List nonterminals) 36 throws ParserBuildException 37 { 38 Map done = new Hashtable(nonterminals.size()); for (int i = 0; i < nonterminals.size(); i++) { 41 String nt = (String ) nonterminals.get(i); 42 checkNullability(syntax, nt, done); 43 } 44 } 45 46 47 48 public boolean isNullable(String nonterminal) { 49 Boolean nullable = (Boolean ) get(nonterminal); 50 return nullable.booleanValue(); 51 } 52 53 54 private boolean checkNullability(Syntax syntax, String nonterm, Map done) 55 throws ParserBuildException 56 { 57 Boolean n = (Boolean ) get(nonterm); 58 if (n != null) 59 return n.booleanValue(); 60 61 if (done.get(nonterm) != null) 62 return false; 64 done.put(nonterm, nonterm); 66 for (int j = 0; j < syntax.size(); j++) { 68 Rule rule = syntax.getRule(j); 69 String nt = rule.getNonterminal(); 71 if (nt.equals(nonterm) && rule.rightSize() <= 0) return putSymbol(nonterm, true); 73 } 74 75 for (int j = 0; j < syntax.size(); j++) { 77 Rule rule = syntax.getRule(j); 78 String nt = rule.getNonterminal(); 80 if (nt.equals(nonterm)) { boolean nullable = true; 83 for (int i = 0; nullable && i < rule.rightSize(); i++) { 85 String symbol = rule.getRightSymbol(i); 86 87 if (Token.isTerminal(symbol)) { nullable = false; 89 } 90 else 91 if (symbol.equals(nonterm) == false) { try { 93 nullable = checkNullability(syntax, symbol, done); } 95 catch (Exception ex) { 96 throw new ParserBuildException("Nullable ERROR: "+ex.getMessage()+" <- "+nonterm); 97 } 98 } 99 } 100 101 if (nullable) return putSymbol(nonterm, true); 103 } 104 } 105 return putSymbol(nonterm, false); 106 } 107 108 private boolean putSymbol(String symbol, boolean value) { 109 put(symbol, new Boolean (value)); 110 return value; 111 } 112 113 114 118 public static boolean isNull(String symbol) { 119 return symbol.length() <= 0 || 120 symbol.equals(""+Token.STRING_QUOTE+Token.STRING_QUOTE) || 121 symbol.equals(""+Token.COMMAND_QUOTE+Token.COMMAND_QUOTE) || 122 symbol.equals(""+Token.CHAR_QUOTE+Token.CHAR_QUOTE); 123 } 124 125 126 127 128 130 public static void main(String [] args) { 131 List nt = new ArrayList(); 132 nt.add("S"); nt.add("T"); nt.add("F"); nt.add("L"); 133 134 List sx = new ArrayList(); 135 136 List r = new ArrayList(); 137 r.add("S"); r.add("T"); r.add("L"); r.add("F"); 138 sx.add(r); 139 140 r = new ArrayList(); 141 r.add("S"); r.add("T"); r.add("F"); 142 sx.add(r); 143 144 r = new ArrayList(); 145 r.add("T"); 146 sx.add(r); 147 148 r = new ArrayList(); 149 r.add("F"); 150 sx.add(r); 152 153 try { 154 Nullable n = new Nullable(new Syntax(sx), nt); 155 String s = "S"; 156 System.err.println("nullable "+s+": "+n.isNullable(s)); 157 } 158 catch (Exception e) { 159 e.printStackTrace(); 160 } 161 } 162 163 } | Popular Tags |