Rekursiivisesti etenevä jäsennys
(Alun perin kurssin TIEA241 Automaatit ja kieliopit syksy 2017 materiaaleista.)
Joidenkin kontekstittomien kielioppien pohjalta on varsin helppo laatia ohjelmallinen jäsentäjä (engl. parser) – siis ohjelma (tai aliohjelma), joka ottaa merkkijonon ja selvittää, miten se on johdettavissa kyseisestä kieliopista (tai onko se). Suoraviivainen menetelmä tähän on rekursiivisesti etenevä jäsentäminen (engl. recursive descent parsing). Perusidea on tämä:
-
laadi ensin selaaja (engl. lexer, scanner)
- yksi aliohjelma, joka kutsuttaessa lukee syötteestä seuraavan päätesymbolin ja palauttaa sen
- yleensä kannattaa tukea kurkistusta (engl. lookahead), jolloin selaajalta voi kysyä, mikä on seuraava päätesymboli lukematta sitä pois syötteestä
- lisäksi hyödyllistä on yleensä tarjota myös apufunktio, jolle sanotaan, että seuraavan päätesymbolin tulee olla jokin tietty, ja se sitten lukee seuraavan päätesymbolin syötteestä ja tarkistaa oliko se oikea
-
tee sitten jokaisesta välikesymbolista oma aliohjelmansa (funktio, metodi tms)
- aliohjelma päättelee, mitkä produktiot voivat tulla kyseeseen ja kokeilee niitä yksi kerrallaan
- produktiota käsiteltäessä oikea puoli muuttuu jonoksi aliohjelmakutsuja: päätesymboli on selaajan kutsu ja välikesymboli on (tarvittaessa rekursiivinen) kutsu välikesymbolin aliohjelmalle
- jos useampi produktio tulee kyseeseen, pitää yhden epäonnistuessa kokeilla uudestaan seuraavalla; tätä kutsutaan peruutukseksi (engl. backtracking)
Tarkastellaan alla tarkemmin, miten seuraavaa aritmeettisten lausekkeiden kielioppia voi käyttää jäsentimen muodostamisessa. Esimerkkikoodi on yksinkertaista C++:aa, mutta ideat ovat samankaltaisia missä vain kielessä (niin Javassa kuin Haskellissakin).
E → S
S → F
S → S + F
S → S - F
F → N
F → F * N
F → F / N
N → P
N → - P
P → c
P → ( E )
Selaaja
Selaajan perustehtävänä on napata syötteestä ulos seuraava päätemerkki. Yllä olevassa kieliopissa päätemerkkejä ovat +, -, *, / ja c. Viimeksi mainittua (c) lukuunottamatta tämä on yksinkertaista: luetaan seuraava merkki ja palautetaan se (joskin hyödyllistä on ensin hypätä välilyöntien yli). Asiaa monimutkaistaa tuo c, joka edustaa mitä vain kokonaislukuvakiota, ja vaikka kielioppia ei kiinnostakaan, mikä luku se on, jäsentäjän asiakasta se yleensä kiinnostaa ja sen tulee siksi se pitää tallessa. Siksi päätemerkistä tehdään olio. Kutsun tätä olioluokkaan nimellä lexeme, koska yksittäinen merkkijono, joka vastaa jotain päätemerkkiä, on lekseemi (engl. lexeme). Luokassa on päätemerkin kertova attribuutti ja lisäksi (mahdollisesti) attribuutti, joka kertoo, mikä merkki lekseemin taustalla on.
enum terminal { T_PLUS, // +
T_MINUS, // -
T_STAR, // *
T_SLASH, // /
T_OPAREN, // (
T_CPAREN, // )
T_CONST, // c
END_OF_INPUT
};
struct lexeme {
terminal t;
long val; // defined only for t == T_CONST
};
Itse selaaja on yksinkertainen olio, joka muistaa syötemerkkijonon sekä kohdan, johon asti sitä on käsitelty, ja tarjoaa kolme metodia: peek(), joka palauttaa tiedon siitä, mikä seuraava lekseemi on, get(), joka lukee seuraavan lekseemin ja palauttaa sen, sekä get(terminal), joka tarkistaa, että seuraava lekseemi on oikeanlainen ja lukee sen syötteestä. Näiden tukena on yksityinen metodi scan(), joka varsinaisesti tunnistaa seuraavan lekseemin
class scanner {
private:
struct lexeme next; // next lexeme in the input
std::string input;
size_t inx; // index of character in input past next
void scan() {
while (inx < input.length() && std::isspace(input[inx])) inx++;
if (inx >= input.length()) {
next.t = END_OF_INPUT;
return;
}
switch (input[inx]) {
case '+':
next.t = T_PLUS;
inx++;
break;
case '-':
next.t = T_MINUS;
inx++;
break;
case '*':
next.t = T_STAR;
inx++;
break;
case '/':
next.t = T_SLASH;
inx++;
break;
case '(':
next.t = T_OPAREN;
inx++;
break;
case ')':
next.t = T_CPAREN;
inx++;
break;
default:
if (!('0' <= input[inx] && input[inx] <= '9')) {
throw parse_error("not a valid character");
}
next.t = T_CONST;
next.val = 0;
do {
next.val = next.val * 10 + (input[inx] - '0');
inx++;
} while (inx < input.length() &&
'0' <= input[inx] &&
input[inx] <= '9');
break;
}
}
public:
scanner(std::sting input) {
this.input = input;
inx = 0;
scan();
}
lexeme peek() const { return next; }
lexeme get() {
lexeme rv = next;
scan();
return rv;
}
lexeme get(terminal t) {
if (next.t != t) throw parse_error("expected " + str(t) +
", got " + str(next.t));
lexeme rv = next;
scan();
return rv;
}
};
Rekursiivisesti etenevä jäsennys
Itse jäsennin rakennetaan tekemällä jokaisesta välikesymbolista oma aliohjelmansa. Aliohjelma päättelee syötteen perusteella, mikä produktio tulee kyseeseen, ja sitten toimii sen mukaisesti. Se, mitä aliohjelma palauttaa, riippuu sen käyttötarkoituksesta; tehdään nyt yksinkertainen laskin, jolloin paluuarvona on double. Tarkastellaan esimerkin vuoksi välikesymboleita P (primäärilausekkeet) ja S (summalausekkeet):
P → c
P → ( E )
Produktion valinta on tässä helppoa katsomalla seuraavaa päätemerkkiä. Produktiota käsiteltäessä päätemerkit luetaan selaajalla ja välimerkit hoidetaan rekursiivisella kutsulla.
double evalP(scanner &sc)
{
switch (sc.peek().t) {
case T_CONST:
return sc.get().val;
case T_OPAREN:
{
sc.get();
double v = evalE(sc);
sc.get(T_CPAREN);
return v;
}
default:
throw parse_error("got " + str(sc.peek().t));
}
}
S → F
S → S + F
S → S - F
Tässä haasteita on kaksi: vasen rekursio johtaa suoraan koodattuna päättymättömään rekursioon, ja aivan selvää ei ole, mitä produktiota kulloinkin pitäisi käyttää. Ratkaisu löytyy hoksaamalla, että jokainen S:stä syntyvä merkkijono alkaa jollakin F:n merkkijonolla, ja tämän jälkeen tuleekin merkki, jonka perusteella voidaan produktio valita. Rekursion asemesta kirjoitetaan silmukka.
double evalS(scanner &sc)
{
double rv = evalF(sc);
while (true) {
switch (sc.peek().t) {
case T_PLUS:
sc.get();
rv += evalF(sc);
break;
case T_MINUS:
sc.get();
rv -= evalF(sc);
break;
default:
return rv;
}
}
}
Loput laskimesta jää lukijalle harjoitustehtäväksi.
These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.