Kihagyás

Infix kifejezések: kiértékelés elemzés közben

Feladat (f05)

Írjunk nyelvtant a számológéphez, amely soronként egy-egy kifejezést vár. A kifejezésben értelmezett

  • a 4 matematikai alapművelet,
  • a hatványozás (^),
  • a zárójelezés,
  • az előjelváltás (-) és megtartás (+),
  • mindezek megfelelő prioritással kezelve,
  • az abs() függvény egy paraméterrel,
  • a min() és max() függvények legalább egy paraméterrel, és
  • az M mint memóriarekeszben tárolt érték (melynek kezdetben 0 az értéke).

A számológép soronként olvas és értékel ki.

  • Egy sorban egy kifejezés szerepel.
  • Ha a sor M = tokenekkel lezdődik, akkor az = után szerplő kifejezés értékét el kell menteni a memóriarekeszbe.
  • Az üres sor megengedett.
  • Egy sorban a # utáni rész komment, eldobható.
  • A sorvége jelen kívül az egyéb whitespace karakterek bárhol megengedettek.

Készítsünk egy ANTLR4 nyelvtant, ami megvalósítja a számológépet.

Példa bemenet

input.txt

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
42
24 + 18
6 + 12 + 24
6 * 7
6 + 6 * 6
6 * (3 + 4)
84 / 2
12 + (3 * (25 / 5)) - 9 + (2*3*4)
abs ( -42 )
max ( -42, +42 )
min(42.0,63.222,77.07)
6 + 2*6 + 2^2*6
M = (5 + 18 / 9 - 1) ^ 2 + abs( -12 / 2)
M * 3 / (1 - -2)
# Komment

M = M / 2 / 3
M * (M - 1)

Van már egy elemzőnk, most egészítsük ki, hogy ki is értékelje a kifejezéseket. Két dolog lesz, ami új illetve eltér a korábban már látottaktól.

  • Az egyik a memória, ami a kiértékelés szempontjából egy globális változó lesz. Ezt az elemző osztály attribútumaként meg tudjuk oldani.
  • A másik a hatványozás, ami az eddigi balról jobbra kiértékelés helyett jobbról balra asszociatív. Vagyis a 2^3^5 kifejezést nem (2^3)^5=8^5=2^15 módon, hanem 2^(3^5)=2^243 módon kell kiértékelni. A nyelvtan balról jobbra történő elemzése miatt ez nem megy teljesen párhuzamosan az elemzéssel, a mulop kiértékelésénél be kell várni az utolsó fct értékét is, és utána tudjuk mintegy visszafelé kiszámolni a mulop értékét. Szerencsére egy verem segítségével könnyen meg tudjuk oldani a problémát: a sorban érkező fct értékeit beletesszük a verembe, majd a szabály végén a verem tetején lévő két értékre elvégezzük a hatványozást, és az eredményt visszarakjuk a verembe. Amikor a veremben már csak egy érték marad, az lesz a (rész)kifejezés értéke.
Számológép: kiértékelés

Calculator.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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
grammar Calculator;

options {
    language = Java;
}

@members {
    private double memorySlot = 0.0;
    public static void main(String[] args) throws Exception {
        CalculatorLexer lex = new CalculatorLexer(new ANTLRFileStream(args[0]));
        CommonTokenStream tokens = new CommonTokenStream (lex);
        CalculatorParser parser = new CalculatorParser(tokens);
        parser.start();
    }
}

start
    : (line? COMMENT? LF)* EOF
    ;

line
    : MEMORY '=' expr { memorySlot = $expr.value; System.out.println($MEMORY.text + " = " + $expr.value); }
    | expr { System.out.println($expr.value); }
    ;

expr returns [double value]
    : fstop=addop { $value = $fstop.value; } (OPADD nxtop=addop { if ("+".equals($OPADD.text)) $value += $nxtop.value; else $value -= $nxtop.value; })*
    ;

addop returns [double value]
    : fstop=mulop { $value = $fstop.value; } (OPMUL nxtop=mulop { if ("*".equals($OPMUL.text)) $value *= $nxtop.value; else $value /= $nxtop.value; })*
    ;

mulop returns [double value]
    : { java.util.Stack<Double> valueStack = new java.util.Stack<Double>(); }
        fstop=fct { valueStack.push(new Double($fstop.value)); } (OPPWR nxtop=fct { valueStack.push(new Double($nxtop.value)); })* {
        while (valueStack.size() > 1) {
            double powr = valueStack.pop().doubleValue();
            double base = valueStack.pop().doubleValue();
            valueStack.push(new Double(Math.pow(base, powr)));
        }
        $value = valueStack.pop().doubleValue();
    }
    ;

fct returns [double value]
    : SZAM { $value = Double.parseDouble($SZAM.text); }
    | '(' expr ')' { $value = $expr.value; }
    | 'abs' '(' expr ')' { $value = Math.abs($expr.value); }
    | OPMINMAX '(' fstop=expr { $value = $fstop.value; } (',' nxtop=expr  {
        if ("min".equals(OPMINMAX) && $nxtop.value < $value) $value = $nxtop.value;
        else if ("max".equals(OPMINMAX) && $nxtop.value > $value) $value = $nxtop.value;
    }) * ')'
    | OPADD fct { $value = "-".equals($OPADD.text) ? -$fct.value : $fct.value; }
    | MEMORY { $value = memorySlot; }
    ;

LF       : '\n' ;
WS       : [ \t\r]+ ->skip ;
SZAM     : [0-9]+('.' [0-9]+)? ;
OPADD    : '+' | '-' ;
OPMUL    : '*' | '/' ;
OPPWR    : '^' ;
OPMINMAX : 'min' | 'max' ;
MEMORY   : 'M' ;
COMMENT  : '#' (~[\n])* ;

A hatványozás megoldására van egy másik lehetőség is: alakítsuk át a nyelvtant úgy, hogy a hatványozás részfáit ne egy szinten, egymás mellé építse, hanem binárisan úgy, hogy a kiértékelési sorrend tükröződjön a hierarchiában. Vagyis a mulop ne egy vagy több fct szimpla sorozatából álljon, hanem a bal oldali fct részfa mellett a jobb oldalon megint csak egy hatványozás (mulop) szerepelhessen (de ez el is maradhat).

Számológép: kiértékelés

Calculator.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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
grammar Calculator;

options {
    language = Java;
}

@members {
    private double memorySlot = 0.0;
    public static void main(String[] args) throws Exception {
        CalculatorLexer lex = new CalculatorLexer(new ANTLRFileStream(args[0]));
        CommonTokenStream tokens = new CommonTokenStream (lex);
        CalculatorParser parser = new CalculatorParser(tokens);
        parser.start();
    }
}

start
    : (line? COMMENT? LF)* EOF
    ;

line
    : MEMORY '=' expr { memorySlot = $expr.value; System.out.println($MEMORY.text + " = " + $expr.value); }
    | expr { System.out.println($expr.value); }
    ;

expr returns [double value]
    : fstop=addop { $value = $fstop.value; } (OPADD nxtop=addop { if ("+".equals($OPADD.text)) $value += $nxtop.value; else $value -= $nxtop.value; })*
    ;

addop returns [double value]
    : fstop=mulop { $value = $fstop.value; } (OPMUL nxtop=mulop { if ("*".equals($OPMUL.text)) $value *= $nxtop.value; else $value /= $nxtop.value; })*
    ;

mulop returns [double value]
    : fstop=fct { $value = $fstop.value; } (OPPWR nxtop=mulop { $value = Math.pow($value, $nxtop.value); })?
    ;

fct returns [double value]
    : SZAM { $value = Double.parseDouble($SZAM.text); }
    | '(' expr ')' { $value = $expr.value; }
    | 'abs' '(' expr ')' { $value = Math.abs($expr.value); }
    | OPMINMAX '(' fstop=expr { $value = $fstop.value; } (',' nxtop=expr  {
        if ("min".equals(OPMINMAX) && $nxtop.value < $value) $value = $nxtop.value;
        else if ("max".equals(OPMINMAX) && $nxtop.value > $value) $value = $nxtop.value;
    }) * ')'
    | OPADD fct { $value = "-".equals($OPADD.text) ? -$fct.value : $fct.value; }
    | MEMORY { $value = memorySlot; }
    ;

LF       : '\n' ;
WS       : [ \t\r]+ ->skip ;
SZAM     : [0-9]+('.' [0-9]+)? ;
OPADD    : '+' | '-' ;
OPMUL    : '*' | '/' ;
OPPWR    : '^' ;
OPMINMAX : 'min' | 'max' ;
MEMORY   : 'M' ;
COMMENT  : '#' (~[\n])* ;


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