KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > fri > patterns > interpreter > parsergenerator > syntax > builder > ArtificialRule


1 package fri.patterns.interpreter.parsergenerator.syntax.builder;
2
3 import java.util.*;
4 import fri.patterns.interpreter.parsergenerator.Token;
5 import fri.patterns.interpreter.parsergenerator.util.SymbolToName;
6
7 /**
8     ArtificialRule is needed to
9     <ul>
10         <li>create nonterminals and rules for symbols within parenthesis: "(a b c)" -> "_a_b_c_"</li>
11         <li>create nonterminals and rules for symbols that were quantified with "*", "+", "?"</li>
12     </ul>
13     The nonterminal names get created from symbols that are converted to names.
14     Every created nonterminal starts with "_" (Token.ARTIFICIAL_RULE_START_CHARACTER).
15     <p>
16     Example:
17     <pre>
18         sentence1 ::= word* ;
19         sentence2 ::= word+ ;
20         sentence3 ::= word? ;
21     </pre>
22     will be converted to following rules
23     <pre>
24         _sentence1_OPTLIST ::= _sentence1_LIST;
25         _sentence1_OPTLIST ::= ;
26         _sentence1_LIST ::= _sentence1_LIST word;
27         _sentence1_LIST ::= word;
28         
29         _sentence2_LIST ::= _sentence2_LIST word;
30         _sentence2_LIST ::= word;
31
32         _sentence3_OPT ::= word;
33         _sentence3_OPT ::= ;
34     </pre>
35      
36     @author (c) 2002 Fritz Ritzberger
37 */
38
39 class ArtificialRule
40 {
41     private List rules;
42     private String JavaDoc nonterminal;
43     
44     /**
45         Creates an artificial rule from an expression within parenthesis.
46         Argument sentencesInParenthesis holds a List of arbitrary deep Lists
47         that contain String or ArtificialRule at end.
48         The method getRules() will return as much rules as are contained on any
49         level in sentencesInParenthesis.
50     */
51     public ArtificialRule(List sentencesInParenthesis, String JavaDoc catSym) { // make "(b c)" to rule "_b_c_ ::= b c"
52 StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
53         parenthesisContentsToString(sentencesInParenthesis, sb, catSym);
54         nonterminal = ensureUnderscore(sb.toString());
55         rules = createRule(nonterminal, sentencesInParenthesis);
56     }
57     
58     private void parenthesisContentsToString(List sentences, StringBuffer JavaDoc sb, String JavaDoc catSym) {
59         for (int i = 0; i < sentences.size(); i++) {
60             Object JavaDoc o = sentences.get(i);
61             
62             if (o instanceof List) {
63                 parenthesisContentsToString((List)o, sb, ""); // catenize symbol only on first level
64 }
65             else {
66                 if (o instanceof String JavaDoc)
67                     o = SymbolToName.makeIdentifier((String JavaDoc)o, ""); // no "_" for quotes
68 sb.append(o.toString()); // ArtificialRule goes here
69 }
70
71             if (i < sentences.size() - 1)
72                 sb.append((catSym.length() > 0 ? "_" + catSym : "") + "_");
73         }
74     }
75
76     
77     /**
78         Creates an artificial rule from with a quantifier like "*", "+", "?".
79         From this some rules are resulting that getRules() will return.
80         "token" is either String or ArtificialRule.
81     */
82     public ArtificialRule(Object JavaDoc token, String JavaDoc quantifier) { // make "a*", "a+", "a?" to rules
83 nonterminal = token.toString();
84         
85         String JavaDoc listNonterm = null; // needed for * and +
86
87         if (quantifier.equals("+") || quantifier.equals("*")) {
88             List sentences = new ArrayList();
89
90             listNonterm = ensureUnderscore(nonterminal)+"_LIST";
91             
92             // for now leave out the left side nonterminal of list
93 List sentence = new ArrayList(); // mandatory tokenlist expands to
94 sentence.add(listNonterm); // the list and
95 sentence.add(token.toString()); // the token
96 sentences.add(sentence);
97
98             sentence = new ArrayList();
99             sentence.add(token.toString()); // or the token alone
100 sentences.add(sentence);
101             
102             rules = createRule(listNonterm, sentences); // adds the left side nonterminal of list
103
104             if (quantifier.equals("+"))
105                 nonterminal = listNonterm; // "_a_LIST" is the substitute for "a+"
106 }
107
108         if (quantifier.equals("*") || quantifier.equals("?")) {
109             List sentences = new ArrayList();
110
111             nonterminal = ensureUnderscore(nonterminal)+(quantifier.equals("*") ? "_OPTLIST" : "_OPT");
112
113             String JavaDoc nonterm = quantifier.equals("*") ? listNonterm : token.toString();
114             
115             List sentence = new ArrayList(); // optional tokenlist expands to
116 sentence.add(nonterm); // the mandatory list when *, the token when ?
117 sentences.add(sentence);
118
119             sentences.add(new ArrayList()); // or nothing
120
121             List mandatoryList = quantifier.equals("*") ? rules : null;
122
123             rules = createRule(nonterminal, sentences);
124
125             if (mandatoryList != null)
126                 rules.addAll(mandatoryList);
127         }
128     
129         if (token instanceof ArtificialRule) // could be '(' token ')'
130 rules.addAll(((ArtificialRule)token).getRules());
131     }
132     
133
134     private String JavaDoc ensureUnderscore(String JavaDoc nonterminal) {
135         if (nonterminal.startsWith(Token.ARTIFICIAL_NONTERMINAL_START_CHARACTER) == false)
136             nonterminal = Token.ARTIFICIAL_NONTERMINAL_START_CHARACTER + nonterminal;
137         return nonterminal;
138     }
139     
140     private List createRule(String JavaDoc nonterminal, List sentences) {
141         for (int i = 0; i < sentences.size(); i++) {
142             List deep = (List) sentences.get(i);
143             List flat = flattenLists(deep, new ArrayList());
144             flat.add(0, nonterminal);
145             sentences.set(i, flat);
146         }
147         return sentences;
148     }
149
150
151     /**
152         The passed "deep" container contains Lists of arbitrary depth, that means every List
153         element can be a List. This method resolves them to a sequential List of Lists.
154         @param container List that contains Lists that contain Lists ...
155         @param result List containing only Lists, retrieved from the "tree" container.
156         @return the result flattened List (identical with passed "flat" List).
157     */
158     public static List flattenLists(List deep, List flat) {
159         for (int i = 0; i < deep.size(); i++) {
160             Object JavaDoc o = deep.get(i);
161             
162             if (o instanceof List)
163                 flattenLists((List)o, flat);
164             else
165                 flat.add(o);
166         }
167         return flat;
168     }
169
170     
171             
172     /**
173         Returns the artificial name of this rule.
174         This is used to represent this rule within other rules.
175     */
176     public String JavaDoc toString() {
177         return nonterminal;
178     }
179
180     /**
181         Returns all real rules of this artificial rule.
182     */
183     public List getRules() {
184         return rules;
185     }
186
187
188     /**
189         Resolves a List of rules that contain ArtificialRules to a
190         to a list of real rules and stores those in resultSyntax.
191         @param rules List of rules to resolve, containing ArtificialRules on the right side.
192         @param resultSyntax List of rules that will not contain ArtificialRules. Will not be cleared when passed!
193     */
194     public static void resolveArtificialRules(List rules, List resultSyntax) {
195         for (int j = 0; j < rules.size(); j++) {
196             List rule = (List) rules.get(j);
197
198             resultSyntax.add(rule); // add it
199
200             for (int k = 1; k < rule.size(); k++) { // optionally modify it
201 Object JavaDoc symbol = rule.get(k);
202                 
203                 if (symbol instanceof ArtificialRule) { // when containing rules
204 rule.set(k, symbol.toString()); // set the rule's nonterminal
205
206                     ArtificialRule ar = (ArtificialRule)symbol;
207                     resolveArtificialRules(ar.getRules(), resultSyntax); // add the rule
208 }
209             }
210         }
211     }
212
213
214     public static void main(String JavaDoc [] args) {
215         List ruleA = new ArrayList();
216         List ruleB = new ArrayList();
217         List parenthesisRule = new ArrayList();
218         ruleA.add("a1"); ruleA.add("a2");
219         ruleB.add("b1");
220         parenthesisRule.add(ruleA); parenthesisRule.add(ruleB);
221         ArtificialRule afr = new ArtificialRule(parenthesisRule, "OR");
222         System.err.println(afr.toString()+" ::= "+afr.getRules());
223         
224         ArtificialRule afr2 = new ArtificialRule(afr, "*");
225         System.err.println(afr2.toString()+" ::= "+afr2.getRules());
226     }
227
228 }
Popular Tags