Syntaksisuunnittelun täydellisyyden mahdottomuus



Tutkin huvikseni Javan syntaksin muuttamista niin, että luokkien parametrit (Map<String, Integer>) kirjoitetaan hakasulkeisiin (Map[String, Integer]), niin kuin useimmissa kielissä, jotka eivät ole Java tai C++. Osoittautui ettei LALR(1)-parsereiden tapauksessa muutoksella ole suurta merkitystä parserin kokoon eikä minkäänlaista oikeellisuuden saavutettavuuteen. Puhtaan esteettisesti muutos on jopa voitto, koska sisäkkäisten parametrien yhtaikaisen sulkemisen (Set<Set<Integer>>) yhteydessä lekserin ei tarvitse kikkailla ymmärtääkseen, että kyseessä on kaksi perättäistä >-tokenia eikä yksi >>.

Molemmilla tavoilla jäsennyksen perusongelma on, että samasta jäsennystilasta voi alkaa muuttujaesittely (Set[String] mySet;) tai  taulukkoelementin asetus (set[index] = myValue;). LALR(1)-parserissa ei voi tehdä yhtään reduktiota, ennen kuin on selvillä, minkä jäsennyssäännön mukaan reduktio tulisi tehdä. Ylläolevassa esimerkissä päästään niinkin pitkälle kuin mySet/= ennen kuin tiedetään kummassa tapauksessa ollaan.

Ratkaisu olisi huomattavasti siistimpi, jos LALR-jäsentimen generointia varten kehittäisi vain aavistuksen verran ilmaisuvoimaisemman syötemuodon, joka mahdollistaisi säännöt muotoa A : B C D E F, eli lauseke A on lausekkeet B, C ja D peräjälkeen, paitsi jos se on myös lausekkeet E ja F peräjälkeen. Nykyiselläänhän ainakaan Bison ei osaa tätä paitsi-osuutta. Teoriassa tämä olisi toteutettavissa, mutta käytännössä jo Bisonin tasoisen jäsenningeneraattorin implementointi hipoo kontekstiriippumattomien kielien teoriani käytännön soveltamisen äärirajoja, joten en ole varma kannattaako minun edes yrittää. Tämä on kuitenkin tapaus, jossa tarvitaan vain yksi tarpeeksi fiksu tai jääräpäinen ratkaisija, ja lopputuloksesta on iloa monelle.

Jäsentimen ilmaisun yksinkertaisuus (kuitenkin niin, että moniselittelisyyttä ei pääse vuotamaan jostain raosta sisään) on tärkeää siksi, että se mahdollistaa jäsentimien kirjoittamisen myös niille, jotka eivät ole ottaneet teoreettista tietojenkäsittelytiedettä elämäntehtäväkseen. Nykyinen ohjelmistoteollisuus tuntuu kammoksuvan laajennettavia syntakseja — lähinnä koska työkalut niiden toteuttamiseen ovat tällä hetkellä suoraan sanottuna onnettomia. Pidän kuitenkin syntaksin laajennettavuutta yleiskäyttöisessä ohjelmointikielessä toivottavana.

Joskus kauan sitten ohjelmointikielissä ei ollut suoraa syntaktista tukea regexpeille, xml:lle eikä xpathille. Nythän olemme päässeet pois pimeältä keskiajalta, mutta ajatusleikkinä voimme siirtää itsemme sinne takaisin. Tällaisessa tilanteessa, jos ohjelmoija keksii: “hei, tässä voisi käyttää regexpejä” (“now you have two problems”), ja kieli mahdollistaa syntaksin laajentamisen, hän voi miettiä kieleen sopivan syntaksilaajennuksen, jolla regexpien suora esittäminen onnistuu, toteuttaa sen, ja enabloida sen joko siinä modulissa, jossa regexpejä käytetään, tai koko projektissaan, jos niitä on kaikki paikat täynnä.

Tässä on muutama kohta, joissa voidaan mennä pahasti metsään.

Ensinnäkään ei kannata kuvitella, että laajennus tulee automaattisesti käyttöön kaikessa ko. kielen koodissa, jota tiimi ikinä kirjoittaa. Pikemminkin on syytä lähteä uusien laajennusten kanssa liikkeelle pienesti, ja enabloida ne vain siellä missä niitä oikeasti kaivattiin. Kun käytäntö osoittaa, että laajennus on tehty kunnolla, eikä sotke syntaksia muiden asioiden osalta, ja että laajennus on hyödyllinen yleisesti, se tulee yleisempään käyttöön lähes itsestään. Vaihtoehtoisesti, jos ratkaisu osoittautuu kelvottomaksi — ja tapoja on monia, kaikki niistä eivät etukäteen selkeitä — se voidaan haudata hiljaisuudessa, vaikka se jäisikin elämään elävän kuolleen elämää siinä yhdessä projektissa yhdessä tiedostossa, missä se alun perin näki päivänvalon. Eli siis laajennuksen voimassaoloa pitää voida säädellä pitkin projektia. Ei kaikki-tai-ei-mitään-ratkaisuja.

Toiseksi laajennus pitää voida olla kirjoitettavissa normaalilla ohjelmointiponnistelulla. Tässä LALR(1):n kaltainen formalismi auttaa. Ja tämän takia haluaisin nähdä LALR-syötekielien jatkokehitystä, koska pienillä muutoksilla voi oikeassa paikassa olla suuri merkitys.

Kolmanneksi pitää muistaa mitä Fred Brooks sanoi hopealuodeista: niitä ei ole. Syntaksin laajentaminen on ratkaisu harvoin. Se on sitä kuitenkin joskus.

Neljänneksi olisi hyvä, että tietokone pitää huolen siitä, etteivät yhtaikaa käytössä olevat laajennukset tallo toistensa varpaille. Tässäkin LALR(1):n kaltainen formalismi auttaa. Jos kaikki laajennukset on ilmaistu samanlaisina sääntöinä, on koneen helppo laskea mistä tahansa sääntöjoukosta, aiheuttaako niiden yhtaikainen voimassaolo konflikteja.

Vaikka emme enää ole siellä keskiajalla, ja kielemme tukevat regexpejä, on hybristä ajatella, että kielemme ovat täydellisiä, ja mitään laajennustarpeita ei tulevaisuudessa enää ilmene.

Tämän artikkelin on kirjoittanut Teemu Kalvas ja sitä ovat sittemmin muokanneet muut Codenton työntekijät.

Yksi kommentti artikkeliin ”Syntaksisuunnittelun täydellisyyden mahdottomuus

  1. Jatkokehitystä itseasiassa on tapahtunut. Tomita eli yleistetty LR parser (GLR) keksittiin 1980 luvun puolivälissä ja on mukana bisonissa. Kyseinen parseri sietää konflikteja forkkaamalla parse-stackin ja jatkamalla kullakin erikseen niin kauan, kunnes inputin perusteella tiedetään mitä tehdä.

    P.S. Voisin käydä syksyllä demoamassa ‘parser’ ja ‘lexer’ lausekkeita.

Vastaa

Sähköpostiosoitettasi ei julkaista. Pakolliset kentät on merkitty *