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:
2023-02-02 13:09:36