Automata, Languages and Compilers 2017/18 spring

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:

Siin tipud avaldis0, avaldis1, avaldis2, avaldis5, avaldis, programm ja lause teatud mõttes lihtsalt müra -- nad ei andnud mingit infot selle avaldise kohta. Programmi interpreteerimisel või madala taseme keelde transleerimisel oleks aga palju mugavam toimetada andmestruktuuriga, mis sisaldab ainult olulist infot.

Sama programmi olulise info saaksime me esitada näiteks sellise puuga:

Taolist minimalistlikku esitust nimetatakse abstraktseks süntaksipuuks (ingl.k abstract syntax tree ehk AST). (Parse-puud nimetatakse mõnikord konkreetseks süntaksipuuks.)

AKTK abstraktne süntaksipuu

AKTK jaoks oleme me 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 week9.ast.

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

import java.util.Arrays;
import week9.ast.AstNode;
import week9.ast.FunctionCall;
import week9.ast.IntegerLiteral;
...
	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 nüüd ei takista meid miski.)

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

import java.util.Arrays;
import week9.ast.AstNode;
import week9.ast.Block;
import week9.ast.Expression;
import week9.ast.ExpressionStatement;
import week9.ast.FunctionCall;
import week9.ast.IntegerLiteral;
...
	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.