Automata, Languages and Compilers 2019/20 spring

Sissejuhatus

ANTLR'i 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 faili teie jaoks, sest kompileerimiseks on vaja, et ta läheks õigesse paketti. (Repos asub ta ülalmainitud demos paketis!)

grammar Arith; // grammatika nimi peab klappima failinimega
@header { package week7.demos; } // Seda on vaja, et loodud failid läheks õige paketti.

// 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;

ANTLR'is eristame kahte tüüpi reegleid - parserireegleid ning lekserireegleid.

Parserireeglite muutujanimed algavad väiketähega ning 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 ?*+, 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.

Kurjad lekserireeglid

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 ANTLR'i 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'i 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 ANTLR 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üntaks.
  • 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 spec 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?