Bystroushaak's blog / Czech section / Jak se píše programovací jazyk / Jak se píše programovací jazyk 2: Lexer

Jak se píše programovací jazyk 2: Lexer

V předchozí části (Jak se píše programovací jazyk 1: Motivace) jsem popsal motivaci, jenž mě zavedla na trnitou cestu vývojářů vlastního jazyka. V dnešní části se podíváme na to jak vlastně má můj jazyk vypadat a taky se na první a pravděpodobně nejjednodušší komponentu: lexer.

Self

Základní syntaxi Selfu dobře popisuje následující obrázek:

Pokud by vás zajímaly podrobnosti, doporučuji anglickou wikipedii, Self handbook, či můj paralelně vycházející 📂Seriál o Selfu.

tinySelf

tinySelf, jak jsem se kdysi nerozvážně (ukázalo se, že stejně pojmenovaný projekt už kdysi existoval) rozhodl můj jazyk nazvat, je v podstatě Self, i když trochu „vylepšený“ po stránce syntaxe.

Například jsem přidal podporu pro kaskády, jak je používá Smalltalk. Nikdy jsem nechápal, proč v původním Selfu nejsou, když tam dokonale sednou. Taky jsem změnil "komentář" na # komentář, protože uvozovky se podle mého názoru víc hodí na stringy, než na komentáře a také se lépe píšou na české klávesnici, než standardní Selfovské 'stringy' psané jednoduchými uvozovkami. Pro stringy je nyní možné používat obojí, což člověku šetří escapování, pokud zrovna potřebuje napsat string s uvozovkami.

Kromě toho jsem změnil i syntaxi objektů a bloků, kde jsem umožnil vynechání otevíracího |, takže je možné psát (slot |) místo (| slot |). K parsování to stejně není zapotřebí a vždycky mi to přišlo jako zbytečný opruz. Chtěl jsem přidat i (| code), ale ukázalo se, že to už parseru vadí hodně, takže je nutné zapisovat objekty bez slotů jako (|| code).

Oproti Selfu také není podtržítko na začátku zprávy rezervované pro volání primitivních zpráv. _s je normálně použitelná unární zpráva. Primitivní zprávy (volání kódu interpretru) jsou implementované jako zprávy poslané objektu primitive. Primitivních zpráv je stejně v běžném kódu minimum, tak mi nikdy nebylo jasné, proč by pro ně měla být vyhrazená syntaxe.

Lexer

Psaní jazyka začíná lexerem. Ten definuje, z jakých komponent se jazyk skládá rozřezáním zdrojového kódu na tokeny. Ve standardním imperativním jazyce to můžou být různé příkazy, definice funkce, if podmínky, klíčová slova a tak podobně. V tinySelfu je to vesměs definice objektů, slotů, bloků, nebo posílání zpráv mezi nimi.

Lexer vám kód rozřeže na pole jednotlivých elementů. Z kódu jako:

(| asd = 1 | ^asd.)

vám udělá pole ve stylu:

[
  Token("OBJ_START", "("),
  Token("SEPARATOR", "|"),
  Token("IDENTIFIER", "asd"),
  Token("ASSIGNMENT", "="),
  Token("NUMBER", "1"),
  Token("SEPARATOR", "|"),
  Token("RETURN", "^"),
  Token("IDENTIFIER", "asd"),
  Token("OBJ_END", ")")
]

Výstupem je plochá struktura, do které byl jen rozřezán vstupní řetězec a kde byly ke každé části přiřazeny typy tokenu.

Lexer je možné si napsat ručně, formou stavového automatu, který v cyklu prochází kód znak po znaku a postupně ho rozřezává a analyzuje rozřezané kousky (tokeny), aby jim přisoudil typ. Kdysi jsem něco podobného z neznalosti a z nutnosti udělal (tenkrát v D nebyl žádný lexer), když jsem si psal HTML parser, proto mi věřte, když vám tento přístup DÚRAZNĚ NEDOPORUČÍM.

Jedná o nepružný, k chybám náchylný, na pochopení složitý a těžce udržitelný přístup. Až na některé velmi speciální případy, kdy přesně víte co děláte a proč, se vám vždy vyplatí použít nějakou knihovnu, kterou nakrmíte popisy tokenů a ona vám stavový automat na základě popisu vygeneruje.

V mém případě se jedná o knihovnu rply (podrobnosti přinese příští díl), konkrétně část rply.LexerGenerator.

tinySelfové tokeny

tinySelf je tvořen následujícími tokeny:

SELF

Klíčové slovo self tvoří token Self. Použití je podobné jako třeba v pythonu, či this v javě.

NUMBER

Čísla. 5 je číslo. -5 je číslo. 4.32 je taky číslo, stejně jako \xFF.

OBJ_START

Začátek definice objektu. Jedná se jednoduše o závorku ( za níž následuje zbytek objektu.

OBJ_END

Ukončovací závorka ) značící konec objektu. Nejkratší (prázdný) objekt v Selfu je ().

BLOCK_START

Začátek bloku [. Bloky jsou objekty, které mají parenta nadefinovaného na lokální scope, takže se chovají podobně jako lambda funkce.

BLOCK_END

Konec bloku ]. Nejkratší blok vypadá takhle; [].

SINGLE_Q_STRING a DOUBLE_Q_STRING

Definice stringů. Jak jsem zmiňoval, bere se ‘string’ a “string” se standardníma escape sekvencema.

FIRST_KW

V Selfu existují tři druhy zpráv objektům; unární, binární a keyword. Unární nepřijímá žádný parametr. Binární jeden, keyword pak libovolný počet.

Self přinesl oproti Smalltalku drobné vylepšení, kde keyword zprávy jsou jednoznačně parsovatelné prostým okem tím, že vynucuje každé následující klíčové slovo zprávy začínat velkým písmenem.

Ve Smalltalku může zpráva at: 1 put: 2 znamenat buď (at: 1) put: 2, tedy poslání zprávy at: a následné poslání zprávy put: výsledku z prvního volání, nebo poslání zprávy at:put: se dvěma parametry 1 a 2. V Selfu je nutné druhý popsaný případ zapsat jako at: 1 Put: 2, což jednoznačně identifikuje kde keyword zpráva začíná a končí. Proto taky lexer rozlišuje začátek keyword zprávy (string začínající malým písmenem s dvojtečkou na konci) a pokračování.

KEYWORD

Zmiňované pokračování zprávy. String začínající velkým písmenem, s dvojtečkou na konci.

IDENTIFIER

String začínající malým či velkým písmenem, či podtržítkem následující tím samým, či číslicí. asd, BSD, _A či _35 jsou validní identifikátory, respektive unární zprávy.

OPERATOR

Jako operátor (binární zprávu) je možné použít znaky z množiny: !@$%&*-+~/?<>, v libovolném počtu opakování. @ je operátor, stejně jako @@.

Operátory vždy očekávají jeden parametr. a + b je binární zpráva oprerátoru + s parametrem b zaslaná objektu a.

ARGUMENT

Hlavně u bloků je potřeba napsat co za argumenty přijímají. Argumenty se zapisují jako identifikátory začínající dvojtečkou.

Ukázky:

:a

:parameter

:_

:_5OK

ASSIGNMENT

Speciální operátor přiřazení. Má význam v definici slotů, kde definuje sloty pouze ke čtení. Také je ho možné použít jako běžný operátor (binární zprávu). Zapisuje se jako znak pro rovná se (=).

RW_ASSIGNMENT

Přiřazení do slotu ke čtení i zápisu. Takto jde přiřazovat pouze konstanty, nebo reference na jiné objekty, nikoliv metody.

Zapisuje se jako šipka do leva (<-).

RETURN

Vrácení hodnoty z objektu / bloku. Zapisuje se jako stříška (^).

END_OF_EXPR

Konec výrazu. Odděluje řetězce zpráv. Zapisuje se stejně jako ve Smalltalku tečkou (.).

SEPARATOR

Oddělovač slotů od kódu. Zapisuje se jako svislá čárka (|).

CASCADE

Vyhrazený operátor kaskády. Zapisuje se jako středník (;). Sděluje interpretru, že následující zpráva se posílá stejnému objektu jako předchozí.

COMMENT

Komentář začínající #, končící koncem řádku.

Ještě k lexeru

Může se zdát, že v lexeru je toho spousta, ale ve skutečnosti je celý jazyk dost jednoduchý a ukázka všeho co je v něm možné se vejde tak nějak na pohlednici:

()  # Prázdný objekt.
(| |)  # Taky prázdný objekt, ale s definicí (prázdných) slotů.
(| slot |)  # Objekt obsahující jeden slot (key/val storage, kde slot = nil.).

# Objekt obsahující definice dvou slotů; read only ‚s‘ a zapisovatelného slotu ‚s2‘.
# Ekvivalentní slovníku {"s": None, "s2": 1}, když pominu zapisovatelnost slotů.
(| s = nil. s2 <- 1 |)

# Objekt obsahující slot ‚s‘, a taky kód, který tomuto slotu pošle unární zprávu ‚printLine‘. Poslední výraz je vždy vrácen, takže bude vrácena hodnota slotu ‚s‘.
(s = 1 | s printLine. s)
(| s = 1. | s printLine. ^s. )  # Totožný kód jako v předchozím případě s alternativní syntaxí slotů a explicitní return.

[ ]  # prázdný blok
[:a | a printLine. a]  # blok přijímající parametr ‚a‘, který vypíše posláním zprávy ‚printLine‘ a vrátí.
[| :a | a printLine. exit: a.]  # totožný kód - return v bloku vrací z nadřazeného scope, nikoliv jen z bloku samotného!.

# Komplexnější objekt obsahující asi všechny elementy jazyka.
( a = 1. b <- 2. c |
  (a + b) > 0
    ifTrue: [c: a+b. ^c]
    False: [self logger log: a; log b.].

  logger log: 'Vsechny zpravy se prvne resolvuji na Self'.
  self logger log: "Toto je tedy totozna zprava".

  ^ (| output = "vysledek". line <- "metody" |)
)

Celý kód lexeru se vejde na 40 řádek a jde jen o definici jednotlivých elementů jazyka pomocí regexpů:

# -*- coding: utf-8 -*-
from rply import LexerGenerator


lg = LexerGenerator()
lg.ignore(r'\s+')

lg.add('SELF', r'self')

lg.add('NUMBER', r'(0x[0-9a-fA-F]+)|((\-)?\d+(\.\d)?)')

lg.add('OBJ_START', r'\(')
lg.add('OBJ_END', r'\)')

lg.add('BLOCK_START', r'\[')
lg.add('BLOCK_END', r'\]')

lg.add('SINGLE_Q_STRING', r"'(?:\\.|[^'\\])*'")
lg.add('DOUBLE_Q_STRING', r'"(?:\\.|[^"\\])*"')

lg.add('FIRST_KW', r'([a-z_][a-zA-Z0-9_]*\.)*[a-z_]+[a-zA-Z0-9_]*:')
lg.add('KEYWORD', r'[A-Z]+[a-zA-Z0-9_]*:')
lg.add('ARGUMENT', r':[a-zA-Z_]*[a-zA-Z0-9_]+')

lg.add('RW_ASSIGNMENT', r'\<-')

lg.add('OPERATOR', r'[!@\$%&\*\-\+~/?<>,]+|==+')
lg.add('RETURN', r'\^')
lg.add('END_OF_EXPR', r'\.')
lg.add('SEPARATOR', r'\|')
lg.add('CASCADE', r'\;')

lg.add('IDENTIFIER', r'([a-zA-Z_][a-zA-Z0-9_]*\.)*[a-zA-Z_]*[a-zA-Z0-9_\*]+')

lg.add('ASSIGNMENT', r'=')

lg.add('COMMENT', r'#.*[\n|$]?')


lexer = lg.build()

Pokračování

V příštím díle se podíváme na parser, který tokeny bere a sestavuje z nich AST - abstraktní syntaktický strom.

Relevantní diskuze

Become a Patron