deadlime

Keltél már fel úgy reggel, hogy kedved lenne írni egy programozási nyelvet? Nem? Az azért elég fura. De nem azért vagyunk most itt, hogy megvitassuk kinek hol siklott félre az élete, írjunk inkább egy programozási nyelvet!

A programozási nyelv írás remek lehetőség lappangó istenkomplexusunk kiélésre, mivel teremthetünk egy világot a saját szabályaink szerint. Nem szereted, ha az if után valaki új sorba írja a kapcsos zárójelet? Dobjál rá syntax error-t! Kiráz a hideg a camel case-es függvény nevektől? Tiltsd be őket! Valami fura oknál fogva azt szeretnéd, hogy az összes változó $ jellel kezdődjön? Itt van rá a remek lehetőség!

Egy ilyen volumenű projekt rengeteg előzetes tervezéssel indul, kezdve azzal, hogy milyen problémát akarunk megoldani az új nyelvvel, egészen az olyan apró részletekig, mint hogy hogyan működik a változók láthatósága vagy hogy legyen-e külön operátor string-ek összefűzésére. Ezt mi most mind kihagyjuk és rögtön belevágunk a közepébe... vagy valamelyik részébe. Nem tudom, mivel nem terveztük meg.

Tartalom

0. Első lépések
1. A lexikális elemző
2. Operátorok
3. Műveleti sorrend
4. A szintaktikai elemző
5. Utasítások
6. A kiértékelő
7. Zárójelezés
8. Számos lehetőség
9. Változók
10. Vezérlési szerkezetek
11. Itt a vég

Első lépések

Kezdetben vala a nyers szöveg. A karakterekből tokenek születnek, amiből növesztünk egy szintaxis fát. A fa rugalmas alapanyag, sok mindent lehet belőle csinálni, mint például natív binárist vagy virtuális gép bájt kódot, de akár rögtön le is futtathatjuk.

Ahhoz, hogy nekiláthassunk, szükségünk lesz egy programozási nyelvre, mivel a sajátunk még messze nincs olyan állapotban, hogy saját magában meg lehessen írni. Én az OCaml-t választottam, mert szeretem olyan dolgokkal kínozni magam, amihez vajmi keveset értek. És ezt tényleg úgy kell érteni, hogy a projekt kezdetekor zéró OCaml tudással rendelkeztem és a funkcionális nyelvekről is nagyjából annyit tudtam, amennyi átszivárgott belőlük más nyelvekbe.

Első mérföldkőnek a boolean típus értékeinek tokenné alakítását választottam, mivel csak a true és a false értékekből áll. Rögtön válaszút elé érkeztünk. Legyenek ezek az értékek külön tokenek (TTrue és TFalse) vagy legyen egy TBool token, ami felvehet true vagy false értéket? Nem tűnik úgy, mintha nagy jelentősége lenne, én az utóbbival mentem:

type token =
  | TBool of bool
  | TEOF

let show_token token =
  match token with
  | TBool b -> Printf.sprintf "TBool(%B)" b
  | TEOF    -> "TEOF"

Az OCaml szintaxisa talán egy kicsit idegen lehet, a type-ot én egy felokosított enum-nak képzeltem el, a match pedig egy felokosított switch.

A token típus fogja tartalmazni az összes tokenünket, a show_token pedig csak egy segéd függvény, amit a fejlesztés során használunk majd, hogy ki tudjunk dolgokat íratni a képernyőre, amíg a saját nyelvünknek nincs ilyen funkciója. Felvettünk még egy end-of-file tokent, ami a program végét hivatott jelezni.

A lexikális elemző

Avagy más néven a lexer. A komoly név egyszerű belsőt takar. A kapott nyers szöveget karakterenként beolvassa és tokeneket épít belőle. Ehhez nem árt tudni, hogy hol tartunk éppen, így definiálunk neki egy struct-szerű képződményt (azt hiszem az OCaml neve record), amiben a számunkra fontos adatokat tárolhatjuk:

exception LexError of string

type lexer_state = {
  src : string;
  len : int;
  mutable pos : int;
  mutable line : int;
  mutable col : int;
}

Az elemzés tekintetében a pos lesz nekünk fontos, a line és a col csak azért van, hogy barátságosabb hibaüzeneteket tudjunk generálni a felhasználóknak.

Definiálunk még néhány segéd függvényt, hogy egyszerűbb legyen az életünk:

let make_lexer src = {
  src;
  len = String.length src;
  pos = 0;
  line = 1;
  col = 1;
}

let step ls =
  ls.pos <- ls.pos + 1;
  ls.col <- ls.col + 1

let step_line ls =
  ls.pos <- ls.pos + 1;
  ls.line <- ls.line + 1;
  ls.col <- 1

let current_char ls = ls.src.[ls.pos]

A make_lexer egy kezdő állapotot állít elő számunkra. A step egy egyszerű, soron belüli léptetés, a step_line párja pedig az új sorba lépés. A current_char visszaadja azt a karaktert, amin éppen állunk.

A nyelv adottságai miatt a problémák nagy részét mintaillesztéssel és rekurzióval fogjuk megoldani.

let tokenize src = 
  let ls = make_lexer src in

  let rec loop tokens =
    if ls.pos < ls.len then
      match current_char ls with
      | '\n' ->
        step_line ls;
        loop tokens
      | ' ' | '\t' | '\r' ->
        step ls;
        loop tokens
      | 'a'..'z' ->
        loop (tokenize_name ls :: tokens)
      | c ->
        raise (LexError (Printf.sprintf "Unexpected character '%c' on line %d col %d" c ls.line ls.col))
    else
      TEOF :: tokens
  in

  List.rev (loop [])

Csinálunk egy példányt a struct-unkból (ls) és egy rekurzív függvényt (loop), amit aztán meg is hívunk egy üres listával. A rekurzió addig megy, amíg a forráskód végére nem érünk, ekkor hozzáad a token lista elejéhez egy TEOF tokent. Valamiért a lista elejére szeretnek ebben a nyelvben pakolni, ezért kell a függvény végén megfordítanunk a listát a List.rev hívással.

Ha még nem vagyunk a fájl végén, akkor megvizsgáljuk az aktuális karaktert. Szóköz-jellegű karakterek esetén csak léptetünk, de nem fűzünk hozzá semmit a listához, ha alfabetikus adatot kapunk, akkor egy másik függvénnyel értelmezzük és hozzáfűzzük a tokenekhez, egyébként pedig hibát dobunk ismeretlen karakterre (amihez használjuk a line és col értékeinket).

let tokenize_name ls =
  let is_name_char ch = ch >= 'a' && ch <= 'z' in

  let start_col = ls.col in
  let start = ls.pos in

  while ls.pos < ls.len && is_name_char (current_char ls) do
    step ls
  done;

  let name = String.sub ls.src start (ls.pos - start) in
  match name with
  | "true"  -> TBool true
  | "false" -> TBool false
  | _       -> raise (LexError (Printf.sprintf "Unexpected name '%s' on line %d col %d" name ls.line start_col))

A névhez addig léptetünk, amíg megfelelő karaktereket látunk (amihez definiáljuk az is_name_char kis segéd függvényt). Ez után a kapott pozíciók alapján kinyerjük a nevet a forrásból és megpróbáljuk értelmezni. Szerény kis nyelvkezdeményünk egyelőre a true és a false kivételével nem ért meg semmit.

Nincs más hátra, mint egy "main" függvény, amivel kipróbálhatjuk a remek lexikális elemzőnket:

let () =
  let src = {|true false
true
true false

false|} in
  try
    let tokens = tokenize src in
    print_endline (String.concat "; " (List.map show_token tokens))
  with LexError e -> print_endline ("Fatal error: " ^ e)

A forráskódot tokenizáljuk és a kapott tokeneket kiíratjuk a korábban definiált show_token függvény segítségével. Az eredmény pedig valami ilyesmi lesz:

$ ocaml main.ml
TBool(true); TBool(false); TBool(true); TBool(true); TBool(false); TBool(false); TEOF

Persze előfordulhat, hogy elfelejtjük, hogy milyen tokeneket képes értelmezni a nyelvünk...

true false
false true true
true oops false
true
false
true
false

...és kapunk egy csúnya hibát:

$ ocaml main.ml
Fatal error: Unexpected name 'oops' on line 3 col 6

Ennek a lépésnek a teljes kódja megtekinthető itt.

Bár vannak tokenjeink, az értékek megléte önmagában még nem elég összetett ahhoz, hogy legyen miből szintaxis fát növeszteni. Így szükségünk lesz még valamire, ami használja is ezeket az értékeket.

Operátorok

Kezdetnek mondjuk definiálhatnánk néhány operátort. Mehetünk a szokásos C-jellegű !, &&, || trióval, vagy mondjuk a kicsit Python-osabb not, and, or szavakkal. A végeredményen nem változtat, csak a lexikális elemző lesz tőle egy kicsit más. Én most az utóbbit választottam.

Először is szükségünk lesz új token típusokra:

type token =
  | TBool of bool
  | TBoolAnd
  | TBoolOr
  | TBoolNot
  | TEOF

Amihez sajnos a show_token függvényünket is ki kell egészíteni új match ágakkal:

let show_token token =
  match token with
  | TBool b  -> Printf.sprintf "TBool(%B)" b
  | TBoolAnd -> "TBoolAnd"
  | TBoolOr  -> "TBoolOr"
  | TBoolNot -> "TBoolNot"
  | TEOF     -> "TEOF"

Aztán a tokenize_name függvényben lekezeljük az új neveket:

match name with
| "true"  -> TBool true
| "false" -> TBool false
| "and"   -> TBoolAnd
| "or"    -> TBoolOr
| "not"   -> TBoolNot
| _       -> raise (LexError (Printf.sprintf "Unexpected name '%s' on line %d col %d" name ls.line start_col))

A not true or false and true forráskóddal megfuttatva a programunkat így már az alábbi kimenetet fogjuk kapni:

$ ocaml main.ml
TBoolNot; TBool(true); TBoolOr; TBool(false); TBoolAnd; TBool(true); TEOF

Ennek a lépésnek a módosításai megtekinthetőek itt.

Vannak boolean értékeink és operátorok, amik kezdenek is valamit ezekkel az értékekkel, most már van miből felépíteni a fát.

Műveleti sorrend

Mielőtt belekezdenénk a konkrét feldolgozásba, érdemes egy pár szót ejteni a műveleti sorrendről, mivel a szintaktikai elemző működését és felépítését nagyban ez vezérli.

Általában az egy változós operátor előbb jut érvényre, mint a két változós operátor (a not false and true kifejezést úgy értelmezzük, hogy (not false) and true, bár még nincsenek zárójeleink).

Előfordulhat, hogy két operátor egy szinten van (például a - és a +), azok kiértékelése több módon is történhet:

• nem engedjük, hogy ilyen történjen (például nem akarunk olyat a nyelvünkben, hogy 1 < 2 < 3, csak olyat, hogy 1 < 2 and 2 < 3)
• balról jobbra értékeljük ki (1 + 2 - 3 az (1 + 2) - 3)
• jobbról balra értékeljük ki (1 + 2 - 3 az 1 + (2 - 3))

Érdemes áttanulmányozni "kész" programozási nyelvek (például a C++) műveleti sorrendre vonatkozó dokumentációját.

A szintaktikai elemző

A szintaktikai elemző (parser) fogja a tokenek listáját és megpróbálja a saját szabályai szerint értelmezni őket és építeni belőle egy szintaxis fát. Figyelembe véve a nyelv által jelenleg támogatott tokeneket, a fa elemei a következő típusokat vehetik fel:

type expr =
  | EBool of bool
  | EBoolNot of expr
  | EBoolAnd of expr * expr
  | EBoolOr of expr * expr

Az EBool olyan, mint a TBool, a többinek viszont van egy olyan érdekessége, hogy paraméterként expr típusú dolgokat kaphatnak, így a típus is rekurzív. Írhatunk például olyanokat, hogy EBoolOr(EBoolNot(EBool(true)), EBool(false)). A * itt nem a szorzást jelenti, csak a paraméterek elválasztó karaktere.

A fenti kifejezés fa nézetben

Itt is lesz egy segéd függvényünk, hogy ki tudjuk íratni az elkészült kifejezést:

let rec show_expr e =
  match e with
  | EBool b -> Printf.sprintf "EBool(%B)" b
  | EBoolNot e' -> Printf.sprintf "EBoolNot(%s)" (show_expr e')
  | EBoolAnd (l, r) -> Printf.sprintf "EBoolAnd(%s, %s)" (show_expr l) (show_expr r)
  | EBoolOr (l, r) -> Printf.sprintf "EBoolOr(%s, %s)" (show_expr l) (show_expr r)

Mivel a típus rekurzív, így az expr típusú paraméterekre újra meg kell hívnunk a show_expr függvényt. A szokásos mintaillesztés és rekurzió. Az EBoolNot sorában lévő e' nem valamilyen speciális nyelvi elem, az aposztróf is a változó nevének a része.

A lexikális elemzőhöz hasonlóan a szintaktikai elemzőnek is lesz egy belső állapota és néhány segéd függvénye.

exception ParseError of string

type parser_state = {
  mutable tokens : token list;
}

let make_parser tokens = { tokens }

let peek ps =
  match ps.tokens with
  | t :: _ -> t
  | [] -> TEOF

let consume ps =
  match ps.tokens with
  | t :: rest -> ps.tokens <- rest; t
  | [] -> TEOF

A parser_state-ben egyelőre csak a tokenjeink vannak, mire ide értünk elveszett az az információ, hogy melyik sorban és oszlopban járunk, úgyhogy egyelőre le kell mondanunk a felhasználóbarátabb hibaüzenetekről.

A peek visszaadja, hogy mi a következő token anélkül, hogy kivenné a listából. Itt megfigyelhető, hogy mennyire okos tud lenni a match, a t :: _ szerkezet ismerős lehet a tokenize-ből, mint a lista elejére fűző operátor, de ebben a kontextusban a t változóba a lista első elemét fogja tenni a match, a lista többi részével pedig nem kívánunk foglalkozni (_).

A consume is visszaadja a következő tokent, de ki is szedi a listából (a lista maradéka lesz a ps.tokens új értéke).

Rá is térhetünk a konkrét értelmezésre. A műveleti sorrend, amit szeretnénk elérni:

1. típusok értelmezése (parse_primary)
2. boolean not operátor (parse_bool_unary)
3. boolean and és or operátor (parse_bool_expr)

Először a kifejezéseket fogjuk feldolgozni... mivel csak kifejezéseink vannak. És csak boolean típusunk, ezért végeredményben csak boolean kifejezéseket fogunk feldolgozni. A kódban a gyengébb operátoroktól haladunk lefelé az erősebb operátorokig.

let rec parse_expr ps =
  parse_bool_expr ps

and parse_bool_expr ps =
  let rec loop left =
    match peek ps with
    | TBoolAnd ->
      ignore (consume ps);
      let right = parse_bool_unary ps in
      loop (EBoolAnd (left, right))
    | TBoolOr ->
      ignore (consume ps);
      let right = parse_bool_unary ps in
      loop (EBoolOr (left, right))
    | _ -> left
  in
  loop (parse_bool_unary ps)

A parse_expr-nek nincs sok értelme, csak nem akartam, hogy egy olyan specifikus nevű függvénnyel induljon a kifejezések feldolgozása, mint a parse_bool_expr.

Az egymásra épülő rekurzív függvények az and segítségével vannak összefűzve. Itt a tokenize-ból már ismert rekurzív loop szerkezetet használjuk, ami megkapja a két változós operátor bal operandusát egy lentebbi szinttől. Ha talál hozzá and vagy or operátort, akkor épít egy megfelelő fa elemet és megpróbál rekurzívan további and vagy or operátorokat keresni. Ha nem sikerül, akkor visszaadja az eddig összegyűjtött dolgokat (vagy az eredeti bal operandust).

Érdemes itt még megjegyezni, hogy a boolean operátorok esetén tradicionálisan az and erősebb szokott lenni, mint az or. A jelenlegi implementációnk szerint viszont egy szinten vannak és balról jobbra kerülnek kiértékelésre.

Mivel mi vagyunk eme világ alkotói, tekinthetünk erre elvárt működésként vagy hibaként is. Utóbbi értelmezés esetén a javítás remek gyakorlási lehetőség az olvasó számára. Ehhez a parse_bool_expr-et kell szétszedni két szintre: a parse_bool_or_expr a parse_bool_and_expr-re hívna tovább, a parse_bool_and_expr pedig a parse_bool_unary-ra.

A következő szintünk az egy változós operátor (not):

and parse_bool_unary ps =
  match peek ps with
  | TBoolNot ->
    ignore (consume ps);
    EBoolNot (parse_bool_unary ps)
  | _ -> parse_primary ps

Ha találunk not tokent, akkor visszaadjuk a hozzá tartozó fa elemet (aminek az értéke szintén lehet egy not operátor vagy egy egyszerű érték), egyébként megpróbálunk egyszerű értékeket keresni.

Nem maradt más hátra, mint az egyszerű értékek feldolgozása:

and parse_primary ps =
  match peek ps with
  | TBool b ->
    ignore (consume ps);
    EBool b
  | t -> raise (ParseError (Printf.sprintf "Unexpected token '%s'" (show_token t)))

Ha true vagy false következik, akkor tovább növesztjük a fát egy EBool elemmel, egyébként dobunk egy hibát, hogy ilyen tokenre nem számítottunk. Végül a függvény, ami ezt az egészet meghívja:

let parse_program tokens =
  let ps = make_parser tokens in
  let expr = parse_expr ps in
  let t = peek ps in
  if t <> TEOF then
    raise (ParseError (Printf.sprintf "Unexpected token '%s'" (show_token t)));
  expr

Mivel jelenleg csak egy kifejezésből áll a nyelvünk, ha a kifejezés értelmezése után maradt még token, ami nem a TEOF, akkor baj van.

Az új "main" függvényünkben felépítjük a fát és ki is íratjuk:

let () =
  let src = {|not true or false and true|} in
  try
    let tokens = tokenize src in
    print_endline (String.concat "; " (List.map show_token tokens));
    let ast = parse_program tokens in
    print_endline (show_expr ast)
  with
  | LexError e -> print_endline ("Fatal error: " ^ e)
  | ParseError e -> print_endline ("Parse error: " ^ e)

A kimenet pedig valahogy így néz ki:

$ ocaml main.ml
TBoolNot; TBool(true); TBoolOr; TBool(false); TBoolAnd; TBool(true); TEOF
EBoolAnd(EBoolOr(EBoolNot(EBool(true)), EBool(false)), EBool(true))

A sok rekurzió egy kicsit össze tudja zavarni az ember lelki világát, úgyhogy ezen a ponton érdemes átgondolni, hogy hogyan is épül fel a fa.

1. a parse_bool_expr meghívja a parse_bool_unary-t, ami megtalálja a TBoolNot tokent, visszaad egy EBoolNot elemet, aminek az értékéhez újra meghívja saját magát
2. a következő TBool token nem illeszkedik a parse_bool_unary dolgaira, így tovább csorog a parse_primary-ba, ahol lesz belőle egy EBool elem és visszaugrunk a parse_bool_expr-be
3. a parse_bool_expr-ben belépünk a loop-ba, ami talál egy TBoolOr tokent, amiből lesz egy EBoolOr elem, aminek a bal oldali operandusa a korábban megkapott EBoolNot(EBool(true)), a jobb oldali operandus kiszámításához pedig meghívja a parse_bool_unary-t
4. a parse_bool_unary nem lát egy változós operátort, úgyhogy a parse_primary ad vissza egy EBool-t és visszaugrunk a loop-ba
5. kész az EBoolOr elemünk, amit bal oldali operandusként használva újra meghívjuk a loop-ot
6. a loop talál egy TBoolAnd tokent, amiből lesz egy EBoolAnd és keres hozzá egy jobb oldali operandust a parse_bool_unary segítségével
7. a parse_bool_unary nem lát egy változós operátort, úgyhogy a parse_primary ad vissza egy EBool-t és visszaugrunk a loop-ba
8. a TEOF token következik, ami nem illeszkedik semmire, úgyhogy kiszállunk a loop-ból és a parse_bool_expr-ből is
9. a parse_program látja a TEOF-ot és ez boldogsággal tölti el

Persze előfordulhat olyan eset is, ahol a parse_program már nem ilyen boldog. Mondjuk próbáljuk ki azt, hogy false not and true:

$ ocaml main.ml
TBool(false); TBoolNot; TBoolAnd; TBool(true); TEOF
Parse error: Unexpected token 'TBoolNot'

Ennek a lépésnek a módosításai megtekinthetőek itt.

A programunk jelenleg egy darab kifejezésből áll, amit ugyan ki lehetne értékelni, de senki nem kezd semmit ezzel az értékkel. Szükségünk lenne egy utasításra.

Utasítások

Az első felmerülő gondolatom az volt, hogy jó lenne, ha valami kimenetet is tudna generálni a programunk. Ennek tükrében a print egy remek választásnak tűnik, mint első utasítás.

Újra alkalmunk van meghozni egy rakás döntést a szintaktikával kapcsolatban. Én azzal mentem, hogy az utasításokat új sorok választják el egymástól, nincs erre külön karakter bevezetve (mint például a klasszikus ;). Az utasítás pedig függvényhívásként fog kinézni: print(kifejezés).

Először is szükségünk lesz néhány új tokenre:

type token =
  (* ... *)
  | TLeftParen
  | TRightParen
  | TNewLine
  | TIdentifier of string
  (* ... *)

Innentől az új sor is egy token lesz, mivel van nyelvi jelentősége. A TIdentifier egy általános azonosító lesz, amit a print-re is használni fogunk. A (* és *) pedig a kommenteket hivatott jelölni OCaml-ben, úgyhogy azok csak a meglévő részek helyett vannak, hogy ne kelljen mindent ismételni.

Természetesen a show_token-t is frissítenünk kell az új érkezőkkel:

let show_token token =
  match token with
  (* ... *)
  | TLeftParen -> "TLeftParen"
  | TRightParen -> "TRightParen"
  | TNewLine -> "TNewLine"
  | TIdentifier s -> Printf.sprintf "TIdentifier(%s)" s
  (* ... *)

Eddig talán semmi meglepő. A lexikális elemzőnk tokenize_name része egyszerűsödik egy kicsit, mivel innentől minden alfabetikus azonosítót elfogadunk a lexikális elemzés szintjén:

let tokenize_name ls =
  (* ... *)
  match name with
  | "true"  -> TBool true
  | "false" -> TBool false
  | "and"   -> TBoolAnd
  | "or"    -> TBoolOr
  | "not"   -> TBoolNot
  | _       -> TIdentifier name

Az ismeretlen azonosítók innentől a szintaktikai elemzés során fognak hibát dobni.

A tokenize mintaillesztését is módosítanunk kell egy kicsit, hogy támogassuk az új nyelvi elemeket.

match current_char ls with
| ' ' | '\t' | '\r' ->
  step ls;
  loop tokens
| '\n' ->
  step_line ls;
  loop (TNewLine :: tokens)
| '(' ->
  step ls;
  loop (TLeftParen :: tokens)
| ')' ->
  step ls;
  loop (TRightParen :: tokens)
| 'a'..'z' ->
  loop (tokenize_name ls :: tokens)
| c ->
  raise (LexError (Printf.sprintf "Unexpected character '%c' on line %d col %d" c ls.line ls.col))

Az új sor karakterre már nem csak léptetünk, ezen kívül kezeljük a nyitó- és csukó zárójeleket is.

A szintaxis fa egy új típussal bővül az utasításokhoz, aminek a print lesz az első tagja.

type stmt =
  | SPrint of expr

A könnyebb debuggolás érdekében ide sem árt a kapcsolódó show_stmt függvény:

let show_stmt s =
  match s with
  | SPrint e -> Printf.sprintf "SPrint(%s)" (show_expr e)

A szintaktika elemzéshez szükségünk lesz két új segéd függvényre:

let expect ps tok =
  let t = consume ps in
  if t <> tok then
    raise (ParseError (Printf.sprintf "Unexpected token '%s', expected '%s'" (show_token t) (show_token tok)))

let skip_newlines ps =
  while peek ps = TNewLine do ignore (consume ps) done

Az expect hibát dob, ha a következő token nem az, mint amire számítunk. A skip_newlines segítségével pedig az üres sorokat hagyhatjuk figyelmen kívül.

A jó hír az, hogy a parse_expr rekurziós láncunkhoz nem is kell hozzányúlnunk. Egy új láncot indítunk:

let rec parse_stmts ps =
  let rec loop stmts =
    skip_newlines ps;
    match peek ps with
    | TEOF -> ignore (consume ps); stmts
    | _ -> loop (parse_stmt ps :: stmts)
  in

  List.rev (loop [])

A rekurzív szerkezet már ismerős lehet a tokenize-ból, az üres sorokat ignoráljuk, a fájl vége esetén kiszállunk a rekurzióból, egyébként pedig feldolgozzuk a következő utasítást és hozzácsapjuk a lista elejéhez. A végén pedig itt is meg kell fordítanunk a listát.

and parse_stmt ps =
  match peek ps with
  | TIdentifier "print" ->
    ignore (consume ps);
    expect ps TLeftParen;
    let expr = parse_expr ps in
    expect ps TRightParen;
    SPrint(expr)
  | t -> raise (ParseError (Printf.sprintf "Unexpected token '%s'" (show_token t)))

A hozzá tartozó parse_stmt, ami a print azonosítót kezeli. Az azonosító után egy nyitó zárójelnek kell következnie, ami után egy kifejezésre számítunk, amit egy csukó zárójel zár le. Egyéb utasításokat még nem kezelünk, úgyhogy minden másra hibát dobunk (ide vándorolt át a tokenize_name-ben megszüntetett kivétel dobás).

Ezek után a parse_program igényel még némi egyszerűsítést:

let parse_program tokens =
  let ps = make_parser tokens in
  parse_stmts ps

És a "main" függvényünk is módosul egy picit:

let () =
  let src = {|print(false or true)

print(false)|} in
  try
    let tokens = tokenize src in
    print_endline (String.concat "; " (List.map show_token tokens));
    let stmts = parse_program tokens in
    print_endline (String.concat "\n" (List.map show_stmt stmts));
  with
  | LexError e -> print_endline ("Fatal error: " ^ e)
  | ParseError e -> print_endline ("Parse error: " ^ e)

Kimenetként pedig a következőt kell látnunk:

$ ocaml main.ml
TIdentifier(print); TLeftParen; TBool(false); TBoolOr; TBool(true); TRightParen; TNewLine; TNewLine; TIdentifier(print); TLeftParen; TBool(false); TRightParen; TEOF
SPrint(EBoolOr(EBool(false), EBool(true)))
SPrint(EBool(false))

Ennek a lépésnek a módosításai megtekinthetőek itt.

Most már nem csak egy szintaxis fánk van, hanem soronként egy, egy nagyobb programnál egy egész szintaxis erdőt növesztünk.

Ezzel sikerült eljutnunk egy olyan pontra, ahol már van mit érdemben kiértékelni, ha lefuttatnánk ezt a programot, akkor látható eredménye lenne. Kezdjük is el a kiértékelést.

A kiértékelő

A kiértékelő utasításonként megy végig a szintaxis fákon és hajtja végre őket.

Meglepő módon ez a lépés is azzal indul, hogy csinálunk egy új típust és megírjuk a hozzá tartozó show_ függvényt:

type value =
  | VBool of bool

let show_value v =
  match v with
  | VBool b -> Printf.sprintf "%B" b

Jöhet a kifejezések kiértékelése.

let rec eval expr =
  match expr with
  | EBool b -> VBool b
  | EBoolNot e ->
    (match eval e with
    | VBool b -> VBool (not b))
  | EBoolAnd (l, r) ->
    (match eval l, eval r with
    | VBool a, VBool b -> VBool (a && b))
  | EBoolOr (l, r) ->
    (match eval l, eval r with
    | VBool a, VBool b -> VBool (a || b))

Nem meglepő, hogy itt is mintaillesztéssel és rekurzióval operálunk. Mivel boolean típuson kívül mással még nem rendelkezünk, az eval-ban lévő mintaillesztések egy kicsit furán hathatnak, de később még jól fognak jönni.

let exec stmt =
  match stmt with
  | SPrint e ->
    print_endline (show_value (eval e))

Az exec-ben a print_endline egy beépített függvény, a show_value-t pedig végre már nem csak debuggolási céllal használjuk, hanem a tényleges kód kiértékelés során.

Már csak a "main" függvény módosítása maradt hátra, hogy végrehajtsuk az utasításokat:

let () =
  let src = {|print(false or not true)

print(not false and true)|} in
  try
    let tokens = tokenize src in
    let stmts = parse_program tokens in
    List.iter exec stmts
  with
  | LexError e -> print_endline ("Fatal error: " ^ e)
  | ParseError e -> print_endline ("Parse error: " ^ e)

A kimenet pedig reményeink szerint az lesz, amire számítunk:

$ ocaml main.ml
false
true

Ennek a lépésnek a módosításai megtekinthetőek itt.

Tulajdonképpen van egy kész programunk, ami boolean kifejezéseket tud kiértékelni és kiírja az eredményüket. De azért kár lenne itt megállni.

Zárójelezés

Jelenleg, ha megpróbáljuk futtatni a print(not (false or not true)) programot, akkor a következő hibát kapjuk:

$ ocaml main.ml
Parse error: Unexpected token 'TLeftParen'

Sajnos a nyelv hibakezelése nem segít megérteni, hogy honnan jön pontosan a hiba, de joggal gyanakodhatunk a parse_primary függvényre. Szóval ha szeretnénk támogatni a tetszőleges zárójelezhetőséget, akkor felvehetünk a kifejezés feldolgozó láncba egy új függvényt:

1. típusok értelmezése (parse_primary)
2. zárójelezés (parse_bracketing)
3. boolean not operátor (parse_bool_unary)
4. boolean and és or operátor (parse_bool_expr)

and parse_bracketing ps =
  match peek ps with
  | TLeftParen ->
    ignore (consume ps);
    let expr = parse_expr ps in
    expect ps TRightParen;
    expr
  | _ -> parse_primary ps

Nem feltétlen kellene az új függvény, elég lenne egy új ág a parse_primary mintaillesztésében is, de úgy érzem ez így jobban kifejezi a műveleti sorrendet.

A módosításunk után már a megfelelő kimenetet fogjuk kapni:

$ ocaml main.ml
true

Ennek a lépésnek a módosításai megtekinthetőek itt.

Ez azért elég menő, hogy kevesebb, mint tíz sornyi kóddal implementáltuk a tetszőleges zárójelezhetőséget. Ideje valami nagyobb szintaxis fába vágni a fejszénket.

Számos lehetőség

Van egy működő folyamatunk, ami értelmezni és futtatni tudja a kapott nyers szöveget. Egy új típus, mondjuk a számok hozzáadása már nem jelent különösebb meglepetést kód szinten. Az összes réteghez hozzá kell nyúlnunk ugyan, de a módosítások egyszerűek, még ha viszonylag sok kóddal is járnak. Először is a tokenek:

type token =
  (* ... *)
  | TNumber of float
  | TLt
  | TLtEq
  | TGt
  | TGtEq
  | TEq
  | TNotEq
  | TPlus
  | TMinus
  | TAsterisk
  | TSlash
  | TPercent
  (* ... *)

Jó sok új token, implementálni fogjuk a <, <=, >, >=, ==, <> összehasonlító operátorokat és a +, -, *, /, % aritmetikai operátorokat is. Természetesen a show_token függvényt is bővíteni kell, de ezt mindenki képzeletére bízom az előző bővítések alapján.

A lexikális elemző mintaillesztése a tokenize függvényben a következőkkel bővül:

match current_char ls with
(* ... *)
| '+' -> step ls; loop (TPlus :: tokens)
| '-' -> step ls; loop (TMinus :: tokens)
| '*' -> step ls; loop (TAsterisk :: tokens)
| '/' -> step ls; loop (TSlash :: tokens)
| '%' -> step ls; loop (TPercent :: tokens)
| '<' ->
  step ls;
  (match current_char ls with
  | '=' -> step ls; loop (TLtEq :: tokens)
  | '>' -> step ls; loop (TNotEq :: tokens)
  | _   -> loop (TLt :: tokens))
| '>' ->
  step ls;
  (match current_char ls with
  | '=' -> step ls; loop (TGtEq :: tokens)
  | _   -> loop (TGt :: tokens))
| '=' ->
  step ls;
  (match current_char ls with
  | '=' -> step ls; loop (TEq :: tokens)
  | c   -> raise (LexError (Printf.sprintf "Unexpected character '%c' on line %d col %d" c ls.line ls.col)))
| '0' .. '9' ->
  loop (tokenize_number ls :: tokens)
(* ... *)

Apró újdonság itt, hogy egyes operátorokhoz két karaktert együtt kell néznünk. Valamint nincs még = operátorunk, úgyhogy arra még hibát dobunk.

Ezzel bevezettünk egy érdekes bug-ot is: a step ls utáni current_char hívás nem ellenőrzi, hogy vége van-e a forráskódnak, így előfordulhat, hogy egy nem várt OCaml kivételt kapunk (Invalid_argument "index out of bounds".) olyan egyébként is hibás inputra, mint például a print(1 <.

A tokenize_number kísértetiesen hasonlít a korábbi tokenize_name függvényre, csak éppen számokkal:

let tokenize_number ls =
  let is_number_char ch = ch >= '0' && ch <= '9' || ch == '.' in
  let start = ls.pos in

  while ls.pos < ls.len && is_number_char (current_char ls) do
    step ls
  done;

  TNumber (float_of_string (String.sub ls.src start (ls.pos - start)))

A szintaxis fa is bővül az új operátorokhoz szükséges elemekkel:

type expr =
  (* ... *)
  | ENumber of float
  | EGt of expr * expr
  | EGtEq of expr * expr
  | ELt of expr * expr
  | ELtEq of expr * expr
  | EEq of expr * expr
  | ENotEq of expr * expr
  | EAdd of expr * expr
  | ESub of expr * expr
  | EMul of expr * expr
  | EDiv of expr * expr
  | EMod of expr * expr
  (* ... *)

Visszajutottunk a szintaktikai elemzőhöz, így ismét felmerül a műveleti sorrend kérdése. Az új operátorok így illeszkednek bele a jelenlegi rendszerünkbe:

1. típusok értelmezése (parse_primary)
2. zárójelezés (parse_bracketing)
3. szorzás és osztás (parse_mul_div)
4. összeadás és kivonás (parse_add_sub)
5. összehasonlító operátorok (parse_comparison)
6. boolean not operátor (parse_bool_unary)
7. boolean and és or operátor (parse_bool_expr)

Szóval a parse_bool_unary után kell beszúrnunk a láncba három új függvényt:

and parse_comparison ps =
  let left = parse_add_sub ps in
  match peek ps with
  | TLt    -> ignore (consume ps); ELt (left, parse_add_sub ps)
  | TLtEq  -> ignore (consume ps); ELtEq (left, parse_add_sub ps)
  | TGt    -> ignore (consume ps); EGt (left, parse_add_sub ps)
  | TGtEq  -> ignore (consume ps); EGtEq (left, parse_add_sub ps)
  | TEq    -> ignore (consume ps); EEq (left, parse_add_sub ps)
  | TNotEq -> ignore (consume ps); ENotEq (left, parse_add_sub ps)
  | _ -> left

Hasonló a szerkezete a korábbiakhoz, nem hívja saját magát rekurzívan, mert nem akartam támogatni a 1 < 2 >= 0 == 0 jellegű kifejezéseket. Vannak nyelvek, amik ezt részben támogatják (például Python-ban az a < b < c formátum működik), ez pusztán csak ízlés kérdése.

and parse_add_sub ps =
  let rec loop left =
    match peek ps with
    | TPlus  -> ignore (consume ps); loop (EAdd (left, parse_mul_div ps))
    | TMinus -> ignore (consume ps); loop (ESub (left, parse_mul_div ps))
    | _ -> left
  in
  loop (parse_mul_div ps)

Itt megvan az említett belső rekurzív loop, úgyhogy írhatunk olyat, hogy 1 + 2 + 3 - 4, ami aztán balról jobbra fog kiértékelődni.

and parse_mul_div ps =
  let rec loop left =
    match peek ps with
    | TAsterisk -> ignore (consume ps); loop (EMul (left, parse_bracketing ps))
    | TSlash    -> ignore (consume ps); loop (EDiv (left, parse_bracketing ps))
    | TPercent  -> ignore (consume ps); loop (EMod (left, parse_bracketing ps))
    | _ -> left
  in
  loop (parse_bracketing ps)

A szorzás-osztás változatához nem lehet sok mindent hozzáfűzni, ugyanaz a logika, mint az összeadás-kivonásnál, csak a láncban utánunk következő függvényt hívjuk meg benne.

Még egy apró pici módosítás a parse_primary függvényben.

and parse_primary ps =
  match peek ps with
  | TBool b -> ignore (consume ps); EBool b
  | TNumber n -> ignore (consume ps); ENumber n
  | t -> raise (ParseError (Printf.sprintf "Unexpected token '%s'" (show_token t)))

A TBool-hoz hasonlóan lekezeljük a TNumber típusunkat is.

Ezzel vissza is értünk a kiértékeléshez. Természetesen bővül a value típus és a hozzá tartozó show_value függvény:

exception RuntimeError of string

type value =
  | VBool of bool
  | VNumber of float

let show_value v =
  match v with
  | VBool b -> string_of_bool b
  | VNumber n ->
    if Float.is_integer n then string_of_int (int_of_float n)
    else string_of_float n

Aztán kiegészül az eval is:

let rec eval expr =
  match expr with
  | EBool b -> VBool b
  | ENumber b -> VNumber b
  | EBoolNot e ->
    (match eval e with
    | VBool b -> VBool (not b)
    | _ -> raise (RuntimeError "Invalid type"))
  | EBoolAnd (l, r) -> eval_bool_arithmetic ( && ) l r
  | EBoolOr (l, r)  -> eval_bool_arithmetic ( || ) l r
  | EGt (l, r)      -> eval_comparison ( > ) l r
  | EGtEq (l, r)    -> eval_comparison ( >= ) l r
  | ELt (l, r)      -> eval_comparison ( < ) l r
  | ELtEq (l, r)    -> eval_comparison ( <= ) l r
  | EEq (l, r)      -> eval_comparison ( = ) l r
  | ENotEq (l, r)   -> eval_comparison ( <> ) l r
  | EAdd (l, r)     -> eval_arithmetic ( +. ) l r
  | ESub (l, r)     -> eval_arithmetic ( -. ) l r
  | EMul (l, r)     -> eval_arithmetic ( *. ) l r
  | EDiv (l, r)     -> eval_arithmetic ( /. ) l r
  | EMod (l, r)     ->
    (match eval l, eval r with
    | VNumber a, VNumber b -> VNumber (float_of_int (int_of_float a mod int_of_float b))
    | _ -> raise (RuntimeError "Invalid type"))

A bináris és/vagy operátorokat is kiemeltem egy kis segéd függvénybe, ahogy az új operátorok elkészültek. A függvény neve utáni első paraméter az operátor zárójelben, amit így át lehet passzolni, mint bármilyen más függvényt. Az aritmetikai operátorok egy kicsit furák, mivel az OCaml-nek külön operátorai vannak float-ok között végzett műveletekre.

A maradék operátor egy kicsit kilóg a sorból, mivel nincs értelmezve float típusra, így először át kell konvertálnunk mindent int-re, majd az eredményt vissza float-ra, mivel a mi nyelvünk egyetlen szám típusa float a motorháztető alatt.

and eval_bool_arithmetic op l r =
  match eval l, eval r with
  | VBool a, VBool b -> VBool (op a b)
  | _ -> raise (RuntimeError "Invalid type")

and eval_comparison op l r =
  match eval l, eval r with
  | VNumber a, VNumber b -> VBool (op a b)
  | _ -> raise (RuntimeError "Invalid type")

and eval_arithmetic op l r =
  match eval l, eval r with
  | VNumber a, VNumber b -> VNumber (op a b)
  | _ -> raise (RuntimeError "Invalid type")

Maguk a segéd függvények nagyon hasonlítanak egymásra, csak az változik, hogy milyen típusokon hajlandóak dolgozni és annak milyen típus lesz az eredménye.

Egy dinamikusan típusos nyelvben ilyen helyeken születnek meg azok a szabályok, ami alapján a típus rendszer működik. Például az eval_bool_arithmetic elfogadhatna mindkét oldalon VNumber-t is és hozhatna egy szabályt, hogy a 0 az false, minden más true.

Apró érdekesség itt még, hogy az == és <> jelenleg csak számokra működik, nem tudjuk azt lefuttatni, hogy print(true == true), a többi összehasonlító operátornak viszont nem feltétlenül van értelme boolean értékek esetén (bár ha a false az 0, a true pedig 1, akkor értelmezhetőek azok is). További döntések, amiket a világ alkotóiként meghozhatunk.

És ezzel sikeresen be is vezettünk egy új típust a programozási nyelvünkbe. Ha lefuttatjuk mondjuk a

print(1 + 1 * 2 - 8 < 3 and not 15 / 5 > 7 - 1 + 2 - 3)

programot, akkor a következő kimenetet kapjuk:

$ ocaml main.ml
true

De mi történik akkor, ha azt a programot futtatjuk le, hogy print(-6 < 0)?

$ ocaml main.ml
Parse error: Unexpected token 'TMinus'

Ó, jaj! Nem támogatjuk a forráskódban a negatív számokat.

Mint mindenre, erre is többféle megoldás létezik. Kezelhetjük szimplán a negatív számokat (- után számnak kell következnie) vagy lehet a - egyszerre egy és két változós operátor is (az ESub mellett mondjuk egy ENeg), így írhatunk mondjuk olyat, hogy -(6 - 5). Én az előbbivel mentem, de érdemes megpróbálni leimplementálni a második változatot is a gyakorlás kedvéért.

and parse_primary ps =
  match peek ps with
  (* ... *)
  | TMinus ->
    ignore (consume ps);
    (match peek ps with
    | TNumber n -> ignore (consume ps); ENumber (-1. *. n)
    | t -> raise (ParseError (Printf.sprintf "Unexpected token '%s'" (show_token t))))
  (* ... *)

Talán az egyetlen meglepő rész az a (-1. *. n), ami a korábban már említett fura viszony eredménye az OCaml és a float között.

Újra megfuttatva a print(-6 < 0) programot már a helyes megoldást kapjuk:

$ ocaml main.ml
true

Ennek a lépésnek a módosításai megtekinthetőek itt.

Most, hogy már vannak boolean és szám értékeink is, jó lenne őket eltárolni valahol. Itt az ideje a változók bevezetésének.

Változók

A lexikai és szintaktikai elemzés oldalán nem lesznek nagy meglepetések, de a kiértékelés egy kicsit bonyolódni fog. Kezdjük is a szokásos tokeneknél:

type token =
  (* ... *)
  | TEqual
  (* ... *)

A lexer-ben már megágyaztunk neki, amikor az == operátort felvettük, csak a hibaüzenetet kell kicserélni az új működésre.

match current_char ls with
(* ... *)
| '=' ->
  step ls;
  (match current_char ls with
  | '=' -> step ls; loop (TEq :: tokens)
  | _   -> loop (TEqual :: tokens))
(* ... *)

A szintaxis fa kap egy új kifejezést a változókhoz és egy új utasítást az értékadáshoz.

type expr =
  (* ... *)
  | EVar of string

type stmt =
  | SPrint of expr
  | SAssign of string * expr

Az egyszerű értékek kezelése során minden ismeretlen azonosítót változóként fogunk kezelni, majd a kiértékelés eldönti, hogy tényleg létezik-e.

and parse_primary ps =
  match peek ps with
  (* ... *)
  | TIdentifier i -> ignore (consume ps); EVar i
  (* ... *)

Az utasításoknál pedig ha valami azonosítóval kezdődik, akkor arra számítunk, hogy az egy értékadás lesz.

and parse_stmt ps =
  match peek ps with
  (* ... *)
  | TIdentifier t ->
    ignore (consume ps);
    expect ps TEqual;
    SAssign (t, parse_expr ps)
  (* ... *)

Rá is térhetünk az izgalmas részre, a kiértékelésre. A kód futtatása során valahol tárolnunk kell, hogy melyik változónak mi az értéke.

Egy komolyabb programozási nyelvben ez egy bonyolultabb kérdés lenne, mivel kezelnünk kellene a változók hatáskörét is, de a mi kis nyelvünk még nem jutott el olyan érettségi szintre, hogy legyenek hatáskörök, így nekünk elég lesz egy hash-tábla a kulcs-értékek tárolására.

let make_env () = 
  Hashtbl.create 16

let set_env env name value =
  Hashtbl.replace env name value

let lookup_env env name =
  match Hashtbl.find_opt env name with
  | Some v -> v
  | None -> raise (RuntimeError (Printf.sprintf "Undefined variable: %s" name))

A make_env csinál egy üres környezetet, a set_env segítségével beállíthatjuk egy változó értékét, a lookup_env pedig visszaadja ezt az értéket vagy elszáll hibával, ha nem létezik az adott nevű változó.

Az eval és exec részen elég nagy átalakításokra van szükség. Mindkét függvény meg kell, hogy kapja az env változót, amit az összes kapcsolódó hívásnál át kell passzolnunk.

Ezen kívül kezelnünk kell az új kifejezést, ami beolvassa a változó értékét.

let rec eval env expr =
  match expr with
  (* ... *)
  | EVar v -> lookup_env env v
  (* ... *)

Valamint az új utasítást is, ami beállítja egy változó értékét. A változó értéke itt lehet egy kifejezés is, úgyhogy azt előbb ki kell számolnunk.

let exec env stmt =
  match stmt with
  (* ... *)
  | SAssign (name, value) ->
    set_env env name (eval env value)

Az új env változó miatt minimális változások történtek a "main" függvényben is:

let tokens = tokenize src in
let stmts = parse_program tokens in
let env = make_env () in
List.iter (exec env) stmts

A kimenet pedig reményeink szerint a következő lesz:

$ ocaml main.ml
5                                 
6
true

Ennek a lépésnek a módosításai megtekinthetőek itt.

Alakul a nyelv, de valami még hiányzik... a hab a mi kis grammatikai tortánkra.

Vezérlési szerkezetek

Kezd nagyon hosszúra nyúlni ez a bejegyzés, de nem érezném igazi nyelvnek az alkotásunkat a jó öreg if, elif, else és while nélkül. Vegyük is fel hozzájuk az új tokeneket. A négy kulcsszó mellett a két kapcsos zárójel is újdonság lesz a nyelvben.

type token =
  (* ... *)
  | TIf
  | TElseIf
  | TElse
  | TWhile
  | TLeftCurlyBracket
  | TRightCurlyBracket
  (* ... *)

A tokenize_name-ben a szokott módon lekezeljük az új neveket.

match name with
(* ... *)
| "if"    -> TIf
| "elif"  -> TElseIf
| "else"  -> TElse
| "while" -> TWhile
(* ... *)

A tokenize-ban pedig az új zárójeleket.

match current_char ls with
(* ... *)
| '{' -> step ls; loop (TLeftCurlyBracket :: tokens)
| '}' -> step ls; loop (TRightCurlyBracket :: tokens)
(* ... *)

Az utasítások bővítése során belefutunk egy kis újdonságba, az if és a while is utasítások listáját kapja paraméterül.

type stmt =
  | SPrint of expr
  | SAssign of string * expr
  | SIf of expr * stmt list * stmt list
  | SWhile of expr * stmt list

És egyébként is, hol van az elif és az else? Hát, azok olyan dolgok, amiket csak szintaktikai cukornak szokás hívni. Kényelmi funkciók a nyelv felhasználóinak számára, amiknek a szintaxis fa szintjén már nem kell létezni. Az SIf(feltétel, igaz utasítások, hamis utasítások) egyedül le tud kezelni minden esetet:

• ha van elif ág, akkor a hamis utasítások egy egy elemű lista lesz, amiben egy újabb SIf() van
• ha nincsen else ág, akkor az utolsó SIf() hamis utasításai egy üres lista lesz

Az utasítások feldolgozásán egy kicsit módosítanunk kell, eddig TEOF-ig olvastuk be az utasításokat, de innentől lesznek olyan eseteink, amikor az utasítások a következő csukó kapcsos zárójelig tartanak.

let rec parse_stmts ps stop_token =
  let rec loop stmts =
    skip_newlines ps;
    if (peek ps) <> stop_token then
      loop (parse_stmt ps :: stmts)
    else
      stmts
  in

  List.rev (loop [])

A parse_program-ot is hozzá kell igazítani a változáshoz:

let parse_program tokens =
  let ps = make_parser tokens in
  parse_stmts ps TEOF

A parse_stmt egy gyanúsan rövid módosítással úszta meg a történetet:

and parse_stmt ps =
  match peek ps with
  | TIf ->
    parse_if ps
  (* ... *)

Aztán persze jön a tényleges kód, ami az if ágat kezeli.

and parse_if ps =
  ignore (consume ps);
  expect ps TLeftParen;
  let cond = parse_expr ps in
  expect ps TRightParen;

  expect ps TLeftCurlyBracket;
  let then_branch = parse_stmts ps TRightCurlyBracket in
  expect ps TRightCurlyBracket;

  let else_branch = parse_else ps in

  SIf (cond, then_branch, else_branch)

Először a feltételt olvassuk be, aminél számítunk arra, hogy ( és ) között van. Aztán az utasításokat, amik a feltétel teljesülése során futnak majd le, ezeknek { és } között kell lenniük. Az else ágát pedig egy másik függvény kezeli le.

and parse_else ps =
  match peek ps with
  | TElseIf ->
    [ parse_if ps ]
  | TElse ->
    ignore (consume ps);
    expect ps TLeftCurlyBracket;
    let stmts = parse_stmts ps TRightCurlyBracket in
    expect ps TRightCurlyBracket;
    stmts
  | _ -> []

Az elif ág kezelése visszahív a parse_if-re, de az eredményét egy listában adja vissza. Az else ág pedig feldolgozza az utasításokat, amik utána következnek.

and parse_stmt ps =
  match peek ps with
  (* ... *)
  | TWhile ->
    ignore (consume ps);
    expect ps TLeftParen;
    let cond = parse_expr ps in
    expect ps TRightParen;

    expect ps TLeftCurlyBracket;
    let stmts = parse_stmts ps TRightCurlyBracket in
    expect ps TRightCurlyBracket;

    SWhile (cond, stmts)
  (* ... *)

A while kezelése szinte azonos az if-fel, csak nincsen hozzá else ág.

Ezzel a feldolgozás végére is értünk, jöhet a kiértékelés. Először is kicsit átrendeztem az exec függvényt, hogy több utasítást várjon bemenetként és az eredeti exec tartalma átvándorolt az exec_stmt-be.

let rec exec env stmts =
  List.iter (exec_stmt env) stmts

and exec_stmt env stmt =
  match stmt with
  (* ... *)
  | SIf (cond, then_branch, else_branch) ->
    (match eval env cond with
    | VBool true  -> (exec env then_branch)
    | VBool false -> (exec env else_branch)
    | _ -> raise (RuntimeError "If condition must be a boolean"))
  | SWhile (cond, stmts) ->
    let rec loop () =
      match eval env cond with
      | VBool true ->
        exec env stmts;
        loop ()
      | VBool false -> ()
      | _ -> raise (RuntimeError "While condition must be a boolean")
    in
    loop ()

Ezt a módosítást rögtön használja is az SIf és az SWhile kezelése. Az SIf-nél mintaillesztéssel döntjük el, hogy melyik ág utasításait futtassuk le. Az SWhile-nál pedig rekurzióval futtatjuk meg a kapcsolódó utasításokat, amíg a feltétel hamis nem lesz.

A "main" függvényben csak az exec használatát kell kijavítanunk.

let tokens = tokenize src in
let stmts = parse_program tokens in
let env = make_env () in
exec env stmts

Aztán futtathatunk valamit, ami végre igazi kódnak néz ki:

fizzbuzz = -15
fizz = -3
buzz = -5
i = 1
while (i <= 15) {
  if (i % 15 == 0) {
    print(fizzbuzz)
  } elif (i % 3 == 0) {
    print(fizz)
  } elif (i % 5 == 0) {
    print(buzz)
  } else {
    print(i)
  }
  i = i + 1
}

Sajnos nem léteznek a stringek a mi kis világunkban, úgyhogy csak így lehetett megoldani, de a kimenet így is magáért beszél. Vállalati szintű problémákat oldunk meg egyszerű eleganciával.

$ ocaml main.ml
1
2
-3
4
-5
-3
7
8
-3
-5
11
-3
13
14
-15

Ennek a lépésnek a módosításai megtekinthetőek itt.

Itt a vég

Ide is eljutottunk hát. "A gép forog, az alkotó pihen." Messze a leghosszabb írás, ami eddig a blogon megjelent. Gratulálok mindenkinek, akinek sikerült eljutnia idáig. Remélem okoztam néhány éjszakába nyúló programozós estét.

És a végeredmény? Alig 500 sorban írtunk valamit, ami programozási nyelvnek nevezhető (még ha elég korlátolt is). Engem meglepett a végén, hogy milyen rövidre sikeredett.

Számtalan bővítési lehetőség és a hozzá tartozó kihívások rejlenek még ebben a projektben, de egy jó alapot sikerült összerakni a további kísérletezgetéshez. Csak hogy néhány logikus következő lépést említsek:

• a hibakezelés kibővítése (ParseError és RuntimeError esetén is lehessen tudni, hogy hol volt a hiba az eredeti forráskódban)
• rövidzár-kiértékelés boolean kifejezéseknél (ha a and b esetén a false-ra értékelődik ki, akkor nem kell b-t kiértékelni)
• függvények (és a velük jövő probléma a változók hatásköreivel)
• string típus és a hozzá tartozó operátorok, függvények/utasítások
• listák és asszociatív tömbök

Én viszont zárom soraimat, köszönöm a figyelmet.

TEOF