Praksa programskih jezikov

Praksa programskih jezikov#

Da lahko začnemo raziskovati lastnosti programskih jezikov, potrebujemo primer takega jezika. To bo enostaven ukazni (oz. imperativni) programski jezik IMP, ki podpira aritmetične izraze (cela števila, spremenljivke, aritmetične operacije), logične izraze (logični konstanti ter primerjave aritmetičnih izrazov) ter ukaze (pogojne stavke, zanke, …).

Sintaksa jezika#

Prva stvar, ki jo moramo podati v definiciji programskega jezika, je njegova sintaksa - torej zapis vseh izrazov, ki jih jezik omogoča. Ločujemo med konkretno sintakso, ki definira zaporedja znakov, ki predstavljajo veljavne programe, ter abstraktno sintakso, ki možne izraze jezika predstavi z drevesno strukturo. Na primer, 1 + (2 * 3) in 1+2*3 sta različna niza konkretne sintakse, ki oba predstavljata izraz abstraktne sintakse, predstavljen z drevesom

ki ga na krajše pišemo kar kot $1 + (2 * 3)$, pri čemer matematična pisava nakazuje, da nas podrobnosti, kot so presledki, ne zanimajo.

Konkretna sintaksa#

Konkretno sintakso običajno podajamo v Backus-Naurovi obliki (BNF). Ker mora konkretno sintakso razumeti tudi računalnik, v njej upoštevamo tudi presledke, zamike, oklepaje, komentarje, … Ta je sestavljena iz pravil, ki povedo, kakšne vrste simbolov lahko nastopajo v jeziku. Pravilo, ki podaja sintakso določenega simbola je oblike

<simbol> ::= moznost1 | moznost2 | ...

kjer je vsaka izmed možnosti sestavljena iz enega ali več nizov ali drugih simbolov. Na primer, simbol za števko `<digit>` je lahko kateri koli izmed nizov `"0"`, `"1"`, …, `"9"`, številka pa je sestavljena iz ene ali več števk ter morebitnega predznaka:

```text
<digit> ::= "0" | "1" | ... | "9"
<digits> ::= "" | <digit> <digits>
<integer> ::= <digits> | "-" <digits>

Za programski jezik IMP bo konkretna sintaksa

<space> ::= " " | "\n" | "\t" | "\r"
<spaces> ::= "" | <spaces1>
<spaces1> ::= <space> <spaces>

<alpha> ::= "a" | "b" | ... | "z"
<alphanum> ::= <alpha> | <digit>
<alphanums> ::= "" | <alphanum> <alphanums>
<ident> ::= <alpha> <alhpanums>
<location> ::= "#" <ident>

<exp> ::= <atomic_exp> <spaces> "+" <spaces> <atomic_exp>
        |  <atomic_exp> <spaces> "-" <spaces> <atomic_exp>
        |  <atomic_exp> <spaces> "*" <spaces> <atomic_exp>
        |  <atomic_exp>
<atomic_exp> ::= <location>
              |  <integer>
              |  "(" <spaces> <exp> <spaces> ")"
<bexp> ::= "TRUE"
        |  "FALSE"
        |  <exp> <spaces> "=" <spaces> <exp>
        |  <exp> <spaces> "<" <spaces> <exp>
        |  <exp> <spaces> ">" <spaces> <exp>
<cmd> ::= "IF" <spaces1> <bexp> <spaces1> "THEN" <spaces1> <cmd> <spaces1> "ELSE" <spaces1> <cmd>
        |  "WHILE" <spaces1> <bexp> <spaces1> "DO" <spaces1> <cmd>
        |  <atomic_cmd> <spaces> ";" <spaces> <cmd>
<atomic_cmd> ::= <location> <spaces> ":=" <spaces> <exp>
              |  "SKIP"
              |  "(" <spaces> <cmd> <spaces> ")"

Kaj predstavljajo zgoraj omenjeni simboli, si bomo ogledali pri abstraktni sintaksi jezika IMP, za idejo pa lahko vseeno podamo primer veljavnega programa v konkretni sintaksi:

#fact := 1;
WHILE #m > 0 DO (
    #fact := #fact * #m;
    #m := #m - 1
)

Videti je, da program v pomnilniško lokacijo #fact shrani fakulteto števila, shranjenega v #m, vendar tega ne vemo, dokler ne podamo semantike jezika.

Abstraktna sintaksa#

Kot smo že videli, v abstraktni sintaksi možne izraze predstavimo z drevesi, katerih otroci predstavljajo njihove podizraze. Zaradi krajšega zapisa pa tudi abstraktno sintakso podamo v zapisu, podobnemu BNF, pri čemer nas podrobnosti, kot so oklepaji ali točen zapis spremenljivk in števil ne zanima. Tako bomo predpostavili, da $n$ predstavlja poljubno celo število, $\ell$ pa poljubno pomnilniško lokacijo.

Kot smo že omenili, je jezik IMP sestavljen iz aritmetičnih izrazov, ki jih bomo označevali s spremenljivko $e$, logičnih izrazov, ki jih bomo označevali z $b$, ter ukazov, ki jih bomo označevali s $c$.

\[\begin{split} \begin{aligned} \text{aritmetični izraz } e &::= \ell \mid \intsym{n} \mid e_1 + e_2 \mid e_1 - e_2 \mid e_1 * e_2 \\ \text{logični izraz } b &::= \true \mid \false \mid e_1 = e_2 \mid e_1 < e_2 \mid e_1 > e_2 \\ \text{ukaz } c &::= \ifthenelse{b}{c_1}{c_2} \mid \whiledo{b}{c} \mid c_1 ; c_2 \mid \ell := e \mid \skip \end{aligned} \end{split}\]

Oglejmo si vse veljavne dele jezika, pri čemer bomo za vsakega neformalno povedali, kaj predstavlja. Aritmetični izrazi so sestavljeni iz branja vrednosti pomnilniških lokacij, celoštevilskih konstant (ki jih podčrtamo, da jih ločimo od celih števil) ter aritmetičnih operacij, logični izrazi pa so sestavljeni iz logičnih konstant ter primerjav. Ukazi so bolj zanimivi:

pogojni ukaz, ki izvede $c_1$, kadar $b$ predstavlja resnično logično vrednost, oziroma $c_2$, kadar $b$ predstavlja neresnično logično vrednost;
zanka while izvaja ukaz $c$, dokler $b$ predstavlja resnično logično vrednost;
zaporedno izvajanje najprej izvede $c_1$ - ko (če) se ta konča, izvede še $c_2$;
prirejanje izračuna aritmetični izraz $e$ ter njegovo vrednost zapiše v pomnilniško lokacijo $\ell$;
zadnji ukaz ne naredi ničesar, uporabimo pa ga na primer takrat, kadar v pogojnem stavku želimo nekaj storiti le v eni izmed vej.

Zgornji program bi v abstraktni sintaksi lahko predstavili z ukazom

\[\begin{split} \begin{aligned} &\mathsf{fact} := \intsym{1}; \\ &\whiledo{\mathsf{m} > \intsym{0}}{} \\ &\quad \mathsf{fact} := \mathsf{fact} * \mathsf{m}; \\ &\quad \mathsf{m} := \mathsf{m} - \intsym{1} \end{aligned} \end{split}\]

Implementacija jezika#

Običajno bi po sintaksi jezika formalno podali še njegovo semantiko, torej pomen posameznih delov. Ker za to še nimamo ustreznih matematičnih orodij, bomo ravnali podobno kot pri večini programskih jezikov: napisali bomo implementacijo, torej program, ki prebere ukaze, zapisane v konkretni sintaksi, ter jih na nek (po vsej sreči smiselen) način izvede. Nato pa bomo proglasili, da je pomen programa v IMPu tisto, kar implementacija z njim naredi. Implementacijo bomo napisali v programskem jeziku OCaml, ki je eden najprikladnejših jezikov za implementacije programskih jezikov. Končnica ML namreč pomeni meta-language oziroma metajezik, torej jezik za opis jezikov.

Implementacija abstraktne sintakse#

Sintakso, ki je sestavljena iz treh vrst izrazov, bomo predstavili s tremi induktivnimi tipi. Pomnilniške lokacije bomo predstavili kar z nizi, vendar jih bomo zaradi lažjega razločevanja ovili s konstruktorjem.

type location = Location of string

type exp =
  | Lookup of location
  | Int of int
  | Plus of exp * exp
  | Minus of exp * exp
  | Times of exp * exp

type bexp =
  | Bool of bool
  | Equal of exp * exp
  | Less of exp * exp
  | Greater of exp * exp

type cmd =
  | IfThenElse of bexp * cmd * cmd
  | WhileDo of bexp * cmd
  | Seq of cmd * cmd
  | Assign of location * exp
  | Skip

Na primer, aritmetična izraza $e_1 = (\intsym{6} * \intsym{7})$ in $e_2 = (\mathsf{m} - \intsym{1})$ bi predstavili z

let exp1 = Times (Int 6, Int 7)
let exp2 = Minus (Lookup (Location "m"), Int 1)

val exp1 : exp = Times (Int 6, Int 7)

val exp2 : exp = Minus (Lookup (Location "m"), Int 1)

logični izraz $b = (\mathsf{m} > \intsym{0})$ z

let bexp = Greater (Lookup (Location "m"), Int 0)

val bexp : bexp = Greater (Lookup (Location "m"), Int 0)

ukaza $c_1 = (\mathsf{m} := e_2)$ in $c_2 = (\whiledo{b}{c_1})$ pa z

let cmd1 = Assign (Location "m", exp2)
let cmd2 = WhileDo (bexp, cmd1)

val cmd1 : cmd = Assign (Location "m", Minus (Lookup (Location "m"), Int 1))

val cmd2 : cmd =
  WhileDo (Greater (Lookup (Location "m"), Int 0),
   Assign (Location "m", Minus (Lookup (Location "m"), Int 1)))

Implementacija izvajanja#

Pomen bomo najprej določili aritmetičnim izrazom, ki naj bi predstavljali cela števila. Ker izrazi lahko vsebujejo pomnilniške lokacije, mora funkcija za evalvacijo poleg izraza sprejeti tudi trenutno stanje pomnilnika, ki ga bomo predstavili kar s seznamom parov, ki danim lokacijam pripiše cela števila, na primer

let st1 = [(Location "m", 10); (Location "n", 0)]
let st2 = [(Location "m", 5)]

val st1 : (location * int) list = [(Location "m", 10); (Location "n", 0)]

val st2 : (location * int) list = [(Location "m", 5)]

let rec eval_exp st = function
  | Lookup l -> List.assoc l st
  | Int n -> n
  | Plus (e1, e2) -> eval_exp st e1 + eval_exp st e2
  | Minus (e1, e2) -> eval_exp st e1 - eval_exp st e2
  | Times (e1, e2) -> eval_exp st e1 * eval_exp st e2

val eval_exp : (location * int) list -> exp -> int = <fun>

Tako na primer velja

eval_exp [] exp1

- : int = 42

eval_exp st1 exp2

- : int = 9

eval_exp st2 exp2

- : int = 4

Podobno lahko definiramo funkcijo za evalvacijo logičnih izrazov, ki sprejme stanje in logični izraz ter vrne logično vrednost:

let eval_bexp st = function
  | Bool b -> b
  | Equal (e1, e2) -> eval_exp st e1 = eval_exp st e2
  | Less (e1, e2) -> eval_exp st e1 < eval_exp st e2
  | Greater (e1, e2) -> eval_exp st e1 > eval_exp st e2

val eval_bexp : (location * int) list -> bexp -> bool = <fun>

eval_bexp st1 bexp

- : bool = true

eval_bexp st2 bexp

- : bool = true

Nazadnje definirajmo še funkcijo za evalvacijo ukazov. Funkcija sprejme stanje in ukaz, vrne pa končno vrednost stanja po izvršenem ukazu.

let rec eval_cmd st = function
  | IfThenElse (b, c1, c2) ->
      if eval_bexp st b then eval_cmd st c1 else eval_cmd st c2
  | WhileDo (b, c) ->
      (* eval_cmd st (IfThenElse (b, Seq (c, WhileDo (b, c)), Skip)) *)
      if eval_bexp st b then
        let st' = eval_cmd st c in
        eval_cmd st' (WhileDo (b, c))
      else st
  | Seq (c1, c2) ->
      let st' = eval_cmd st c1 in
      eval_cmd st' c2
  | Assign (l, e) -> (l, eval_exp st e) :: List.remove_assoc l st
  | Skip -> st

val eval_cmd : (location * int) list -> cmd -> (location * int) list = <fun>

eval_cmd st1 cmd1

- : (location * int) list = [(Location "m", 9); (Location "n", 0)]

eval_cmd st2 cmd1

- : (location * int) list = [(Location "m", 4)]

eval_cmd st1 cmd2

- : (location * int) list = [(Location "m", 0); (Location "n", 0)]

eval_cmd st2 cmd2

- : (location * int) list = [(Location "m", 0)]

Implementacija razčlenjevalnika#

Razčlenjevalnikov običajno ne pišemo direktno, temveč se poslužimo posebnih orodij, ki sprejmejo definicijo jezika v zapisu podobnem BNF, ter iz nje samodejno ustvarijo program. V primeru OCamla sta taka programa ocamlyacc in njegova naprednejša različica Menhir. Prav tako je sestavni del razčlenjevalnika lekser, ki zaporedje znakov najprej pretvori v zaporedje leksemov, kjer so zaporedne števke že združene v števila, ključne besede nadomeščene s posebnimi simboli, presledki in komentarji pa odstranjeni.

Mi pa bomo zato, da bomo ostali znotraj enega orodja in zraven ponovili še malo funkcijskega programiranja, ubrali bolj neposredno pot in uporabili kombinatorje razčlenjevalnikov. Vsak razčlenjevalnik bo sestavljen iz manjših razčlenjevalnikov, od katerih bo vsak predelal del besedila. Poglejmo najprej, kakšne oblike bodo.

Tip razčlenjevalnikov `'a parser`#

Recimo, da želimo razčlenjevalnik za cela števila. Začnimo z željo po funkciji string -> int, ki vzame vhodni niz ter vrne prebrano število, na primer iz niza "42" dobimo število 42.

Ker vsak niz ne bo predstavljal števila, moramo najprej popraviti ti rezultata, da dobimo string -> int option. Tako bomo iz niza "42" dobili Some 42, iz niza "abc" pa None.

Razčlenjevalnike bomo združevali in vsak ne bo prebral celotnega niza, temveč samo njegov začetek, preostanek pa bo predal nadaljnjim razčlenjevalnikom. Zato ne vrnemo samo rezultata, temveč tudi preostali niz, zato je še boljši tip string -> (int * string) option. Tako bi razčlenjevalnik pri vhodu "42abc" vrnil Some (42, "abc"), pri vhodu "42" rezultat Some (42, ""), pri vhodu "abc42" pa None, saj začetek ne predstavlja števila.

Niz je veliko enostavneje brati postopoma, če ga poprej pretvorimo v zaporedje znakov. Za pretvorbo uporabljamo funkciji:

let explode str = List.init (String.length str) (String.get str)
let implode chrs = String.init (List.length chrs) (List.nth chrs)

val explode : string -> char list = <fun>

val implode : char list -> string = <fun>

explode "abc"

- : char list = ['a'; 'b'; 'c']

implode ['T'; 'P'; 'J']

- : string = "TPJ"

Tudi tip razčlenjevalnikov spremenimo v char list -> (int * char list) option. Ker seveda ne bomo brali samo celih števil, celoten tip razčlenjevalnikov parametriziramo glede na tip prebranih vrednosti:

type 'a parser = char list -> ('a * char list) option

type 'a parser = char list -> ('a * char list) option

Zgoraj opisani razčlenjevalnik bi tako lahko definirali kot:

let parse_int : int parser =
  fun chrs ->
  let rec take_initial_digits =
    function
    | chr :: chrs when String.contains "0123456789" chr ->
        let digits, rest = take_initial_digits chrs in
        (chr :: digits, rest)
    | chrs -> ([], chrs)
  in
  match take_initial_digits chrs with
  | ([], chrs) -> None
  | (digits, chrs) ->
      Some (int_of_string (implode digits), chrs)

val parse_int : int parser = <fun>

parse_int (explode "42abc")

- : (int * char list) option = Some (42, ['a'; 'b'; 'c'])

parse_int (explode "42")

- : (int * char list) option = Some (42, [])

parse_int (explode "abc42")

- : (int * char list) option = None

Pri definiciji smo ročno dopisali tip int parser, saj bi nam OCaml sicer prikazoval ekvivalenten, vendar manj pregleden tip char list -> (int * char list) option. Za preglednejše testiranje si napišimo pomožno funkcijo ($$$) : 'a parser -> string -> ('a * string) option, ki samodejno poskrbi za pretvorbo med nizi in zaporedji znakov.

let ( $$$ ) (parser : 'a parser) str =
  match parser (explode str) with
  | None -> None
  | Some (x, rest) -> Some (x, implode rest)

val ( $$$ ) : 'a parser -> string -> ('a * string) option = <fun>

Funkciji damo simbolno ime ( $$$ ), da jo lahko kličemo infiksno kot parser $$$ niz.

parse_int $$$ "42abc"

- : (int * string) option = Some (42, "abc")

Osnovni razčlenjevalniki#

Vse razčlenjevalnike pisati na tak način bi bilo precej nerodno. Raje si bomo definirali nekaj osnovnih, ki jih bomo združevali v večje. Prvi je razčlenjevalnik fail, ki vedno zavrne vhod:

let fail : 'a parser = fun _chrs -> None

val fail : 'a parser = <fun>

fail $$$ "42abc"

- : ('a * string) option = None

Nato imamo funkcijo return, ki sprejme vrednost v in vrne razčlenjevalnik, ki ne glede na vhod vrne uspešno prebrano vrednost v, celoten vhod pa posreduje naprej.

let return v : 'a parser = fun chrs -> Some (v, chrs)

val return : 'a -> 'a parser = <fun>

return 10 $$$ "42abc"

- : (int * string) option = Some (10, "42abc")

Prvi razčlenjevalnik, ki bo dejansko upošteval vhod, je character, ki prebere prvi znak, kadar obstaja, ostale pa pošlje naprej:

let character : char parser = function
  | [] -> None
  | chr :: chrs -> Some (chr, chrs)

val character : char parser = <fun>

character $$$ "42abc"

- : (char * string) option = Some ('4', "2abc")

character $$$ ""

- : (char * string) option = None

Nato imamo izbiro, ki najprej poskusi en razčlenjevalnik, če pa temu ne uspe, pa še drugega. Oba razčlenjevalnika morata seveda vračati vrednost enakega tipa.

let ( || ) (parser1 : 'a parser) (parser2 : 'a parser) : 'a parser =
 fun chrs ->
  match parser1 chrs with
  | None -> parser2 chrs
  | Some (v, chrs') -> Some (v, chrs')

val ( || ) : 'a parser -> 'a parser -> 'a parser = <fun>

(fail || character) $$$ "42abc"

- : (char * string) option = Some ('4', "2abc")

(return 'X' || character) $$$ "42abc"

- : (char * string) option = Some ('X', "42abc")

Nazadnje moramo znati razčlenjevalnike še združevati, kar storimo s funkcijo >>=, ki dva razčlenjevalnika veriži enega za drugim. V večini primerov bo drugi razčlenjevalnik odvisen od vrednosti, ki jo je prebral prvi. Na primer, če bomo najprej prebrali znak za začetek komentarja, bomo preskočili vse do konca vrstice, če pa bomo našli kaj drugega, pa bomo pričakovali veljaven ukaz. Tako je parser1 razčlenjevalnik, ki vrne vrednost tipa 'a, med tem ko parser2 ni razčlenjevalnik, temveč funkcija 'a -> 'b parser, ki vrne razčlenjevalnik odvisen od prebranega rezultata.

let ( >>= ) (parser1 : 'a parser) (parser2 : 'a -> 'b parser) : 'b parser =
 fun chrs ->
  match parser1 chrs with
  | None -> None
  | Some (v, chrs') -> parser2 v chrs'

val ( >>= ) : 'a parser -> ('a -> 'b parser) -> 'b parser = <fun>

Veriženje deluje tako, da najprej uporabimo parser1. Če že ta zavrne vhod, takoj končamo in vrnemo None. V primeru, pa da dobimo neko vrednost v, jo skupaj s preostankom znakov podamo funkciji parser2, ki potem uspešno ali neuspešno vrne končni rezultat.

Na primer, spodnja kombinacija najprej prebere katerikoli znak, nato pa ta znak poda funkciji, ki ne glede na preostanek, ki sledi, vedno vrne niz, sestavljen iz 10 kopij tega znaka.

let vedno_preberi_10_kopij_znaka c = return (String.make 10 c)

val vedno_preberi_10_kopij_znaka : char -> string parser = <fun>

character >>= vedno_preberi_10_kopij_znaka $$$ "42abc"

- : (string * string) option = Some ("4444444444", "2abc")

Isto seveda lahko dosežemo tudi z anonimno funkcijo:

(character >>= fun c -> return (String.make 10 c)) $$$ "42abc"

- : (string * string) option = Some ("4444444444", "2abc")

Osnovni kombinatorji#

Izkaže se, da je zgoraj naštetih pet razčlenjevalnikov, torej fail, return, character, || in >>= dovolj, da izrazimo vse razčlenjevalnike, ki jih potrebujemo. Na primer, če želimo vrniti par zaporedoma prebranih vrednosti, lahko to zapišemo kot:

let pair parser1 parser2 = parser1 >>= fun v1 -> parser2 >>= fun v2 -> return (v1, v2)

val pair : 'a parser -> 'b parser -> ('a * 'b) parser = <fun>

pair character character $$$ "42abc"

- : ((char * char) * string) option = Some (('4', '2'), "abc")

Če želimo, da uspešno prebrana vrednost zadošča še kakšnemu predikatu, uporabimo funkcijo satisfy, kjer v drugem delu odvisno od pogoja vrednost vrnemo ali zavrnemo:

let satisfy cond parser =
  parser >>= fun v -> if cond v then return v else fail

val satisfy : ('a -> bool) -> 'a parser -> 'a parser = <fun>

Na primer, spodnji razčlenjevalnik sprejema samo znake 'a', 'b' in 'c'.

satisfy (String.contains "abc") character $$$ "123"

- : (char * string) option = None

satisfy (String.contains "abc") character $$$ "a23"

- : (char * string) option = Some ('a', "23")

Pri zapisu pogojnih razčlenjevalnikov uporabljamo operacijo x |> f, ki funkcijo f uporabi na vrednosti x. Isti primer kot zgoraj bi napisali na sledeč način, kjer je bolj jasno, da najprej preberemo znak, nato pa preverimo, da je eden od znakov niza "abc".

character |> satisfy (String.contains "abc") $$$ "a23"

- : (char * string) option = Some ('a', "23")

Konkretna uporaba kombinatorja satisfy je razčlenjevalnik exactly, ki sprejme natanko znak chr:

let exactly chr = character |> satisfy (( = ) chr)

val exactly : char -> char parser = <fun>

(exactly 'a' || exactly 'b') $$$ "abc"

- : (char * string) option = Some ('a', "bc")

Enako si lahko definiramo razčlenjevalnike, ki sprejemajo samo števke, črke ali presledke:

let digit =
  let is_digit = String.contains "0123456789" in
  character |> satisfy is_digit

let alpha =
  let is_alpha = String.contains "abcdefghijklmnopqrstvwuxyz" in
  character |> satisfy is_alpha

let space =
  let is_space = String.contains " \n\t\r" in
  character |> satisfy is_space

val digit : char parser = <fun>

val alpha : char parser = <fun>

val space : char parser = <fun>

Podoben kombinator je map, ki prebere rezultat v in ga pretvori s pomočjo funkcije f.

let map f parser = parser >>= fun v -> return (f v)

val map : ('a -> 'b) -> 'a parser -> 'b parser = <fun>

(character |> map Char.uppercase_ascii) $$$ "abc"

- : (char * string) option = Some ('A', "bc")

Poseben primer operacije >>= je >>, kjer ne upoštevamo vrednosti, ki jo je prebral prvi razčlenjevalnik. Na primer, vemo, da se zanka vedno začne s ključno besedo while, ampak sama vrednost "while" za pomen programa ni pomembna.

let ( >> ) parser1 parser2 = parser1 >>= fun _ -> parser2

val ( >> ) : 'a parser -> 'b parser -> 'b parser = <fun>

(exactly 'a' >> exactly 'b' >> character) $$$ "abcde"

- : (char * string) option = Some ('c', "de")

(exactly 'a' >> exactly 'b' >> character) $$$ "bacde"

- : (char * string) option = None

Postopek lahko posplošimo na poljuben niz znakov. Razčlenjevalnik napišemo tako, da besedo str razbijemo na seznam znakov chrs, nato iz tega naredimo seznam razčlenjevalnikov, ki zaporedoma sprejemajo natanko te znake, nato pa jih vse skupaj verižimo s pomočjo >>. Ta razčlenjevalnik bomo uporabljali za prebiranje ključnih besed kot so while, if in podobno, zato na koncu vrnemo vrednost ().

let word str =
  let chrs = explode str in
  let chr_parsers = List.map exactly chrs in
  List.fold_right ( >> ) chr_parsers (return ())

val word : string -> unit parser = <fun>

word "WHILE" $$$ "WHILE TRUE DO SKIP"

- : (unit * string) option = Some ((), " TRUE DO SKIP")

word "WHILE" $$$ "IF TRUE THEN SKIP ELSE SKIP"

- : (unit * string) option = None

Podobno lahko s pomočjo fold_right zaporedoma z || poskusimo vse razčlenjevalnike iz danega seznama:

let one_of parsers = List.fold_right ( || ) parsers fail

val one_of : 'a parser list -> 'a parser = <fun>

one_of [word "WHILE"; word "IF"] $$$ "WHILE TRUE DO SKIP"

- : (unit * string) option = Some ((), " TRUE DO SKIP")

one_of [word "WHILE"; word "IF"] $$$ "IF TRUE THEN SKIP ELSE SKIP"

- : (unit * string) option = Some ((), " TRUE THEN SKIP ELSE SKIP")

one_of [word "WHILE"; word "IF"] $$$ "SKIP"

- : (unit * string) option = None

Rekurzivno si lahko definiramo tudi razčlenjevalnika many in many1, ki dani razčlenjevalnik uporabita poljubno mnogokrat oziroma vsaj enkrat, vrneta pa seznam uspešno prebranih vrednosti:

let rec many parser = many1 parser || return []

and many1 parser =
  parser >>= fun v ->
  many parser >>= fun vs -> return (v :: vs)

val many : 'a parser -> 'a list parser = <fun>
val many1 : 'a parser -> 'a list parser = <fun>

many digit $$$ "1234abc567"

- : (char list * string) option = Some (['1'; '2'; '3'; '4'], "abc567")

S pomočjo vseh zgoraj naštetih kombinatorjev zdaj veliko lepše napišemo razčlenjevalnik za branje celih števil. Najprej moramo prebrati vsaj eno števko, nato seznam števk združimo v en sam niz, na koncu pa pogoljufamo in s pomočjo vgrajene funkcije to pretvorimo v število.

let integer = many1 digit |> map implode |> map int_of_string

val integer : int parser = <fun>

integer $$$ "123abc"

- : (int * string) option = Some (123, "abc")

Razčlenjevalniki za IMP#

Razvili smo vsa orodja, ki jih potrebujemo, da preberemo celotno sintakso jezika IMP. Za ločevanje med posameznimi deli bomo uporabili presledke. Pri ključnih besedah bomo zahtevali vsaj enega, okoli operatorjev pa ne nujno:

let spaces = many space >> return ()
let spaces1 = many1 space >> return ()

val spaces : unit parser = <fun>

val spaces1 : unit parser = <fun>

Zaradi enostavnosti bomo za večje podizraze zahtevali, da se pojavijo v oklepajih:

let parens parser =
  exactly '(' >> spaces >> parser >>= fun v -> spaces >> exactly ')' >> return v

val parens : 'a parser -> 'a parser = <fun>

parens integer $$$ "(1234)"

- : (int * string) option = Some (1234, "")

Lokacije se bodo začele z znakom #, ki jim bo sledilo ime. To bo sestavljeno iz alfanumeričnih znakov, od katerih mora biti prvi črka.

let ident =
  alpha >>= fun chr ->
  many (alpha || digit) >>= fun chrs -> return (implode (chr :: chrs))

let location = word "#" >> ident >>= fun ident -> return (Location ident)

val ident : string parser = <fun>

val location : location parser = <fun>

location $$$ "#fact"

- : (location * string) option = Some (Location "fact", "")

Dvojiška operacija je podana s simbolom op, njegovim pomenom f ter z razčlenjevalnikom argumentov parser. Med operacijo in argumentoma so morebitni presledki

let binop parser op f =
  parser >>= fun v1 ->
  spaces >> word op >> spaces >>
  parser >>= fun v2 ->
  return (f v1 v2)

val binop : 'a parser -> string -> ('a -> 'a -> 'b) -> 'b parser = <fun>

Pri razčlenjevalniku za aritmetične izraze sledimo sintaksi. Izrazi so lahko sestavljeni iz aritmetičnih operacij ali atomarni, pri čemer so atomarni izrazi lokacije, konstante ali običajni izrazi v oklepajih.

let rec exp chrs =
  one_of
    [
      binop atomic_exp "+" (fun e1 e2 -> Plus (e1, e2));
      binop atomic_exp "-" (fun e1 e2 -> Minus (e1, e2));
      binop atomic_exp "*" (fun e1 e2 -> Times (e1, e2));
      atomic_exp;
    ]
    chrs

and atomic_exp chrs =
  one_of
    [
      (location >>= fun l -> return (Lookup l));
      (integer >>= fun n -> return (Int n));
      parens exp;
    ]
    chrs

val exp : exp parser = <fun>
val atomic_exp : exp parser = <fun>

exp $$$ "1 + 3"

- : (exp * string) option = Some (Plus (Int 1, Int 3), "")

Podobno definiramo razčlenjevalnik za Booleove izraze:

let bexp =
  one_of
    [
      word "TRUE" >> return (Bool true);
      word "FALSE" >> return (Bool false);
      binop exp "=" (fun e1 e2 -> Equal (e1, e2));
      binop exp "<" (fun e1 e2 -> Less (e1, e2));
      binop exp ">" (fun e1 e2 -> Greater (e1, e2));
    ]

val bexp : bexp parser = <fun>

bexp $$$ "1 + 3 < 2 * 4"

- : (bexp * string) option =
Some (Less (Plus (Int 1, Int 3), Times (Int 2, Int 4)), "")

Podobno definiramo tudi razčlenjevalnik za ukaze:

let rec cmd chrs =
  let if_then_else =
    word "IF" >> spaces1 >> bexp >>= fun b ->
    spaces1 >> word "THEN" >> spaces1 >> cmd >>= fun c1 ->
    spaces1 >> word "ELSE" >> spaces1 >> atomic_cmd >>= fun c2 ->
    return (IfThenElse (b, c1, c2))
  and while_do =
    word "WHILE" >> spaces1 >> bexp >>= fun b ->
    spaces1 >> word "DO" >> spaces1 >> atomic_cmd >>= fun c ->
    return (WhileDo (b, c))
  and seq =
    atomic_cmd >>= fun c1 ->
    spaces >> word ";" >> spaces >> cmd >>= fun c2 ->
    return (Seq (c1, c2))
  in
  one_of [ if_then_else; while_do; seq; atomic_cmd ] chrs

and atomic_cmd chrs =
  let assign =
    location >>= fun l ->
    spaces >> word ":=" >> spaces >> exp >>= fun e ->
    return (Assign (l, e))
  and skip = word "SKIP" >> return Skip
  in
  one_of [ assign; skip; parens cmd ] chrs

val cmd : cmd parser = <fun>
val atomic_cmd : cmd parser = <fun>

cmd $$$ "IF 3 < 4 THEN SKIP ELSE SKIP"

- : (cmd * string) option =
Some (IfThenElse (Less (Int 3, Int 4), Skip, Skip), "")

Vsaka IMP datoteka je sestavljena iz enega samega ukaza (ki je seveda lahko sestavljen iz več ukazov, ločenih s podpičjem). Da preberemo celotno datoteko, torej le pokličemo razčlenjevalnik cmd. Če nam ni ostalo nič neprebranih znakov, poženemo eval_cmd na praznem seznamu, sicer pa program zavrnemo:

let run str =
  match str |> String.trim |> explode |> cmd with
  | Some (c, []) -> eval_cmd [] c
  | Some (_, _ :: _) | None -> failwith "Parsing error"

val run : string -> (location * int) list = <fun>

run "#n := 10; #fact := 1; WHILE #n > 0 DO ( #fact := #fact * #n; #n := #n - 1 )"

- : (location * int) list = [(Location "n", 0); (Location "fact", 3628800)]