001: package ro.infoiasi.donald.compiler.lexer;
002:
003: import ro.infoiasi.donald.compiler.lexer.exceptions.*;
004: import ro.infoiasi.donald.compiler.simple.*;
005: import java.util.*;
006:
007: public class ExpTree extends BinTree {
008: private Alphabet alpha = new Alphabet();
009:
010: public ExpTree() {
011: super ();
012: }
013:
014: public ExpTree(ExpList el) throws ExpParseError {
015: super ();
016: alpha = el.getAlphabet();
017: addRootSubTree(create(el));
018: }
019:
020: private static ExpTree create(AbstractList el) throws ExpParseError {
021: el = removeParenthesis(el);
022: ExpTree et = new ExpTree();
023: if (!el.isEmpty()) {
024: OperatorToken minOpToken = null;
025: int minI = 0;
026: for (int i = 0; i < el.size(); i++) {
027: Class c = el.get(i).getClass();
028: if (c == OperatorToken.class) {
029: OperatorToken opToken = (OperatorToken) el.get(i);
030: if (minOpToken == null
031: || (minOpToken.compareTo(opToken) > 0)) {
032: minOpToken = opToken;
033: minI = i;
034: }
035: } else if (c == ParenthesisLeft.class) {
036: // skip paranthesis
037: ParenthesisLeft paraLeft = (ParenthesisLeft) el
038: .get(i);
039: ParenthesisRight paraRight = paraLeft.pair();
040: i += paraRight.tokenNo() - paraLeft.tokenNo();
041: }
042: }
043: //System.out.println("[["+minI+"]]");
044: if (minOpToken == null) {
045: if (el.size() > 1
046: || el.get(0).getClass() != SymbolToken.class) {
047: throw new ExpParseError("No operator found",
048: ((ExpToken) el.get(0)).strIndex(),
049: ((ExpToken) el.get(el.size() - 1))
050: .strIndex());
051: } else {
052: et.addRoot(el.get(0));
053: }
054: } else {
055: et.addRoot(minOpToken);
056: if (minOpToken.operator().isUnaryLeft()) {
057: if (minI != el.size() - 1) {
058: throw new ExpParseError(
059: "Operator is unary and binds to the left only",
060: minOpToken.strIndex());
061: }
062: ExpTree et1 = create((AbstractList) (el.subList(0,
063: minI)));
064: if (et1.IsEmpty()) {
065: throw new ExpParseError(
066: "Operator is unary and binds to the left only",
067: minOpToken.strIndex());
068: }
069: et.addLeftSubTree(et1, et.root());
070: } else if (minOpToken.operator().isUnaryRight()) {
071:
072: } else if (minOpToken.operator().isBinary()) {
073: ExpTree et1 = create((AbstractList) (el.subList(0,
074: minI)));
075: ExpTree et2 = create((AbstractList) (el.subList(
076: minI + 1, el.size())));
077: if (et1.IsEmpty() || et2.IsEmpty()) {
078: //??? I still have some doubts - the | operator allows an empty operand
079: throw new ExpParseError("Operator is binary",
080: minOpToken.strIndex());
081: }
082: et.addLeftSubTree(et1, et.root());
083: et.addRightSubTree(et2, et.root());
084: } else {
085: throw new ExpParseError(
086: "Operator is not unary or binary",
087: ((ExpToken) el.get(0)).strIndex());
088: }
089: }
090: }
091: return et;
092: }
093:
094: private static AbstractList removeParenthesis(AbstractList el) {
095: boolean over = false;
096: while (!el.isEmpty() && !over) {
097: over = true;
098: if (el.get(0).getClass() == ParenthesisLeft.class
099: && el.get(el.size() - 1).getClass() == ParenthesisRight.class) {
100: ParenthesisLeft paraLeft = (ParenthesisLeft) el.get(0);
101: ParenthesisRight paraRight = (ParenthesisRight) el
102: .get(el.size() - 1);
103: if (paraLeft.pair() == paraRight) {
104: el = (AbstractList) el.subList(1, el.size() - 1);
105: over = false;
106: }
107: }
108: }
109: return el;
110: }
111:
112: public Alphabet getAlphabet() {
113: return alpha;
114: }
115: }
|