001: package ro.infoiasi.donald.compiler.parser;
002:
003: import ro.infoiasi.donald.compiler.cfg.*;
004: import java.io.*;
005: import java.util.*;
006:
007: public abstract class AbstractLR1Parser extends AbstractParser {
008: public AbstractLR1Parser(ParserSpec spec) {
009: super (spec, true);
010: }
011:
012: public AbstractLR1Parser(String parserSpecPath) throws IOException,
013: SpecParseException {
014: super (parserSpecPath, true);
015: }
016:
017: protected int stateNo;
018: protected ParseAction[][] actionTable;
019: protected Integer[][] gotoTable;
020: protected Integer startStateIndex;
021:
022: public ParseAction getAction(int state, Terminal a) {
023: return actionTable[state][a.getIndex()];
024: }
025:
026: public int getGoto(int state, NonTerminal x) {
027: Integer newState = gotoTable[state][x.getIndex()];
028: if (newState != null) {
029: return newState.intValue();
030: } else {
031: return -1;
032: }
033: }
034:
035: public Production getStartProduction() {
036: return sp;
037: }
038:
039: public int getStateNo() {
040: return stateNo;
041: }
042:
043: public int getStartState() {
044: return startStateIndex.intValue();
045: }
046:
047: public interface ParseAction {
048: boolean isShiftAction();
049:
050: boolean isReduceAction();
051: }
052:
053: public class ShiftAction implements ParseAction {
054: private Integer stateIndex;
055:
056: public ShiftAction(Integer stateIndex) {
057: this .stateIndex = stateIndex;
058: }
059:
060: public Integer getStateIndex() {
061: return stateIndex;
062: }
063:
064: public boolean isShiftAction() {
065: return true;
066: }
067:
068: public boolean isReduceAction() {
069: return false;
070: }
071:
072: public String toString() {
073: return stateIndex.toString();
074: }
075: }
076:
077: public class ReduceAction implements ParseAction {
078: private Production production;
079:
080: public ReduceAction(Production production) {
081: this .production = production;
082: }
083:
084: public Production getProduction() {
085: return production;
086: }
087:
088: public boolean isShiftAction() {
089: return false;
090: }
091:
092: public boolean isReduceAction() {
093: return true;
094: }
095:
096: public String toString() {
097: return production.toString();
098: }
099: }
100:
101: public List parse() throws IOException, SyntaxError {
102: List pi = new LinkedList();
103: LinkedList stack = new LinkedList();
104: stack.add(startStateIndex);
105: Terminal a = lexer.nextToken().getSymbol();
106:
107: while (true) {
108: if (DEBUG) {
109: System.out.print("Stack: ");
110: Iterator stackIt = stack.iterator();
111: while (stackIt.hasNext()) {
112: Integer stateIndex = (Integer) stackIt.next();
113: System.out.print(stateIndex.intValue() + " ");
114: }
115: System.out.println();
116: }
117:
118: Integer stateIndex = (Integer) stack.getLast();
119: ParseAction pa = actionTable[stateIndex.intValue()][a
120: .getIndex()];
121: if (pa == null) {
122: throw new SyntaxError(a);
123: }
124: if (pa.isShiftAction()) {
125: ShiftAction sa = (ShiftAction) pa;
126: stack.add(sa.getStateIndex());
127: a = lexer.nextToken().getSymbol();
128: } else {
129: ReduceAction ra = (ReduceAction) pa;
130: Production prod = ra.getProduction();
131: if (prod == sp) {
132: return pi; // accept
133: }
134: for (int i = 0; i < prod.getRHS().size(); i++) {
135: stack.removeLast();
136: }
137: stateIndex = (Integer) stack.getLast();
138: stack.addLast(gotoTable[stateIndex.intValue()][prod
139: .getLHS().getIndex()]);
140: pi.add(prod);
141: }
142: }
143: }
144: }
|