|
1
19
20
21 package org.netbeans.modules.languages.parser;
22
23 import java.util.ArrayList  ;
24 import java.util.Collections ;
25 import java.util.HashSet ;
26 import java.util.HashSet ;
27 import java.util.Iterator ;
28 import java.util.List ;
29 import java.util.Map ;
30 import java.util.Set ;
31 import java.util.Set ;
32 import java.util.Stack ;
33 import java.util.StringTokenizer ;
34 import org.netbeans.api.languages.ASTItem;
35 import org.netbeans.api.languages.ASTItem;
36 import org.netbeans.api.languages.ParseException;
37 import org.netbeans.modules.languages.Feature;
38 import org.netbeans.modules.languages.Language;
39 import org.netbeans.modules.languages.LanguagesManagerImpl;
40 import org.netbeans.modules.languages.parser.TokenInput;
41 import org.netbeans.api.languages.ASTNode;
42 import org.netbeans.api.languages.LanguagesManager;
43 import org.netbeans.api.languages.ASTToken;
44 import org.netbeans.modules.languages.Language;
45 import org.netbeans.modules.languages.LanguagesManagerImpl;
46
47
48
52 public class LLSyntaxAnalyser {
53
54 private Language language;
55 private List <Rule> rules;
56 private Map <String ,Map > first;
57 private Set <String > skip;
58 private int traceSteps = -1;
59 private boolean cancel = false;
60 private boolean printFirst = false;
61
62
63 private LLSyntaxAnalyser (Language language) {
64 this.rules = language.getRules ();
65 this.skip = new HashSet <String > (language.getSkipTokenTypes ());
66 this.skip.add ("error");
67 this.language = language;
68 initTracing ();
69 }
70
71
72
74 public void cancel () {
75 cancel = true;
76 }
77
78 public List <Rule> getRules () {
79 return rules;
80 }
81
82 public static LLSyntaxAnalyser create (Language language) {
83 return new LLSyntaxAnalyser (language);
84 }
85
86 public ASTNode read (TokenInput input, boolean skipErrors) throws ParseException {
87 cancel = false;
88 if (rules.isEmpty () || input.eof ())
89 return readNoGrammar (input, skipErrors);
90 if (first == null) {
91 first = Petra.first2 (rules);
92 boolean hasConflicts = AnalyserAnalyser.printConflicts (first, null);
93 if (hasConflicts)
94 AnalyserAnalyser.printRules (rules, null);
95 if (printFirst)
96 AnalyserAnalyser.printF (first, null);
97 AnalyserAnalyser.printUndefinedNTs (rules, null);
98 }
99 return read2 (input, skipErrors);
100 }
101
102
103
105 private ASTNode read2 (TokenInput input, boolean skipErrors) throws ParseException {
106 Stack <Object > stack = new Stack <Object > ();
107 Node root = null, node = null;
108 Iterator it = Collections.singleton ("S").iterator ();
109 do {
110 int offset = input.getOffset ();
111 List whitespaces = readWhitespaces (node, input, skipErrors);
112 if (node != null)
113 offset = input.getOffset ();
114 while (!it.hasNext ()) {
115 if (stack.empty ()) break;
116 node = (Node) stack.pop ();
117 it = (Iterator ) stack.pop ();
118 }
119 if (!it.hasNext ()) break;
120 Object current = it.next ();
121 if (current instanceof String ) {
122 String nt = (String ) current;
123 int newRule = getRule (nt, input);
124 if (newRule == -1) {
125 if (!skipErrors)
126 throw new ParseException ("No rule for " + input.next (1) + " in " + input, root.createASTNode ());
127 if (input.eof ()) {
128 if (node == null)
129 root = node = new Node ("Root", -1, offset, whitespaces);
130 createErrorNode (node, input.getOffset ());
131 return root.createASTNode ();
133 }
134 createErrorNode (node, input.getOffset ()).addItem (readEmbeddings (input.read (), skipErrors));
136 } else {
137 Rule rule = (Rule) rules.get (newRule);
138 Feature parse = language.getFeature ("PARSE", rule.getNT ());
139 if (parse != null) {
140 stack.push (it);
141 stack.push (node);
142 it = Collections.EMPTY_LIST.iterator ();
143 ASTNode nast = (ASTNode) parse.getValue (
144 new Object [] {input, stack}
145 );
146 node.addItem (nast);
147 } else {
149 if (node == null || it.hasNext () || !nt.equals (node.nt)) {
150 if (nt.indexOf ('$') > 0 || nt.indexOf ('#') > 0) {
151 stack.push (it);
152 stack.push (node);
153 } else {
154 Node nnode = new Node (
155 rule.getNT (),
156 newRule,
157 offset,
158 whitespaces
159 );
160 if (node != null) {
161 node.addNode (nnode);
162 stack.push (it);
163 stack.push (node);
164 } else {
165 root = nnode;
166 }
167 node = nnode;
168 }
169 }
170 it = rule.getRight ().iterator ();
172 }
173 }
174 } else {
175 ASTToken token = (ASTToken) current;
176 if (input.eof ()) {
177 if (!skipErrors)
178 throw new ParseException ("Unexpected end of file in " + input, root.createASTNode ());
179 createErrorNode (node, input.getOffset ());
180 return root.createASTNode ();
182 } else
183 if (!isCompatible (token, input.next (1))) {
184 if (!skipErrors)
185 throw new ParseException ("Unexpected token " + input.next (1) + " in " + input + ". Expecting " + token, root.createASTNode ());
186 createErrorNode (node, input.getOffset ()).addItem (readEmbeddings (input.read (), skipErrors));
187 } else {
189 node.addItem (readEmbeddings (input.read (), skipErrors));
190 }
192 }
193 } while (true);
194 if (!skipErrors && !input.eof ())
195 throw new ParseException ("Unexpected token " + input.next (1) + " in " + input, root.createASTNode ());
196 while (
197 !input.eof () )
200 createErrorNode (node, input.getOffset ()).addItem (readEmbeddings (input.read (), skipErrors));
201 return root.createASTNode ();
202 }
203
204 private static boolean isCompatible (ASTToken t1, ASTToken t2) {
205 if (t1.getType () == null) {
206 return t1.getIdentifier ().equals (t2.getIdentifier ());
207 } else {
208 if (t1.getIdentifier () == null)
209 return t1.getType ().equals (t2.getType ());
210 else
211 return t1.getType ().equals (t2.getType ()) &&
212 t1.getIdentifier ().equals (t2.getIdentifier ());
213 }
214 }
215
216 private List <ASTItem> readWhitespaces (
217 Node node,
218 TokenInput input,
219 boolean skipErrors
220 ) throws ParseException {
221 List <ASTItem> result = null;
222 while (
223 !input.eof () &&
224 skip.contains (input.next (1).getType ())
225 ) {
226 ASTToken token = input.read ();
227 if (node != null)
228 node.addItem (readEmbeddings (token, skipErrors));
229 else {
230 if (result == null)
231 result = new ArrayList <ASTItem> ();
232 result.add (readEmbeddings (token, skipErrors));
233 }
234 }
235 return result;
236 }
237
238 private ASTItem readEmbeddings (
239 ASTToken token,
240 boolean skipErrors
241 ) throws ParseException {
242 List <ASTItem> children = token.getChildren ();
243 if (children.isEmpty ())
244 return token;
245 TokenInput in = TokenInput.create (children);
246 Language language = ((LanguagesManagerImpl) LanguagesManager.getDefault ()).
247 getLanguage (children.get (0).getMimeType ());
248 ASTNode root = language.getAnalyser ().read (in, skipErrors);
249 return ASTToken.create (
250 token.getMimeType (),
251 token.getType (),
252 token.getIdentifier (),
253 token.getOffset (),
254 token.getLength (),
255 Collections.<ASTItem>singletonList (root)
256 );
257 }
258
259 private ASTNode readNoGrammar (
260 TokenInput input,
261 boolean skipErrors
262 ) throws ParseException {
263 Node root = new Node ("S", -1, input.getIndex (), null);
264 while (!input.eof ()) {
265 ASTToken token = input.read ();
266 root.addItem (readEmbeddings (token, skipErrors));
267 }
268 return root.createASTNode ();
269 }
270
271 private Node createErrorNode (Node parentNode, int offset) {
272 if (parentNode != null) {
273 List l = parentNode.children;
274 if (l != null && l.size () > 0) {
275 Object possibleErrorNode = l.get (l.size () - 1);
276 if (possibleErrorNode instanceof Node)
277 if (((Node) possibleErrorNode).nt.equals ("ERROR"))
278 return (Node) possibleErrorNode;
279 }
280 }
281 Node errorNode = new Node (
282 "ERROR",
283 -2,
284 offset,
285 null
286 );
287 if (parentNode != null)
288 parentNode.addNode (errorNode);
289 return errorNode;
290 }
291
292 private int getRule (String nt, TokenInput input) {
293 Map m = (Map ) first.get (nt);
294 if (m == null) return -1;
295 int i = 1;
296 while (true) {
297 ASTToken token = input.next (i);
298 if (token == null ) {
299 Set result = (Set ) (Set ) m.get ("#");
300 if (result == null || result.size () > 1) return -1;
301 return ((Integer ) result.iterator ().next ()).intValue ();
302 }
303 T t = new T (token);
304 Map r = (Map ) m.get (t);
305 if (r == null) {
306 t.type = null;
307 r = (Map ) m.get (t);
308 }
309 if (r == null) {
310 t.type = token.getType ();
311 t.identifier = null;
312 r = (Map ) m.get (t);
313 }
314 if (r == null) {
315 Set s = (Set ) m.get ("#");
316 if (s == null)
317 s = (Set ) m.get ("&");
318 if (s == null) {
319 System.out.println("No way! " + nt + " : " + input.next (1) + " " + input.next (2));
320 return -1;
321 }
322 if (s.size () > 1) {
323 System.out.println("Too many choices! " + nt + " : " + input.next (1) + " " + input.next (2) + ":" + input);
324 return -1;
325 }
326 return ((Integer ) s.iterator ().next ()).intValue ();
327 }
328 m = r;
329 }
330 }
331
332 private void initTracing () {
333 Feature properties = language.getFeature ("PROPERTIES");
334 if (properties == null) return;
335 try {
336 traceSteps = Integer.parseInt ((String ) properties.getValue ("traceSteps"));
337 } catch (NumberFormatException ex) {
338 traceSteps = -2;
339 }
340 if (properties.getBoolean ("printRules", false))
341 AnalyserAnalyser.printRules (rules, null);
342 printFirst = properties.getBoolean ("printFirst", false);
343 }
344
345 private Feature optimiseProperty;
346 private boolean removeEmpty = false;
347 private boolean removeSimple = false;
348 private boolean removeEmptyN = true;
349 private boolean removeSimpleN = true;
350 private Set <String > empty = new HashSet <String > ();
351 private Set <String > simple = new HashSet <String > ();
352
353 private boolean removeNT (Node n) {
354 if (optimiseProperty == null) {
355 Feature properties = language.getFeature ("PROPERTIES");
356 optimiseProperty = language.getFeature ("AST");
357 if (optimiseProperty != null) {
358 String s = (String ) optimiseProperty.getValue ("removeEmpty");
359 if (s != null) {
360 if (s.startsWith ("!")) {
361 removeEmptyN = false;
362 s = s.substring (1);
363 }
364 removeEmpty = "true".equals (s);
365 if (!"false".equals (s)) {
366 StringTokenizer st = new StringTokenizer (s, ",");
367 while (st.hasMoreTokens ())
368 empty.add (st.nextToken ());
369 }
370 }
371 s = (String ) optimiseProperty.getValue ("removeSimple");
372 if (s != null) {
373 if (s.startsWith ("!")) {
374 removeSimpleN = false;
375 s = s.substring (1);
376 }
377 removeSimple = "true".equals (s);
378 if (!"false".equals (s)) {
379 StringTokenizer st = new StringTokenizer (s, ",");
380 while (st.hasMoreTokens ())
381 simple.add (st.nextToken ());
382 }
383 }
384 }
385 }
386 if (n.children == null)
387 return removeEmpty || (removeEmptyN == empty.contains (n.nt));
388 else
389 return removeSimple || (removeSimpleN == simple.contains (n.nt));
390 }
391
392
393
395
396 public static class Rule {
397
398 private String nt;
399 private List right;
400
401 private Rule () {}
402
403 public static Rule create (
404 String nt,
405 List right
406 ) {
407 Rule r = new Rule ();
408 r.nt = nt;
409 r.right = right;
410 return r;
411 }
412
413 public String getNT () {
414 return nt;
415 }
416
417 public List getRight () {
418 return right;
419 }
420
421 private String toString = null;
422
423 public String toString () {
424 if (toString == null) {
425 StringBuilder sb = new StringBuilder ();
426 sb.append ("Rule ").append (nt).append (" = ");
427 int i = 0, k = right.size ();
428 if (i < k)
429 sb.append (right.get (i++));
430 while (i < k)
431 sb.append (' ').append (right.get (i++));
432 toString = sb.toString ();
433 }
434 return toString;
435 }
436 }
437
438 public static class T {
439 String type;
440 String identifier;
441
442
447 T (ASTToken t) {
448 type = t.getType ();
449 identifier = t.getIdentifier ();
450 if (type == null && identifier == null)
451 System.out.println("null null!!!");
452 }
453
454 public boolean equals (Object o) {
455 if (!(o instanceof T)) return false;
456 return (((T) o).type == null || ((T) o).type.equals (type)) &&
457 (((T) o).identifier == null || ((T) o).identifier.equals (identifier));
458 }
459
460 public int hashCode () {
461 return type == null ? -1 : type.hashCode () *
462 (identifier == null ? -1 : identifier.hashCode ());
463 }
464
465 public String toString () {
466 if (type == null)
467 return "\"" + identifier + "\"";
468 if (identifier == null)
469 return "<" + type + ">";
470 return "[" + type + "," + identifier + "]";
471 }
472 }
473
474 private class Node {
475
476 String nt;
477 int rule;
478 int offset;
479 List <Object > children;
480
481 Node (
482 String nt,
483 int rule,
484 int offset,
485 List children
486 ) {
487 this.nt = nt;
488 this.rule = rule;
489 this.offset = offset;
490 if (children != null) {
491 Iterator it = children.iterator ();
492 while (it.hasNext ()) {
493 Object o = it.next ();
494 if (o instanceof ASTItem)
495 addItem ((ASTItem) o);
496 else
497 addNode ((Node) o);
498 }
499 }
500 }
501
502 void addNode (Node n) {
503 if (children == null) children = new ArrayList <Object > ();
504 children.add (n);
507 }
508
509 void addItem (ASTItem item) {
510 if (children == null) children = new ArrayList <Object > ();
511 children.add (item);
514 }
515
516 void replace (ASTNode n1, Node n2) {
517 int i, k = children.size ();
518 for (i = 0; i < k; i++) {
519 Object o = children.get (i);
520 if (n2.equals (o)) {
521 children.set (i, n1);
522 return;
523 }
524 }
525 throw new IllegalStateException ();
526 }
527
528 private int getEndOffset () {
529 if (children == null) return offset;
530 if (children.isEmpty ()) return offset;
531 Object l = children.get (children.size () - 1);
532 if (l instanceof ASTToken)
533 return ((ASTToken) l).getOffset () + ((ASTToken) l).getLength ();
534 if (l instanceof Node) {
535 return ((Node) l).getEndOffset ();
536 }
537 return ((ASTNode) l).getEndOffset ();
538 }
539
540 ASTNode createASTNode () {
541 List <ASTItem> l = new ArrayList <ASTItem> ();
542 if (children == null) {
543 if (removeNT (this)) return null;
544 } else {
545 if (children.size () == 1 &&
546 children.get (0) instanceof Node &&
547 removeNT (this)
548 ) return ((Node) children.get (0)).createASTNode ();
549 Iterator it = children.iterator ();
550 while (it.hasNext ()) {
551 Object o = it.next ();
552 if (o instanceof Node) {
553 ASTNode nn = ((Node) o).createASTNode ();
554 if (nn != null) l.add (nn);
555 } else
556 l.add ((ASTItem) o);
557 }
558 }
559 return ASTNode.create (
560 language.getMimeType (),
561 nt,
562 l,
563 offset
564 );
565 }
566 }
567 }
568
569
570 |
Popular Tags |
Java API By Example, From Geeks To Geeks.