Automaadid, keeled ja translaatorid

Sissejuhatus

Teemat tutvustav video: ANTLR intro.

ANTLRi dokumentatsioonist saab väga põhjalikku infot selle kasutuse kohta. Kõige olulisemad on järgmised lehed:

• Parseri reeglid
• Lekseri reeglid

Grammatika loomine

Grammatikad peavad olema defineeritud .g4 laiendiga failis, mille nimi kattub nende grammatika nimega. Näiteks järgnev näitena toodud grammatika peaks olema defineeritud failis Arith.g4. Me edaspidi loome neid failid teie jaoks, sest kompileerimiseks on vaja, et nad läheks õigetesse pakettidesse. (Repos asub see näide demos paketis!)

grammar Arith; // grammatika nimi peab klappima failinimega
@header { package week7.demos; } // loodud failide pakett.

// parseri reeglid algavad väikeste tähtedega
expr
    :   expr '+' term
    |   expr '-' term
    |   term
    ;

term
    :   term '*' factor
    |   term '/' factor
    |   factor
    ;

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

// lekseri reeglid algavad suurte tähtedega
Variable
    :   [a-zA-Z_][a-zA-Z_0-9]*
    ;

Literal
    :   [0-9]|[1-9][0-9]+
    ;

// Järgmise lekseemi suuname ära (-> skip).
WS: [ \t\r\n]+ -> skip;

ANTLRis eristame kahte tüüpi reegleid - parserireegleid ning lekserireegleid.

• Parserireeglite muutujanimed algavad väiketähega. Need tähistavad mitteterminale. Erinevad produktsioonireeglid on eraldatud püstkriipsuga. Parserireegel võib sisaldada ka tühja reeglit, mis teeb selle reegli valikuliseks. Lisaks on võimalik kasutada ka operaatoreid ?, * ja +, mis on analoogid vastavate regulaaravaldiste operaatoritele.
• Lekserireeglite muutujanimed algavad suurtähega. Need lubavad meil defineerida terminalsümboleid paindlikumalt, kasutades regulaaravaldistele sarnast süntaksit. Terminalsümboleid võib lisada ka parserireeglite sisse kasutades ülakomasid.

Harjutus

Hea harjutus oleks mõni grammatika, näiteks siit lehelt nüüd ANTLRi abil kirjutada, et harjuda ANTLRi pluginaga. Pärast peab loodud parsepuud Java abil töötlema, aga sellega võime tegeleda järgmisel nädalal.

Kurjad lekserireeglid

Teemat tutvustav video: ANTLRi lekser.

Kuigi lekserireeglid võivad tunduda teisejärgulised ning "lihtsam" osa grammatika defineerimisest, siis tegelikult nõuavad lekserireeglid palju tähelepanu. Mõned näited lekseri "veidrast" käitumisest on paketis lexerdemos.

GreedyLexer.g4

Grammatika GreedyLexer.g4 võimaldab aru saada, kuidas lekserireeglid erinevad parserireeglitest. Seal on samasugune asi defineeritud kahel viisil: esiteks a tähtedega lekserireeglitega ja teiseks b tähtedega parserireeglitega. IntelliJ ANTLR pluginaga saab kontrollida, mis juhtub, kui sisestada teatud arv korduvaid a või b tähti. Huvitavad olukorrad on näiteks järgmised:

• aaaaaa vs bbbbbb – üks ei sobitu, aga teine sobitub;
• aaaaaaa vs bbbbbbb – mõlemad sobituvad, aga parsepuud on erinevad.

Priority.g4

Näiteks juhul kui üks sõnejupp sobitub kahe lekserireegliga, siis sellest sõnejupist saab esimesena defineeritud lekserireegli token. Grammatikas Priority.g4 reegel doubleRule on küll õigesti defineeritud, kuid kuna üldisem lekserireegel Kurjus sobitub kõigega, millega sobitub lekserireegel Tere, siis ka õige sisendiga "tere" saame me vea. Ja kahjuks ANTLRi veateade pole meie jaoks väga abistav:

line 1:0 mismatched input 'tere' expecting 'tere'

Number.g4

Sarnane olukord on ka näites Number.g4, aga seal võib olukorda ka lahendada võtmesõnaga fragment, sest seal on DIGIT ainult vaja täisarvude INT defineerimisel. Fragment tähendab, et lekseem iseseisvalt ei eksisteeri ja seetõttu ei sega lekseri tööd: teda lihtsalt kopeeritakse tähthaaval sinna sisse, kus teda kasutatakse.

Mõnikord on vaja ka arvestada sellega, et korduse kasutamisel on reeglid on võimalikult ahned. Korduse mitte-ahneks tegemine käis küsimärgi lisamisega, st * asemel *? ning + asemel +?.

Lekseri tükeldamise harjutamine

Grammatika Munch.g4 abil saab lahendada ühte tüüpi Moodle quizi ülesannet. Meil on antud lekseri reeglid ja peame oskama ennustada, kuidas see tükeldub lekseemideks. Kuna seda tüüpi küsimusi meeldib meile eksami Moodle quizis küsida, siis oleks hea kui oskate seda ANTLRi abil lahendada. (Lekseri tööpõhimõtte kohta olid lingid materjalidele sellel lehel.)

Tuntud keelte grammatikad

Kui paigaldusega läks kõik hästi, siis võid vaadata mõned näited grammatikate kohta. Terve hunnik ANTLRi grammatikate näited on järgmises GitHub repos:

https://github.com/antlr/grammars-v4

Edasi võid vaadata, kuidas päris programmeerimiskeelte dokumentatsioonides grammatikat spetsifitseeritakse.

• Java
  • Java 7 mitmene grammatika, mis kompaktselt defineerib keele süntaksi.
  • Java 7 avaldiste kihiline grammatika. See on üheselt parsitav ja selle läbi saab ka defineerida iga avaldise tähendust. Väike väljalõige sellest grammatikast: java_simple.txt. Java 8 enam mitmest grammatikat ei sisalda. Lõpus on lihtsalt kihilise grammatika kokkuvõtte: Java 8 kihiline grammatika.
  • Java ANTLR grammatika: Java mitmene grammatika, aga operaatorid on prioriteedi järjekorras ja vaikimisi vasakassotsiatiivsed. (Ainult omistamise puhul on assotsiatiivsus annotatsiooniga välja toodud.)
• Python
  • Pythoni abstraktne grammatika
• Kotlin
  • http://confluence.jetbrains.com/display/Kotlin/Grammar
• PHP
  • https://github.com/nikic/PHP-Parser/blob/master/grammar/zend_language_parser.phpy
• Ruby
  • http://web.njit.edu/all_topics/Prog_Lang_Docs/html/ruby/yacc.html
  • https://github.com/ruby/ruby/blob/trunk/parse.y
• SQL
  • Oracle SQL, SELECT lause
    • Kas select nimi, t.amet, tt.vanus, o.nimi osakonnanimi from tootajad t, osakonnad o where t.osakond = o.id on süntaktiliselt korrektne Oracle SQL lause?
  • ANTLR 3 PL/SQL grammatika
• Dokumentkeelte spetsifitseerimisel kasutatakse kontekstivaba grammatikate ja regulaaravaldiste segu (EBNF). Kuidas oleks näiteks <!ELEMENT p (#PCDATA | p | ul | dl | table | h1|h2|h3)*> grammatikana?