O programskih jezikih na splošno

Osnovno načelo dobrega načrtovanja programskega jezika: programski jezik je orodje, ki programerju omogoča, da na čim bolj neposreden način poda natančna navodila, kako naj računalik opravi neko nalogo.

Zakaj imamo toliko programskih jezkov?

  1. Ker se programski jeziki sproti prilagajajo razvoju računalniške tehnologije in potrebam programerjev.

  2. Ker se razvijajo novi programerski koncepti in tehnike.

  3. Ker niso vsi stili programiranja enako primerni za reševanje vseh nalog.

Anatomija programskega jezika

Programski jezik je zasnovan kot sistem, ki ima naslednje komponente:

Programski jezik nima nujno vseh teh komponent, čeprav vsaj sintakso in dinamično semantiko vedno imamo. Opis jezika je lahko

Pogosto je definicija jezika kombinacija obeh pristopov. Implementacija jezika je program, ki preverja sintakso in statično semantiko jezika ter omogoča izvajanje programov. To je lahko tolmač (angl. interpreter), prevajalnik (angl. compiler), oboje, ali pa kombinacija (glej just-in-time compilation.

Pomemben del programskega jezika so tudi metode za analizo programov (s katerimi ugotavljamo, kakšne lastnosti ima program) in dokazovanje pravilnosti (s katerimi dokazujemo, da ima program želene lastnosti).

Aritmetični izrazi

Začnimo z zelo preprostim programskim jezikom, ki je tako preprost, da ga v praksi sploh ne obravnavamo kot samostojen programski jezik.

Obravnavajmo celoštevilske aritmetične izraze: cela števila, operaciji * in + tera spremenljivkami. To bi lahko bil majhen košček resnega programskega jezika.

Sintaksa

Sintaksa pove, kakšne izraze in programe lahko pišemo v programskem jeziku.

Konkretna sintaksa aritmetičnih izrazov

Programer zapiše program kot niz znakov, na primer:

"y + (5 + 7 * x) * 8"

Ta oblika je primerna za človeka, a ni primerna za obdelavo z računalnikom, saj ne odraža strukture izraza. Zgornji izraz predstavimo z drevesom takole:

      +
     / \
    y   *
       / \
      +   8
     / \
    5   *
       / \
      7   x

Na ta način se znebimo presledkov in oklepajev in jasno ponazorimo strukturo izraza. Tudi programsko kodo lahko predstavimo z drevesi. Ali znate razbrati program, ki ga predstavlja naslednje drevo?

     ;
    / \
  :=   \
 /  \   \
i    0   \
        while
       /     \
      <       \
     / \       \
    i  10       ;
               / \
              /   \
             /     \
           :=       \
          /  \     print
         i    +      |
             / \     i
            i   1

Abstraktna sintaksa aritmetičnih izrazov

Izraze lahko opišemo s podatkovno strukturo drevo. To je oblika, primerna za obdelavo, ni pa primerna za človeka.

Prednosti:

  1. Iz drevesa je takoj razvidna struktura programa ali izraza.

  2. Drevo ne vsebuje nepomembnih komponent (na primer presledkov in oklepajev).

Kako implementiramo drevesa, je odvisno od programskega jezika, ki ga uporabimo. V Javi se to seveda naredi z razredi. Kasneje bomo spoznali še druge načine.

Slovnica in slovnična pravila

Pravila, ki opisujejo, kako tvorimo izraze ali drevesa, se imenujejo slovnična pravila ali gramatika. Poznamo več načinov, kako podamo pravila, mi si bomo ogledali poenostavljeno verzijo t.i. oblike BNF, ki delno določa konkretno sintakso:

⟨izraz⟩ ::= ⟨aditivni-izraz⟩ EOF

⟨aditivni-izraz⟩ ::= ⟨multiplikativni-izraz⟩ | ⟨aditivni-izraz⟩ + ⟨multiplikativni-izraz⟩

⟨multiplikativni-izraz⟩ ::= ⟨osnovni-izraz⟩ | ⟨multiplikativni-izraz⟩ * ⟨osnovni-izraz⟩

⟨osnovni-izraz⟩ ::= ⟨spremenljivka⟩ | ⟨številka⟩ | ( ⟨aditivni-izraz⟩ )

⟨spremenljivka⟩ ::= [a-zA-Z]+

⟨številka⟩ ::= -? [0-9]+

Pri opisu spremenljivk in številke smo uporabili regularne izraze: v oglatih oklepajih navedemo, kateri znaki so dovoljeni, znak + pa pomeni “ena ali več ponovitev”.

Glede na pravila, je dani izraz veljaven ali ne. Primeri:

Ali bi lahko 1 * 2 + x razčlenili kot 1 * (2 + x) glede na zgornja pravila?

Iz konkretne v abstraktno sintakso

Konkretno sintakso predelamo v abstraktno sintakso s postopkom razčlenjevana (angl. parsing), ki ima dve fazi:

Leksična analiza odstrani nebistvene znake, kot so presledki in prehodi v novo vrsto, pogosto tudi komentarje.

Za aritmetične izraze so osnovni gradniki:

Primer: x * (5 + 8) nam da niz gradnikov

SPREMENLJIVKA(x) KRAT OKLEPAJ ŠTEVILKA(5) PLUS ŠTEVILKA(8) ZAKLEPAJ

Ta niz nam da ustrezno drevo.

Primer: x * ((5 + 8 nam da niz gradnikov

SPREMENLJIVKA(x) KRAT OKLEPAJ OKLEPAJ ŠTEVILKA(5) PLUS ŠTEVILKA(8)

Ta niz ni veljaven in ne določa drevesa. Javimo sintaktično napako.

Na vajah boste spoznali razčlenjevalnik za aritmetične izraze, implementiran v Javi. Običajno pa razčlenjevalnika ne implementiramo z golimi rokami, ker je to precej zamudno, ampak uporabimo parser generator - program, ki sprejme slovnična pravila in iz njih generira razčlenjevalnik (primer takega opisa za aritmetične izraze v OCamlu).

Iz abstraktne v konkretno sintakso

Pretvorba abstraktne sintakse v konkretno je preprosta, saj le obidemo sintaktično drevo in zgradimo ustrezni niz. Pojavi se vprašanje, kako vstaviti oklepaje, na katerega boste odgovorili na vajah.

Operacijska semantika

Kakšen je postopek, s katerim izračunamo vrednost izraza? Podali bomo dva osnovna načina.

Ko računamo vrednost izraza, moramo poznati vrednosti spremenljivk. Preslikavi, ki spremenljivke slika v njihove vrednosti, pravimo okolje (angl. environment). Na primer, če ima x vrednost 3, y vrednost 7 in z vrednost 10, to predstavimo z okoljem [x ↦ 3, y ↦ 7, z ↦ 10].

Semantika velikih korakov

Semantika velikih korakov se imenuje tako, ker iz izraza (abstraktnega drevesa) dobimo njegovo vrednost (število) v enem “velikem” koraku. Predstavimo jo z relacijo

η | e ↪ n

kjer je η okolje, e je izraz in n celo število. Zgornji izraz preberemo takole: “V okolju η se izraz e evalvira v število n.”

Na primer, pričakujemo, da velja

[x ↦ 3, y ↦ 2, z ↦ 5] | x + 2 * y ↪ 7

Pravila za računanje izrazov podamo kot pravila sklepanja. Pravilo sklepanja zapišemo takole:

P₁ P₂ ⋯ Pᵢ
----------
    S

To preberemo: Če smo že dokazali predpostavke P₁, P₂, ⋯, Pᵢ , potem sledi tudi sklep S.

Na primer:

x > 0      y < 0
----------------
    x · y < 0

Preberemo: “če je x pozitiven in y negativen, potem je x · y negativen.”

Lahko se zgodi, da pravilo nima predpostavk:

--------
   S

Takemu pravilu pravimo tudi aksiom, saj pove da S velja. Primer aksioma je zakon refleksivnosti za enakost:

-----
x = x

Pravila za semantiko velikih korakov se glasijo:

Dogovori:

Pravila:

 η(x) = n
----------
η | x ↪ n


----------
η | n ↪ n


η | e₁ ↪ n₁     η | e₂ ↪ n₂    n₁ · n₂ = n
------------------------------------------
            η | e₁ * e₂ ↪ n


η | e₁ ↪ n₁     η | e₂ ↪ n₂    n₁ + n₂ = n
------------------------------------------
            η | e₁ + e₂ ↪ n

Pozor, v pravilu za seštevanje znak + nad črto pomeni matematično operacijo seštevanje, pod črto pa je to del sintakse aritmetičnih izrazov, se pravi + je samo simbol v izrazu. Pri pravilu za množenje te težave nismo imeli, ker smo matematično množenje označili z ·, množenje kot simbol pa z *.

Semantika malih korakov

Semantika velikih korako deluje hierarhično: najprej izračunamo vrednosti podizrazov in nato vrednost celotnega izraza. V šoli pa otroke učimo, da se računa “po korakih”, se pravi, da opravimo eno operacijo naenkrat. Tak postopek se imenuje semantika malih korakov. Podamo jo z relacijo (pozor, puščico ↪ smo spremenili v puščico ↦)

η | e ↦ e'

ki pove, kako naredimo en osnovni korak v računanju.

Pravila se glasijo:

 η(x) = n
----------
η | x ↦ n


      η | e₁ ↦ e₁'
----------------------
η | e₁ + e₂ ↦ e₁' + e₂


      η | e₂ ↦ e₂'
----------------------
η | n₁ + e₂ ↦ n₁ + e₂'


  n₁ + n₂ = n
---------------
 η | n₁ + n₂ ↦ n


      η | e₁ ↦ e₁'
----------------------
η | e₁ * e₂ ↦ e₁' * e₂


      η | e₂ ↦ e₂'
----------------------
η | n₁ * e₂ ↦ n₁ * e₂'


  n₁ · n₂ = n
-----------------
 η | n₁ * n₂ ↦ n
Primer
[x ↦ 3, y ↦ 2, z ↦ 5]  |  x + 2 * y  ↦  3 + 2 * y

Korake lahko nadaljujemo, dokler gre:

  1. [x ↦ 3, y ↦ 2, z ↦ 5] | x + 2 * y ↦ 3 + 2 * y
  2. [x ↦ 3, y ↦ 2, z ↦ 5] | 3 + 2 * y ↦ 3 + 2 · 2
  3. [x ↦ 3, y ↦ 2, z ↦ 5] | 3 + 2 · 2 ↦ 3 + 4
  4. [x ↦ 3, y ↦ 2, z ↦ 5] | 3 + 4 ↦ 7

Pozor, zgornja pravila ne dopuščajo nobene svobode pri računanju. Na primer, če želimo izračunati

[] | 2 * 3 + 5 * 6

potem moramo naprej izračunati 2 * 3, da dobimo 6 + 5 * 6 in šele nato 5 * 6, da dobimo 6 + 30. Ugotovite, zakaj je tako.

Primer

Izvajanje se lahko tudi zatakne, na primer, če spremenljivka nima vrednosti:

[x ↦ 3]  |  x + 2 * y  ↦  3 + 2 * y

Naslednjega koraka ni, ker ne moremo uporabiti nobenega od pravil, ki so na voljo.