Napisao sam programski jezik. Evo i kako možeš.

Tijekom posljednjih 6 mjeseci radio sam na programskom jeziku nazvanom Pinecone. Još ga ne bih nazvao zrelim, ali već ima dovoljno značajki koje rade kako bi bile korisne, kao što su:

  • varijable
  • funkcije
  • korisnički definirane strukture

Ako ste zainteresirani za to, pogledajte Pineconeovu odredišnu stranicu ili njegov GitHub repo.

Nisam stručnjak. Kad sam započeo ovaj projekt, nisam imao pojma što radim, a još uvijek nemam. Pohađao sam nula satova o stvaranju jezika, malo sam o tome čitao na mreži i nisam slijedio puno savjeta koje sam dobio.

Pa ipak, ipak sam stvorio potpuno novi jezik. I djeluje. Dakle, sigurno nešto radim kako treba.

U ovom postu zaronit ću ispod haube i pokazati vam cjevovod koji Pinecone (i drugi programski jezici) koriste za pretvaranje izvornog koda u magiju.

Dotaknut ću se i nekih kompromisa koje sam napravio i zašto sam donio odluke koje sam donio.

Ovo nikako nije cjelovit vodič o pisanju programskog jezika, ali dobro je polazište ako vas zanima razvoj jezika.

Početak rada

"Nemam apsolutno pojma odakle bih uopće započeo" nešto je što čujem kad kažem drugim programerima da pišem jezik. U slučaju da je to vaša reakcija, sada ću proći kroz neke početne odluke i korake koji se poduzimaju prilikom pokretanja bilo kojeg novog jezika.

Sastavljeno vs Protumačeno

Dvije su glavne vrste jezika: sastavljeni i protumačeni:

  • Prevodnik odgonetne sve što će program učiniti, pretvara ga u "strojni kod" (format koji računalo može izvoditi vrlo brzo), a zatim sprema da se kasnije izvrši.
  • Tumač prođe kroz izvorni kod redak po redak, shvaćajući što radi.

Tehnički se bilo koji jezik može sastaviti ili protumačiti, ali jedan ili drugi obično ima više smisla za određeni jezik. Općenito, tumačenje ima tendenciju biti fleksibilnije, dok sastavljanje ima veće performanse. Ali ovo je samo grebanje površine vrlo složene teme.

Izuzetno cijenim performanse i vidio sam nedostatak programskih jezika koji su istovremeno visoki i orijentirani na jednostavnost, pa sam krenuo sa kompajliranim za Pinecone.

To je bila važna odluka koju treba donijeti rano, jer na nju utječu mnoge odluke o dizajnu jezika (na primjer, statično tipkanje velika je korist za kompilirane jezike, ali ne toliko za interpretirane).

Unatoč činjenici da je Pinecone dizajniran s namjerom sastavljanja, on ima potpuno funkcionalan tumač koji je bio jedini način pokretanja neko vrijeme. Za to postoji niz razloga, koje ću kasnije objasniti.

Odabir jezika

Znam da je to pomalo meta, ali programski jezik je sam po sebi program i zato ga trebate napisati na jeziku. Odabrao sam C ++ zbog njegove izvedbe i velikog skupa značajki. Također, zapravo uživam raditi u C ++-u.

Ako pišete interpretirani jezik, ima puno smisla pisati ga u kompajliranom jeziku (poput C, C ++ ili Swift) jer će se izvedba izgubljena na jeziku vašeg tumača i tumača koji tumači vašeg tumača složiti.

Ako planirate kompajlirati, prihvatljiviji je sporiji jezik (poput Pythona ili JavaScript-a). Vrijeme sastavljanja može biti loše, ali po mom mišljenju to nije ni približno toliko velika stvar kao loše vrijeme izvođenja.

Dizajn visoke razine

Programski jezik općenito je strukturiran kao cjevovod. Odnosno, ima nekoliko faza. Svaka faza ima podatke formatirane na specifičan, dobro definiran način. Također ima funkcije za pretvaranje podataka iz svake faze u sljedeću.

Prva faza je niz koji sadrži cijelu ulaznu izvornu datoteku. Posljednja faza je nešto što se može pokrenuti. Sve će to postati jasno dok korak po korak prolazimo kroz cjevovod Pinecone.

Lexing

Prvi korak u većini programskih jezika je leksiranje ili tokeniziranje. 'Lex' je kratica za leksičku analizu, vrlo otmjenu riječ za razdvajanje hrpe teksta na žetone. Riječ 'tokenizer' ima puno više smisla, ali 'lexer' je toliko zabavno reći da je ionako koristim.

Žetoni

Token je mala jedinica jezika. Token može biti naziv varijable ili funkcije (AKA identifikator), operator ili broj.

Zadatak Lexera

Lexer bi trebao preuzeti niz koji sadrži cijelu datoteku u vrijednosti izvornog koda i ispljunuti popis koji sadrži svaki token.

Buduće faze plinovoda neće se vraćati na izvorni izvorni kod, tako da lexer mora pružiti sve potrebne podatke. Razlog ovog relativno strogog formata cjevovoda je taj što lexer može obavljati zadatke poput uklanjanja komentara ili otkrivanja je li nešto broj ili identifikator. Želite tu logiku držati zaključanu u lexeru, kako ne biste morali razmišljati o tim pravilima prilikom pisanja ostatka jezika i kako biste mogli promijeniti ovu vrstu sintakse na jednom mjestu.

Savijati

Onoga dana kad sam započeo jezik, prvo što sam napisao bio je jednostavan lexer. Ubrzo nakon toga, počeo sam učiti o alatima koji bi leksiranje navodno učinili jednostavnijim i manje dopadljivim.

Prevladavajući takav alat je Flex, program koji generira leksere. Dajete mu datoteku koja ima posebnu sintaksu za opis gramatike jezika. Iz toga generira C program koji leksira niz i daje željeni izlaz.

Moja Odluka

Odlučio sam zadržati lexer koji sam zasad napisao. Na kraju, nisam vidio značajne koristi upotrebe Flex-a, barem nedovoljne da opravdaju dodavanje ovisnosti i kompliciranje procesa izrade.

Moj lexer dugačak je samo nekoliko stotina redaka i rijetko mi stvara probleme. Valjanje vlastitog lexera također mi daje veću fleksibilnost, poput mogućnosti dodavanja operatora u jezik bez uređivanja više datoteka.

Raščlanjivanje

Druga faza cjevovoda je parser. Analizator pretvara popis tokena u stablo čvorova. Stablo koje se koristi za pohranu ove vrste podataka poznato je kao Sažetak sintakse ili AST. Barem u Pineconeu AST nema informacije o vrstama niti koji su identifikatori koji. To su jednostavno strukturirani tokeni.

Dužnosti raščlanjivača

Analizator dodaje strukturu uređenom popisu tokena koje lexer proizvodi. Da bi zaustavio nejasnoće, parser mora uzeti u obzir zagrade i redoslijed operacija. Jednostavno raščlanjivanje operatora nije užasno teško, ali kako se dodaje više jezičnih konstrukcija, raščlanjivanje može postati vrlo složeno.

Bizon

Ponovno je donesena odluka o uključivanju biblioteke treće strane. Pretežna biblioteka za raščlanjivanje je Bison. Bison puno radi kao Flex. Datoteku napišete u prilagođenom formatu koja pohranjuje gramatičke podatke, a zatim je Bison koristi za generiranje C programa koji će izvršiti vaše raščlanjivanje. Nisam odlučila koristiti Bizone.

Zašto je običaj bolji

S lexerom je odluka o korištenju vlastitog koda bila prilično očita. Lexer je toliko trivijalan program da se moje pisanje nije činilo gotovo jednako glupo kao da se ne piše moj vlastiti "lijevi jastučić".

S parserom je druga stvar. Moj Pinecone parser trenutno ima 750 redaka, a napisao sam ih tri jer su prva dva bila smeće.

Prvotno sam odluku donio iz više razloga, i iako nije prošlo potpuno glatko, većina ih se drži istinom. Glavni su sljedeći:

  • Minimizirajte prebacivanje konteksta u tijeku rada: prebacivanje konteksta između C ++ i Pinecone dovoljno je loše bez ubacivanja Bizonove gramatike
  • Neka gradnja bude jednostavna: svaki put kad se gramatika promijeni, Bison se mora pokrenuti prije gradnje. To se može automatizirati, ali postaje bol prilikom prebacivanja između sustava gradnje.
  • Volim graditi cool sranja: nisam napravio Pinecone jer sam mislio da će to biti lako, pa zašto bih onda dodijelio središnju ulogu kad bih to mogao učiniti sam? Prilagođeni parser možda nije trivijalan, ali je u potpunosti izvediv.

U početku nisam bio potpuno siguran idem li održivim putem, ali povjerenje mi je dalo ono što je Walter Bright (programer na ranoj verziji C ++-a i tvorac jezika D) rekao na tema:

"Nešto kontroverznije, ne bih se trudio gubiti vrijeme s lexer ili generatorima parsera i drugim takozvanim" kompajlerima kompajlera ". Oni su gubljenje vremena. Pisanje leksera i parsera mali je postotak posla pisanja kompajlera. Korištenje generatora oduzet će približno toliko vremena koliko i njegovo ručno pisanje, a oženit će vas generatorom (što je važno prilikom prenošenja kompajlera na novu platformu). A generatori također imaju nesretnu reputaciju emitiranja loših poruka o pogreškama. "

Stablo akcije

Sada smo napustili područje zajedničkih, univerzalnih pojmova ili barem više ne znam koji su to pojmovi. Prema mojem razumijevanju, ono što ja nazivam 'stablom akcija' najsličnije je IR-u LLVM-a (srednji prikaz).

Postoji suptilna, ali vrlo značajna razlika između stabla radnji i apstraktnog stabla sintakse. Trebalo mi je dosta vremena da shvatim da bi uopće trebala postojati razlika između njih (što je pridonijelo potrebi za ponovnim prepisivanjem parsera).

Stablo akcije protiv AST-a

Pojednostavljeno, stablo radnji je AST s kontekstom. Taj je kontekst informacija poput toga koji tip funkcija vraća ili da dva mjesta na kojima se koristi varijabla zapravo koriste istu varijablu. Budući da treba shvatiti i zapamtiti sav ovaj kontekst, kod koji generira stablo radnji treba puno tablica pretraživanja prostora imena i drugih thingamabobova.

Pokretanje stabla radnji

Jednom kad imamo stablo akcija, pokretanje koda je jednostavno. Svaki čvor akcije ima funkciju 'execute' koja uzima neki ulaz, radi sve što bi radnja trebala (uključujući eventualno pozivanje podakcije) i vraća izlazni rezultat akcije. Ovo je tumač na djelu.

Opcije sastavljanja

"Ali čekaj!" Čujem kako kažete: "zar Pinecone ne bi trebao sastaviti?" Da je. Ali sastavljanje je teže od tumačenja. Postoji nekoliko mogućih pristupa.

Izradi vlastiti sastavljač

Ovo mi je u početku zvučalo kao dobra ideja. Obožavam sam izrađivati ​​stvari i žulja me izlika da bih se dobro snašao u montaži.

Nažalost, pisanje prijenosnog kompajlera nije tako lako kao pisanje nekog strojnog koda za svaki jezični element. Zbog broja arhitektura i operativnih sustava, nepraktično je za bilo kojeg pojedinca pisati pozadinsku pozadinu kompajlera za više platformi.

Čak se i timovi koji stoje iza Swifta, Rusta i Clanga ne žele sami time zamarati, pa umjesto toga svi koriste ...

LLVM

LLVM je zbirka alata za kompajliranje. To je u osnovi knjižnica koja će vaš jezik pretvoriti u kompajliranu izvršnu binarnu datoteku. Činilo se kao savršen izbor, pa sam odmah uskočio. Nažalost, nisam provjerio koliko je duboka voda i odmah sam se utopio.

LLVM, iako nije težak montažni jezik, gigantsko je složena knjižnica. To nije nemoguće koristiti, a oni imaju dobre vodiče, ali shvatio sam da ću se morati malo vježbati prije nego što budem spreman u potpunosti implementirati Pinecone kompajler s njim.

Transpiling

Želio sam nekakav kompilirani Pinecone i htio sam to brzo, pa sam se okrenuo jednoj metodi za koju sam znao da može uspjeti: transpiliranju.

Napisao sam Pinecone u C ++ transpiler i dodao mogućnost automatske kompilacije izlaznog izvora s GCC-om. Ovo trenutno radi za gotovo sve programe Pinecone (iako postoji nekoliko rubnih slučajeva koji ga prekidaju). Nije posebno prijenosno ili skalabilno rješenje, ali zasad djeluje.

Budućnost

Pod pretpostavkom da nastavim razvijati Pinecone, dobit će podršku za sastavljanje LLVM-a prije ili kasnije. Ne sumnjam koliko radim na njemu, transpiler nikada neće biti potpuno stabilan, a prednosti LLVM-a su brojne. Samo je pitanje kada imam vremena napraviti neke uzorke projekata u LLVM-u i razriješiti se toga.

Do tada, interpreter je izvrstan za trivijalne programe, a C ++ transpiliranje radi za većinu stvari koje trebaju više performansi.

Zaključak

Nadam se da sam programske jezike učinio malo manje tajanstvenima za vas. Ako ga i sami želite napraviti, toplo ga preporučujem. Postoji mnoštvo detalja o provedbi koje treba dokučiti, ali ovdje bi vam trebao biti dovoljan okvir za pokretanje.

Evo mojih savjeta za početak (zapamtite, ja zapravo ne znam što radim, pa shvatite to s rezervom):

  • Ako sumnjate, idite protumačiti. Tumačeni jezici općenito su lakši za dizajn, izgradnju i učenje. Ne obeshrabrujem vas da napišete sastavljenu, ako znate da to želite učiniti, ali ako ste na ogradi, išao bih protumačiti.
  • Što se tiče lexera i parsera, radite što god želite. Postoje valjani argumenti za i protiv pisanja vlastitog. Na kraju, ako dobro osmislite svoj dizajn i sve implementirate na razuman način, to zapravo nije važno.
  • Učite iz cjevovoda s kojim sam završio. Puno pokušaja i pogrešaka uloženo je u projektiranje cjevovoda koji imam sada. Pokušao sam eliminirati AST-ove, AST-ove koji se pretvaraju u stabla radnji na mjestu i druge strašne ideje. Ovaj cjevovod radi, zato ga nemojte mijenjati ako nemate stvarno dobru ideju.
  • Ako nemate vremena ili motivacije za implementaciju složenog jezika opće namjene, pokušajte implementirati ezoterični jezik kao što je Brainfuck. Ti tumači mogu biti kratki od nekoliko stotina redaka.

Jako malo žalim što se tiče razvoja Pineconea. Putem sam donio niz loših izbora, ali prepisao sam većinu koda na koji utječu takve pogreške.

Trenutno je Pinecone u dovoljno dobrom stanju da dobro funkcionira i da ga je lako poboljšati. Pisanje Pinecone-a za mene je bilo izuzetno edukativno i ugodno iskustvo, a tek je započelo.