001: package fri.patterns.interpreter.parsergenerator.parsertables;
002:
003: import java.util.*;
004: import fri.patterns.interpreter.parsergenerator.Token;
005: import fri.patterns.interpreter.parsergenerator.syntax.*;
006:
007: /**
008: Nullability of a nonterminal means that it can be "nothing", i.e.
009: there is a rule that contains the nonterminal on the left side and
010: no symbol on the right side (empty right side), expressing an optional
011: rule.
012: <p>
013: <b>Algorithm:</b><br>
014: Sort rules by size.
015: Search every rule that contain the nonterminal on left side.
016: Scan the left side of every rule until a terminal or a non-nullable
017: nonterminal appears. If found, rule is not nullable, else it is nullable.
018: If one of the rules that derive nonterminal is nullable, this nonterminal
019: is nullable.
020:
021: @author (c) 2000, Fritz Ritzberger
022: */
023:
024: class Nullable extends Hashtable {
025: /** The special empty symbol. */
026: public static final String NULL = "";
027:
028: /**
029: Explores the nullability of all nonterminals in syntax. Provides nullability
030: as Boolean within this Map, key is nonterminal.
031: @param syntax the grammar to scan for nonterminals and their nullability.
032: @param nonterminals pre-built list of nonterminals.
033: */
034: public Nullable(Syntax syntax, List nonterminals)
035: throws ParserBuildException {
036: // loop nonterminals
037: Map done = new Hashtable(nonterminals.size()); // avoid endless loops
038: for (int i = 0; i < nonterminals.size(); i++) {
039: String nt = (String) nonterminals.get(i);
040: checkNullability(syntax, nt, done);
041: }
042: }
043:
044: /** Returns true if passed nonterminal is nullable, else false. */
045: public boolean isNullable(String nonterminal) {
046: Boolean nullable = (Boolean) get(nonterminal);
047: return nullable.booleanValue();
048: }
049:
050: private boolean checkNullability(Syntax syntax, String nonterm,
051: Map done) throws ParserBuildException {
052: Boolean n = (Boolean) get(nonterm);
053: if (n != null)
054: return n.booleanValue();
055:
056: if (done.get(nonterm) != null)
057: return false; // endless recursion
058:
059: done.put(nonterm, nonterm); // avoid endless loops
060:
061: // loop rules for an empty rule deriving this nonterminal
062: for (int j = 0; j < syntax.size(); j++) {
063: Rule rule = syntax.getRule(j);
064: String nt = rule.getNonterminal(); // left side of derivation
065:
066: if (nt.equals(nonterm) && rule.rightSize() <= 0) // this rule derives the nonterminal and is empty
067: return putSymbol(nonterm, true);
068: }
069:
070: // loop rules for nullable nonterminal sequences
071: for (int j = 0; j < syntax.size(); j++) {
072: Rule rule = syntax.getRule(j);
073: String nt = rule.getNonterminal(); // left side of derivation
074:
075: if (nt.equals(nonterm)) { // this rule derives the nonterminal
076: boolean nullable = true; // assume it is nullable
077:
078: // then all symbols on right side must be nullable
079: for (int i = 0; nullable && i < rule.rightSize(); i++) {
080: String symbol = rule.getRightSymbol(i);
081:
082: if (Token.isTerminal(symbol)) { // a terminal ends symbol-loop
083: nullable = false;
084: } else if (symbol.equals(nonterm) == false) { // do not search self
085: try {
086: nullable = checkNullability(syntax, symbol,
087: done); // is nullable when this symbol is nullable
088: } catch (Exception ex) {
089: throw new ParserBuildException(
090: "Nullable ERROR: "
091: + ex.getMessage() + " <- "
092: + nonterm);
093: }
094: }
095: }
096:
097: if (nullable) // one nullable rule is enough for nonterminal to be nullable
098: return putSymbol(nonterm, true);
099: }
100: }
101: return putSymbol(nonterm, false);
102: }
103:
104: private boolean putSymbol(String symbol, boolean value) {
105: put(symbol, new Boolean(value));
106: return value;
107: }
108:
109: /**
110: Detect an empty terminal in input grammar: length == 0, '', "", ``.
111: @return true when symbol is empty.
112: */
113: public static boolean isNull(String symbol) {
114: return symbol.length() <= 0
115: || symbol.equals("" + Token.STRING_QUOTE
116: + Token.STRING_QUOTE)
117: || symbol.equals("" + Token.COMMAND_QUOTE
118: + Token.COMMAND_QUOTE)
119: || symbol.equals("" + Token.CHAR_QUOTE
120: + Token.CHAR_QUOTE);
121: }
122:
123: // test main
124:
125: public static void main(String[] args) {
126: List nt = new ArrayList();
127: nt.add("S");
128: nt.add("T");
129: nt.add("F");
130: nt.add("L");
131:
132: List sx = new ArrayList();
133:
134: List r = new ArrayList();
135: r.add("S");
136: r.add("T");
137: r.add("L");
138: r.add("F");
139: sx.add(r);
140:
141: r = new ArrayList();
142: r.add("S");
143: r.add("T");
144: r.add("F");
145: sx.add(r);
146:
147: r = new ArrayList();
148: r.add("T");
149: sx.add(r);
150:
151: r = new ArrayList();
152: r.add("F");
153: //r.add("S");
154: sx.add(r);
155:
156: try {
157: Nullable n = new Nullable(new Syntax(sx), nt);
158: String s = "S";
159: System.err
160: .println("nullable " + s + ": " + n.isNullable(s));
161: } catch (Exception e) {
162: e.printStackTrace();
163: }
164: }
165:
166: }
|