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
    • 5. Grammatikad ja lekser
    • 6. Käsitsi parsimine
      • Avaldisgrammatikad
      • Implementatsioon
      • Vasakrekursioon
      • Ennustav parsimine*
      • Lausearvutus*
      • Kodutöö
    • 7. ANTLRiga töötamine
    • 8. Interpretaator
    • 9. Kompilaator
    • 10. Edasi!
  • Huviring
  • Bitbucket
  • Moodle
  • Zulip
  • Zoom

Vasakrekursiooni elimineerimine

Loengus käsitletakse palju formaalsemalt vasakrekursiooni eemaldamist ja sellisel tasemel on kasulik see endale eksami teooria osaks selgeks teha, aga praegu on peamine eesmärk näidede põhjal kõhutunnet arendada. Kuna regulaaravaldised on juba selged ja me teame, et iga regulaaravaldis on ka grammatikana kirja pandav, siis väljendame asju pigem regulaaravaldistena.

Kirjutage järgmised grammatikad ümber regulaaravaldistena:

  • S → Sa | x
  • S → Sa | x | y
  • S → Sa | Sb | x | y
  • S → Sa | Sb | x | y | ε

Nüüd võib, kui on aega palju, ka vaadata, kuidas neid teisendada tagasi grammatikaks, aga pigem kasutades paremrekursiooni. Selleks tuuakse sisse lisareegel, mis selle kordamist teostab.

OriginaalneRegulaaravaldisTeisendatud
S → Sa
S → x

S → xa*


S → xR
R → aR
R → ε

Natuke suurem näide

Kui oled ülalolevad näited läbi teinud, siis tegelikult oled juba kõiki võimalusi näinud, aga Sa pead lihtsalt ära tabama, et vasakrekursiooni eemaldamise mõttes on järgmised kolm grammatikat samamoodi käsitletavad:

  • S → Sa | x
  • S → SaS | x
  • S → Sõöäü | aSbS | ε

Kui Sa ei usu, siis pane õigetesse kohtadesse sulud, näiteks S(õöäü) ja a(SbS). Proovime järgmisest grammatikast vasakrekursiooni elimineerida:

S → 'sala'
S → S 'kala'
S → S 'maja'
S → ε

Meil on siin kaks produktsiooni S → 'sala' ja S → ε, mis ei ole vasakrekursiivsed, ja kaks produktsiooni S → S 'kala' ja S → S 'maja', mis on vasakrekursiivsed. Mis on tulemus?

Alustame mitterekursiivsetest reeglitest, mida saab regulaaravaldisena kokku kirjutada: ('sala' | ε) ehk lihtsalt ('sala')?. Edasi jätkame vasakrekursiivsete reeglite S-ile järgnevate osade itereerimisega: ( 'kala' | 'maja' )*. Kokku saame siis:

S → ('sala')? ('kala'|'maja')*

EBNF Grammatika teisendamine koodiks

Grammatikates kasutatakse väga tihti neid regulaaravaldiste lisamugavusi. Sellist notatsiooni nimetatakse EBNFiks (Extended Backus–Naur form). Sellisel kujul grammatika saab ka teisendada koodiks ja ASTi tagastamiseks on see lihtsam võrreldes Varmo meetodiga. Kui oled ise lahendanud, siis võid eelmise näite vastuse ära vaadata ja võrrelda järgmise koodiga:

    void s() throws ParseException {
        if (peek() == 's') {
            match("sala");
        }
        while (peek() == 'k' || peek() == 'm') {
            switch(peek()) {
                case 'k':
                    match("kala");
                    break;
                default:
                    match("maja");
            }
        }
    }

Lihtsad ülesanded

Proovi nüüd ise järgmise grammatikaga seda teha:

S → a | b | c
S → Sx | Sy

Ja mis nüüd saab, kui lihtsate tähtede asemel paneme midagi keerulisemat?

S → A | b | cA
S → SX | SyX
A → aA | a
X → x | zXz

Avaldisgrammatika ASTi genereerimine


Mõtleme nüüd ka selle peale, kuidas avaldisgrammatikate korral abstraktset süntaksipuud tagastada. Näiteks avaldise x+x*x+x jaoks tahame sellist lihtsat puud nagu paremal pildil kujutatud. Kui seda teha meie soovitud EBNF grammatika põhjal, siis see ei ole väga keeruline:

E → T(+T)*
T → F(*F)*
F → (E)
F → x

Mõtle kõigepealt näidetega see kõik läbi, kui Sul on lihtsalt terve rida plussiga eraldatud liidetavaid. Ehk joonista järgmiste avaldiste ASTid:

  • x
  • x+x
  • (x+x)+x
  • ... kuni saad aru, kuidas saad seda programmis esitada.

Pane siin tähele, et sellise avaldise, kus kogu aeg "lisad" ühe x-i juurde, ei tohiks ju olla struktuuri mõttes väga erinev programmist arvutab 0, 0+1, (0+1)+1, ... Seega, kui oskad kirjutada (enam-vähem mõistliku) programmi, mis väljastab ekraanile arvud 0,1,2,3,..., siis sealt ei ole üldsegi suur samm kirjutada programm, mis vasakassotsiatiivse operaatori ASTi ehitaks.

  • 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