Függvények kezelése
Feladat (f10)
Írjunk nyelvtant egy egyszerű programnyelvhez.
A programnyelv egyszerű kifejezéseket értékel ki, amelyekben értelmezett
- a 4 matematikai alapművelet,
- a hatványozás (
^),
- a zárójelezés,
- az előjelváltás (
-) és megtartás (+),
- logikai operátorokat (
not, and, or),
- relációs operátorokat,
- mindezek megfelelő prioritással kezelve,
- az
abs operátor,
- a sztring típusú értéket, melynek megadására az aposztróf és idézőjel is használható,
- a sztring határolójele a
\' vagy \" escape szekvenciával a sztringben is használható,
- sztringekre értelmezett a
+ művelet mint konkatenáció (számok automatikusan sztringgé konvertálódnak, ha kell),
- a függvényhívás nulla vagy több bemenő módú argumentummal, és
- az angol ábécé betűjével kezdődő, a továbbiakban aláhúzást, számot és/vagy az angol ábécé betűit tartalmazó azonosító mint változó (amiknek kezdetben 0 az értéke).
A program a következőképpen néz ki:
- Egy sorban egy utasítás vagy változódeklaráció szerepelhet.
- Egy utasítás lehet egy szimpla kifejezés.
- A nyelv ismeri az
if-then-else-end, while-do-end, és for-in-do-end vezérlési szerkezeteket (összetett utasításokat).
- A
for egy adott intervallum elemein megy végig egyesével növekvő sorrendben (a szintaxisért lásd a példa inputot).
- Az összetett vezérléseknél bizonyos helyeken megengedett a sortörés.
- A kiértékelés során nincs automatikus kiíratás, van viszont a nyelvben
print(.) utasítás.
- A változókat a
var kulcsszó segítségével első használatuk előtt deklarálni kell.
- Ha a sor egy azonosítóval és az
= tokennel lezdődik, akkor az = után szerplő kifejezés értékét el kell menteni a megfelelő memóriarekeszbe.
- A függvénydefiníció a
function tokennel kezdődik, majd függvénynév, pereméterlista, az utasításai (amelyekben szerepelhet a return utasítás is), végül az end kulcsszó.
- A függvényen belül deklarált változók lokálisak, és "eltakarják" a globális változókat.
- 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 az ilyen programok kiértékelését.
Példa bemenet
input.txt
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 | function answer()
return "42"
end
answer()
function diff(x, y)
if x < y
then return y - x
else return x - y
end
end
diff (24, 18)
var A
var M
var S
M = 1
A = diff ( (5 + 18 / 9 - 1) ^ 2 , abs -12 / 2 )
S = "Hello!"
while A > 0 do
A = A - 1
M = A / M
S = S + '!'
print (A + ": " + S)
end
A * 3 / (1 - -2)
# Komment
S = S + ' Vilag!'
M = A / 2 / 3
var I
for I in (A, 10) do
print ( S + " " + I * (I - 1))
end
|
Külön Lexer és Parser
Induljunk ki az előző órai megoldásból:
A nyelvtan
Functions.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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167 | grammar Functions;
options {
language = Java;
}
@header {
import java.util.ArrayList;
import java.util.List;
}
@members {
public static void main(String[] args) throws Exception {
FunctionsLexer lex = new FunctionsLexer(new ANTLRFileStream(args[0]));
CommonTokenStream tokens = new CommonTokenStream (lex);
FunctionsParser parser = new FunctionsParser(tokens);
parser.start(args.length > 1 && "--generate".equals(args[1]));
}
}
start [ boolean genSrc ]
@init{ ast.Program p = new ast.Program(); }
@after{ if (genSrc) {
System.out.println(p);
} else {
p.execute();
}
}
: sequence[p] { p.addStatements($sequence.node); } EOF
;
sequence [ ast.Program prog ] returns [ ast.Sequence node ]
: { $node = new ast.Sequence(prog); } (statement[prog] LF+ { $node.addStatement($statement.node); })+
;
statement [ ast.Program prog ] returns [ ast.Statement node ]
: expr
{ $node = new ast.ExprStmt($prog, $expr.node); }
| ID '=' expr
{ $node = new ast.Assignment($prog, $ID.text, $expr.node); }
| { ast.Statement fbnode = null; }
KW_IF ic=logical_expr LF*
KW_THEN LF* tb=sequence[prog] LF*
( KW_ELSE LF* fb=sequence[prog] LF* { fbnode = $fb.node; } )?
KW_END
{ $node = new ast.If($prog, $ic.node, $tb.node, fbnode); }
| KW_WHILE wc=logical_expr LF*
KW_DO LF* wb=sequence[prog] LF*
KW_END
{ $node = new ast.While($prog, $wc.node, $wb.node); }
| KW_FOR ID KW_IN LPAR beg=expr OPLST end=expr RPAR LF*
KW_DO LF* lb=sequence[prog] LF*
KW_END
{ $node = new ast.For($prog, $ID.text, $beg.node, $end.node, $lb.node); }
| KW_RET expr
{ $node = new ast.Return($prog, $expr.node); }
| KW_VAR ID
{ $node = new ast.VarDecl($prog, $ID.text); }
| KW_FUNC fname=ID LPAR parlist RPAR LF sequence[prog] KW_END
{ ast.Function fnc = new ast.Function($fname.text, $parlist.list);
fnc.addStatements($sequence.node);
$prog.addFunction(fnc);
$node = new ast.FncDecl($prog, fnc);
}
| KW_PRINT LPAR expr RPAR
{ $node = new ast.Print($prog, $expr.node); }
;
parlist returns [ List<String> list ]
: { $list = new ArrayList<String>(); }
( fstpar=ID { $list.add($fstpar.text); }
( OPLST nxtpar=ID { $list.add($nxtpar.text); } )*
)?
;
expr returns [ ast.Expression node ]
: logical_expr { $node=$logical_expr.node; }
| num_expr { $node=$num_expr.node; }
;
logical_expr returns [ ast.Expression node ]
: fstop=logical_tag { $node = $fstop.node; }
(OPOR nxtop=logical_tag { $node = new ast.Binary($OPOR.text, $node, $nxtop.node); })*
;
logical_tag returns [ ast.Expression node ]
: fstop=logical_fct { $node = $fstop.node; }
(OPAND nxtop=logical_fct { $node = new ast.Binary($OPAND.text, $node, $nxtop.node); })*
;
logical_fct returns [ ast.Expression node ]
: rel=num_expr op=(OPEQ|OPREL) rer=num_expr { $node = new ast.Binary($op.text, $rel.node, $rer.node); }
| OPNOT logical_fct { $node = new ast.Unary($OPNOT.text, $logical_fct.node); }
| LPAR logical_expr RPAR { $node = new ast.Parens($logical_expr.node); } RPAR
| vr=variable { $node = $vr.node; }
| fr=functioncall { $node = $fr.node; }
;
num_expr returns [ ast.Expression node ]
: fstop=addop { $node = $fstop.node; }
(OPADD nxtop=addop { $node = new ast.Binary($OPADD.text, $node, $nxtop.node); })*
;
addop returns [ ast.Expression node ]
: fstop=mulop { $node = $fstop.node; } (OPMUL nxtop=mulop {
$node = new ast.Binary($OPMUL.text, $node, $nxtop.node);
})*
;
mulop returns [ ast.Expression node ]
: fstop=num_fct { $node = $fstop.node; } (OPPWR nxtop=mulop {
$node = new ast.Binary($OPPWR.text, $node, $nxtop.node);
})?
;
num_fct returns [ ast.Expression node ]
: SZAM { $node = new ast.Const($SZAM.text); }
| LPAR num_expr { $node = new ast.Parens($num_expr.node); } RPAR
| op=(OPADD|OPABS) num_fct { $node = new ast.Unary($op.text, $num_fct.node); }
| vr=variable { $node = $vr.node; }
| fr=functioncall { $node = $fr.node; }
;
variable returns [ ast.Expression node ]
: ID { $node = new ast.Variable($ID.text); }
;
functioncall returns [ ast.Expression node ]
: ID LPAR arglist RPAR { $node = new ast.FunctionCall($ID.text, $arglist.list); }
;
arglist returns [ List<ast.Expression> list ]
: { $list = new ArrayList<ast.Expression>(); }
( fstarg=expr { $list.add($fstarg.node); }
( OPLST nxtarg=expr { $list.add($nxtarg.node); } )*
)?
;
LF : '\n' ;
WS : [ \t\r]+ ->skip ;
KW_DO : 'do' ;
KW_ELSE : 'else' ;
KW_END : 'end' ;
KW_FOR : 'for' ;
KW_FUNC : 'function' ;
KW_IF : 'if' ;
KW_IN : 'in' ;
KW_PRINT : 'print' ;
KW_RET : 'return' ;
KW_THEN : 'then' ;
KW_VAR : 'var' ;
KW_WHILE : 'while' ;
SZAM : [0-9]+('.' [0-9]+)? ;
OPOR : 'or' ;
OPAND : 'and' ;
OPNOT : 'not' ;
OPREL : '<' | '<=' | '>' | '>=' ;
OPEQ : '==' | '!=' ;
OPADD : '+' | '-' ;
OPMUL : '*' | '/' ;
OPPWR : '^' ;
OPABS : 'abs' ;
OPLST : ',' ;
LPAR : '(' ;
RPAR : ')' ;
ID : [A-Za-z][_0-9A-Za-z]* ;
COMMENT : '#' (~[\n])* ->skip ;
|
Első körben szedjük szét a nyelvtant egy Lexer-re és egy Parser-re.
A trükk az, hogy grammar helyett lexer grammar és parser grammar -ral kezdjük a fájlokat.
Figyeljünk oda, hogy a parsernek az options { tokenVocab = ... }-bal megadjuk, hogy mi a lexer, amivel dolgoznia kell,
és hogy ilyenkor a parser-ben nem lehet tokendefiníció (jelen esetben az = mint értékadás operátornak kell új tokent definiálni).
A sztringek (az escape sequence-ek miatt) önmagukban is összetettebb tokenek lesznek, ezért nekik tokenosztályokat (módokat) definiálunk,
egyet-egyet az ' és az " karakterekkel kezdődő sztringeknek.
Amikor a DEFAULT_MODE tokenosztályban megtaláljuk a kezdő karaktereket, módot váltunk mode(.), de jelezzük, hogy ez a karakter a következő tokenhez tartozik majd (more).
Vagyis nem lesznek külön STRABEG és STRQBEG tokenjeink.
Az tokenosztályokban megfelelőképpen kezeljük az adott speciális karaktereket, majd a lezárás után megint módot váltunk (vissza).
Hogy ne kétféle sztringünk legyen, a felismerésnék az STRAEND és STRQEND helyett is a STRING tokentípust "használjuk" (type(.)).
A két tokenosztályban a fragment-ek nem valódi tokenek, csak bennünket segítenek.
Persze a nyelvtanba (parser) is be kell szúrni a STRING tokenek felismerését, de ez talán nem olyan nehéz.
A sztringet mint érték típust, és az esetleges hibás műveleteket (pl. sztring osztása) nem a nyelvtan, hanem a kiértékelés fogja lekezelni (már ahogy).
A nyelvtan
FunctionsLexer.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 | lexer grammar FunctionsLexer;
options {
language = Java;
}
tokens { STRING }
LF : '\n' ;
WS : [ \t\r]+ ->skip ;
KW_DO : 'do' ;
KW_ELSE : 'else' ;
KW_END : 'end' ;
KW_FOR : 'for' ;
KW_FUNC : 'function' ;
KW_IF : 'if' ;
KW_IN : 'in' ;
KW_PRINT : 'print' ;
KW_RET : 'return' ;
KW_THEN : 'then' ;
KW_VAR : 'var' ;
KW_WHILE : 'while' ;
SZAM : [0-9]+('.' [0-9]+)? ;
OPASSIGN : '=' ;
OPOR : 'or' ;
OPAND : 'and' ;
OPNOT : 'not' ;
OPREL : '<' | '<=' | '>' | '>=' ;
OPEQ : '==' | '!=' ;
OPADD : '+' | '-' ;
OPMUL : '*' | '/' ;
OPPWR : '^' ;
OPABS : 'abs' ;
OPLST : ',' ;
LPAR : '(' ;
RPAR : ')' ;
ID : [A-Za-z][_0-9A-Za-z]* ;
COMMENT : '#' (~[\n])* ->skip ;
STRABEG : '\'' -> mode(ASTR), more ;
STRQBEG : '"' -> mode(QSTR), more ;
mode ASTR;
fragment STRA : ~[\r\n\\']+ ;
fragment STRAESC : '\\\\' | '\\\'' ;
STRAEND : ( STRA | STRAESC )* '\'' ->type(STRING), mode(DEFAULT_MODE);
mode QSTR;
fragment STRQ : ~[\r\n\\"]+ ;
fragment STRQESC : '\\\\' | '\\"' ;
STRQEND : ( STRQ | STRQESC )* '"' ->type(STRING), mode(DEFAULT_MODE);
|
FunctionsParser.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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139 | parser grammar FunctionsParser;
options {
tokenVocab = FunctionsLexer;
language = Java;
}
@header {
import java.util.ArrayList;
import java.util.List;
}
@members {
public static void main(String[] args) throws Exception {
FunctionsLexer lex = new FunctionsLexer(CharStreams.fromFileName(args[0]));
CommonTokenStream tokens = new CommonTokenStream (lex);
FunctionsParser parser = new FunctionsParser(tokens);
parser.start(args.length > 1 && "--generate".equals(args[1]));
}
}
start [ boolean genSrc ]
@init{ ast.Program p = new ast.Program(); }
@after{ if (genSrc) {
System.out.println(p);
} else {
p.execute();
}
}
: sequence[p] { p.addStatements($sequence.node); } EOF
;
sequence [ ast.Program prog ] returns [ ast.Sequence node ]
: { $node = new ast.Sequence(prog); } (statement[prog] LF+ { $node.addStatement($statement.node); })+
;
statement [ ast.Program prog ] returns [ ast.Statement node ]
: expr
{ $node = new ast.ExprStmt($prog, $expr.node); }
| ID OPASSIGN expr
{ $node = new ast.Assignment($prog, $ID.text, $expr.node); }
| { ast.Statement fbnode = null; }
KW_IF ic=logical_expr LF*
KW_THEN LF* tb=sequence[prog] LF*
( KW_ELSE LF* fb=sequence[prog] LF* { fbnode = $fb.node; } )?
KW_END
{ $node = new ast.If($prog, $ic.node, $tb.node, fbnode); }
| KW_WHILE wc=logical_expr LF*
KW_DO LF* wb=sequence[prog] LF*
KW_END
{ $node = new ast.While($prog, $wc.node, $wb.node); }
| KW_FOR ID KW_IN LPAR beg=expr OPLST end=expr RPAR LF*
KW_DO LF* lb=sequence[prog] LF*
KW_END
{ $node = new ast.For($prog, $ID.text, $beg.node, $end.node, $lb.node); }
| KW_RET expr
{ $node = new ast.Return($prog, $expr.node); }
| KW_VAR ID
{ $node = new ast.VarDecl($prog, $ID.text); }
| KW_FUNC fname=ID LPAR parlist RPAR LF sequence[prog] KW_END
{ ast.Function fnc = new ast.Function($fname.text, $parlist.list);
fnc.addStatements($sequence.node);
$prog.addFunction(fnc);
$node = new ast.FncDecl($prog, fnc);
}
| KW_PRINT LPAR expr RPAR
{ $node = new ast.Print($prog, $expr.node); }
;
parlist returns [ List<String> list ]
: { $list = new ArrayList<String>(); }
( fstpar=ID { $list.add($fstpar.text); }
( OPLST nxtpar=ID { $list.add($nxtpar.text); } )*
)?
;
expr returns [ ast.Expression node ]
: logical_expr { $node=$logical_expr.node; }
| num_expr { $node=$num_expr.node; }
;
logical_expr returns [ ast.Expression node ]
: fstop=logical_tag { $node = $fstop.node; }
(OPOR nxtop=logical_tag { $node = new ast.Binary($OPOR.text, $node, $nxtop.node); })*
;
logical_tag returns [ ast.Expression node ]
: fstop=logical_fct { $node = $fstop.node; }
(OPAND nxtop=logical_fct { $node = new ast.Binary($OPAND.text, $node, $nxtop.node); })*
;
logical_fct returns [ ast.Expression node ]
: rel=num_expr op=(OPEQ|OPREL) rer=num_expr { $node = new ast.Binary($op.text, $rel.node, $rer.node); }
| OPNOT logical_fct { $node = new ast.Unary($OPNOT.text, $logical_fct.node); }
| LPAR logical_expr { $node = new ast.Parens($logical_expr.node); } RPAR
| vr=variable { $node = $vr.node; }
| fr=functioncall { $node = $fr.node; }
;
num_expr returns [ ast.Expression node ]
: fstop=addop { $node = $fstop.node; }
(OPADD nxtop=addop { $node = new ast.Binary($OPADD.text, $node, $nxtop.node); })*
;
addop returns [ ast.Expression node ]
: fstop=mulop { $node = $fstop.node; } (OPMUL nxtop=mulop {
$node = new ast.Binary($OPMUL.text, $node, $nxtop.node);
})*
;
mulop returns [ ast.Expression node ]
: fstop=num_fct { $node = $fstop.node; } (OPPWR nxtop=mulop {
$node = new ast.Binary($OPPWR.text, $node, $nxtop.node);
})?
;
num_fct returns [ ast.Expression node ]
: SZAM { $node = new ast.Const($SZAM.text); }
| STRING { $node = new ast.Const($STRING.text); }
| LPAR num_expr { $node = new ast.Parens($num_expr.node); } RPAR
| op=(OPADD|OPABS) num_fct { $node = new ast.Unary($op.text, $num_fct.node); }
| vr=variable { $node = $vr.node; }
| fr=functioncall { $node = $fr.node; }
;
variable returns [ ast.Expression node ]
: ID { $node = new ast.Variable($ID.text); }
;
functioncall returns [ ast.Expression node ]
: ID LPAR arglist RPAR { $node = new ast.FunctionCall($ID.text, $arglist.list); }
;
arglist returns [ List<ast.Expression> list ]
: { $list = new ArrayList<ast.Expression>(); }
( fstarg=expr { $list.add($fstarg.node); }
( OPLST nxtarg=expr { $list.add($nxtarg.node); } )*
)?
;
|
Ahhoz, hogy a sztringeket valóban kezelni is tudjuk, a Value, Const és Binary AST node-okat kell módosítanunk.
A Value változik a legtöbbet, az eddigi kettő (logikai, szám) értéktípus helyett három lesz.
A sztringnek az értékét mint értéket, és nem mint reprezentációt tároljuk (arra ott van a Const típus literal mezője).
A Value AST node
Value.java
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 | package ast;
public class Value {
public enum ValueKind { BOOLEAN, NUMBER, STRING };
private final ValueKind kind;
private final boolean bVal;
private final double dVal;
private final String sVal;
public Value(boolean v) {
this.kind = ValueKind.BOOLEAN;
this.bVal = v;
this.dVal = 0.0;
this.sVal = null;
}
public Value(double v) {
this.kind = ValueKind.NUMBER;
this.bVal = false;
this.dVal = v;
this.sVal = null;
}
public Value(String v) {
this.kind = ValueKind.STRING;
this.bVal = false;
this.dVal = 0.0;
this.sVal = v;
}
public boolean isString() {
return kind == ValueKind.STRING;
}
public boolean getLogicValue() {
if (this.kind != ValueKind.BOOLEAN) {
throw new RuntimeException("Not a logic value!");
}
return this.bVal;
}
public double getNumericValue() {
if (this.kind != ValueKind.NUMBER) {
throw new RuntimeException("Not a numeric value!");
}
return this.dVal;
}
public String getStringValue() {
if (this.kind != ValueKind.STRING) {
throw new RuntimeException("Not a string value!");
}
return this.sVal;
}
public String toString() {
switch (this.kind) {
case BOOLEAN: return this.bVal ? "true" : "false";
case NUMBER: return Double.toString(this.dVal);
case STRING: return this.sVal;
}
return null;
}
}
|
A Const feladata azzal bővül, hogy a megfelelő típusú értéket tárolja el.
Ez ugye vagy egy szám, vagy egy sztring (logikai konstansaink nincsenek); akkor utóbbi, ha sztringhatároló karakterekkel kezdődik.
A Const AST node
Const.java
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 | package ast;
public class Const extends Expression {
private String literal;
private Value value;
public Const(String literal) {
this.literal = literal;
char first = literal.charAt(0);
if (first == '\'' || first == '"') {
if (first == '"') {
literal = literal.replaceAll("\\\\\"", "\"");
} else {
literal = literal.replaceAll("\\\\'", "'");
}
this.value = new Value(literal.substring(1, literal.length() - 1));
} else {
this.value = new Value(Double.parseDouble(literal));
}
}
@Override
public Value evaluate(Program p) {
return this.value;
}
@Override
public String toString() {
return this.literal;
}
}
|
És ami még hiányzik: az összeadást (de csak azt) a sztringekre is definiálni kell.
A Binary AST node
Binary.java
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
67
68
69
70
71
72
73
74
75 | package ast;
import java.io.*;
public class Binary extends Expression {
private enum BinaryOperator {
ADD("+"), SUB("-"), MUL("*"), DIV("/"), PWR("^"),
LT("<"), LTE("<="), GT(">"), GTE(">="),
EQ("=="), NE("!=");
private String text;
private BinaryOperator(String text) {
this.text = text;
}
public static BinaryOperator getBinaryOperator(String text) {
for (BinaryOperator b : BinaryOperator.values()) {
if (b.toString().equals(text)) {
return b;
}
}
return null;
}
public String toString() {
return this.text;
}
}
private BinaryOperator op = null;
private Expression lhsNode = null;
private Expression rhsNode = null;
public Binary(String op, Expression lhs, Expression rhs) {
this.op = BinaryOperator.getBinaryOperator(op);
this.lhsNode = lhs;
this.rhsNode = rhs;
}
@Override
public Value evaluate(Program p) {
final double EPS = 1e-10;
Value lhs = this.lhsNode.evaluate(p);
Value rhs = this.rhsNode.evaluate(p);
switch (this.op) {
case ADD: {
if (lhs.isString() || rhs.isString()) {
String ls = lhs.isString() ? lhs.getStringValue() : lhs.toString();
String rs = rhs.isString() ? rhs.getStringValue() : rhs.toString();
return new Value(ls + rs);
} else {
return new Value(lhs.getNumericValue() + rhs.getNumericValue());
}
}
case SUB: return new Value(lhs.getNumericValue() - rhs.getNumericValue());
case MUL: return new Value(lhs.getNumericValue() * rhs.getNumericValue());
case DIV: return new Value(lhs.getNumericValue() / rhs.getNumericValue());
case PWR: return new Value(Math.pow(lhs.getNumericValue(), rhs.getNumericValue()));
case LT : return new Value( (lhs.getNumericValue() < rhs.getNumericValue()) &&
(Math.abs(lhs.getNumericValue() - rhs.getNumericValue()) >= EPS) );
case LTE: return new Value( (lhs.getNumericValue() < rhs.getNumericValue()) ||
(Math.abs(lhs.getNumericValue() - rhs.getNumericValue()) < EPS));
case GT : return new Value( (lhs.getNumericValue() > rhs.getNumericValue()) &&
(Math.abs(lhs.getNumericValue() - rhs.getNumericValue()) >= EPS) );
case GTE: return new Value( (lhs.getNumericValue() > rhs.getNumericValue()) ||
(Math.abs(lhs.getNumericValue() - rhs.getNumericValue()) < EPS));
case EQ : return new Value(Math.abs(lhs.getNumericValue() - rhs.getNumericValue()) < EPS);
case NE : return new Value(Math.abs(lhs.getNumericValue() - rhs.getNumericValue()) >= EPS);
}
return null;
}
@Override
public String toString() {
if (lhsNode == null) System.out.println("l.<NULL>");
if (rhsNode == null) System.out.println("r.<NULL>");
return lhsNode.toString() + " " + op.toString() + " " + rhsNode.toString();
}
}
|
Visitor-ok
Az eddigiek során szemantikus akciókkal oldottuk meg az AST építését.
Valójában az elemző a nyelvtan alapján maga is épít egy saját AST-t, és a visitor-ok segítségével megtehetjük, hogy ezt az AST-t járjuk be.
Ennek több előnye is van.
Egyrészt a nyelvtan megtisztul, megszabadul a szemantikus akcióktól (azok gyakorlatilag a visitor-ba lesznek kiszervezve).
Másrészt a visitor-ok segítségével a bejárási sorrendet is szabályozni tudjuk (ugye saját AST-t is ezért építettünk).
Először is tisztítsuk meg a nyelvtant, és ahol sok alternatíva van, ott adjunk nekik nevet (#név formában), és készítsünk egy visitor objektumot is.
Fontos, hogy az elemzés után magunknak kell kezdeményeznünk a bejárást az elemző által visszaadott elemzési fa gyökerének vizitálásával.
A tiszta nyelvtan
FunctionsLexer.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 | lexer grammar FunctionsLexer;
options {
language = Java;
}
tokens { STRING }
LF : '\n' ;
WS : [ \t\r]+ ->skip ;
KW_DO : 'do' ;
KW_ELSE : 'else' ;
KW_END : 'end' ;
KW_FOR : 'for' ;
KW_FUNC : 'function' ;
KW_IF : 'if' ;
KW_IN : 'in' ;
KW_PRINT : 'print' ;
KW_RET : 'return' ;
KW_THEN : 'then' ;
KW_VAR : 'var' ;
KW_WHILE : 'while' ;
SZAM : [0-9]+('.' [0-9]+)? ;
OPASSIGN : '=' ;
OPOR : 'or' ;
OPAND : 'and' ;
OPNOT : 'not' ;
OPREL : '<' | '<=' | '>' | '>=' ;
OPEQ : '==' | '!=' ;
OPADD : '+' | '-' ;
OPMUL : '*' | '/' ;
OPPWR : '^' ;
OPABS : 'abs' ;
OPLST : ',' ;
LPAR : '(' ;
RPAR : ')' ;
ID : [A-Za-z][_0-9A-Za-z]* ;
COMMENT : '#' (~[\n])* ->skip ;
STRABEG : '\'' -> mode(ASTR), more ;
STRQBEG : '"' -> mode(QSTR), more ;
mode ASTR;
fragment STRA : ~[\r\n\\']+ ;
fragment STRAESC : '\\\\' | '\\\'' ;
STRAEND : ( STRA | STRAESC )* '\'' ->type(STRING), mode(DEFAULT_MODE);
mode QSTR;
fragment STRQ : ~[\r\n\\"]+ ;
fragment STRQESC : '\\\\' | '\\"' ;
STRQEND : ( STRQ | STRQESC )* '"' ->type(STRING), mode(DEFAULT_MODE);
|
FunctionsParser.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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118 | parser grammar FunctionsParser;
options {
tokenVocab = FunctionsLexer;
language = Java;
}
@header {
import java.util.ArrayList;
import java.util.List;
}
@members {
public static void main(String[] args) throws Exception {
FunctionsLexer lex = new FunctionsLexer(CharStreams.fromFileName(args[0]));
CommonTokenStream tokens = new CommonTokenStream (lex);
FunctionsParser parser = new FunctionsParser(tokens);
ParseTree tree = parser.start();
FunctionsVisitor visitor = new FunctionsVisitor();
ast.Program p = (ast.Program) (visitor.visit(tree));
if (args.length > 1 && "--generate".equals(args[1])) {
System.out.println(p);
} else {
p.execute();
}
}
}
start
: sequence EOF
;
sequence
: (statement LF+ )+
;
statement
: expr #exprStatement
| ID OPASSIGN expr #assignStatement
| KW_IF logical_expr LF*
KW_THEN LF* tb=sequence LF*
( KW_ELSE LF*
fb=sequence LF*
)?
KW_END #ifStatement
| KW_WHILE logical_expr LF*
KW_DO LF*
sequence LF*
KW_END #whileStatement
| KW_FOR ID KW_IN LPAR beg=expr OPLST end=expr RPAR LF*
KW_DO LF* sequence LF*
KW_END #forStatement
| KW_RET expr #returnStatement
| KW_VAR ID #declarationStatement
| KW_FUNC ID LPAR parlist RPAR LF
sequence
KW_END #functionStatement
| KW_PRINT LPAR expr RPAR #printStatement
;
parlist
: ( ID ( OPLST ID )* )?
;
expr
: logical_expr
| num_expr
;
logical_expr
: logical_tag ( OPOR logical_tag )*
;
logical_tag
: logical_fct ( OPAND logical_fct )*
;
logical_fct
: rel=num_expr op=( OPEQ | OPREL ) rer=num_expr #relational
| OPNOT logical_fct #logUnary
| LPAR logical_expr RPAR #logParens
| variable #logVariable
| functioncall #logFunctionCall
;
num_expr
: addop ( OPADD addop )*
;
addop
: mulop ( OPMUL mulop )*
;
mulop
: num_fct ( OPPWR mulop )?
;
num_fct
: SZAM #numLiteral
| STRING #strLiteral
| LPAR num_expr RPAR #numParens
| op=( OPADD | OPABS ) num_fct #numUnary
| variable #numVariable
| functioncall #numFunctionCall
;
variable
: ID
;
functioncall
: ID LPAR arglist RPAR
;
arglist
: ( expr ( OPLST expr )* )?
;
|
A nyelvtanból (Java) forráskód generálásakor az ANTLR-nek meg kell adni a -visitors kapcsolót,
ez le fog generálni egy ...ParserVisitor interfészt (FunctionsParserVisitor.java) és egy ...ParserBaseVisitor osztályt (FunctionsParserBaseVisitor.java),
mindkettő generikus.
(Meg generál még hasonló ...Listener.java-kat is, az egy másikfajta módszer az elemző saját AST-jének bejárására, csak ott a bejárási sorrend adott).
Ezekben a visitorok-ban megtalálhatjuk, hogy milyen lehetőségeink vannak a bejárás során, milyen elemeket tudunk meglátogatni.
Fontos, hogy a részfák bejárásáról (vizitálásáról) nekünk kell gondoskodnunk (szemben a listener-ekkel, ahol a bejárás független).
Mi most annyit csinálunk, hogy amit eddig szemantikus akciókkal oldottunk meg -- vagyis az általunk definiált AST felépítését --, azt vizitorokban csináljuk meg.
A saját visitor-unk
FunctionsVisitor.java
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183 | import java.util.List;
import org.antlr.v4.runtime.tree.TerminalNode;
import org.antlr.v4.runtime.tree.ParseTree;
public class FunctionsVisitor extends FunctionsParserBaseVisitor<ast.ASTNode> {
private ast.Program prog;
@Override
public ast.Program visitStart(FunctionsParser.StartContext ctx) {
this.prog = new ast.Program();
this.prog.addStatements((ast.Sequence)(this.visit(ctx.sequence())));
return this.prog;
}
@Override
public ast.Sequence visitSequence(FunctionsParser.SequenceContext ctx) {
ast.Sequence node = new ast.Sequence(this.prog);
for (FunctionsParser.StatementContext stmt : ctx.statement()) {
node.addStatement((ast.Statement)(this.visit(stmt)));
}
return node;
}
@Override
public ast.ExprStmt visitExprStatement(FunctionsParser.ExprStatementContext ctx) {
ast.ExprStmt node = new ast.ExprStmt(this.prog,
(ast.Expression)(this.visit(ctx.expr()))
);
return node;
}
@Override public ast.Assignment visitAssignStatement(FunctionsParser.AssignStatementContext ctx) {
ast.Assignment node = new ast.Assignment(this.prog,
ctx.ID().getText(),
(ast.Expression)(this.visit(ctx.expr()))
);
return node;
}
@Override public ast.If visitIfStatement(FunctionsParser.IfStatementContext ctx) {
ast.If node = new ast.If(this.prog,
(ast.Expression)(this.visit(ctx.logical_expr())),
(ast.Sequence)(this.visit(ctx.tb)),
(ast.Sequence)((ctx.fb != null)? this.visit(ctx.fb) : null)
);
return node;
}
@Override public ast.While visitWhileStatement(FunctionsParser.WhileStatementContext ctx) {
ast.While node = new ast.While(this.prog,
(ast.Expression)(this.visit(ctx.logical_expr())),
(ast.Sequence)(this.visit(ctx.sequence()))
);
return node;
}
@Override public ast.For visitForStatement(FunctionsParser.ForStatementContext ctx) {
ast.For node = new ast.For(this.prog,
ctx.ID().getText(),
(ast.Expression)(this.visit(ctx.beg)),
(ast.Expression)(this.visit(ctx.end)),
(ast.Sequence)(this.visit(ctx.sequence()))
);
return node;
}
@Override public ast.Return visitReturnStatement(FunctionsParser.ReturnStatementContext ctx) {
ast.Return node = new ast.Return(this.prog,
(ast.Expression)(this.visit(ctx.expr()))
);
return node;
}
@Override public ast.VarDecl visitDeclarationStatement(FunctionsParser.DeclarationStatementContext ctx) {
ast.VarDecl node = new ast.VarDecl(this.prog,
ctx.ID().getText()
);
return node;
}
@Override public ast.FncDecl visitFunctionStatement(FunctionsParser.FunctionStatementContext ctx) {
ast.Function func = new ast.Function(ctx.ID().getText(),
(ast.ParList)(this.visit(ctx.parlist()))
);
func.addStatements((ast.Sequence)(this.visit(ctx.sequence())));
this.prog.addFunction(func);
ast.FncDecl node = new ast.FncDecl(this.prog,
func
);
return node;
}
@Override public ast.ASTNode visitPrintStatement(FunctionsParser.PrintStatementContext ctx) {
ast.Print node = new ast.Print(this.prog,
(ast.Expression)(this.visit(ctx.expr()))
);
return node;
}
@Override public ast.ParList visitParlist(FunctionsParser.ParlistContext ctx) {
ast.ParList node = new ast.ParList();
for (TerminalNode nxt : ctx.ID()) {
node.add(nxt.getText());
}
return node;
}
@Override public ast.Expression visitExpr(FunctionsParser.ExprContext ctx) {
return (ast.Expression) this.visit((ctx.logical_expr() != null) ? ctx.logical_expr() : ctx.num_expr());
}
@Override public ast.Expression visitLogical_expr(FunctionsParser.Logical_exprContext ctx) {
int tagIndex = 0;
ast.Expression node = (ast.Expression)(this.visit(ctx.logical_tag(tagIndex++)));
for (TerminalNode op : ctx.OPOR()) {
node = new ast.Binary(op.getText(), node, (ast.Expression)(this.visit(ctx.logical_tag(tagIndex++))));
}
return node;
}
@Override public ast.Expression visitLogical_tag(FunctionsParser.Logical_tagContext ctx) {
int tagIndex = 0;
ast.Expression node = (ast.Expression)(this.visit(ctx.logical_fct(tagIndex++)));
for (TerminalNode op : ctx.OPAND()) {
node = new ast.Binary(op.getText(), node, (ast.Expression)(this.visit(ctx.logical_fct(tagIndex++))));
}
return node;
}
@Override public ast.Binary visitRelational(FunctionsParser.RelationalContext ctx) {
return new ast.Binary(ctx.op.getText(), (ast.Expression)(this.visit(ctx.rel)), (ast.Expression)(this.visit(ctx.rer)));
}
@Override public ast.Unary visitLogUnary(FunctionsParser.LogUnaryContext ctx) {
return new ast.Unary(ctx.OPNOT().getText(), (ast.Expression)(this.visit(ctx.logical_fct())));
}
@Override public ast.Parens visitLogParens(FunctionsParser.LogParensContext ctx) {
return new ast.Parens((ast.Expression)(this.visit(ctx.logical_expr())));
}
@Override public ast.Expression visitLogVariable(FunctionsParser.LogVariableContext ctx) {
return (ast.Expression)(this.visit(ctx.variable()));
}
@Override public ast.Expression visitLogFunctionCall(FunctionsParser.LogFunctionCallContext ctx) {
return (ast.Expression)(this.visit(ctx.functioncall()));
}
@Override public ast.ASTNode visitNum_expr(FunctionsParser.Num_exprContext ctx) {
int tagIndex = 0;
ast.Expression node = (ast.Expression)(this.visit(ctx.addop(tagIndex++)));
for (TerminalNode op : ctx.OPADD()) {
node = new ast.Binary(op.getText(), node, (ast.Expression)(this.visit(ctx.addop(tagIndex++))));
}
return node;
}
@Override public ast.Expression visitAddop(FunctionsParser.AddopContext ctx) {
int tagIndex = 0;
ast.Expression node = (ast.Expression)(this.visit(ctx.mulop(tagIndex++)));
for (TerminalNode op : ctx.OPMUL()) {
node = new ast.Binary(op.getText(), node, (ast.Expression)(this.visit(ctx.mulop(tagIndex++))));
}
return node;
}
@Override public ast.Expression visitMulop(FunctionsParser.MulopContext ctx) {
ast.Expression node = (ast.Expression)(this.visit(ctx.num_fct()));
if (ctx.mulop() != null) {
node = new ast.Binary(ctx.OPPWR().getText(), node, (ast.Expression)(this.visit(ctx.mulop())));
}
return node;
}
@Override public ast.Const visitNumLiteral(FunctionsParser.NumLiteralContext ctx) {
return new ast.Const(ctx.SZAM().getText());
}
@Override public ast.Const visitStrLiteral(FunctionsParser.StrLiteralContext ctx) {
return new ast.Const(ctx.STRING().getText());
}
@Override public ast.Parens visitNumParens(FunctionsParser.NumParensContext ctx) {
return new ast.Parens((ast.Expression)(this.visit(ctx.num_expr())));
}
@Override public ast.Unary visitNumUnary(FunctionsParser.NumUnaryContext ctx) {
return new ast.Unary(ctx.op.getText(), (ast.Expression)(this.visit(ctx.num_fct())));
}
@Override public ast.Expression visitNumVariable(FunctionsParser.NumVariableContext ctx) {
return (ast.Expression)(this.visit(ctx.variable()));
}
@Override public ast.Expression visitNumFunctionCall(FunctionsParser.NumFunctionCallContext ctx) {
return (ast.Expression)(this.visit(ctx.functioncall()));
}
@Override public ast.Variable visitVariable(FunctionsParser.VariableContext ctx) {
return (ast.Variable)(new ast.Variable(ctx.ID().getText()));
}
@Override public ast.FunctionCall visitFunctioncall(FunctionsParser.FunctioncallContext ctx) {
return (ast.FunctionCall)(new ast.FunctionCall(ctx.ID().getText(), (ast.ArgList)(this.visit(ctx.arglist()))));
}
@Override public ast.ArgList visitArglist(FunctionsParser.ArglistContext ctx) {
ast.ArgList node = new ast.ArgList();
for (ParseTree nxt : ctx.expr()) {
node.add((ast.Expression)(this.visit(nxt)));
}
return node;
}
}
|
A visitor-ok egy adott típusú elemmel tudnak visszatérni, ezért csinálunk egy fiktív AST node-ot, ami az AST összes elemének őse lesz.
Jelen esetben ez egy üres interfész lesz, amit minden node-unk implementálni fog.
Az AST node-ok őse és használata
ASTNode.java
| package ast;
public interface ASTNode {
}
|
Body.java
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 | package ast;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public abstract class Body implements ASTNode {
private List<Statement> statements = new ArrayList<Statement>();
public void addStatements(Sequence s) {
statements = s.getStatements();
}
public void execute() {
for (Statement s: statements) {
s.execute();
}
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
for (Statement s: statements) {
str.append(s.toString());
}
return str.toString();
}
}
|
Expression.java
| package ast;
public abstract class Expression implements ASTNode {
public abstract Value evaluate(Program p);
}
|
Statement.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | package ast;
import java.util.ArrayList;
import java.util.List;
public abstract class Statement implements ASTNode {
protected Program program = null;
protected Statement(Program prog) {
program = prog;
}
public abstract void execute();
public abstract String toString();
}
|
Mivel a paraméter és argumentumlistákat is külön szabállyal oldottuk meg,
ezeknek a visitor-ai is a közös ős típussal fognak visszatérni az eddigi listák helyett.
Felveszünk tehát két új node-ot ezeknek, amik szintén ASTNode-ok lesznek.
Hogy a használatukban ne legyen változás, az eddig használt típusokból származtatjuk őket.
Két új technikai node és azok használata
ArgList.java
| package ast;
import java.util.ArrayList;
public class ArgList extends ArrayList<Expression> implements ASTNode {
}
|
ParList.java
| package ast;
import java.util.ArrayList;
public class ParList extends ArrayList<String> implements ASTNode {
}
|
Function.java
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 | package ast;
import java.util.Iterator;
import java.util.List;
public class Function extends Body {
private String fname;
private ParList pnames;
public Function(String fname, ParList pnames) {
this.fname = fname;
this.pnames = pnames;
}
public String getFname() {
return fname;
}
public List<String> getParameterNames() {
return pnames;
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append("function ");
str.append(fname);
str.append("(");
Iterator<String> parit = pnames.iterator();
if (parit.hasNext()) {
str.append(parit.next());
while (parit.hasNext()) {
str.append(", ");
str.append(parit.next());
}
}
str.append(")\n");
str.append(super.toString());
str.append("end\n");
return str.toString();
}
}
|
FunctionCall.java
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 | package ast;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class FunctionCall extends Expression {
private String fname;
private ArgList args;
public FunctionCall(String fname, ArgList args) {
this.fname = fname;
this.args = args;
}
@Override
public Value evaluate(Program p) {
Function f = p.getFunction(this.fname);
Map<String, Value> params = new HashMap<String, Value>();
Iterator<String> parameters = f.getParameterNames().iterator();
Iterator<Expression> arguments = args.iterator();
while (parameters.hasNext() && arguments.hasNext()) {
String pname = parameters.next();
Expression e = arguments.next();
params.put(pname, e.evaluate(p));
}
p.newStackFrame();
for (Map.Entry<String, Value> arg : params.entrySet()) {
p.addVariable(arg.getKey());
p.setVariable(arg.getKey(), arg.getValue());
}
Value retval = null;
try {
f.execute();
} catch (Returning r) {
retval = r.getValue();
}
p.freeStackFrame();
return retval;
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append(fname);
str.append("(");
Iterator<Expression> argit = args.iterator();
if (argit.hasNext()) {
str.append(argit.next().toString());
while (argit.hasNext()) {
str.append(", ");
str.append(argit.next().toString());
}
}
str.append(")");
return str.toString();
}
}
|
Utolsó frissítés:
2023-02-02 13:09:36