Logică și structuri discrete - Gramatici

Gramatici și compilatoare
Când o gramatică definește un limbaj de programare, ea e și punctul de plecare pentru compilator, care traduce cod sursă în cod executabil care poate fi rulat de procesor.
Vom modela întâi un procesor simplu, și apoi vom traduce fragmente simple de program (doar cu atribuire, if și while) pentru a fi rulate pe acest procesor.
Gramatica noastră are structura:
  instr ::= var op_atr valoare | if boolexp lista_instr else lista_instr | while boolexp lista_instr
  boolexp ::= var op_cmp valoare
  lista_instr ::= instr*
  var ::= caracter
  valoare ::= var | întreg
  op_atr ::= = | += | -= | *= | /= | %=
  op_cmp ::= == | != | < | <= | > | >=
Avem deci un fragment de C puternic simplificat:
-- am omis detalii de sintaxă concretă (paranteze la expresii boolene, punct-virgulă și acolade la instrucțiuni), exprimând doar sintaxa abstractă (structura). Nu vom porni de la textul programului, ci direct de la reprezentarea lui în ML
-- singurele operații sunt de atribuire (eventual compusă cu operatori aritmetici), având în partea dreaptă o constantă sau o variabilă: x = 5, a -= b (a = a - b), i += 1 (i = i + 1), etc. Aceste operații simple seamănă cu instrucțiunile procesoarelor uzuale. Am limitat numărul variabilelor pentru că și procesorul are un număr limitat de regiștri (locații interne de memorie cu care poate opera direct), adesea denumite cu litere (deși nu neapărat așa de multe).
Avem deci o corespondență 1:1 între atribuiri și instrucțiunile procesorului și va trebui să tratăm doar secvențierea instrucțiunilor compuse if și while.
Reprezentarea programului sursă:

type register = char                             (* processor registers = variables *)
type rightpart = R of register | I of int        (* second arg of binary op *)
type binop = LD | ADD | SUB | MUL | DIV | MOD    (* =, +=, -=, *=, /=, %= *)
type cmpop = Eq | Ne | Lt | Le | Gt | Ge         (* ==, !=, <, <=, >, >= *)
type boolexp = register * cmpop * rightpart
type statement = Asgn of binop * register * rightpart
                 | If of boolexp * statement list * statement list
                 | While of boolexp * statement list

let factprog =
  [ Asgn (LD, 'n', I 5) ; Asgn (LD, 'r', I 1) ;        (* n = 5; r = 1; *)
    While (('n', Gt, I 0), [Asgn (MUL, 'r', R 'n'); Asgn (SUB, 'n', I 1)]) ]        (* while (n > 0) { r *= n; n -= 1; } *)

let collprog =
  [ Asgn (LD, 'n', I 10); Asgn (LD, 's', I 0);        (* n = 10; s = 0; *)
    While (('n', Gt, I 1),                            (* while (n > 1) { *)
           [ Asgn (ADD, 's', I 1); Asgn (LD, 'p', R 'n'); Asgn (MOD, 'p', I 2);        (* s += 1; p = n; p %= 2; *)
             If (('p', Eq, I 0), [ Asgn (DIV, 'n', I 2) ],                    (* if (p == 0) n /= 2; *)
             [ Asgn (MUL, 'n', I 3); Asgn (ADD, 'n', I 1) ]) ]) ]             (* else { n *= 3; n += 1; } } *)

type flag_t = Neg | Z | Pos        (* processor flags after CMP instruction *)
type jmpcond = T | E | NE | L | LE | G | GE
type instruction = HLT | BOP of binop * register * rightpart
                   | CMP of register * rightpart | JMP of jmpcond * int

let factbin =
  [|BOP (LD, 'n', I 5); BOP (LD, 'r', I 1); CMP ('n', I 0); JMP (LE, +3);
    BOP (MUL, 'r', R 'n'); BOP (SUB, 'n', I 1); JMP (T, -5); HLT|]
let collbin =
  [|BOP (LD, 'n', I 10); BOP (LD, 's', I 0); JMP (T, +9);
    BOP (ADD, 's', I 1); BOP (LD, 'p', R 'n'); BOP (MOD, 'p', I 2);
    CMP ('p', I 0); JMP (NE, +2); BOP (DIV, 'n', I 2); JMP (T, +2);
    BOP (MUL, 'n', I 3); BOP (ADD, 'n', I 1); 
    CMP ('n', I 1); JMP (G, -11); HLT|]