KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > fri > patterns > interpreter > parsergenerator > parsertables > Nullable


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 /**
8     Nullability of a nonterminal means that it can be "nothing", i.e.
9     there is a rule that contains the nonterminal on the left side and
10     no symbol on the right side (empty right side), expressing an optional
11     rule.
12     <p>
13     <b>Algorithm:</b><br>
14     Sort rules by size.
15     Search every rule that contain the nonterminal on left side.
16     Scan the left side of every rule until a terminal or a non-nullable
17     nonterminal appears. If found, rule is not nullable, else it is nullable.
18     If one of the rules that derive nonterminal is nullable, this nonterminal
19     is nullable.
20
21     @author (c) 2000, Fritz Ritzberger
22 */

23
24 class Nullable extends Hashtable
25 {
26     /** The special empty symbol. */
27     public static final String JavaDoc NULL = "";
28     
29     /**
30         Explores the nullability of all nonterminals in syntax. Provides nullability
31         as Boolean within this Map, key is nonterminal.
32         @param syntax the grammar to scan for nonterminals and their nullability.
33         @param nonterminals pre-built list of nonterminals.
34     */

35     public Nullable(Syntax syntax, List nonterminals)
36         throws ParserBuildException
37     {
38         // loop nonterminals
39
Map done = new Hashtable(nonterminals.size()); // avoid endless loops
40
for (int i = 0; i < nonterminals.size(); i++) {
41             String JavaDoc nt = (String JavaDoc) nonterminals.get(i);
42             checkNullability(syntax, nt, done);
43         }
44     }
45
46
47     /** Returns true if passed nonterminal is nullable, else false. */
48     public boolean isNullable(String JavaDoc nonterminal) {
49         Boolean JavaDoc nullable = (Boolean JavaDoc) get(nonterminal);
50         return nullable.booleanValue();
51     }
52
53
54     private boolean checkNullability(Syntax syntax, String JavaDoc nonterm, Map done)
55         throws ParserBuildException
56     {
57         Boolean JavaDoc n = (Boolean JavaDoc) get(nonterm);
58         if (n != null)
59             return n.booleanValue();
60
61         if (done.get(nonterm) != null)
62             return false; // endless recursion
63

64         done.put(nonterm, nonterm); // avoid endless loops
65

66         // loop rules for an empty rule deriving this nonterminal
67
for (int j = 0; j < syntax.size(); j++) {
68             Rule rule = syntax.getRule(j);
69             String JavaDoc nt = rule.getNonterminal(); // left side of derivation
70

71             if (nt.equals(nonterm) && rule.rightSize() <= 0) // this rule derives the nonterminal and is empty
72
return putSymbol(nonterm, true);
73         }
74
75         // loop rules for nullable nonterminal sequences
76
for (int j = 0; j < syntax.size(); j++) {
77             Rule rule = syntax.getRule(j);
78             String JavaDoc nt = rule.getNonterminal(); // left side of derivation
79

80             if (nt.equals(nonterm)) { // this rule derives the nonterminal
81
boolean nullable = true; // assume it is nullable
82

83                 // then all symbols on right side must be nullable
84
for (int i = 0; nullable && i < rule.rightSize(); i++) {
85                     String JavaDoc symbol = rule.getRightSymbol(i);
86
87                     if (Token.isTerminal(symbol)) { // a terminal ends symbol-loop
88
nullable = false;
89                     }
90                     else
91                     if (symbol.equals(nonterm) == false) { // do not search self
92
try {
93                             nullable = checkNullability(syntax, symbol, done); // is nullable when this symbol is nullable
94
}
95                         catch (Exception JavaDoc ex) {
96                             throw new ParserBuildException("Nullable ERROR: "+ex.getMessage()+" <- "+nonterm);
97                         }
98                     }
99                 }
100
101                 if (nullable) // one nullable rule is enough for nonterminal to be nullable
102
return putSymbol(nonterm, true);
103             }
104         }
105         return putSymbol(nonterm, false);
106     }
107
108     private boolean putSymbol(String JavaDoc symbol, boolean value) {
109         put(symbol, new Boolean JavaDoc(value));
110         return value;
111     }
112
113
114     /**
115         Detect an empty terminal in input grammar: length == 0, '', "", ``.
116         @return true when symbol is empty.
117     */

118     public static boolean isNull(String JavaDoc 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     // test main
129

130     public static void main(String JavaDoc [] 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         //r.add("S");
151
sx.add(r);
152
153         try {
154             Nullable n = new Nullable(new Syntax(sx), nt);
155             String JavaDoc s = "S";
156             System.err.println("nullable "+s+": "+n.isNullable(s));
157         }
158         catch (Exception JavaDoc e) {
159             e.printStackTrace();
160         }
161     }
162
163 }
Popular Tags