Automata, Languages and Compilers

Parse-puu teisendamine abstraktseks süntaksipuuks

Parse-puu on suur ja kohmakas, sest see sisaldab lisaks programmi sisulisele struktuurile ka infot parsimise protsessi kohta. Toome uuesti ära programmi 5 + 2 *4 parse-puu. Tema kõrval on vastav abstraktne süntaksipuu (edaspidi AST, abstract syntax tree).

Parse-puu sisaldab kahte asja, mis ASTis enam ei esine:

1. Mitte-terminale nagu term ja faktor, mis on parseril ainult vaja õige struktuuri saavutamiseks.
2. Terminalsümbolid nagu sulud või semikoolon, mis samuti teenivad seda rolli, et programmi (puu)struktuur saaks õigesti väljendatud.

Mõnikord räägitakse ka konkreetsest süntaksipuust, kus kõik terminalsümbolid on siiski esindatud, aga ei pruugi sisaldada kõiki parseri vahetippe.

Abstraktne süntaksipuu säilitab küll programmi tähenduse, aga selle põhjal ei saa taastada programmi esialgset kuju: näiteks on avaldisel 5 + (2 * 4) täpselt samasugune AST nagu meie näitel. Programmi interpreteerimisel või madala taseme keelde transleerimisel on palju mugavam toimetada andmestruktuuriga, mis sisaldab ainult olulist infot.

Aritmeetilise avaldise AST loomine

Alustame aritmeetilise avaldisega ja loome lihtsalt sellise primitiivse süntaksipuu, mis on lihtsalt käsitsi parseri Node klassi isenditest koosnev puu. Väljund peaks olema selline puu nagu üleval paremal pildil. See pilt ongi tegelikult sellesama ülesanne lahendusega loodud.

Selleks kasutame jällegi ArithBaseVisitor, aga factor erinevate harude asemel võime lihtsalt terminalide sõneesituse põhjal uue tipu tagastada.

        ArithVisitor<Node> visitor = new ArithBaseVisitor<Node>() {

            @Override
            public Node visitTerminal(TerminalNode terminal) {
                return new Node(terminal.getText());
            }

            @Override
            public Node visitBinaryExpr(BinaryExprContext ctx) {
                ...
            }

            @Override
            public Node visitBinaryTerm(BinaryTermContext ctx) {
                ...
            }

            @Override
            public Node visitParen(ParenContext ctx) {
                ...
            }
        };
        return visitor.visit(tree);

expr
    :   expr op='+' term     #BinaryExpr
    |   expr op='-' term     #BinaryExpr
    |   term                 #SimpleExpr
    ;

term
    :   term op='*' factor   #BinaryTerm
    |   term op='/' factor   #BinaryTerm
    |   factor               #SimpleTerm
    ;

factor
    :   '(' expr ')'         #Paren
    |   Variable             #Variable
    |   Literal              #Literal
    ;

AKTK abstraktne süntaksipuu

AKTK jaoks oleme disaininud ühe komplekti klasse, mille abil saaks panna just selle keele programmide olulise info. Teisisõnu, nende klassidega saab esitada AKTK programmide süntaksipuid. Need klassid sisalduvad paketis week7.ast.

Järgnev näide demonstreerib, kuidas kirjutada käsitsi abstraktne süntaksipuu avaldisele 5 + 2 *4.

    private static AstNode createSampleExpressionAst() {

        return new FunctionCall (
                "+",
                Arrays.asList(
                        new IntegerLiteral(5),
                        new FunctionCall (
                                "*",
                                Arrays.asList(
                                        new IntegerLiteral(2),
                                        new IntegerLiteral(4)
                                )
                        )
                )
        );
    }

Nagu näha (ja võibolla märkasid juba AstNode alamklasse uurides), ei ole meie abstraktses süntaksipuus eraldi mõistet operatsioonide jaoks -- liitmise, lahutamise ja teised unaarsed/binaarsed operatsioonid esitame me funktsiooni väljakutsetena, kus funktsiooni nimeks on lihtsalt vastav operaator. Kui me hakkame hiljem kirjutama AKTK interpretaatorit, siis on võibolla näha, miks taoline klasside kokkuhoid kasulik on. (Pane tähele, et abstraktse süntaksipuu juures ei pea me enam muretsema parsimise pärast -- kuigi AKTK konkreetne süntaks ei lubanud funktsiooni nimena kasutada sümbolit +, siis siin ei takista meid miski.)

Kui me tahame 5 + 2 *4 käsitleda kui täielikku AKTK programmi (mitte lihtsalt avaldist), siis tuleb meil avaldise AST-ile veel mõned kihid peale kasvatada:

	private static AstNode createSampleProgramAst() {
		return new Block (
			Arrays.asList (
				new ExpressionStatement((Expression) createSampleExpressionAst())
			)
		);
	}

See on kasulik selleks, et me edaspidi saaksime alati eeldada, et programm koosneb lausete jadast (mida me väljendame klassiga Block), hoolimata sellest, kas seal on üks lause või rohkem.

Loe Block-i ja teiste AST klasside otstarbe kohta täpsemaid selgitusi vastavate klasside lähtekoodist.