Kihagyás

Infix kifejezések: elemzés

Feladat (f04)

Adott egy nyelvtanunk egyszerű valós, zárójeles infix matematikai kifejezésekre (mint például: 42, 24 + 18, 6 + 12 + 24, 6 * 7, 6 + 6 * 6, 6 * (3 + 4), 84 / 2, 12 + (3 * (25 / 5)) - 9 + (2*3*4)):

1
2
3
4
K → T '+' K | T '-' K | T
T → F '*' T | F '/' T | F
F → szam | '(' K ')'
szam = [0-9]+ { '.' [0-9]+ }

Ez erősen LL(1) nyelvtan-e? Számoljunk FIk és FOk halmazokat!

Mire és hogyan számolunk FIk és FOk halmazokat, és mikor lesz egy nyelvtan LL(k)?

Ezeket a halmazokat a nyelvtan nemterminális szimbólumaira számoljuk, iteratív módon. A FIk(A) halmaz az A nemterminálisból levezethető terminális szavak első maximum k hosszú prefixeit, a FOk(A) halmaz az A-ból levezethető részt követő terminális szavak első maximum k hosszú prefixeit tartalmazza.

A FIk halmazok számolásánál az alapelv, hogy A → xα alakú szabályokból (ahol x hossza legalább k, vagy α = λ, azaz x után nincs semmi) meghatározhatók a FIk(A) kezdeti elemei (minden A nemtrminálisra), utána pedig iteratívan, az A → αBβ alakú szabályok alapján, a FIk(B) halmazokat az előző iteráció eredményével közelítve előbb-utóbb minden FIk halmaz megkapható.

A FI1 halmazok
FI1 K T F felhasznált szabályok
H0 szam, '(' F → szam, F → '(' ...
H1 szam, '(' szam, '(' T → F ..., T → F
H2 szam, '(' szam, '(' szam, '(' K → T ..., K → T
H3 szam, '(' szam, '(' szam, '('

A FOk halmazok számolása az B → αAβ alakú szabályokból indul és felhasználja a FIk halmazokat. FOk(S) (ahol S a kezdőszimbólum) értéke nyilván tartalmazza λ-t. Utána az alapelv az, hogy a β-ból levezethező szavak mögé írva FOk(B) elemeit, az így kapott szavak legfeljebb k hosszú prefixei is benne lesznek a FOk(A) halmazban. A FOk(B) halmazokat pedig az előbb látottakhoz hasonlóan iteratívan közelíthetjük.

A FO1 halmazok
FO1 K T F
H0 λ K a kezdőszimbólum
H1 λ, ')' λ, '+', '-' K → T '+' ..., K → T '-' ..., K → T, F → ... K ')'
H2 λ, ')', λ, '+', '-', ')' λ, '*', '/', +', '-' K → T, T → F '*' ..., T → F '/' ..., T → F
H3 λ, ')', λ, '+', '-', ')' λ, '*', '/', +', '-', ')' T → F
H4 λ, ')', λ, '+', '-', ')' λ, '*', '/', +', '-', ')'

A nyelv akkor lesz LL(k), ha A → α és A → β esetén legfeljebb k nemterminális előrenézésével eldönthető, melyiket kell alkalmazni, vagyis a FIk(α FOk(A)) és FIk(β FOk(A)) halmazok diszjunktak.

LL(1)-e a nyelvtan?

Mivel például FIk(T '+' K FOk(K)) és FIk(T '-' K FOk(K)) nem diszjunkt, a fenti nyelvtan nem LL(k).

Feladat

Alakítsuk át a fenti nyelvtant LL(1) nyelvtanná!

LL(1) verzió

Egy lehetséges megoldás: 

1
2
3
4
5
6
K  → T TX
TX → '+' T TX | '-' T TX | λ
T  → F FX
FX → '*' F FX | '/' F FX | λ
F  → szam | '(' K ')'
szam = [0-9]+ { '.' [0-9]+ }

Nézzünk egy komolyabb példát.

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)

Egyelőre az elemzésnek kell működnie, ehhez pedig első körben egy LL(k) nyelvtan kell, ANTLR4 nyelven. Pontosabban, mint azt korábban is láttuk, az ANTLR le tud nyelni pár nem LL(k) konstrukciót. Konkrétan, a nyelvtanban megengedettek reguláris műveletek, mint pl. az iteráció (*, +), elhagyható elemek / szabályrészek (?). Ha pusztán ezek miatt lenne nem LL(k) a nyelvtan, azt az ANTLR könnyedén megemészti. (A korábbi példában is ezekhez hasonló konstrukció implicit használatával küszöbölte ki a balrekurziót.)

Számológép: csak elemzé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
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);
        parser.start();
    }
}

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

line
    : MEMORY '=' expr
    | expr
    ;

expr
    : addop (OPADD addop)*
    ;

addop
    : mulop (OPMUL mulop)*
    ;

mulop
    : fct (OPPWR fct)*
    ;

fct
    : SZAM
    | '(' expr ')'
    | 'abs' '(' expr ')'
    | OPMINMAX '(' expr (',' expr) * ')'
    | OPADD fct
    | MEMORY
    ;

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