Kihagyás

ANTLR: ANother Tool for Language Recognition

Feladat (f02)

Adott az

1
2
3
S -> '+' A A | '*' A A
A -> szam | S
szam = [0-9]+

nyelvtan. Készíts hozzá egy ANTLR 4 elemzőt, ami hagyományos infix formában kiírja a kifejezést és kiszámolja a kifejezés értékét! Az elemző a paraméterben kapott nevű fájl tartalmát dolgozza fel.

Példa bemenet

input.txt

1
* * 2 3 + 3 4

Először is próbáljuk meg átültetni a nyelvtant az ANTLR .g4-es formátumára. Induljunk ki egy minimális g4 nyelvtanfájlból. Egy S -> A | B | t szabály (illetve ez 3 azonos jobboldalú szabály) például s : a | b | T; lesz, amit szebben

1
2
3
4
5
s
    : a
    | b
    | T
    ;
alakban írunk. Egy t = [0-9]+ tokendefiníció pedig T : [0-9]+; alakban írható. A szabályokban használhatunk "inline" tokendefiníciókat is, pl. a fenti kombináció
1
2
3
4
5
6
s
    : a
    | b
    | T
    ;
T : [0-9]+;
helyett
1
2
3
4
s
    : a
    | b
    | '[0-9]+';
alakban is megadható. A nemterminálisokat kisbetűvel, a terminális tokeneket pedig nagybetűvel írjuk. (Ezek nem csak egy-egy betűből állhatnak.)

Töltsük le az ANTLR jar fájlt, ami az elemző generálásához és a Java-s generált elemző futtatásához szükséges osztályokat is tartalmazza.

Az elemző forrásait a java -jar antlr-4.9.3-complete.jar Simple.g4 parancs segítségével tudjuk legenerálni. Nézzük meg, hogy milyen Java nyelvű forrásfájlokat generált a fenti parancs!

A generált forrásokat a javac -cp .:antlr-4.9.3-complete.jar *.java parancs segítségével tudjuk lefordítani.

Az elemző nyelve

Megjegyzendő, hogy az elemző generálását mindenképpen egy Java nyelvű program végzi, de ez nem csak Java, hanem például C++ vagy Python nyelvű forráskódot is generálhat. Az így generált elemző fordításához/futtatásához további elemek szükségesek (például Java esetén az alapvető .class fájlok, C++ esetén header fájlok és az alapvető osztályokat/függvényeket megvalósító library is).

1. lépés: csak nyelvtan

Simple.g4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
grammar Simple;

options {
    language = Java;
}

start
    : MUVELET operand operand ;

operand
    : SZAM
    | start ;

SZAM       : [0-9]+;
MUVELET    : [*+];
WHITESPACE : [ \t\r\n]+ -> skip;

  • Elemző generálás: java -jar antlr-4.9.3-complete.jar Simple.g4
  • Elemző fordítás: javac -cp .:antlr-4.9.3-complete.jar *.java
    • Ez így még nem futtatható.

Hogyan tehetjük futtathatóvá az elemzőt? A nyelvtanban lehetőségünk van kódrészleteknek a megadására, amiket az elemző generálásakor az ANTLR a megfelelő helyekre be fog szúrni:

  • global scope:
    • @header { ... }: a ... a fájl elejére lesz beszúrva
    • @members { ... }: a ... az elemző osztályba lesz beszúrva
  • szabály scope (a szabály : jele elé beszúrva):
    • @init { ... }: a szabály metódusának elejére lesz beszúrva a ...
    • @after { ... }: a szabály metódusának végére lesz beszúrva a ...
A beszúrható kódrészletek

Az ANTLR a beszúrandó kódrészleteken csak jól meghatározott, nagyon minimális változtatásokat képes elvégezni. Mivel ezek a kódrészletek a genrált elemző forráskódjába fognak bekerülni, a generálás nyelvén kell őket megírni. A gyakorlaton ez a Java nyelv lesz.

2. lépés: elemzés

Simple.g4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
grammar Simple;

options {
    language = Java;
}

@members {
    public static void main(String[] args) throws Exception {
         SimpleLexer lex = new SimpleLexer(new ANTLRFileStream(args[0]));
         CommonTokenStream tokens = new CommonTokenStream (lex);
         SimpleParser parser = new SimpleParser(tokens);
         System.out.println("=" + parser.start().value);
    }
}

start
    : MUVELET operand operand ;

operand
    : SZAM
    | start ;

SZAM       : [0-9]+;
MUVELET    : [*+];
WHITESPACE : [ \t\r\n]+ -> skip;

  • Elemző generálás: java -jar antlr-4.9.3-complete.jar Simple.g4
  • Elemző fordítás: javac -cp .:antlr-4.9.3-complete.jar *.java
  • Elemző futtatás: java -cp .:antlr-4.9.3-complete.jar SimpleParser input.txt

Hogyan fogunk számolni? Ehhez több dolog szükséges:

  • Az egyes nyelvtani szabályokhoz szemantikus akciókat rendelhetünk. Ezek a nyelvtani szabályokba beszúrt { ... } alakú kódrészletek, melyek az elemzés során ott és akkor lesznek végrehajtva, amikor az elemzés az adott ponthoz ér.
    • Ezekben az akciókban hivatkozhatunk a szabályban (korábban) szereplő elemekre (tokenekre és nemterminálisokra). A szabályban szereplő TOKEN tokenre vagy rule nemterminálisra az akcióban (a { ... } részben) a $TOKEN vagy $rule azonosítókkal hivatkozhatunk, illetve lehetőségünk van ezeket megcímkézni, elnevezni a label=TOKEN vagy 'label=rule' formában, ami után $label-ként hivatkozhatunk rájuk (ez kifejezetten jól jön, ha a szabályban egy adott nemterminális vagy token többször is szerepel). A tokeneknek többek között .text, .int vagy .line attribútumaik is vannak, amiket az akciókban a megfelelő módon felhasználhatunk.
  • Az egyes szabályoknak lehetnek attribútumaik, vagy másképpen fogalmazva paramétereik és visszatérési értékeik.
    • A szabályok általános alakja: rule [ ptype1 par1, ... ] returns [ rtype1 ret1, ... ] locals [ ltype1 loc1, ...] : ...
    • Paraméterekkel rendelkező szabályt alkalmazni ("meghívni") csak megfelelő paraméterezéssel lehet: rule [arg1, ...]
    • Visszatérési érték(ek)kel rendelkező szabály által visszaadott értékek kezelése: sub=rule [arg1, ...] { ... $sub.ret1 ... }
3. lépés: számolás

Simple.g4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
grammar Simple;

options {
    language = Java;
}

@members {
    public static void main(String[] args) throws Exception {
         SimpleLexer lex = new SimpleLexer(new ANTLRFileStream(args[0]));
         CommonTokenStream tokens = new CommonTokenStream (lex);
         SimpleParser parser = new SimpleParser(tokens);
         System.out.println("=" + parser.start().value);
    }                                                           
}

start returns [ int value ]
    : MUVELET o1=operand { System.out.print($MUVELET.text); }
              o2=operand { $value = ("+".equals($MUVELET.text)) ? $o1.value + $o2.value : $o1.value * $o2.value; } ;

operand returns [ int value ]
    : SZAM { $value = $SZAM.int; System.out.print($SZAM.text); }
    | { System.out.print("("); } sub=start { $value = $sub.value; System.out.print(")"); } ;

SZAM       : [0-9]+;
MUVELET    : [*+];
WHITESPACE : [ \t\r\n]+ -> skip;

  • Elemző generálás: java -jar antlr-4.9.3-complete.jar Simple.g4
  • Elemző fordítás: javac -cp .:antlr-4.9.3-complete.jar *.java
  • Elemző futtatás: java -cp .:antlr-4.9.3-complete.jar SimpleParser input.txt

Utolsó frissítés: 2022-01-10 11:51:41