Arvutiteaduse instituut
  1. Esileht
  2. Automaadid, keeled ja translaatorid
EN
Logi sisse

Automaadid, keeled ja translaatorid

  • Üldinfo
  • Ajakava
  • Eksami näidised
  • Teemad
    • 1. Soojendus
    • 2. Regulaaravaldised
    • 3. Automaadid
    • 4. Avaldise struktuur
      • Avaldispuu läbimine
        • Pythoni avaldiste struktuur*
        • Java AST analüüs*
      • Eksami alusosa!
      • Regulaaravaldiste analüüs
      • Raskemad harjutused*
      • Isabelle*
      • Kodutöö
      • Minimeerimine*
    • 5. Grammatikad ja lekser
    • 6. Käsitsi parsimine
    • 7. ANTLRiga töötamine
    • 8. Interpretaator
    • 9. Kompilaator
    • 10. Edasi!
  • Huviring
  • Bitbucket
  • Moodle
  • Zulip
  • Zoom

Java süntaksipuu analüüs

Süntaksipuu mõiste kohta loe sissejuhatust lehelt Pythoni programmi struktuur.

Selle lisatöö eesmärk on Java süntakspuud uurida. Ülesannete kirjeldused on klassis week4.javaAnalysis.SimpleProgramAnalysis, mida saab esitada siia. Teised failid on testimise serveris olemas. Selle lahendamiseks on hea järgmised sissejuhatavad harjutused läbi teha.

AST View

AST View on pistikprogramm, mille abil saab vaadata redaktoris avatud Java programmi süntaksipuud. Jälgi järgmistel lehtedel juhendit, et enda IDEs seda paigaldada. (Kui Sa üldse ei tea, kuidas pistikprogramme paigaldada, siis pead kõigepealt seda endale selgeks tegema).

  • IntelliJ: https://plugins.jetbrains.com/plugin/9345-jdt-astview
  • Eclipse: https://eclipse.org/jdt/ui/astview/index.php

AST View ei ole hädavajalik, aga see võimaldab näha näidisprogrammide esitus süntakspuuna. Me kasutame siin Eclipse'i kompilaatori esitus, aga ülesanne saab samahästi lahendada ka IntelliJ abil.

AST View Harjutus

Ava klass week4.javaAnalysis.example.ASTViewDemo:


public class ASTViewDemo {
	public static void arvuta(String[] args) {
		System.out.println(liida(3, 6));
	}

	private static int arvuta(int a, int b) {
		return a + b * 2;
	}
}E

  • Otsi välja tipp, mis tähistab alamavaldist b * 2.
  • Mitmendal süntaksipuu tasemel see tipp asub, kui me loeme, et tipp tüübiga TypeDeclaration on tasemel 1?

Vihje: kui teed AST View tipul topeltklõpsu, siis näidatakse milline osa Java koodist sellele tipule vastab

Eclipse'i Java parser ja AST

Süntaksipuu käsitsi uurimine võib olla huvitav aga tüütu. Tüütute asjade tegemiseks tuleb teatavasti kirjutada programm. See programm peaks uurima sedasama puukujulist andmestruktuuri, millel baseerub ka AST View töö.

Programmi tekstist süntaksipuu (andmestruktuuri) saamiseks läheb vaja parserit. Parserite tegemine on selle aine üks põhiteema, aga praegu me kasutame teiste poolt tehtud parserit, täpsemalt Eclipse'i Java parserit.

Esimene katsetus

Lisatöö example pakettis on ka näidisprogram SimpleJavaASTDemo, millele saab anda ette mingi Java faili ja mis kuvab ekraanile kõik selles leiduvad muutuja-, välja-, -klassi, paketi- ja meetodinimed. (Vaikimisi kasutab ta argumendina enda lähetkood, seega proovi teda lihtsalt käivitada!). Loodetavasti näed programmi väljundis rida nimesid.

Java AST

Eclipse'i Java AST on puukujuline andmestruktuur, mille tipud on tüüpi org.eclipse.jdt.core.dom.ASTNode. Puu moodustamiseks ja juurtipu kättesaamiseks sai selle aine jaoks tehtud abimeetod JavaASTUtils.parseCompilationUnit ning tipu alluvate küsimiseks abimeetod JavaASTUtils.getChildNodes. (Kes tahab näha, kuidas puud luua ja läbida ise, võiks vaadata siia või siia.)

Enamasti ei piisa meil programmide analüüsimisel ainult puu kuju teadmisest -- me tahame teada ka millist programmi konstruktsiooni mingi tipp tähistab. Nagu võib aimata reast if (node instanceof SimpleName simpleName), on iga tipp tegelikult mitte otseselt klassi ASTNode isend, vaid kuulub mõnesse ASTNode alamklassi.

Uuri natuke Eclipse'i Java AST dokumentatsiooni, eriti neid klasse, mida on lisatöö ülesande püstituses mainitud!

Harjutus: Süntaksipuu tippude küsimine teades tipu tüüpi

Proovi Eclipse'i AST dokumentatsiooni ja AST View abil ennustada, mida kuvab järgnev meetod, kui seda kutsuda välja selle lehe alguses toodud ASTViewDemo süntaksipuuga:

...
	private static void doSomething(ASTNode node, String source) {

		CompilationUnit compUnit = (CompilationUnit) node;
		TypeDeclaration typeDecl = (TypeDeclaration) compUnit.types().get(0);
		Block body = typeDecl.getMethods()[1].getBody();
		ReturnStatement returnStmt = (ReturnStatement) body.statements().get(0);
		InfixExpression returnExpr = (InfixExpression)returnStmt.getExpression();
		Expression subExpr = returnExpr.getRightOperand();

		System.out.println(source.substring(
				subExpr.getStartPosition(),
				subExpr.getStartPosition() + subExpr.getLength()
		));

	}
...

Harjutus: Eelneva kombineerimine

Enamasti on vaja programmide analüüsimisel kombineerida puu läbimise võtteid, kus me tipu tüüpi ei arvesta (otsi ülaltpoolt JavaASTUtils.getChildNodes(node)), tipu tüübi tuvastamist (if (node instanceof SimpleName simpleName)) ning konkreetsele tiputüübile spetsiifilist infot (simpleName.getIdentifier()).

Eclipse'i Java AST-i teegis on muidugi ka olemas ASTVisitor, millega neid süntaksipuid töödelda.

Proovi nüüd kirjutada programm, mis võtab ette mingi Java faili ja ütleb:

  • Mitu if-lauset esineb selles programmis?
  • Mitu neist on ilma else-haruta?
  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Tartu Ülikooli arvutiteaduse instituudi kursuste läbiviimist toetavad järgmised programmid:
euroopa sotsiaalfondi logo