Језичка лабораторија у Ракету (2. део)

NZT 22.10.201727.03.2022

Аутор: Лука Хаџи-Ђокић

У првом делу објаснили смо шта је језик, као и, из птичије перспективе, састав једног преводиоца написаног у Ракету. Како бисмо се приближили правом решењу, морамо прецизирати како желимо да наш језик изгледа и ради. За почетак, можемо дати једноставан пример:

[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]

У том примеру налазе се скоро све компоненте нашег језика који ћемо у име овог часописа назвати “libre-lang”. Либре-ланг има четири кључне речи и четири операције над једним од два типа података које језик подржава – целе бројеве (енг. integer) и ниске (енг. string). Иако Вам на први поглед можда не изгледа тако, ово је довољно за извршавање скоро сваког алгоритма који можемо да замислимо – језик је Тјуринг-потпун (енг. Turing-complete). Тјурингова машина је апстрактна машина која представља један од првих математичких модела израчунавања. Једна од битних хипотеза рачунарства, тзв. Черч-Тјурингова теза (енг. Church-Turing thesis) говори нам да се свака функција која се интуитивно може сматрати израчунљивом, такође може израчунати уз помоћ Тјурингове машине. Међутим, како се сваки програм тјурингове машине (или неког еквивалентног модела израчунавања) може превести у наш језик и (ако изузмемо временска, меморијска или енергетска ограничења) извршити, што јесте дефиниција Тјуринг-потпуности (или Тјуринг-комплетности), тако се Черч-Тјурингова теза односи и на либре-ланг. За програмске језике опште употребе то је једна врло битна карактеристика. Са друге стране, постоје многи доменски језици у употреби данас, као што су ХТМЛ или Ког (енг. Coq), код којих је тежња ка Тјуринг-комплетности неизводљива или чак непожељна.

Имплементација читача

Као што смо у претходном делу сазнали, главни делови преводиоца нашег језика су “читач” и “експандер”. Како бисмо имплементирали читач, поделићемо његов посао на три дела:

Лексер (енг. Lexer)
Токенизатор (енг. Tokenizer)
Парсер (енг. Parser)

Лексер врши лексичку анализу, тј. претвара ниску (садржај неке датотеке на нашем језику) у низ лексема, тј. речи либре-ланга. Разлика између токенизатора и лексера није увек јасна јер врше сличан посао, а неретко се користе и као синоними. У нашем коду, токенизатор ће да учитава датотеку и, уз помоћ лексера, од ње правити листу токена. На крају, парсер као улазни податак узима претходно генерисану листу токена и од ње прави синтаксно стабло, представљено уз помоћ С-израза. За почетак, инсталираћемо пакет браг уз помоћ ракоа:

[code]raco pkg install brag[/code]

Затим, можемо направити директоријум и почети:

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

Датотеку lexer.rkt започећемо на следећи начин, како бисмо наговестили ракет преводиоцу да користимо (основни) ракет језик и да ћемо користити део пакета brag под називом support:

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

Затим, дефинишемо функцију libre-lexer уз помоћ функције lexer-srcloc из brag/support колекције, на следећи начин:

[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 за аргументе узима низ правила облика (шаблон токен), и враћа функцију која над текстом врши трансформације на основу тих правила – када наиђе на одређени шаблон, замени га одговарајућим токеном. Ови токени су структуре које, између осталог, имају тип, вредност тј. лексему подударну шаблону, у целости или трансформисану на неки начин, као на пример код токена ‘STRING, где смо се отарасили наводника уз помоћ функције substring, или ‘INTEGER, где смо лексему претворили у број. Такође се чувају и информације о позицији лексеме у нашем почетном програму, што нам омогућава да исписујемо корисне и правилне грешке кориснику нашег језика. Ако обратимо пажњу на шаблоне у претходном коду, видећемо неке као што су from/stop-before “/ /” “\n”, што се, уз мало знања енглеског, може превести у “од / / до \n, не укључујући \n”. Осим таквих, има и специјалних шаблона као што је (eof) – крај датотеке (енг. end of file), или оних датих скраћеницом – whitespace – белина (чији токен, узгред, не укључујемо у крајњи резултат, што је означено са #:skip? #t). number, word, keyword и operator су скраћенице које нису део brag/support колекције, па ћемо их дефинисати изнад libre-lexer функције.

[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]

Све што преостаје јесте да додамо (provide libre-lexer) на крај датотеке, што омогућава приступ овој функцији из других датотека.

Токенизатор

Сада ћемо направити датотеку tokenizer.rkt и попунити је са:

[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]

>
Већину посла лексичке анализе завршили смо у лексеру, па све што преостаје за ову функцију је да учитава текст са улаза ip (енг. input port, најчешће је то датотека, или, ако је омогућено, РЕПЛ). Чувају се неки потребни подаци о улазном медијуму и дефинишемо функцију која из улазног медијума издваја следећи токен уз помоћ лексера.

Парсер

Парсер је написан у brag језику, који служи као језик за генерисање парсера од граматике у Бакус-Науровој форми.

libre-prog, тј. програм, се састоји из 0 или више libre-stmt ( * означава “0 или више”, а + “1 или више”).

libre-stmt је један од libre-print, libre-init, libre-while и libre-if (мада група унутар [ ] није обавезна), окружен са “[“ и ”]“. Симболе ”[“ и ”]“ можемо одбацити са / јер заграде се већ налазе око самог резултујућег С-израза, па су знакови интерпункције често непотребни после парсирања. Из сличног разлога, ни сам libre-stmt израз не служи ничему, па, уз помоћ @, трансформишемо израз облика:

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

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

libre-print, libre-init, libre-while и libre-if су сличне конструкције, састоје се од кључне речи која се одбацује јер име наредбе се налази у самом С-изразу. Затим libre-expr, што је израз либре језика, и наставак који зависи од функционалности саме наредбе (libre-print исписује низ израза, libre-init учитава израз у променљиву, libre-while извршава низ наредби ако је израз тачан, а libre-if извршава прву наредбу ако је израз тачан, а другу ако је нетачан)

libre-expr је libre-symbol, libre-bool или libre-arit, тј. симбол, буловски израз или аритметички израз. Пошто се састоји само из једног С-израза, такође га можемо елиминисати уз помоћ @ .

libre-bool је једноставан, ако узмемо у обзир његову семантику (коју ћемо касније имплементирати) и њиме се упоређују изрази.

libre-arit, или тачније, libre-sum и libre-prod, нису тако очигледни. Како би обезбедили редослед операција (множење и дељење пре сабирања и одузимања), производи морају бити угнежђени дубље од сума, како би први били израчунати, док операције на истом нивоу вршимо с лева на десно (лева асоцијативност). Зато се правило libre-sum састоји од libre-sum (што обезбеђује леву асоцијативност) и libre-prod (што обезбеђује већи приоритет производа). libre-prod је конструисан аналогно томе. libre-symbol, libre-number и libre-id су правила која означавају вредности – бројеве, ниске и променљиве.

Узмимо за пример следећи либре-ланг програм:

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

Он ће бити парсиран у следећи С-израз:

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

У наредном делу серијала позабавићемо се експандером што ће нам омогућити да претходно парсиран израз семантички анализирамо и извршимо.

Претходни део | Наставак