Jezička laboratorija u Raketu (2. deo)

Autor: Luka Hadži-Đokić

U prvom delu objasnili smo šta je jezik, kao i, iz ptičije perspektive, sastav jednog prevodioca napisanog u Raketu. Kako bismo se približili pravom rešenju, moramo precizirati kako želimo da naš jezik izgleda i radi. Za početak, možemo dati jednostavan primer:

[code][print "Upisite broj:"] // Ovaj program izracunava faktorijal broja sa standardnog ulaza
[init foo ,i]
[init bar foo-1]
[if foo > 0 [while bar > 0
[init foo foo*bar]
[init bar bar-1]]]
[if foo > 0 [print foo] [print "Broj je manji od 0"]][/code]

U tom primeru nalaze se skoro sve komponente našeg jezika koji ćemo u ime ovog časopisa nazvati “libre-lang”. Libre-lang ima četiri ključne reči i četiri operacije nad jednim od dva tipa podataka koje jezik podržava – cele brojeve (eng. integer) i niske (eng. string). Iako Vam na prvi pogled možda ne izgleda tako, ovo je dovoljno za izvršavanje skoro svakog algoritma koji možemo da zamislimo – jezik je Tjuring-potpun (eng. Turing-complete). Tjuringova mašina je apstraktna mašina koja predstavlja jedan od prvih matematičkih modela izračunavanja. Jedna od bitnih hipoteza računarstva, tzv. Čerč-Tjuringova teza (eng. Church-Turing thesis) govori nam da se svaka funkcija koja se intuitivno može smatrati izračunljivom, takođe može izračunati uz pomoć Tjuringove mašine. Međutim, kako se svaki program tjuringove mašine (ili nekog ekvivalentnog modela izračunavanja) može prevesti u naš jezik i (ako izuzmemo vremenska, memorijska ili energetska ograničenja) izvršiti, što jeste definicija Tjuring-potpunosti (ili Tjuring-kompletnosti), tako se Čerč-Tjuringova teza odnosi i na libre-lang. Za programske jezike opšte upotrebe to je jedna vrlo bitna karakteristika. Sa druge strane, postoje mnogi domenski jezici u upotrebi danas, kao što su HTML ili Kog (eng. Coq), kod kojih je težnja ka Tjuring-kompletnosti neizvodljiva ili čak nepoželjna.

Kao što smo u prethodnom delu saznali, glavni delovi prevodioca našeg jezika su “čitač” i “ekspander”. Kako bismo implementirali čitač, podelićemo njegov posao na tri dela:

• Lekser (eng. Lexer)
• Tokenizator (eng. Tokenizer)
• Parser (eng. Parser)

Lekser vrši leksičku analizu, tj. pretvara nisku (sadržaj neke datoteke na našem jeziku) u niz leksema, tj. reči libre-langa. Razlika između tokenizatora i leksera nije uvek jasna jer vrše sličan posao, a neretko se koriste i kao sinonimi. U našem kodu, tokenizator će da učitava datoteku i, uz pomoć leksera, od nje praviti listu tokena. Na kraju, parser kao ulazni podatak uzima prethodno generisanu listu tokena i od nje pravi sintaksno stablo, predstavljeno uz pomoć S-izraza. Za početak, instaliraćemo paket brag uz pomoć rakoa:

[code]raco pkg install brag[/code]

Zatim, možemo napraviti direktorijum i početi:

[code]mkdir libre-lang
cd libre-lang[/code]

Datoteku lexer.rkt započećemo na sledeći način, kako bismo nagovestili raket prevodiocu da koristimo (osnovni) raket jezik i da ćemo koristiti deo paketa brag pod nazivom support:

[code]#lang racket
(require brag/support)[/code]

Zatim, definišemo funkciju libre-lexer uz pomoć funkcije lexer-srcloc iz brag/support kolekcije, na sledeći način:

[code](define libre-lexer
(lexer-srcloc
[(eof) (return-without-srcloc eof)]
[whitespace (token lexeme #:skip? #t)]
[(from/stop-before "//" "\n") (token ‘COM lexeme)]
[(:or "print" "init" "while" "if"
"==" "!=" "<" ">" "+" "-" "*" "/" ",i" ",s"
"[" "]") (token lexeme lexeme)]
[number (token ‘INTEGER (string->number lexeme))]
[(:or (from/to "\"" "\"") (from/to "’" "’"))
(token ‘STRING
(substring lexeme
1 (sub1 (string-length lexeme))))]
[word (token ‘ID (string->symbol lexeme))]))[/code]

lexer-srcloc za argumente uzima niz pravila oblika (šablon token), i vraća funkciju koja nad tekstom vrši transformacije na osnovu tih pravila – kada naiđe na određeni šablon, zameni ga odgovarajućim tokenom. Ovi tokeni su strukture koje, između ostalog, imaju tip, vrednost tj. leksemu podudarnu šablonu, u celosti ili transformisanu na neki način, kao na primer kod tokena ‘STRING, gde smo se otarasili navodnika uz pomoć funkcije substring, ili ‘INTEGER, gde smo leksemu pretvorili u broj. Takođe se čuvaju i informacije o poziciji lekseme u našem početnom programu, što nam omogućava da ispisujemo korisne i pravilne greške korisniku našeg jezika. Ako obratimo pažnju na šablone u prethodnom kodu, videćemo neke kao što su from/stop-before “/ /” “\n”, što se, uz malo znanja engleskog, može prevesti u “od / / do \n, ne uključujući \n”. Osim takvih, ima i specijalnih šablona kao što je (eof) – kraj datoteke (eng. end of file), ili onih datih skraćenicom – whitespace – belina (čiji token, uzgred, ne uključujemo u krajnji rezultat, što je označeno sa #:skip? #t). number, word, keyword i operator su skraćenice koje nisu deo brag/support kolekcije, pa ćemo ih definisati iznad libre-lexer funkcije.

[code](define-lex-abbrev number (:+ numeric))
(define-lex-abbrev word (:seq alphabetic (:* (:or alphabetic numeric))))
(define-lex-abbrev keyword (:or "print" "init" "while" "if"))
(define-lex-abbrev operator (:or "==" "!=" "<" ">" "+" "-" "*" "/" ",i" ",s"))[/code]

Sve što preostaje jeste da dodamo (provide libre-lexer) na kraj datoteke, što omogućava pristup ovoj funkciji iz drugih datoteka.

Sada ćemo napraviti datoteku tokenizer.rkt i popuniti je sa:

[code]#lang racket
(require "lexer.rkt" brag/support)

(define (make-tokenizer ip [path #f])
(port-count-lines! ip)
(lexer-file-path path)
(define (next-token) (libre-lexer ip))
next-token)

(provide make-tokenizer)[/code]

>
Većinu posla leksičke analize završili smo u lekseru, pa sve što preostaje za ovu funkciju je da učitava tekst sa ulaza ip (eng. input port, najčešće je to datoteka, ili, ako je omogućeno, REPL). Čuvaju se neki potrebni podaci o ulaznom medijumu i definišemo funkciju koja iz ulaznog medijuma izdvaja sledeći token uz pomoć leksera.

Parser je napisan u brag jeziku, koji služi kao jezik za generisanje parsera od gramatike u Bakus-Naurovoj formi.

[code]#lang brag
libre-prog: libre-stmt*
@libre-stmt: /"[" [libre-print | libre-init | libre-while | libre-if] /"]" [/COM]
libre-print: /"print" libre-expr+
libre-init: /"init" libre-expr (",i" | ",s" | libre-expr)
libre-while: /"while" libre-expr libre-stmt+
libre-if: /"if" libre-expr libre-stmt [libre-stmt]
@libre-expr: libre-symbol | libre-bool | libre-arit
libre-bool: libre-expr ("==" | ">" | "<" | "!=") libre-expr
@libre-arit: libre-sum
libre-sum: [libre-sum ("+" | "-")] libre-prod
libre-prod: [libre-prod ("*" | "/")] libre-number
@libre-symbol: libre-number | STRING
@libre-number: libre-id | INTEGER
@libre-id: ID[/code]

libre-prog, tj. program, se sastoji iz 0 ili više libre-stmt ( * označava “0 ili više”, a + “1 ili više”).

libre-stmt je jedan od libre-print, libre-init, libre-while i libre-if (mada grupa unutar [ ] nije obavezna), okružen sa “[“ i ”]“. Simbole ”[“ i ”]“ možemo odbaciti sa / jer zagrade se već nalaze oko samog rezultujućeg S-izraza, pa su znakovi interpunkcije često nepotrebni posle parsiranja. Iz sličnog razloga, ni sam libre-stmt izraz ne služi ničemu, pa, uz pomoć @, transformišemo izraz oblika:

[code](libre-stmt (libre-init …))[/code]

u

[code](libre-init …)[/code]

libre-print, libre-init, libre-while i libre-if su slične konstrukcije, sastoje se od ključne reči koja se odbacuje jer ime naredbe se nalazi u samom S-izrazu. Zatim libre-expr, što je izraz libre jezika, i nastavak koji zavisi od funkcionalnosti same naredbe (libre-print ispisuje niz izraza, libre-init učitava izraz u promenljivu, libre-while izvršava niz naredbi ako je izraz tačan, a libre-if izvršava prvu naredbu ako je izraz tačan, a drugu ako je netačan)

libre-expr je libre-symbol, libre-bool ili libre-arit, tj. simbol, bulovski izraz ili aritmetički izraz. Pošto se sastoji samo iz jednog S-izraza, takođe ga možemo eliminisati uz pomoć @ .

libre-bool je jednostavan, ako uzmemo u obzir njegovu semantiku (koju ćemo kasnije implementirati) i njime se upoređuju izrazi.

libre-arit, ili tačnije, libre-sum i libre-prod, nisu tako očigledni. Kako bi obezbedili redosled operacija (množenje i deljenje pre sabiranja i oduzimanja), proizvodi moraju biti ugnežđeni dublje od suma, kako bi prvi bili izračunati, dok operacije na istom nivou vršimo s leva na desno (leva asocijativnost). Zato se pravilo libre-sum sastoji od libre-sum (što obezbeđuje levu asocijativnost) i libre-prod (što obezbeđuje veći prioritet proizvoda). libre-prod je konstruisan analogno tome. libre-symbol, libre-number i libre-id su pravila koja označavaju vrednosti – brojeve, niske i promenljive.

Uzmimo za primer sledeći libre-lang program:

[code][init foo 42+7*7][/code]

On će biti parsiran u sledeći S-izraz:

[code](libre-prog (libre-init foo (libre-sum
(libre-sum (libre-prod 42)) "+" (libre-prod
(libre-prod (libre-prod 7) "*" 7) "*" 7))))[/code]

U narednom delu serijala pozabavićemo se ekspanderom što će nam omogućiti da prethodno parsiran izraz semantički analiziramo i izvršimo.

Prethodni deo | Nastavak