Automata, Languages and Compilers 2017/18 spring

9. kodutöö: AST koostamine

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

package week9;
import week9.ast.AstNode;

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

Selle saavutamiseks on vaja:

1. genereerida ANTLR-i abil Aktk.g4 grammatikast (võib kasutada meie näidislahendust, aga ka enda lahendust, mida on sobivalt märgendatud) AKTK parser (koos abiklassidega);
2. kirjutada kood, mis genereeritud parseri abil teisendab sõnena esitatud programmi parse-puuks;
3. 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 ArvuliteraalContext) {
			return new IntegerLiteral(Integer.parseInt(tree.getText()));
		}
		else if (tree instanceof SoneliteraalContext) {
			// 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));
		}
	}

Huvilistele

• Kui sulle ei meeldi instanceof, siis uuri, kuidas saaks ülesannet lahendada visitor disainimustri abil.
• Kui sulle ei meeldi parse-puus liikumine getChild indeksite järgi, siis uuri, milliseid kasulikke meetodeid on konkreetetel Context klassidel ja kuidas alamtippe saab ise nimetada.

Soovitused

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

Lahenduse esitamine

• Esitada tuleb vähemalt järgmised failid:
  • AktkAst.java
    • klassis AktkAst peab olema meetod signatuuriga public static AstNode createAst(String program)
  • AktkLexer.java
  • AktkParser.java
  • AktkListener.java
  • AktkVisitor.java
• Ja kui kasutad ANTLRi genereeritud 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 ja .interp laiendiga genereeritud faile (Aktk.interp, Aktk.tokens, AktkLexer.interp ja AktkLexer.tokens)