Kirjoittaja: fergusq
Kirjoitettu: 19.06.2013 – 21.07.2013
Tagit: teksti, koodi näytille, vinkki
Merkkijonojen parsiminen on hyvä taito osata, joten väsäsin tämän koodivinkin, joka parsii yksinkertaisia laskulausekkeita ja siinä samalla laskee niiden arvon.
Laskin koostuu lekseristä ja jäsentimestä eli parserista.
Lekseri yksinkertaisesti lukee merkkejä ja muodostaa niistä listan, jossa peräkkäiset numerot on liitetty yhteen ja muut merkit ovat omissa merkkijonoissaan. Näitä merkkijonoja kutsutaan englannin kielessä nimellä "token".
Tällainen toiminta riittää yksinkertaisen laskimen toteutukseen. Ohjelmointikielien parsimiseen tarkoitetut lekserit osaavat myös erotella kahden merkin operaattorit (kuten pienempi tai yhtäsuuri <=), sanat ja avainsanat.
Jäsennin (engl. parser) tutkii tokeneita ja jäsentelee ne syntaksin mukaan. Tämän laskimen parseri on nimeltään englanniksi "recursive descend parser". Se tarkoittaa, että parseri on järjestelty funktioihin, ja jokainen funktio jäsentelee yhden lausekkeen. Funktiot voivat kutsua toisiaan rekursiivisesti. Laskimessa rekursiota käytetään funktiossa "jäsennäJaLaskeNumeroTaiSulut", joka kutsuu funktiota "jäsennäJaLaskePlusMinus".
Esimerkiksi syntaksipuu lausekkelle 2*3+10/(1+2):
2 * 3 + 10 / (1 + 2) Selitys Funktio laskimen koodissa
| | | | | | | | | L = Luku / jäsennäJaLaskeNumeroTaiSulut
L | L | | | L | L Y = Yhteen tai vähennyslasku / jäsennäJaLaskePlusMinus
\ | / | | | | | | K = Kerto tai jakolasku / jäsennäJaLaskeKertoJako
\|/ | | | K | K
K | | | \|/
| | | | Y
| | | | |
| | L | L
| | \ | /
| | \ | /
| | \ | /
| | \|/
| | K
| | /
| | /
| | /
\ | /
\ | /
\ | /
\ | /
\|/
YParseri kutsuu ensin funktiota Y. Funktio Y kutsuu funktiota K, lukee operaattorin ja kutsuu taas funktiota K. Funktio K toimii samalla tavalla, kutsuu funktiota L, lukee operaattorin ja kutsuu taas funktiota L. Rekursiivinen laskeutuva jäsennin on yleinen valinta, koska se on yksinkertainen ja sen toimintaa on helppo ymmärtää.
Laskimen parseri laskee laskuja yhtäaikaa parsittaessa. Tämä riittää laskimeen, mutta ohjelmointikielien parserit yleensä vain muuntavat tekstin johonkin toiseen muotoon, jota on helppo tulkata tai kääntää.
Tässä on koodi. "lueTokenit" on lekseri ja muut funktiot liittyvät parseriin.
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Laskin {
public static void main(String[] args) {
System.out.print("Syötä lasku: ");
List<String> tokenit = new ArrayList<>();
// Lue syöte lekseri-funktiolla
try {
lueTokenit(tokenit);
} catch (IOException e) {
e.printStackTrace();
}
// Kutsuu parseria, joka laskee laskun parsimisen lomassa
System.out.println(jäsennäJaLaskePlusMinus(tokenit));
}
/**
* Lekserifunktio, erottelee numerot ja operaattorit toisistaan.
* @throws IOException
*/
public static void lueTokenit(List<String> tokenit) throws IOException {
String luku = "";
while (true) {
// Lue seuraava merkki
char seuraavaMerkki = (char) System.in.read();
// Ohita välilyönnit
while (seuraavaMerkki == ' ' | seuraavaMerkki == '\t')
seuraavaMerkki = (char) System.in.read();
// Jos seuraava merkki on rivinvaihto
if (seuraavaMerkki == '\n') {
// Jos muuttujassa "luku" on luku
// lisää token-listaan
if (luku.length() != 0) {
tokenit.add(luku);
luku = "";
}
// Käyttäjän syöttämä rivi on loppu, poistu loopista
break;
}
// Jos merkki on numero, lisää se "luku" -muuttujaan
if (Character.isDigit(seuraavaMerkki)) {
luku += seuraavaMerkki;
}
// Muulloin merkki on operaattori
else {
// Jos muuttujassa "luku" on luku
// lisää token-listaan
if (luku.length() != 0) {
tokenit.add(luku);
luku = "";
}
// Lisää merkki token-listaan
tokenit.add(""+seuraavaMerkki);
}
}
}
/**
* Lukee token-listasta seuraavan numeron
* Tulostaa virheen ja poistuu ohjelmasta jos
* seuraava tokeni ei ole numero
*/
public static int seuraavaNumero(List<String> tokenit) {
String seuraava = tokenit.remove(0);
try {
return Integer.parseInt(seuraava);
} catch (NumberFormatException ex) {
// Tokeni ei ole numero!
System.err.println(seuraava + " ei ole numero!");
System.exit(0);
}
// Ohjelman ei koskaan pitäisi päästä tänne
return 0;
}
/**
* Jos seuraava tokeni ei ole tietty, tulosta virheviesti ja poistu ohjelmasta
*/
public static void odota(List<String> tokenit, String odotettuToken) {
String seuraava = tokenit.remove(0);
if (!seuraava.equals(odotettuToken)) {
System.err.println("odotettiin '" + seuraava + "':a");
System.exit(0);
}
}
/**
* Jäsennä ja laske yhteen- ja vähennyslaskut
*/
private static int jäsennäJaLaskePlusMinus(List<String> tokenit) {
// laske edessä oleva numero tai kertolasku
int numero = jäsennäJaLaskeKertoJako(tokenit);
// Lue + ja - operaattorit
while (tokenit.size() != 0 && Arrays.asList("+", "-").contains(tokenit.get(0))) {
switch (tokenit.remove(0)) {
case "+":
numero += jäsennäJaLaskeKertoJako(tokenit);
break;
case "-":
numero -= jäsennäJaLaskeKertoJako(tokenit);
break;
}
}
return numero;
}
/**
* Jäsennä ja laske kerto- ja jakolaskut
*/
private static int jäsennäJaLaskeKertoJako(List<String> tokenit) {
// laske edessä oleva lauseke
int numero = jäsennäJaLaskeNumeroTaiSulut(tokenit);
// Lue * ja / operaattorit
while (tokenit.size() != 0 && Arrays.asList("*", "/").contains(tokenit.get(0))) {
switch (tokenit.remove(0)) {
case "*":
numero *= jäsennäJaLaskeNumeroTaiSulut(tokenit);
break;
case "/":
numero /= jäsennäJaLaskeNumeroTaiSulut(tokenit);
break;
}
}
return numero;
}
/**
* Jäsennä ja laske sulkujen sisällä oleva lauseke
* tai numero
*/
private static int jäsennäJaLaskeNumeroTaiSulut(List<String> tokenit) {
// Tarkista, että tokeneita on jäljellä
if (tokenit.size() == 0) {
System.err.println("teksti loppui kesken! odotettiin sulkua tai numeroa");
System.exit(0);
}
// Lue sulkujen sisällä oleva lasku
if (tokenit.get(0).equals("(")) {
odota(tokenit, "(");
int numero = jäsennäJaLaskePlusMinus(tokenit);
odota(tokenit, ")");
return numero;
}
// Muulloin lue numero
return seuraavaNumero(tokenit);
}
}