Koodit: JavaScript: Parsiminen ilman lekseriä

Johdanto

Tekstiä voidaan jäsennellä monella eri tavalla. Yksi suosituimmista on tekstin jakaminen lekserillä sanoihin ja merkkeihin (tokeneihin), ja näiden analysointi. On kuitenkin myös muita tapoja.

Lekserit

Lekseri on ohjelma, joka lukee merkkejä ja palauttaa listan avainsanoista, nimistä, merkkijonoista, operaattoreista, yms. Teksti if a != b then print "a ei ole b" lekseröidään luultavasti Avainsana(if), Nimi(a), Operaattori(!=), Nimi(b), Avainsana(then), Avainsana(print), Merkkijono("a ei ole b"). Eri ohjelmointikielet käyttävät yleensä hieman toisistaan poikkeavia leksereitä riippuen syntaksista. Anna-Liisa voi jossain kielessä takoittaa nimeä Anna-Liisa, ja jossain toisessa kielessä vähennyslaskua Anna miinus Liisa.

Split-funktiolla parsiminen

Ilman lekseriä parsiminen on yleensä hankalaa ja kömpelöä. On kuitenkin joitain tilanteita, jolloin lekserin käyttäminen olisi turhaa ja liian monimutkaista. Esimerkiksi pienissä komentosarjakielissä yksinkertaiset merkkijono-operaatiot riittävät vallan hyvin parsimiseen.

Oletetaan, että komentosarjakieli koostuu riveistä. Jokaisella rivillä on komento, ja mahdollinen lista putkitetuista komennoista. Tämän tapainen ohjelmointikieli on helppo toteuttaa ilman lekseriä käyttäen merkkijono-operaatiota split, joka jakaa tekstin tietyn erotinmerkin avulla ja palauttaa arrayn. Toteutus voisi näyttää tältä:

// Jaa koodi riveihin
var rivit = koodi.split("\n");

for (var i = 0; i < rivit.length; i++) {
	// Jaa lista putkituksista komentoihin
	var komennot = rivit[i].split("|");

	var putki = prompt("Ensimmäisen ohjelman sisääntulo.");

	for (var j = 0; j < komennot.length; j++) {
		// Komennon nimi ja argumentit on eroteltu välilyönneillä
		var komento = komennot[j].split(" ");

		// Siivoa tyhjät kohdat arraysta
		for (var k = 0; k < komento.length; k++) {
			// Poista tyhjät kohdat
			if (komento[k] == "") {
				komento.splice(k, 1);
				k--;
			}
		}

		// Suorita komento
		putki = suoritaKomento(komento, putki);
	}

	alert(putki);
}

Funktio suoritaKomento ottaa argumentteina komennon ja sisääntulon, ja palauttaa ulostulon.

Sulkujen avulla parsiminen

Tämän koodin tapa jäsennellä tekstiä on vastakkaisten sulkujen etsiminen. Koodi etsii tekstistä viimeisen (-sulun, ja sen edestä seuraavan )-sulun. Tämän jälkeen sulkujen sisältä luetaan välilyönnillä erotellut sanat ja laitetaan tauluun. Sitten sulut sisältöineen poistetaan alkuperäisestä tekstistä ja korvataan viittauksella taulussa olevaan arvoon. Prosessi aloitetaan alusta.

Ohjelma ei ymmärrä merkkijonoja, joten esimerkiksi ("Volkswagen (auto)" ("Fiat (auto)")) jäsennellään ["Volkswagen, [auto], ", ["Fiat, [auto], "]], eikä ["Volswagen (auto)", ["Fiat (auto)"]] kuten voisi luulla.

Teksti (a b c (d e f) (g (h))) jäsennellään ja palautettu array on ["a", "b", "c", ["d", "e", "f"], ["g", ["h"]]].

// Parsii sulkujen sisällä olevan datan arrayyn
function parsiKoodi(str) {

	// Varmista, että koodi sisältää vain sallittuja merkkejä.
	// $-merkit voivat sekoittua tmp$ -viittauksiin
	if (str.indexOf("$") != -1) throw "Koodi sisältää kiellettyjä merkkejä!";

	// Taulu väliaikaisia arvoja varten
	var table = new Array();
	var counter = 0;

	while (true) {
		// Etsi viimeinen ( sulku
		var sulku1 = str.lastIndexOf("(");
		// Etsi sitä vastaava ) sulku
		var sulku2 = str.indexOf(")", sulku1);

		// Jos sulkuja ei löytynyt, poistu loopista -- koko teksti on parsittu
		if (sulku1 == -1 || sulku2 == -1) break;

		// Sulkujen sisällä oleva data eroteltuna välilyönneillä
		var sis = str.substring(sulku1+1, sulku2).trim().split(" ");

		// Nimi väliaikaista arvoa varten
		var name = "tmp$" + ++counter;

		for (var i = 0; i < sis.length; i++) {
			// Korvaa viittaukset tauluun oikeilla arvoilla taulusta
			if (table[sis[i]] != undefined) {
				sis[i] = table[sis[i]];
			}
			// Poista tyhjät kohdat
			else if (sis[i] == "") {
				sis.splice(i, 1);
				i--;
			}
		}
		// Lisää data tauluun väliaikaisesti
		table[name] = sis;

		// Korvaa sulut ja niiden sisältö viittauksella taulun väliaikaiseen arvoon
		str = str.substring(0, sulku1) + " " + name + " " + str.substring(sulku2+1, str.length);
	}

	// Palauta viimeisin väliaikainen arvo, eli uloimmat sulut
	return table["tmp$" + counter];
}

Merkki kerrallaan parsiminen

Merkki kerrallaan parsiminen on verrattavissa lekserin avulla parsimiseen, mutta erillistä lekseriä ei kuitenkaan tarvita, koska merkkiyhdistelmiä ei ole. Kieliä, joissa yksittäiset merkit ovat komentoja (kuten Brainfuck) voi parsia vain tällä tavalla.

Esimerkkinä dc:tä muistuttava kieli, joka koostuu numeroista ja komennoista, ja perustuu pinoon. Jokainen numero työnnetään pinoon, ja jokainen operaattori ottaa pinosta kaksi ylintä numeroa ja työntää vastauksen pinoon. Välilyönnit ja kirjaimet ohitetaan.

Pseudokoodina:

Niin kauan kuin sisääntulossa on merkkejä
	Jos seuraava merkki on välilyönti, tabi, uusirivi, tms, siirry seuraavaan merkkiin

	Jos seuraava merkki on numero, työnnä se pinoon
	Jos seuraava merkki on operaattori
		+ ota pinosta 2 ja työnnä summa
		- ota pinosta 2 ja työnnä erotus
		jne...

Lisäksi lekserin ja parserin yhdistäminen on mahdollista, jolloin lekseri itse on merkki-kerrallaan parseri. Esimerkkinä yllä oleva sulku-parseri toteutettuna tällä tavalla.

var pino = new Array();
var taulu = new Array();
var nykyinenSana = "";

// Käy koodin merkit läpi
for (var i = 0; i < koodi.length; i++) {

	// kaikki muut merkit paitsi välilyönnit ja sulut nykyiseen sanaan
	if (koodi.charAt(i).match(/[^\s\(\)]/)) nykyinenSana += koodi.charAt(i);
	else {

		// Muut merkit tarkoittavat, että sana loppui
		// Jos nykyinen sana ei ole tyhjä, lisää se tauluun
		if (nykyinenSana.length != 0) {
			taulu.push(nykyinenSana);
			nykyinenSana = "";
		}

		// Uusi taulu alkaa
		if (koodi.charAt(i) == "(") {
			var uusiTaulu = new Array();

			// Lisää uusi taulu tauluun
			taulu.push(uusiTaulu);

			// Talleta nykyinen taulu pinoon
			pino.push(taulu);

			// Korvaa taulu uudella taululla
			taulu = uusiTaulu;
		}

		// Uusi taulu loppuu
		if (koodi.charAt(i) == ")") {
			// Ota vanha taulu takaisin pinosta
			taulu = pino.pop();
		}
	}
}

// Lisää mahdollinen viimeinen sana tauluun
if (nykyinenSana.length != 0) {
    taulu.push(nykyinenSana);
    nykyinenSana = "";
}

return taulu;

Tämän jälkeen parserin työ on hieman helpompaa, kun sulut on parsittu jo valmiiksi.

Esimerkkejä lekserittömistä parsereista

Erittäin laajalti käytetty lekserittömän parsinnan muoto on säännöllinen lauseke. Regex-lauseet ovat ohjeita merkki-kerrallaan parsereille.

Ohjelmointiputkassa:

• Antti Laaksonen: Laskulausekkeen laskija (VB, laskin)
• Jogge: Lausekkeen laskija QB:lle (QB, laskin)
• JTS: Laskutoimitusten suorittaminen merkkijonosta (PHP, laskin)
• Merri: CSV-parseri (VB, parseri)