Skip to content
leinge edited this page Jul 15, 2013 · 26 revisions

Parser

Der Parser erzeugt aus einem vom Lexer übergebenen Tokenstream den für den weiteren Übersetzungsvorgang notwendigen AST (Abstrat Syntax Tree). Hierzu wird mittels einem Shift Reduce Verfahren der eingegebene Quelltext gegen die Regeln der Grammatik geprüft und gegebenfalls durch Ausgabe von Syntaxfehlern der Parsevorgang abgebrochen. Kann der Parsevorgang erfolgreich abgeschlossen werden, wird der generierte AST anschließend vom Controller an die Semantische Analyse weitergereicht.

Durch den modularen Aufbau des FUC (FU Compiler) kann das Parsermodul, wie auch alle anderen Module durch ein anderes Parsermodul ersetzt werden. Um den Controller die Möglichkeit zu bieten, einen eigens erstellten Parser einzubinden ist das Java Interface Parser aus dem Paket swp_compiler_ss13.common.parser zu implementieren.

Interface

007	public interface Parser {
015        void setLexer(Lexer lexer);
023        void setReportLog(ReportLog reportLog);
033        AST getParsedAST();
034	}

Die Methode setLexer() erhält hierbei ein Object, dass das Lexer Interface implementiert. Von diesem holt der Parser sich dann die einzelnen Token durch Aufruf der im Lexer Interface definierten Methode getNextToken().

Über setReportLog() bekommt der Parser das vom Controller verwendete Reportlog übergeben, in diesem werden sämtliche im Verlauf des Parsevorganges auftretende Fehler und Warnungen protokolliert und nach dem Parsevorgang durch den Controller ausgewertet. Hierbei ist zu beachten, dass das Übergeben eines Fehlers im Controller immer zu einem Abbruch des Übersetzungsvorganges führt und es dabei zu keiner weiteren Auswertung des AST mehr kommt. Die möglichen Fehlertypen sind:

  • UNRECOGNIZED_TOKEN: Ein Token vom Typ NOT_A_TOKEN im Eingabe-Stream
  • WORD_NOT_IN_GRAMMAR: Wenn eine für diese Grammatik ungültige Token-Sequenz eingegeben wird
  • UNDEFINED: Sonst (Programmierfehler)

Der Parsevorgang wird über die Methode getParsedAST() gestartet, diese gibt bei erfolgreichem parsen auch den AST zurück.

Aufbau

Wie im Vorfeld bereits erwähnt, handelt es sich bei dem im FUC verwendeten Parser um einen Shift Reduce Parser, speziell um eine LR(1) Variante. Diese setzt voraus, dass ein entsprechender LR(1) Automat aus den Produktionen der Grammatik erzeugt wird.

Generator

Dies ist definiert in der Klasse LR1Generator aus dem Paket swp_compiler_ss13.fuc.parser.generator, welche die generische Klasse ALRGenerator<LR1Item,LR1State> beerbt, hier werden aus den in den Klassen FirstSets, FollowSets erzeugten First und Follow Mengen der DFA mitsamt der Übergänge generiert.

013	public class LR1Generator extends ALRGenerator<LR1Item, LR1State> {

024        public LR1Generator(Grammar grammar) throws RuntimeException {
025                super(grammar);
026        }

032        @Override
033        protected Dfa<LR1Item, LR1State> createLrDFA(LR1State startState) {
034                return new Dfa<LR1Item, LR1State>(startState);
035        }
036        
037        @Override
038        protected LR1State createStartState() {
039                Grammar grammar = grammarInfo.getGrammar();
040                ITerminalSet empty = grammarInfo.getEmptyTerminalSet();
041                return new LR1State(new LR1Item(grammar.getStartProduction(), 0, empty));
042        }
043        
044        @Override
045        protected void createReduceAction(LRActionTable table, LR1Item item,
046                        LRParserState fromState) throws GeneratorException {
047                // LR (1): Set action not for all FOLLOW symbols but all lookaheads
048                Reduce reduce = new Reduce(item.getProduction());
049                for (Terminal lookahead : item.getLookaheads().getTerminals()) {
050                      table.set(reduce, fromState, lookahead);
051                        setReduceAction(table, reduce, fromState, lookahead);
052                }
053        }
059	}

Durch den generischen Aufbau lässt sich über die gegebene Grammatik hinaus zu jeder anderen LR Grammatik ein enstprechender Automat erzeugen. Als weiteres Beispiel einer Implementierung eines Generators findet sich im selben Paket zusätzlich noch die Klasse LR0Generator zur Erzeugung eines LR(0) Automaten.

Die Produktionen der Grammatik aus denen der Automat erzeugt wird, sind in der Klasse ProjectGrammar im Paket swp_compiler_ss13.fuc.parser.grammar zu finden.

012 public class ProjectGrammar {
013        public static class M1 extends GrammarSpec {

019                public static final Terminal sem = new Terminal(";",
020                                TokenType.SEMICOLON);

039                public static final NonTerminal program = new NonTerminal("program");

057                public static final Production program1 = new Production(0, program,
058                                decls, stmts);

Der Auszug zeigt, dass die Grammatik hier durch eine eingebette Klasse definiert ist, die von der Klasse GrammarSpec erbt. Dabei ist jede Produktion der Klasse durch eine Menge von statischen Terminalen, Nicht Terminalen und Produktionen definiert, welche hier durch die Klassen Terminal, NonTerminal und Production definiert sind. An dieser Stelle ist es durch die Verwendung des Generators möglich, die Grammatik zu erweitern, bzw. gänzlich neue Grammatiken zu definieren und hinzuzufügen. Was aber zur Folge hat, dass ggf. die Reduktionen in der Klasse ReduceImpl angepasst bzw. erweitert werden müssen, ebenso kann eine Funktionserweiterung des Parsers eine direkte Erweiterung aller nachfolgenden Module nach sich ziehen.

Parsevorgang

Die Klasse ReduceImpl befindet sich zusammen mit der Klasse LRParser im Paket swp_compiler_ss13.fuc.parser.parser. In der Klasse LRParser wird der gesamte Parsevorgang beschrieben. Zum Speichern der Zustände und der bereits gelesenen Token bzw. reduzierten AST Knoten werden hier zwei Stacks instanziert.

047                Stack<LRParserState> parserStack = new Stack<>();
050                Stack<Object> valueStack = new Stack<>();

Innerhalb einer Schleife werden die Token solange vom Lexer angefordert, bis dieser ein NOTATOKEN oder ein EOF Token übergibt. Ersteres signalisiert einen Fehler im Tokenstream und führt unmittelbar zum Abbruch des Übersetzungsvorganges. EOF hingegen signalisiert das Ende des Tokenstreams und führt dazu, dass der Übersetzungsvorgang erfolgreich beendet wird, sofern der Parser in der Parsetabelle einen akzeptierenden Zustand erreicht hat. Andernfalls wird auch hier der Parser mit einer Fehlermeldung abbrechen.

058                LRParserState state = parserStack.peek();
076                Terminal terminal = token.getTerminal();
079                action = table.getActionTable().get(state, terminal);

Den Folgezustand berechnet der Parser anhand des im parserStack zuletzt abgelegten Zustands und dem aktuell übergebenen Token. Als Rückgabe erhält dieser den Folgezustand action vom Typ ALRAction. Dieser kann 4 verschiedene Zustände annehmen.

SHIFT

Der Zustand SHIFT führt dazu, dass action auf den parserStack und das aktuelle Token auf dem valueStack abgelegt werden.

086                        case SHIFT: {
087                                // Shift state
088                                Shift shift = (Shift) action;
089                                log.debug(shift.toString());
090                                parserStack.push(shift.getNewState());
091
092                                // Push old token on stack
093                                valueStack.push(token);
094                                token = lexer.getNextToken();
095                        }
096                        break;

REDUCE

Der Zustand REDUCE führt dazu, dass die statische Methode getReduceAction mit der aktuellen Produktion als Parameter aus der Klasse ReduceImpl aufgerufen wird. Im Vorfeld müssen aber noch soviele Zustände vom parserStack entfernt werden, wie die Reduktion an Terminalen und nicht Terminalen auf der rechten Seite der Regel aufweist. (Zeile 101-103)

098                        case REDUCE: {
100                                Reduce reduce = (Reduce) action;
101                                for (int i = 1; i <= reduce.getPopCount(); i++) {
102                                        parserStack.pop();
103                                }
107                                Production prod = reduce.getProduction();
108                                log.debug(reduce.toString() + " " + prod.toString());
109                                ReduceAction reduceAction = null;

112                                reduceAction = ReduceImpl.getReduceAction(prod, reportLog);

In der Klasse ReduceImpl wird dann gemäß der übergebenen Produktion die richtige Regel ausgewählt eine Reduktion vom Typ ReduceAction erzeugt, die abschließend im LRParser ausgeführt wird.

802                case "factor -> string":
803                        return new ReduceAction() {
804                                @Override
805                                public Object create(Object... objs) throws ParserException  {
806                                        LiteralNodeImpl literal = new LiteralNodeImpl();
807                                        Token token = (Token) objs[0];
808                                        literal.setLiteral(token.getValue());
809                                        literal.setLiteralType(new StringType((long) token
810                                                        .getValue().length()));
811                                        literal.setCoverage(token);
812                                        return literal;
813                                }
814
815                        };

Wie im Auszug dargestellt werden beim Erzeugen einer Reduktion die Knoten des AST generiert und sämtliche notwendigen Attribute übergeben. Als Rückgabe liefert eine Reduktion immer einen AST Knoten, dieser wird nach Beendigung der Methode auf dem valueStack gespeichert.

120                  int nrOfValuesReduced = reduce.getPopCount();
121                  LinkedList<Object> valueHandle = new LinkedList<>();
122                  for (int i = 0; i < nrOfValuesReduced; i++) {
123                          valueHandle.addFirst(valueStack.pop());
124                  }
127                  Object newValue = reduceAction.create(arr(valueHandle));
133                  valueStack.push(newValue);

Bevor die Reduktion im LRParser durch Aufruf der create Methode erfolgen kann, müssen erst sämtliche für die Reduktion notwendigen values vom valueStack geholt werden, hierbei ist wieder die Anzahl der Terminale und Nicht Terminale der rechten Regelseite maßgebend. Im letzten Schritt wird der Folgezustand nach der Reduktion bestimmt und auf dem parserStack abgelegt.

ACCEPT

Stellt der Typ von action den Zustand ACCEPT dar und ist das aktuelle Token vom Typ EOF, so ist der Parsevorgang erfolgreich und es wird der generierte AST zurückgegeben, andernfalls wird ein Fehler an das Reportlog übergeben.

ERROR

Der ERROR Zustand wird immer dann erreicht, wenn die mit dem aktuell erhaltenen Token kein korrekter Folgezustand erreicht werden kann. Dieser Fehler wird zunächst nur geloggt; dann tritt die Error-Recovery in Kraft: Diese Methode versucht den Zustand des Parsers zu erkennen, und ggf. durch einfache Manipulation des Token-Stream (z.B. Hinzufügen des Tokens ';') wieder einen Zustand zu erreichen, aus dem der Parser sinnvoll weiterarbeiten kann. Ziel ist es, bei einem Parsing-Durchgang nicht nur einen, sondern möglichst gleich alle Fehler im Quellcode zu finden, um diese dem Programmierer anzuzeigen. Dabei ist keinesfalls garantiert, dass der von der Error-Recovery generierte Zustand wieder korrekt ist - es können sehr gut Folgefehler auftreten.

Tests

Um unsere Softwarekomponenten zu testen, verwenden wir in erster Linie JUnit Tests

Modul Test

Wir haben Modultests implementiert um unsere Parser Klassen zu testen. Das folgende einfache Beispiel zeigt einen solchen Modultest.

  
public class ParserExceptionTest {
	// preparing for the test
	static String test = "Test";
	static ParserException test1 = new ParserException(test);
	
	@BeforeClass
    public static void setUpEarly() {			 
		test1.addReportLogMessage(test);
		test1.addReportLogText(test);
		
	}	 
	// test if the texts are identical
	@Test
	public final void testGetReportLogMessage() {
		assertTrue(test==test1.getReportLogMessage());
	}	 
	// test if the texts are identical
	@Test
	public final void testGetReportLogText() {
		assertTrue(test==test1.getReportLogText());
	}
}
 

Integration Test

Um Parsertests durchzuführen ist es notwendig, mit der gewünschten Grammatik den Parsergenerator (hier LR(0)) zu erzeugen und damit die Parsetabelle zu generieren. Der Quelltext wird dann in Form eines Strings als ByteArrayInputStream an den Lexer übergeben. Anschließend wird der Parsevorgang mit der generierten Parsetabelle und der Lexerinstanz gestartet. Der daraus resultierende AST wird abschließend mit einem von Hand erzeugten Baum verglichen, um fest zu stellen, ob der Parser den korrekten Baum erzeugt hat.

Zum Beispiel:

  
//construct for parsing table
String input = "long l ;";
Grammar grammar = new ProjectGrammar.M1().getGrammar();
ALRGenerator generator = new LR0Generator(grammar);
LRParsingTable table = generator.getParsingTable();

//add the input to the lexer
Lexer lexer = new LexerImpl();
lexer.setSourceStream(new ByteArrayInputStream(input.getBytes()));

// execute the parser with the parsing table
LRParser lrParser = new LRParser();
LexerWrapper lexWrapper = new LexerWrapper(lexer, grammar);
ReportLog reportLog = new ParserReportLogImpl();
		
// construct the parser tree
AST ast = lrParser.parse(lexWrapper, reportLog, table);

// copare the ast with ASTFactory by calling the checkAst method
checkAst(ast);


// the checkAst method
private static void checkAst(AST ast) {
assertNotNull(ast);
ASTFactory factory = new ASTFactory();
factory.addDeclaration("l", new LongType());
AST expected = factory.getAST();		
ASTComparator.compareAST(expected, ast);
}