Kihagyás

ANTLR: Bináris számok

Feladat (f03)

Adott az alábbi attribútumnyelvtan, amely bináris törtek értékének kiszámítására képes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
S → N₁ '.' N₂
        S.v  := N₁.v + N₂.v
        N₁.r := 0
        N₂.r := -N₂.l
N₀ → N₁ B
        N₀.v := N₁.v + B.v
        N₀.l := N₁.l + 1
        N₁.r := N₀.r + 1
        B.r  := N₀.r
N → λ
        N₀.v := 0
        N₀.l := 0
B → '0'
        B.v  := 0
B → '1'
        B.v  := 2^(B.r)

A nyelvtan alapján készítsünk egy ANTLR nyelvtant, ami elvégzi a számítást!

Példa bemenet

input.txt 

1
11111100101.011

Jelenlegi ismereteink szerint az ANTLR-rel csak egy menetben, az elemzés során (balról jobbra) kiértékelhető attribútumnyelvtanokat tudunk kiértékelni. Alakítsuk át a fenti nyelvtant egymenetessé.

Egymenetes bináris tört kiértékelő 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
S → N₁ '.' N₂
        S.v  := N₁.v + N₂.v / 2^(N₂.l)
N₀ → N₁ B
        N₀.v := 2 * N₁.v + B.v
        N₀.l := N₁.l + 1
N → λ
        N₀.v := 0
        N₀.l := 0
B → '0'
        B.v  := 0
B → '1'
        B.v  := 1

Az átírás ANTLR nyelvanná ezek után eléggé nyilvánvaló. Az örökölt attribútumok a szabályok paraméterei, a szintetizált attribútumok a visszatérési értékei lesznek. (Bár most örökölt attribútumok nincsenek.)

Tükörfordítás attribútumnyelvtanról ANTLR-re

Binary.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
27
28
grammar Binary;

options {
    language = Java;
}

@members {
    public static void main(String[] args) throws Exception {
         BinaryLexer lex = new BinaryLexer(new ANTLRFileStream(args[0]));
         CommonTokenStream tokens = new CommonTokenStream (lex);
         BinaryParser parser = new BinaryParser(tokens);
         System.out.println("=" + parser.s().v);
    }                                                           
}

s returns [ double v ]
    : n1=n '.' n2=n { $v = $n1.v + $n2.v / Math.pow(2.0, $n2.l); }
    ;

n returns [ int v, int l ]
    : n1=n b1=b { $v = 2 * $n1.v + $b1.v; $l = $n1.l + 1; }
    | { $v = 0; $l = 0; }
    ;

b returns [ int v ]
    : '0' { $v = 0; }
    | '1' { $v = 1; }
    ;

Bár a fenti nyelvtant az ANTLR megeszi, és még ki is javítja a programozó hanyagságát, azért vegyük észre, hogy a nyelvtan nem LL(k), sőt, balrekurzív! Javítsuk ezt, és közben az egyik nemterminálist tokenné alakíthatjuk.

Nem balrekurzív nyelvtan és ANTLR megvalósítása 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
S → N₁ '.' N₂
        S.v  := N₁.v + N₂.v / 2^(N₂.l)
N₀ → B N₁
        N₀.v := B.v * 2^(N₁.l) + N₁.v + B.v
        N₀.l := N₁.l + 1
N → λ
        N₀.v := 0
        N₀.l := 0
B → '0'
        B.v  := 0
B → '1'
        B.v  := 1

Binary.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 Binary;

options {
    language = Java;
}

@members {
    public static void main(String[] args) throws Exception {
         BinaryLexer lex = new BinaryLexer(new ANTLRFileStream(args[0]));
         CommonTokenStream tokens = new CommonTokenStream (lex);
         BinaryParser parser = new BinaryParser(tokens);
         System.out.println("=" + parser.s().v);
    }                                                           
}

s returns [ double v ]
    : n1=n '.' n2=n { $v = $n1.v + $n2.v / Math.pow(2.0, $n2.l + 1); }
    ;

n returns [ double v, int l ]
    : B n { $l = $n.l + 1; $v = $B.int * Math.pow(2.0, $l) + $n.v; }
    | { $v = 0.0; $l = -1; }
    ;

B : [01] ;

Utolsó frissítés: 2023-02-02 13:09:36