Menu
▾
▴
[Cogkit-svn] SF.net SVN: cogkit:[2096] branches/karajan2/src/cog/modules/karajan2/src/ org/globus/cog/karajan/parser
|
From: <ha...@us...> - 2008-07-27 23:59:19
|
Revision: 2096
http://cogkit.svn.sourceforge.net/cogkit/?rev=2096&view=rev
Author: hategan
Date: 2008-07-27 23:59:16 +0000 (Sun, 27 Jul 2008)
Log Message:
-----------
parser optimizations
Modified Paths:
--------------
branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/AbstractGrammarElement.java
branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/And.java
branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/GrammarElement.java
branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Node.java
branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Or.java
branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Rule.java
branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Rules.java
branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Digits.java
branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Literal.java
branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Newline.java
branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Underscore.java
Modified: branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/AbstractGrammarElement.java
===================================================================
--- branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/AbstractGrammarElement.java 2008-07-27 23:58:18 UTC (rev 2095)
+++ branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/AbstractGrammarElement.java 2008-07-27 23:59:16 UTC (rev 2096)
@@ -9,6 +9,7 @@
*/
package org.globus.cog.karajan.parser;
+import java.util.Collection;
import java.util.Enumeration;
public abstract class AbstractGrammarElement implements GrammarElement {
@@ -59,4 +60,11 @@
public String errorForm() {
return toString();
}
+
+ @Override
+ public Collection<Character> getFirstChars() {
+ return null;
+ }
+
+
}
\ No newline at end of file
Modified: branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/And.java
===================================================================
--- branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/And.java 2008-07-27 23:58:18 UTC (rev 2095)
+++ branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/And.java 2008-07-27 23:59:16 UTC (rev 2096)
@@ -10,6 +10,9 @@
package org.globus.cog.karajan.parser;
import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
import java.util.Set;
import org.apache.log4j.Logger;
@@ -120,5 +123,10 @@
return null;
}
+ @Override
+ public Collection<Character> getFirstChars() {
+ return elements[0].getFirstChars();
+ }
+
}
\ No newline at end of file
Modified: branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/GrammarElement.java
===================================================================
--- branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/GrammarElement.java 2008-07-27 23:58:18 UTC (rev 2095)
+++ branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/GrammarElement.java 2008-07-27 23:59:16 UTC (rev 2096)
@@ -9,6 +9,7 @@
*/
package org.globus.cog.karajan.parser;
+import java.util.Collection;
import java.util.Set;
import org.globus.cog.karajan.parser.predicates.Evaluator;
@@ -24,4 +25,6 @@
Set<Character> getDP();
String errorForm();
+
+ Collection<Character> getFirstChars();
}
Modified: branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Node.java
===================================================================
--- branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Node.java 2008-07-27 23:58:18 UTC (rev 2095)
+++ branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Node.java 2008-07-27 23:59:16 UTC (rev 2096)
@@ -51,6 +51,22 @@
nodes = Collections.emptyList();
properties = Collections.emptyMap();
}
+
+ public Node deepCopy() {
+ Node copy = new Node();
+ copy.properties = new HashMap<String, Object>();
+ copy.properties.putAll(properties);
+ copy.nodeType = nodeType;
+ copy.parent = parent;
+ copy.state = state;
+ copy.nodes = new ArrayList<Node>();
+ for (Node c : nodes) {
+ Node cc = c.deepCopy();
+ copy.nodes.add(cc);
+ cc.parent = copy;
+ }
+ return copy;
+ }
public String get_locator() {
return locator;
Modified: branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Or.java
===================================================================
--- branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Or.java 2008-07-27 23:58:18 UTC (rev 2095)
+++ branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Or.java 2008-07-27 23:59:16 UTC (rev 2096)
@@ -10,87 +10,174 @@
package org.globus.cog.karajan.parser;
import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
import java.util.List;
+import java.util.Map;
import java.util.Set;
+import org.globus.cog.karajan.parser.predicates.Evaluator;
+
public final class Or extends AbstractGrammarElement {
- private GrammarElement[] ands;
+ private GrammarElement[] ands;
+ private Map<Character, List<GrammarElement>> filtered;
+ private List<GrammarElement> open;
+ private boolean strict;
- public Or() {
- }
+ public Or() {
+ }
- public void read(PeekableEnumeration st, PredicateMapping mapping) {
- List a = new ArrayList();
- while (true) {
- And and = new And();
- and.read(st, mapping);
- a.add(and);
- if (st.peek().equals(";")) {
- ands = (GrammarElement[]) a.toArray(GEATYPE);
- break;
- }
- expect(st, "|");
- }
- expect(st, ";");
- }
+ public void read(PeekableEnumeration st, PredicateMapping mapping) {
+ List<And> a = new ArrayList<And>();
+ while (true) {
+ And and = new And();
+ and.read(st, mapping);
+ a.add(and);
+ if (st.peek().equals(";")) {
+ ands = a.toArray(GEATYPE);
+ break;
+ }
+ expect(st, "|");
+ }
+ expect(st, ";");
+ }
- public boolean parse(ParserContext context, Stack stack) throws ParsingException {
- for (int i = 0; i < ands.length; i++) {
- int mark = stack.mark();
- if (ands[i].parse(context, stack)) {
- return true;
- }
- stack.forget(mark);
- }
- return false;
- }
+ private void populateFirstChars() {
+ //System.out.println(this);
+ if (filtered != null) {
+ return;
+ }
+ filtered = new HashMap<Character, List<GrammarElement>>();
+ strict = true;
+ List<Collection<Character>> all = new ArrayList<Collection<Character>>();
+ open = new ArrayList<GrammarElement>();
+ for (GrammarElement ge : ands) {
+ Collection<Character> l = ge.getFirstChars();
+ all.add(l);
+ if (l != null) {
+ for (Character c : l) {
+ if (!filtered.containsKey(c)) {
+ filtered.put(c, new ArrayList<GrammarElement>());
+ }
+ }
+ }
+ else {
+ strict = false;
+ }
+ }
+ for (int i = 0; i < all.size(); i++) {
+ Collection<Character> l = all.get(i);
+ if (l == null) {
+ for (List<GrammarElement> lg : filtered.values()) {
+ lg.add(ands[i]);
+ }
+ open.add(ands[i]);
+ }
+ else {
+ for (Character c : l) {
+ filtered.get(c).add(ands[i]);
+ }
+ }
+ }
+ if (open.isEmpty()) {
+ open = null;
+ }
+ }
- public String toString() {
- StringBuffer sb = new StringBuffer();
- boolean first = true;
- for (int i = 0; i < ands.length; i++) {
- if (first) {
- first = false;
- }
- else {
- sb.append(" |\n");
- }
- sb.append(ands[i]);
- }
- sb.append(" ;\n");
- return sb.toString();
- }
-
- public String errorForm() {
- StringBuffer sb = new StringBuffer();
- boolean first = true;
- for(int i = 0; i < ands.length; i++) {
- if (first) {
- first = false;
- }
- else {
- sb.append(" or ");
- }
- sb.append(ands[i].errorForm());
- }
- return sb.toString();
- }
+ @Override
+ public Collection<Character> getFirstChars() {
+ populateFirstChars();
+ if (open != null) {
+ return null;
+ }
+ else {
+ return filtered.keySet();
+ }
+ }
- public GrammarElement _optimize(Rules rules) {
- if (ands.length == 1) {
- return ands[0].optimize(rules);
- }
- for (int i = 0; i < ands.length; i++) {
- ands[i] = ands[i].optimize(rules);
- }
- return this;
- }
+ public boolean parse(ParserContext context, Stack<Evaluator> stack)
+ throws ParsingException {
- public Set<Character> getDP() {
- return null;
- }
+ List<GrammarElement> l = null;
+ char c = 0;
+ if (context.tok.hasMoreChars()) {
+ c = context.tok.peekChar();
+ l = filtered.get(c);
+ if (l == null) {
+ l = open;
+ }
+ }
+ if (l == null) {
+ if (!strict) {
+ for (GrammarElement and : ands) {
+ int mark = stack.mark();
+ if (and.parse(context, stack)) {
+ return true;
+ }
+ stack.forget(mark);
+ }
+ }
+ }
+ else {
+ for (GrammarElement ge : l) {
+ int mark = stack.mark();
+ if (ge.parse(context, stack)) {
+ return true;
+ }
+ stack.forget(mark);
+ }
+ }
+ return false;
+ }
-
-
-
+ public String toString() {
+ StringBuffer sb = new StringBuffer();
+ boolean first = true;
+ for (int i = 0; i < ands.length; i++) {
+ if (first) {
+ first = false;
+ }
+ else {
+ sb.append(" |\n");
+ }
+ sb.append(ands[i]);
+ }
+ sb.append(" ;\n");
+ return sb.toString();
+ }
+
+ public String errorForm() {
+ StringBuffer sb = new StringBuffer();
+ boolean first = true;
+ for (int i = 0; i < ands.length; i++) {
+ if (first) {
+ first = false;
+ }
+ else {
+ sb.append(" or ");
+ }
+ sb.append(ands[i].errorForm());
+ }
+ return sb.toString();
+ }
+
+ public GrammarElement _optimize(Rules rules) {
+ GrammarElement r;
+ if (ands.length == 1) {
+ r = ands[0].optimize(rules);
+ }
+ else {
+ for (int i = 0; i < ands.length; i++) {
+ ands[i] = ands[i].optimize(rules);
+ }
+ r = this;
+ populateFirstChars();
+ }
+ return r;
+ }
+
+ public Set<Character> getDP() {
+ return null;
+ }
+
}
\ No newline at end of file
Modified: branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Rule.java
===================================================================
--- branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Rule.java 2008-07-27 23:58:18 UTC (rev 2095)
+++ branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Rule.java 2008-07-27 23:59:16 UTC (rev 2096)
@@ -9,6 +9,7 @@
*/
package org.globus.cog.karajan.parser;
+import java.util.Collection;
import java.util.Set;
public final class Rule extends AbstractGrammarElement {
@@ -56,10 +57,18 @@
public String errorForm() {
return or.errorForm();
}
+
+
- public GrammarElement _optimize(Rules rules) {
+ @Override
+ public Collection<Character> getFirstChars() {
+ return or.getFirstChars();
+ }
+
+ public GrammarElement _optimize(Rules rules) {
or = or.optimize(rules);
- return this;
+ //return this;
+ return or;
}
public Set<Character> getDP() {
Modified: branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Rules.java
===================================================================
--- branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Rules.java 2008-07-27 23:58:18 UTC (rev 2095)
+++ branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/Rules.java 2008-07-27 23:59:16 UTC (rev 2096)
@@ -9,6 +9,7 @@
*/
package org.globus.cog.karajan.parser;
+import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
@@ -41,7 +42,12 @@
return rules.get(name);
}
- public GrammarElement _optimize(Rules rules) {
+ @Override
+ public Collection<Character> getFirstChars() {
+ return null;
+ }
+
+ public GrammarElement _optimize(Rules rules) {
Iterator<Map.Entry<String, GrammarElement>> i = this.rules.entrySet().iterator();
while (i.hasNext()) {
Map.Entry<String, GrammarElement> entry = i.next();
@@ -56,7 +62,7 @@
public String toString() {
StringBuffer sb = new StringBuffer();
- Iterator i = rules.values().iterator();
+ Iterator<?> i = rules.values().iterator();
while (i.hasNext()) {
sb.append(i.next());
sb.append('\n');
Modified: branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Digits.java
===================================================================
--- branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Digits.java 2008-07-27 23:58:18 UTC (rev 2095)
+++ branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Digits.java 2008-07-27 23:59:16 UTC (rev 2096)
@@ -9,29 +9,40 @@
*/
package org.globus.cog.karajan.parser.predicates;
+import java.util.Arrays;
+import java.util.Collection;
+
import org.globus.cog.karajan.parser.ParserContext;
import org.globus.cog.karajan.parser.Stack;
-
public class Digits extends AbstractPredicate {
- protected void setParams(String[] params) {
- assertEquals(params.length, 0, getClass());
- }
+ protected void setParams(String[] params) {
+ assertEquals(params.length, 0, getClass());
+ }
- public boolean parse(final ParserContext context, final Stack stack) {
- if (context.tok.hasMoreTokens()) {
- if (!context.tok.isDigits()) {
- return false;
- }
- final String token = context.tok.peekToken();
- stack.push(context.tok.nextToken());
- return true;
- }
- return false;
- }
-
- public String toString() {
- return "DIGITS()";
- }
+ public boolean parse(final ParserContext context, final Stack stack) {
+ if (context.tok.hasMoreTokens()) {
+ if (!context.tok.isDigits()) {
+ return false;
+ }
+ final String token = context.tok.peekToken();
+ stack.push(context.tok.nextToken());
+ return true;
+ }
+ return false;
+ }
+
+ private static final Collection<Character> chars = Arrays
+ .asList(new Character[] { '0', '1', '2', '3', '4', '5', '6', '7', '8',
+ '9' });
+
+ @Override
+ public Collection<Character> getFirstChars() {
+ return chars;
+ }
+
+ public String toString() {
+ return "DIGITS()";
+ }
}
Modified: branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Literal.java
===================================================================
--- branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Literal.java 2008-07-27 23:58:18 UTC (rev 2095)
+++ branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Literal.java 2008-07-27 23:59:16 UTC (rev 2096)
@@ -9,6 +9,9 @@
*/
package org.globus.cog.karajan.parser.predicates;
+import java.util.Collection;
+import java.util.Collections;
+
import org.globus.cog.karajan.parser.Lexer;
import org.globus.cog.karajan.parser.ParserContext;
import org.globus.cog.karajan.parser.Stack;
@@ -48,8 +51,15 @@
}
return true;
}
+
+
- public String toString() {
+ @Override
+ public Collection<Character> getFirstChars() {
+ return Collections.singletonList(value.charAt(0));
+ }
+
+ public String toString() {
return "LITERAL(" + value + ")";
}
Modified: branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Newline.java
===================================================================
--- branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Newline.java 2008-07-27 23:58:18 UTC (rev 2095)
+++ branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Newline.java 2008-07-27 23:59:16 UTC (rev 2096)
@@ -9,6 +9,9 @@
*/
package org.globus.cog.karajan.parser.predicates;
+import java.util.Collection;
+import java.util.Collections;
+
import org.globus.cog.karajan.parser.ParserContext;
import org.globus.cog.karajan.parser.Stack;
@@ -30,7 +33,14 @@
return false;
}
- public String toString() {
+
+
+ @Override
+ public Collection<Character> getFirstChars() {
+ return Collections.singletonList('\n');
+ }
+
+ public String toString() {
return "NEWLINE()";
}
Modified: branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Underscore.java
===================================================================
--- branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Underscore.java 2008-07-27 23:58:18 UTC (rev 2095)
+++ branches/karajan2/src/cog/modules/karajan2/src/org/globus/cog/karajan/parser/predicates/Underscore.java 2008-07-27 23:59:16 UTC (rev 2096)
@@ -9,6 +9,9 @@
*/
package org.globus.cog.karajan.parser.predicates;
+import java.util.Collection;
+import java.util.Collections;
+
import org.globus.cog.karajan.parser.ParserContext;
import org.globus.cog.karajan.parser.Stack;
@@ -37,7 +40,12 @@
return false;
}
- public String toString() {
+ @Override
+ public Collection<Character> getFirstChars() {
+ return Collections.singletonList('_');
+ }
+
+ public String toString() {
return "UNDERSCORE()";
}
}
\ No newline at end of file
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
