Infix kifejezések: AST építés
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)
|
Az eddigi megoldások az elemzéssel (nagyjából) párhuzamosan értékelték ki a kifejezéseket.
Ez eddig elegendő volt, de ezzel a módszerrel biztosan nem tudunk mindent megoldani (gondoljunk a többmenetes kiértékelésre).
Válasszuk szét az elemzést és a kiértékelést!
Az elemzés során építsünk fel egy AST-t, de ne értékeljük ki egyből, párhuzamosan az elemzéssel!
A kiértékelés egy (vagy több) külön menet legyen, miután teljesen végeztünk az elemzéssel.
Hogyan nézne ki az AST, milyen node-okból állna?
Gyakorlatilag az elemzési fát kell felépítenünk, talán annyi kis alkalmazkodással, hogy nem feltétlenül a tényleges nyelvtant kell tükröznie,
hanem már némi szemantikát is belevihetünk.
A nyelvtanunkban például az additív műveleteknek az elemzése egy (változó számú) sokgyerekes csomópontként van megoldva,
holott ezek a műveletek binárisak.
Ha a "lapos" elemzési fa helyett megfelelő módon építjük fel bináris elemekből az AST-t,
akkor magának az AST-nek a szerkezete biztosíthatja majd a megfelelő kiértékelési sorrendet is.
Ezek alapján az AST node-jai a következők lehetnek (de másféle megoldások is szóba jöhetnek!):
A ''Főprogram'' AST node-ja
Program.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | package ast;
import java.util.*;
public class Program {
private List<Line> lines = new ArrayList<Line>();
public void addLine(Line l) {
lines.add(l);
}
public void evaluate() {
for (Line l: lines) {
l.evaluate();
}
}
}
|
Egy sor AST node-ja
Line.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | package ast;
public class Line {
private boolean assign;
private Expression expr;
private Program program;
public Line(Program p, Expression e, boolean a) {
this.program = p;
this.expr = e;
this.assign = a;
}
public void evaluate() {
double value = 0.0;
if (this.assign) {
}
System.out.println(value);
}
}
|
A kifejezések AST node-jainak ősosztálya
Expression.java
| package ast;
public abstract class Expression {
//public abstract double evaluate(Program prog);
}
|
Különféle kifejezések node-jai
Abs.java
| package ast;
public class Abs extends Expression {
private Expression exp;
public Abs(Expression exp) {
this.exp = exp;
}
}
|
Add.java
| package ast;
public class Add extends Expression {
private Expression lhs;
private Expression rhs;
public Add(Expression lhs, Expression rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
}
|
Const.java
| package ast;
public class Const extends Expression {
private double value;
public Const(String token) {
this.value = Double.parseDouble(token);
}
}
|
Max.java
| package ast;
public class Max extends Expression {
private Expression lhs;
private Expression rhs;
public Max(Expression lhs, Expression rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
}
|
Pwr.java
1
2
3
4
5
6
7
8
9
10
11
12
13 | package ast;
public class Pwr extends Expression {
private Expression lhs;
private Expression rhs;
public Pwr(Expression lhs, Expression rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
public Expression rightNode() {
return rhs;
}
}
|
SignP.java
| package ast;
public class SignP extends Expression {
private Expression exp;
public SignP(Expression exp) {
this.exp = exp;
}
}
|
A fenti AST elemeket egyben itt találjátok.
Induljunk ki az utolsó nyelvtanból, de a szemantikus akcióit felejtsük el!
Nem a kifejezést kell ugyanis elemzés közben kiértékelni, hanem az elemzési fát kell felépíteni.
A részfákkal ugyanúgy tudunk bánni, mint a kifejezések értékeivel: egy szabály felépíti és visszaadja a szabályból levezethető rész AST-jét,
amit az őt meghívó szabály beépít majd a saját részfájába.
Az alól egyedül az AST gyökere, a Program node a kivétel, azt előre (az elemzés kezdete előtt) létrehozzuk,
és az elemzés paraméterként kapja majd meg.
Van még egy "trükk", amit ebben a példában alkalmazunk:
Ha a min/max -nak egyetlen operandusa van, akkor az operátor elhagyható, hiszen egyetlen számból álló sorozat esetében annak minimuma és maximuma az egyetlen sorozatelem.
Ha pedig legalább két operandusa van, akkor ugyanúgy bináris operátorként fel tudjuk építeni, mint mondjuk az összeadások vagy a hatványozások sorozatát.
Ezzel ugyan elveszítjük a "forráskódban" fellelhető felesleges min/max operátorokat, de a végeredmény értékét ez nem befolyásolja (és mellesleg egyszerűbb lesz számolni).
Számológép: AST felépítése
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 | grammar Calculator;
options {
language = Java;
}
@members {
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);
ast.Program p = new ast.Program();
parser.start(p);
}
}
start [ ast.Program p ]
: ((line[p] { $p.addLine($line.node); } )? COMMENT? LF)* EOF
;
line [ ast.Program p ] returns [ ast.Line node ]
: MEMORY '=' expr { $node = new ast.Line($p, $expr.node, true); }
| expr { $node = new ast.Line($p, $expr.node, false); }
;
expr returns [ ast.Expression node ]
: fstop=addop { $node = $fstop.node; } (OPADD nxtop=addop {
if ("+".equals($OPADD.text)) $node = new ast.Add($node, $nxtop.node);
else $node = new ast.Sub($node, $nxtop.node);
})*
;
addop returns [ ast.Expression node ]
: fstop=mulop { $node = $fstop.node; } (OPMUL nxtop=mulop {
if ("*".equals($OPMUL.text)) $node = new ast.Mul($node, $nxtop.node);
else $node = new ast.Div($node, $nxtop.node);
})*
;
mulop returns [ ast.Expression node ]
: fstop=fct { $node = $fstop.node; } (OPPWR nxtop=mulop { $node = new ast.Pwr($node, $nxtop.node); })?
;
fct returns [ ast.Expression node ]
: SZAM { $node = new ast.Const($SZAM.text); }
| '(' expr { $node = $expr.node; } ')'
| 'abs' '(' expr ')' { $node = new ast.Abs($expr.node); }
| OPMINMAX '(' fstop=expr { $node = $fstop.node; } (',' nxtop=expr {
if ("min".equals($OPMINMAX.text)) $node = new ast.Min($node, $nxtop.node);
else $node = new ast.Max($node, $nxtop.node);
}) * ')'
| OPADD fct { $node = "-".equals($OPADD.text) ? new ast.SignM($fct.node) : new ast.SignP($fct.node); }
| MEMORY { $node = new ast.Memory(); }
;
LF : '\n' ;
WS : [ \t\r]+ ->skip ;
SZAM : [0-9]+('.' [0-9]+)? ;
OPADD : '+' | '-' ;
OPMUL : '*' | '/' ;
OPPWR : '^' ;
OPMINMAX : 'min' | 'max' ;
MEMORY : 'M' ;
COMMENT : '#' (~[\n])* ;
|
Ahhoz, hogy mindez működjön is, el kell készítenünk az AST elemeit is.
A fenti példákból kiindulva (azokat kiegészítve illetve a hiányzó elemeket ezek alapján elkészítve) ezek a következők lehetnek:
A ''Főprogram'' és a sorok AST node-jai
Program.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | package ast;
import java.util.*;
public class Program {
private List<Line> lines = new ArrayList<Line>();
public void addLine(Line l) {
lines.add(l);
}
public void evaluate() {
for (Line l: lines) {
l.evaluate();
}
}
}
|
Line.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | package ast;
public class Line {
private boolean assign;
private Expression expr;
private Program program;
public Line(Program p, Expression e, boolean a) {
this.program = p;
this.expr = e;
this.assign = a;
}
public void evaluate() {
double value = 0.0;
if (this.assign) {
}
System.out.println(value);
}
}
|
A kifejezések AST node-jainak ősosztálya
Expression.java
| package ast;
public abstract class Expression {
//public abstract double evaluate(Program prog);
}
|
''Levelek'', 0 operandusú kifejezések
Const.java
| package ast;
public class Const extends Expression {
private double value;
public Const(String token) {
this.value = Double.parseDouble(token);
}
}
|
Memory.java
| package ast;
public class Memory extends Expression {
public Memory() {
}
}
|
Unáris kifejezések node-jai
Abs.java
| package ast;
public class Abs extends Expression {
private Expression exp;
public Abs(Expression exp) {
this.exp = exp;
}
}
|
SignM.java
| package ast;
public class SignM extends Expression {
private Expression exp;
public SignM(Expression exp) {
this.exp = exp;
}
}
|
SignP.java
| package ast;
public class SignP extends Expression {
private Expression exp;
public SignP(Expression exp) {
this.exp = exp;
}
}
|
Bináris kifejezések node-jai
Add.java
| package ast;
public class Add extends Expression {
private Expression lhs;
private Expression rhs;
public Add(Expression lhs, Expression rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
}
|
Div.java
| package ast;
public class Div extends Expression {
private Expression lhs;
private Expression rhs;
public Div(Expression lhs, Expression rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
}
|
Max.java
| package ast;
public class Max extends Expression {
private Expression lhs;
private Expression rhs;
public Max(Expression lhs, Expression rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
}
|
Min.java
| package ast;
public class Min extends Expression {
private Expression lhs;
private Expression rhs;
public Min(Expression lhs, Expression rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
}
|
Mul.java
| package ast;
public class Mul extends Expression {
private Expression lhs;
private Expression rhs;
public Mul(Expression lhs, Expression rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
}
|
Pwr.java
1
2
3
4
5
6
7
8
9
10
11
12
13 | package ast;
public class Pwr extends Expression {
private Expression lhs;
private Expression rhs;
public Pwr(Expression lhs, Expression rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
public Expression rightNode() {
return rhs;
}
}
|
Sub.java
| package ast;
public class Sub extends Expression {
private Expression lhs;
private Expression rhs;
public Sub(Expression lhs, Expression rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
}
|
Utolsó frissítés:
2023-02-02 13:09:36