Sulkulausekkeita tukevan laskimen ohjelmointi on yllättävän haastavaa jos sulkujen lisäksi operaattorien presedenssit vaikuttavat laskujärjestykseen (kuten peruslaskutoimituksilla: 1+2*3 = 1+6 = 7, eikä 1+2*3 = 3*3 = 9, koska kertolaskut lasketaan ennen yhteenlaskuja). Koodivinkissä esitellään ratkaisutapa, joka soveltuu yksinkertaisten laskulausekkeiden laskemiseen sekä monimutkaisten ohjelmointikielien tulkkaamiseen.
Rekursiivisesti etenevä jäsennin (Wikipedia: Recursive descent parser) käsittelee operaattorien presedenssit kieliopin (Wikipedia: Context-free grammar) tasolla. Käytännössä jokaista operaattoria vastaa jäsennysfunktio, joka kutsuu rekursiivisesti korkeamman presedenssin (ensin laskettavien) operaattoreiden jäsennysfunktioita. Menetelmä on tehokas ja ilmaisuvoimainen, sekä sopii kokonaisten ohjelmointikielien jäsentämiseen. Esimerkiksi gcc ja clang kääntäjien C- ja C++-parserit ovat käsin koodattuja rekursiivisesti eteneviä jäsentimiä, eli perustuvat samaan arkkitehtuuriin.
Koodivinkki havainnollistaa rekursiivisesti etenevää jäsentämistä kokonaislukulaskimen toteutuksella. Laskimen kielioppi on kommentissa rivillä 30 ja antaa yleiskuvan koodin rakenteesta.
/*
* Rekursiivisesti etenevä kokonaislukulaskin operaattoreilla + - * / % ( )
*
* $ gcc laskin.c -o laskin && ./laskin '(1 + 2*(3-4) + (5-6)*7)/-8 + 9'
* 10
*/
#include <ctype.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Apustusfunktiot parsintaan */
static int peek(const char **pp) {
while (isspace(**pp)) (*pp)++;
return **pp;
}
static int accept(const char **pp, char ch) {
return (peek(pp) == ch) ? *(*pp)++ : 0;
}
static int accept_any(const char **pp, const char *set) {
int ch = peek(pp);
while (*set && ch != *set) set++;
return *set ? accept(pp, ch) : 0;
}
/*
* Laskimen kielioppi:
* expression -> addsub
* addsub -> muldivmod { ( "+" | "-" ) muldivmod }
* muldivmod -> unary { ( "*" | "/" | "%" ) unary }
* unary -> { ( "+" | "-" ) } factor
* factor -> integer | "(" expression ")"
*/
const char *expression(const char *p, long *value);
static const char *factor(const char *p, long *value) {
switch (peek(&p)) {
case '0': case'1': case '2': case '3': case '4':
case '5': case'6': case '7': case '8': case '9':
errno = 0;
*value = strtol(p, (char **)&p, 10);
if (errno) {
perror("invalid integer");
p = NULL;
}
break;
case '(':
if (((p = expression(p+1, value)) && accept(&p, ')')) || !p)
return p;
fprintf(stderr, "missing parenthesis ')': ");
/* fall-through */
default:
if (*p == '\0') {
fprintf(stderr, "unexpected EOF\n");
} else if (isprint(*p)) {
fprintf(stderr, "unexpected character '%c'\n", *p);
} else {
fprintf(stderr, "bad character \"\\x%02X\"\n", *p);
}
p = NULL;
break;
}
return p;
}
/* Kieliopin välikkeiden jäsennysfunktiot */
static const char *unary(const char *p, long *value) {
if (accept(&p, '+')) {
p = unary(p, value);
} else if (accept(&p, '-')) {
if ((p = unary(p, value)))
*value = -*value;
} else {
p = factor(p, value);
}
return p;
}
static const char *muldivmod(const char *p, long *value) {
if ((p = unary(p, value))) {
int op;
long rhs;
while ((op = accept_any(&p, "*/%")) && (p = unary(p, &rhs))) {
if (op == '*') {
*value *= rhs;
} else if (op == '/') {
*value /= rhs;
} else if (op == '%') {
*value %= rhs;
}
}
}
return p;
}
static const char *addsub(const char *p, long *value) {
if ((p = muldivmod(p, value))) {
int op;
long rhs;
while ((op = accept_any(&p, "+-")) && (p = muldivmod(p, &rhs))) {
if (op == '+') {
*value += rhs;
} else if (op == '-') {
*value -= rhs;
}
}
}
return p;
}
const char *expression(const char *p, long *value) {
return addsub(p, value);
}
/* Aloitusvälike: parse -> expression EOF */
int parse(const char *p, long *value) {
if ((p = expression(p, value)) && peek(&p) != '\0') {
fprintf(stderr, "junk at the end of expression: '%s'\n", p);
p = NULL;
}
return p != NULL;
}
/* Yhdistää komentoriviargumentit välilyönneillä ja syöttää parse():lle */
int main(int argc, char *argv[]) {
int ok;
char *expr;
size_t i, size;
if (argc < 2) {
fprintf(stdout, "usage: %s '(1 + 2) * 3'\n", argv[0]);
return 0;
}
for (i = size = 0; ++i < argc; size += strlen(argv[i]) + 1);
if ((expr = malloc(size))) {
long value;
for (i = size = 0; ++i < argc; expr[size++] = " "[i == argc-1]) {
size_t len = strlen(argv[i]);
memcpy(&expr[size], argv[i], len);
size += len;
}
if ((ok = parse(expr, &value)))
fprintf(stdout, "%ld\n", value);
free(expr);
} else {
fprintf(stderr, "malloc(%lu) failed\n", (unsigned long)size);
ok = 0;
}
return !ok;
}Lisäys: Koodi on paikoin turhan tiivistä ja kikkailevaa. Kuvaustakin voisi täydentää joskus paremmalla ajalla. Kirjoitettu alunperin esimerkiksi muualle, mutta en löytänyt ohjelmointiputkan koodivinkeistä samaan tekniikkaan perustuvia laskimia/tulkkeja/kääntäjiä/parsereita, joten lähetin sitten tännekin. Toinen lisäys: Löysinkin Java: Yksinkertainen laskin, mutta ei se mitään. ~2020-02-12
Lisäys: Yleistä siistimistä ja refaktorointia nättiä diffiä varten kommenttiosioon. ~2020-02-18
Nykyaikaisempi tapa lienee muodostaa syötteenä annetusta laskusta ensin ns. normalisoitu versio*, jossa laskujärjestys on vakioitu, ja antaa se sitten varsinaiselle laskintoiminnolle käsiteltäväksi. Tällöin laskintoiminto pysyy yksinkertaisempana, kun sen ei tarvitse osata käsitellä perinteiseen laskujärjestykseen liittyviä monimutkaisia ehtoja.
* Normalisoitu muoto voi olla esimerkiksi sama laskukaava, johon kaikki tarpeelliset sulkeet on lisätty valmiiksi, tai ehkä paremminkin kaavan kääntäminen kokonaan puolalaisen notaation mukaiseksi.
Lausekkeen normalisointiin tarvitaan joka tapauksessa laskujärjestyssääntöjä ymmärtävä normalisointialgoritmi, joka on helposti muokattavissa (yleisessä tapauksessa) laskemaan arvo suoraan ilman normalisoitua välimuotoa. Jäsennyksen ja laskulogiikan irroittaminen toisistaan kyllä kannattaa varsinkin isommissa projekteissa, mutta senkin voi usein tehdä ilman normalisoitua välimuotoa esimerkiksi kutstumalla laskufunktioita suoraan parserista. Säästyy kellosyklit ja muisti.
Infix-lausekkeen postfix-muunnos (normalisointi) ja arvon laskeminen ovat käytännössä sama ongelma. Algoritmi kumpaan tahansa ongelmaan on triviaali muokata ratkaisemaan myös toinen ongelmista. Esimerkiksi koodivinkin laskimella voi tulostaa postfix-muotoisen käänteisen puolalaisen notaation (Wikipedia: Reverse Polish notation) annetusta infix-syötelausekkeesta pienillä lisäyksillä:
git diff -U2 -- laskin.c rpn.c
index 30763d9..d9cd1e2 100644
--- a/laskin.c
+++ b/rpn.c
@@ -46,5 +46,5 @@ static const char *factor(const char *p, long *value) {
perror("invalid integer");
p = NULL;
- }
+ } else printf("%ld ", *value);
break;
@@ -72,7 +72,9 @@ static const char *unary(const char *p, long *value) {
if (accept(&p, '+')) {
p = unary(p, value);
+ printf("u+ ");
} else if (accept(&p, '-')) {
if ((p = unary(p, value)))
*value = -*value;
+ printf("u- ");
} else {
p = factor(p, value);
@@ -93,4 +95,5 @@ static const char *muldivmod(const char *p, long *value) {
*value %= rhs;
}
+ printf("%c ", op);
}
}
@@ -108,4 +111,5 @@ static const char *addsub(const char *p, long *value) {
*value -= rhs;
}
+ printf("%c ", op);
}
}
@@ -123,4 +127,5 @@ int parse(const char *p, long *value) {
p = NULL;
}
+ printf("\n");
return p != NULL;
}Ja ulostus:
$ gcc rpn.c -o rpn && ./rpn '1 + 2 * -3 * (4 - 5) - +6 + (7 - 8) / -(9 - 10)' 1 2 3 u- * 4 5 - * + 6 u+ - 7 8 - 9 10 - u- / + 0
Muunnoksen voi myös tehdä laskulausekkeisiin erikoistuneilla algoritmeilla jotka ovat nopeampia (recursive descent on hidas yksinkertaisissa tapauksissa; esimerkiksi vakiolausekkeen "42" jäsentäminen vaatii kaikkien jäsennysfunktioiden rekursoimisen, mikä JavaScript-kielellä tekee noin 17 funktiokutsua). Shunting-yard ja sen yleistys precedence climbing taitavat olla suosituimmat algoritmit infix-laskulausekkeiden postfix-muunnokseen ja laskemiseen. Monimutkaisemmat rakenteet kuten ternääriset operaattorit (x ? y : z, i < j < k, ...), unary-operaattorit (-a, -+-b, !*p, ...) sekä vaikkapa potenssiinkorotuksen vastaluku (-n^2) eivät kuitenkaan onnistu perinteisellä precedence climbing -algoritmilla.
Jos ollaan tarkkoja, niin gcc, clang ja rustc käyttävät itse asiassa nopeussyistä "hybridijäsennystä", jossa korkean tason rakenteet parsitaan recursive descentillä ja matalan tason aritmeettiset lausekkeet precedence climbingillä.
Aihe on jo aika vanha, joten et voi enää vastata siihen.