Automaadid, keeled ja translaatorid 2016/17 kevad

9. kodutöö: AST koostamine

Selles kodutöös tuleb ANTLR-i kaasabil defineerida meetod createAst, mis annab AKTK programmile vastava abstraktse süntaksipuu:

package kodu9;
import kodu9.ast.AstNode;

public class AKTKi {
	public static AstNode createAst(String program) {
		// Erindi viskamine tuleb asendada reaalse implementatsiooniga
		throw new UnsupportedOperationException();
	}
}

Selle saavutamiseks on vaja:

• genereerida ANTLR-i abil AKTK parser (koos abiklassidega);
• kirjutada kood, mis genereeritud parseri abil teisendab sõnena esitatud programmi parse-puuks;
• kirjutada kood, mis teisendab parse-puu abstraktseks süntaksipuuks. Abstraktse süntaksipuu esitamiseks anname ülesandega kaasa klassi AstNode koos alamklassidega. See punkt on selle koduülesande tuum.

Toome siinkohal ära kärbitud näite AST koostamisest. NB! Lisaks sellele, et siin on nähtavad lüngad, on neis mõned juhtumid ka täiesti käsitlemata -- need tuleb sul üles leida ja ära realiseerida. Selleks soovitame vaadata läbi grammatika reeglid ja otsustada, milliseid reegleid tuleb eraldi käsitleda ja millised saab jätta vaikeimplementatsiooni hooleks.

instanceof-iga variant:

	private static AstNode parseTreeToAst(ParseTree tree) {

		if (tree instanceof ArvuliteraalRContext) {
			// tuleb arvestada, et tegemist võib olla täisarvu või murdarvuga
			if (tree.getText().contains(".")) {
				return new FloatingPointLiteral(Double.parseDouble(tree.getText()));
			}
			else {
				return __________________;
			}
		}
		else if (tree instanceof SoneliteraalRContext) {
			// arvesta, et sõneliteraalil on ümber jutumärgid, mis ei kuulu sõne sisu hulka
			return __________________;
		}
		else if (tree instanceof SuluavaldisContext) {
			// Selle tipu alluvad on alustav sulg, avaldis ja lõpetav sulg
			// NB! Alluvate nummerdamine algab 0-st

			// töötleme rekursiivselt sulgude sees oleva avaldise ja tagastame selle
			return parseTreeToAst(tree.getChild(1));
		}
		else if (tree instanceof KorrutamineJagamineContext
				|| tree instanceof LiitmineLahutamineContext
				|| tree instanceof VordlemineContext) {
			// kõik binaarsed operatsioonid saan käsitleda korraga
			String operaator = tree.getChild(1).getText();
			Expression vasakArgument = (Expression) parseTreeToAst(tree.getChild(0));
			______________________________;

			return new FunctionCall(operaator, Arrays.asList(vasakArgument, ______________));
		}
		else if (tree instanceof MuutujaDeklaratsioonContext) {
			// Muutuja deklaratsiooni esimene alluv (st. alluv 0) on võtmesõna "var",
			// teine alluv on muutuja nimi

			// Algväärtus võib olla, aga ei pruugi.
			// Kontrolli ANTLRi IntelliJ pluginaga järgi, mitu alluvat
			// on muutuja deklaratsioonil, millel on algväärtus ja mitu 
			// alluvat on sellel, millel algväärtust pole.

			return __________________;
		}
		else if (tree instanceof LauseContext) {
			// grammatikast on näha, et lause võib olla ühe alluvaga,
			// (nt. ifLause, whileLause), mis on käsitletud mujal
			if (tree.getChildCount() == 1) {
				AstNode child = parseTreeToAst(tree.getChild(0)); 
				// ainuke asi mida tuleb jälgida, 
				// on see, et kui lause koosneb avaldisest, siis selleks,
				// et temast saaks ikkagi lause,
				// tuleb ta pakendada ExpressionStatement'i sisse
				if (child instanceof Expression) {
					return new ExpressionStatement((Expression) child);
				} 
				else {
					return child;
				}
			}
			// ... aga lause võib olla ka loogelistes sulgudes olev lausete jada
			else {
				assert tree.getChildCount() == 3;
				return parseTreeToAst(tree.getChild(1));
			}
		}

		else {
			// Järele peaks olema jäänud (kui sa lisasid ülespoole ka puuduvad olulised juhtumid)
			// ainult need tiputüübid, millel on ainult
			// üks alluv ja mis olid olulised vaid parsimise jaoks. 
			// Järelikult meil pole abstraktsesse süntaksipuusse neile vastavaid 
			// tippe tarvis ja me liigume kohe nende alluva juurde
			return parseTreeToAst(tree.getChild(0));
		}
	}

Visitor

Kui sulle ei meeldi instanceof, siis uuri, kuidas saaks ülesannet lahendada visitor disainimustri abil.

Soovitused

• Vaata üle ka AST klasside kirjeldused (dokumentatsiooni leiad klasside ja meetodite päistest). Uuri ka klassihierarhiat (Eclipse, IntelliJ).
• AstNode.toString() näitab puu struktuuri tekstilisel kujul.

Lahenduse esitamine

• Esitada tuleb vähemalt järgmised failid:
  • AKTKi.java
    • klassis AKTKi peab olema meetod signatuuriga public static AstNode createAst(String program)
  • AKTKLexer.java
  • AKTKParser.java
  • AKTKListener.java
• Ja kui kasutad ANTLRi genereeritud Visitor, BaseVisitor või BaseListener, siis tuleks neid ka ülesse laadida.
• Kokku võib esitada kuni 9 faili.
• Kõik esitatud failid peavad olema UTF-8 kodeeringus (ANTLR-i poolt genereeritud failide puhul ei pea selle pärast muretsema).
• Esitada ei ole vaja:
  • grammatikat (AKTK.g4)
  • token-laiendiga genereeritud faile (AKTK.tokens ja AKTKLexer.tokens)