Ստեկային մեքենայի մոդել։ Մաս I

Պատկերացենք մի վերացական համակարգիչ, որի պրոցեսորի հրամանները նախատեսված են ստեկային վարքով աշխատելու համար։ Օրինակ ADD հրամանը արգումենտներ չունի, այլ վերցնում է ստեկի գագաթի երկու տարրերը, դրանք գումարում է իրար և արդյունքը նորից գրում է ստեկում։ Ենթադրենք, թե մեքենան կարող է աշխատել միայն ամբողջ թվերի հետ։

Ֆիզիկական կառուցվածքի տեսակետից այդ մեքենան (ստեկային համակարգիչը) ունի ընդհանուր օգտագործման հիշողություն, որում պահվում են կատարվող ծրագիրը, ստատիկ տվյալները, գլոբալ փոփոխականներ, և հենց այդ հիշողության ինչ-որ տիրույթում մոդելավորվում է ստեկը։

(defconstant +size+ 1024 "Հիշողության չափը")
(defparameter *memory* (make-array +size+)
  "Հիշողությունը որպես տրված չափի զանգված")

Մեքենան ունի նաև երեք ռեգիստրներ. ա) հերթական հատարվող հրամանի ցուցիչ՝ IP, բ) ստեկի գագաթի ցուցիչ՝ SP և գ) ստեկի կադրի ցուցիչ՝ FP, որը ֆունկցիաների կանչի ժամանակ օգտագործվում է ֆունկցիայի արգումենտներին և լոկալ փոփոխականների հասցեներին դիմելու համար։

(defparameter *ip* -1 "Հերթական հրամանի ցուցիչ")
(defparameter *sp* -1 "Ստեկի ցուցիչ")
(defparameter *fp* -1 "Ստեկի կադրի ցուցիչ")

Պարզության համար ընդունենք, որ կատարվող ծրագիրը բեռնվում է հիշողության 0 հասցեից։ Ծրագիր զբաղեցրած տիրույթին հաջորդում է ստատիկ տվյալների և գլոբալ փոփոխականների տիրույթը՝ տվյալների սեգմենտը։ Իսկ տվյալների սեգմենտին հաջորդում է ստեկի սեգմենտը։ Օրինակ, եթե հիշողության մեջ բեռնվել է 16 հրամաններից բաղկացած ծրագիր, որում կան 8 գլոբալ փոփոխականներ, ապա կոդի սեգմենտը կսկսվի 0 հասցեից, տվյալների սեգմենտը՝ 16 հասցեից, իսկ ստեկի սեգմենտը՝ 24 հասցեից։

«Ստեկային մեքենայի» հրամանները ստորև կներկայացվեն նրա «ասեմբլերի» լեզվով։ Մեքենայի հիշողություն բեռնվելուց հետո, բնականաբար, հրամանները կունենան այլ տեսք։

Ստեկում հաստատուն թիվ կարելի է ավելացնել PUSH հրամանով։ Օրինակ,

PUSH 777  ; ստեկում ավելացնել 777 արժեքը

Որևէ փոփոխականի արժեք ստեկում ավելացնելու համար նույնպես օգտագործվում է PUSH հրամանը՝ արգումենտում ունենալով փոփոխականի իդենտիֆիկատորը։ Փոփոխականների անունները կարող են սկսվել լատինական փոքրատառով և պարունակել միայն փոքրատառեր և թվանշաններ։ Օրինակ,

PUSH a    ; ստեկում ավելացնել a փոփոխականի զբաղեցրած հասցեում գրված արժեքը
PUSH wu3  ; ստեկում ավելացնել wu3 փոփոխականի զբաղեցրած հասցեում գրված արժեքը

Եթե հարկավոր է ստեկում ավելացնել հենց ռեգիստրի պարունակությունը, ապա ստեկի անունը պետք է սկսել «%» նիշով։ ենթադրենք M-ը ստեկային մեքենայի հիշողությունն է։ Այս դեպքում․

PUSH %FP   ; <=> SP := SP + 1; M[SP] := FP
PUSH %SP   ; <=> SPi := SPo + 1; M[SPi] := SPo

Անուղակի հասցեավորում կարելի է կատարել ռեգիստրի արժեքի օգնությամբ։ Օրինակ,

PUSH FP   ; <=> SP := SP + 1; M[SP] := M[FP]
PUSH FP+3 ; <=> SP := SP + 1; M[SP] := M[FP+3]

Այս չորս տիպի PUSH հրամանները կարելի է իրականացնել հետևյալ կերպ։

(defun push-value (value)
  (setf (aref *memory* (incf *sp*)) value))
(defun push-addr (address)
  (push-value (aref *memory* address)))
(defun push-regv (reg)
  (push-value (case reg (0 *ip*) (1 *sp*) (2 *fp*))))
(defun push-reg (reg &optional (disp 0))
  (let ((bs (case reg (0 *ip*) (1 *sp*) (2 *fp*))))
    (push-addr (+ bs disp))))

Ստեկից տվյալներ հեռացնելու համար է նախատեսված POP հրամանը։ Ստեկի գագաթի տարրը որևէ փոփոխականի վերագրելու համար POP հրամանն արգումենտում ունիփոփոխականի անունը։ Օրինակ.

POP u

Ինչպես PUSH հրամանը, նույնպես էլ POP հրամանը կարող է օգտագործել ռեգիստրի արժեքը՝ անուղակի հասցեավորում կազմակերպելու համար։ Օրինակ.

POP FP+1
POP FP
POP FP-12

Նշված երեք տիպի POP հրամաններն էլ իրականացված են հետևյալ ֆունկցիաներով։

(defun pop-value ()
  (aref *memory* (prog1 *sp* (decf *sp*))))
(defun pop-addr (address)
  (setf (aref *memory* address) (pop-value)))
(defun pop-regv (reg)
  (let ((vl (pop-value)))
    (case reg 
      (0 (setf *ip* vl))
      (1 (setf *sp* vl))
      (2 (setf *fp* vl)))))
(defun pop-reg (reg &optional (disp 0))
  (let ((bs (case reg (0 *ip*) (1 *sp*) (2 *fp*))))
    (pop-addr (+ bs disp))))

Օգտագործողի կողմից տվյալները ներմուծվում են IN հրամանով, որը ներմուծած թիվը գրում է ստեկի գագաթում։ Իսկ գործողությունների արդյունքն օգտագործողի համար արտածվում են OUT հրամանով, որը հեռացնում է ստեկի գագթի արժեքը և արտածում է ստանդարտ արտածման հոսքին։ Հետևյալ երկու ֆունկցիաներն այդ հրամանների իրականացումներն են.

(defun input-num ()
  (format t "? ")
  (push-value (parse-integer (read-line))))
(defun output-num ()
  (format t "> ~d~%" (pop-value)))

Ստեկային մեքենայի հրամանների համակարգում նախատեսված են նաև թվաբանական ու համեմատման գործողություններ, ինչպիսիք են գումարում, հանում, հավասարության ստուգում և այլն։ Բայց նախ սահմանենք binary-op և unary-op ֆունկցիաները, որոնց օգնությամբ կսահմանենք կոնկրետ բինար և ունար գործողություններ։

(defun binary-op (operation)
  (let* ((ao (pop-value))
         (ai (pop-value)))
    (push-value (funcall operation ai ao))))
(defun unary-op (operation)
  (let ((ao (pop-value)))
    (push-value (funcall operation ao))))

Հետո նոր սահմանենք ADD, SUB, MUL, DIV, MOD, EQ, NE, GT, GE, LT, LE բինար գործողությունները, ինչպես նաև NEG և NOT ունար գործողությունները։

(defun op-add () (binary-op #'+))
(defun op-sub () (binary-op #'-))
(defun op-mul () (binary-op #'*))
(defun op-div () (binary-op #'/))
(defun op-mod () (binary-op #'rem))
(defun op-eq () (binary-op #'=))
(defun op-ne () (binary-op #'/=))
(defun op-gt () (binary-op #'>))
(defun op-ge () (binary-op #'>=))
(defun op-lt () (binary-op #'<))
(defun op-le () (binary-op #'<=))
(defun op-not () (unary-op #'not))
(defun op-neg () (unary-op #'(lambda (x) (* x -1))))

Մինչև այս պահը թվարկված հրամաններով կարելի է կառուցել միայն գծային ալգորիթմներ։ Որպեսզի հնարավոր լինի ծրագրավորել ճյուղավորվող ու կրկնվող ալգորիթմներ, մեքենան պետք է ունենա անցման հրամաններ։ Ստեկային մեքենայի մոդելում JZ հրամանը անցում է կատարում տրված հասցեով հրամանին, եթե ստեկի գագաթի տարրը զրո է։ Նմանապես JNZ հրամանը անցում է կատարում տրված հասցեով հրամանին, եթե ստեկի գագաթում զրոյից տարբեր արժեք է։ Այս երկու հրամաններն էլ հեռացնում են ստեկի գագաթի տարրը։ Իսկ JUMP հրամանը պարզապես առանց պայմանի անցում է։ Բոլոր երեք հրամաններն էլ փոխում են IP ռեգիստրի արժեքը։

(defun jump (address)
  (setf *ip* address))
(defun jump-true (address)
  (when (pop-value) (jump address)))
(defun jump-false (address)
  (unless (pop-value) (jump address)))

Ասեմբլերային ծրագրի տեքստում նշիչներ (անցման կետեր) սահմանելու համար է LABEL փսևդոհրամանը։ Այն կատարվող հրամանի չի թարգմանվում, պարզապես իր արգումենտում տրված իդենտիֆիկատորին կապում է IP ռեգիստրի ընթացիկ արժեքը՝ հետագա հղումների համար։

LABEL wb0
;...
JUMP wb0

Եվս երկու հրամաններ, որոնք ապահովելու են ֆունկցիայի կանչ և վերադարձ ֆունկցիայից։ CALL հրամանի արգումենտը LABEL փսևդոհրամանով սահմանված իդենտիֆիկատոր է։

(defun call-func (address)
  (push-value 0)       ; ֆունկցիայի վերադարձրած արժեքի տեղը
  (push-value *ip*)    ; վերադարձի հասցեն, IP ռեգիստրի արժեքը
  (push-value *fp*)    ; ստեկի կադրի հին արժեքը
  (setf *fp* *sp*)     ; ստեկի կադրի ընթացիկ արժեքը
  (setf *ip* address)) ; IP ռեգիստրի նոր արժեքը

Ֆունկցիայից վերադարձի համար է նախատեսված RET հրամանը։ Այն տեղափոխում է ստեկի գագաէի տարրը վերադարձվող արժեքի համար նախատեսված տեսը։ վերականգնում է ստեկի ցուցիչի ռգիստրի հին արժեքը և IP ռեգիստրին վերագրում է CALL հրամանի նախատեսած վերադարձի հասցեն։

(defun return-func ()
  (pop-addr (- *fp* 2))    ; վերադարձվող արժեքը
  (setf *fp* (pop-value))  ; ստեկի կադրի ռեգիստրի վերականգնում
  (setf *ip* (pop-value))) ; վերադարձի հասցե

---

Ամբողջական կոդը տես github կայքում։

	(defconstant +size+ 64 "Հիշողության չափը")
	(defparameter *memory* (make-array +size+)
	"Հիշողությունը որպես տրված չափի զանգված")
	(defparameter *ip* -1 "Հերթական հրամանի ցուցիչ")
	(defparameter *sp* -1 "Ստեկի ցուցիչ")
	(defparameter *fp* -1 "Ստեկի կադրի ցուցիչ")
	(defun push-value (value)
	"Ստեկում ավելացնել տրված արժեքը"
	(setf (aref *memory* (incf *sp*)) value))
	(defun push-addr (address)
	(push-value (aref *memory* address)))
	(defun push-regv (reg)
	(push-value (case reg (0 *ip*) (1 *sp*) (2 *fp*))))
	(defun push-reg (reg &optional (disp 0))
	(let ((bs (case reg (0 *ip*) (1 *sp*) (2 *fp*))))
	(push-addr (+ bs disp))))
	(defun pop-value ()
	(aref *memory* (prog1 *sp* (decf *sp*))))
	(defun pop-addr (address)
	(setf (aref *memory* address) (pop-value)))
	(defun pop-regv (reg)
	(let ((vl (pop-value)))
	(case reg
	(0 (setf *ip* vl))
	(1 (setf *sp* vl))
	(2 (setf *fp* vl)))))
	(defun pop-reg (reg &optional (disp 0))
	(let ((bs (case reg (0 *ip*) (1 *sp*) (2 *fp*))))
	(pop-addr (+ bs disp))))
	(defun input-num ()
	(format t "? ")
	(push-value (parse-integer (read-line))))
	(defun output-num ()
	(format t "> ~d~%" (pop-value)))
	(defun binary-op (operation)
	(let* ((ao (pop-value))
	(ai (pop-value)))
	(push-value (funcall operation ai ao))))
	(defun unary-op (operation)
	(let ((ao (pop-value)))
	(push-value (funcall operation ao))))
	(defun op-add () (binary-op #'+))
	(defun op-sub () (binary-op #'-))
	(defun op-mul () (binary-op #'*))
	(defun op-div () (binary-op #'/))
	(defun op-mod () (binary-op #'rem))
	(defun op-eq () (binary-op #'=))
	(defun op-ne () (binary-op #'/=))
	(defun op-gt () (binary-op #'>))
	(defun op-ge () (binary-op #'>=))
	(defun op-lt () (binary-op #'<))
	(defun op-le () (binary-op #'<=))
	(defun op-not () (unary-op #'not))
	(defun op-neg () (unary-op #'(lambda (x) (* x -1))))
	(defun jump (address)
	(setf *ip* address))
	(defun jump-true (address)
	(when (pop-value) (jump address)))
	(defun jump-false (address)
	(unless (pop-value) (jump address)))
	(defun call-func (address)
	(push-value 0) ; ֆունկցիայի վերադարձրած արժեքի տեղը
	(push-value *ip*) ; վերադարձի հասցեն, IP ռեգիստրի արժեքը
	(push-value *fp*) ; ստեկի կադրի հին արժեքը
	(setf *fp* *sp*) ; ստեկի կադրի ընթացիկ արժեքը
	(setf *ip* address)) ; IP ռեգիստրի նոր արժեքը
	(defun return-func ()
	(pop-addr (- *fp* 2)) ; վերադարձվող արժեքը
	(setf *fp* (pop-value)) ; ստեկի կադրի ռեգիստրի վերականգնում
	(setf *ip* (pop-value))) ; վերադարձի հասցե

view raw gistfile1.lisp hosted with ❤ by GitHub

GNU/bytecode գրադարանի օգտագործման օրինակ

Ծրագրավորման լեզուների կոմպիլյացիայի հերցերն ուսումնասիրելիս ես տևական ժամանակ փնտրում էի մի գրադարան, որը հարավորություն կտար առանց մանրամասնությունների մեջ մտնելու գեներացնել Java վիրտուալ մեքենայի class ֆայլեր։ Առաջին որոնումները բերեցին ASM և BCEL գրադարաններին և Jasmin «Java ասեմբլերին»։ Վերջինս հնարավորություն է տալիս մնեմենիկ հրամաններով հրագրավորել ալգորիթմը, ապա այն «ասեմբլացնել» ու ստանալ վիրտուալ մեքենայի բայթ-կոդ՝ class ֆայլ։

Բայց, տարբեր պատճառներով, այդ գրադարաններից ոչ մեկը ես հարմար չգտա սովորելու համար։ Հետագա որոնումների ընթացքում հանդիպեցի GNU/bytecode գրադարանին, որ Scheme ծրագրավորման լեզվի Kawa իրականացման մաս է կազմում։

Այս գրառման մեջ ես ուզում եմ ֆակտորիալի և ամենամեծ ընդհանուր բաժանարարի հաշվման պարզ օրինակներով ցույց տալ, թե ինչպես կարելի է գեներացնել այդ երկու ալգորիթմները պարունակող class ֆայլը։

Նախ սկսեմ Java տարբերակից.

public class Algorithms {
  public static int factorial( int n )
  {
    if( n == 1 ) return 1;
    return n * factorial( n - 1 );
  }

  public static int gcd( int n, int m )
  {
    while( n != m )
      if( n > m )
        n -= m;
      else
        m -= n;
    return n;
  }
}

Այս դասի նկարագրությունը Algorithms.java ֆայլի մեջ գրառելուց և javac կոմպիլյատորով թարգմանելուց հետո ստացվում է Algorithms.class ֆայլը։ class ֆայլը կարելի է javap դիզասեմբլերով հետ թարգմանել ու տեսնել թե Java լեզվի կոմպիլյատորն ինչ հրամաններ է գեներացրել։ Այդ բոլոր հրամանների նկարագրությունը կարելի է գտնել Java վիրտուալ մեքենայի նկարագրության մեջ։

Compiled from "Algorithms.java"
public class Algorithms {
  public Algorithms();
    Code:
       0: aload_0
       1: invokespecial #1    // Method java/lang/Object."<init>":()V
       4: return 

  public static int factorial(int);
    Code:
       0: iload_0
       1: iconst_1 
       2: if_icmpne     7
       5: iconst_1 
       6: ireturn 
       7: iload_0 
       8: iload_0 
       9: iconst_1 
      10: isub 
      11: invokestatic  #2    // Method factorial:(I)I
      14: imul 
      15: ireturn 

  public static int gcd(int, int);
    Code:
       0: iload_0
       1: iload_1 
       2: if_icmpeq     24
       5: iload_0 
       6: iload_1 
       7: if_icmple     17
      10: iload_0 
      11: iload_1 
      12: isub 
      13: istore_0 
      14: goto          0
      17: iload_1 
      18: iload_0 
      19: isub 
      20: istore_1 
      21: goto          0
      24: iload_0 
      25: ireturn 
}

Այս արտածումը տրված է JVM-ի հրամաններ մնեմոնիկ ներկայացմամբ, որոնց բացատրությունները բերված են JVM Specification էջում։

 

Հիմա ցույց տամ, թե ինչպես եմ gnu.bytecode գրադարանի օգտագործմամբ ստեղծում factorial և gcd ալգորիթմները պարունակող class ֆայլը։ Արդեն նշեցի, որ gnu.bytecode գրադարանը Kawa լեզվի իրականացման մաս է։ Չնայած որ կարելի է կոդից առանձնացնել միայն gnu.bytecode-ն և կառուցել առանձին *.jar ֆայլ, ես կօգտագործեմ հենց kawa-1.13.jar ֆայլը։

ՈՒրեմն, նախ ներմուծում եմ gnu.bytecode գրադարանը․ import gnu.bytecode.*;

Հետո սահմանում եմ AlgoEx դասն իր main մեթոդով․

public class AlgoEx {
    public static void main(String[] args) throws Exception
    {

Հետո ստեղծում եմ ClassType դասի օբյեկտ, որը ներկայացնում է Java վիրտուալ մեքենայի դասը։ Այնուհետև դասի համար որպես ծնող նշում եմ java.lang.Object դասը, իսկ որպես տեսանելիության մոդիֆիկատոր նշում եմ public - Access.PUBLIC հոստատունի օգնությամբ։

        // class `Algorithms'
        ClassType clo = new ClassType("Algorithms");
        clo.setSuper("java.lang.Object");
        clo.setModifiers(Access.PUBLIC);

Քանի որ և՛ factroial, և՛ gcd մեդոդները սահմանելու եմ public ու static մոդիֆիկատորներով, այստեղ սահմանել եմ pubstat հաստատունը․

        final int pubstat = Access.PUBLIC | Access.STATIC;

Հետո clo դասում ավելացնում եմ նոր մեթոդ՝ "factorial" անունով և "(I)I" սիգնատուրայով։ addMethod մեթոդի վերադարձրած հղումև վերագրում եմ Method տիպի mfac փոփոխականին։

        // method `factorial'
        Method mfac = clo.addMethod("factorial", "(I)I", pubstat);

CodeAttr դասը նախատեսված է բուն կոդի գեներացիայի համար։ Ստորև բերված բլոկում կառուցված է ամբողջ թվի ֆակտորիալը հաշվող ֆունկցիայի կոդի գեներացիան․

        CodeAttr code = mfac.startCode();
        code.pushScope();
        code.emitLoad(code.getArg(0));
        code.emitPushInt(1);
        code.emitIfEq();
        code.emitPushInt(1);
        code.emitReturn();
        code.emitElse();
        code.emitLoad(code.getArg(0));
        code.emitDup();
        code.emitPushInt(1);
        code.emitSub(Type.intType);
        code.emitInvoke(mfac);
        code.emitMul();
        code.emitReturn();
        code.emitFi();
        code.popScope();

Նույն կերպ կառուցված է gcd մեթոդի կոդի գեներացիան։

        // method `gcd'
        Method mgcd = clo.addMethod("gcd", "(II)I", pubstat);
        Label bw = new Label(code);
        Label ew = new Label(code);
        code = mgcd.startCode();
        code.pushScope();
        bw.define(code);
        Variable n = code.getArg(0);
        Variable m = code.getArg(1);
        code.emitLoad(n);
        code.emitLoad(m);
        code.emitGotoIfEq(ew);
        code.emitLoad(n);
        code.emitLoad(m);
        code.emitIfGt();
        code.emitLoad(n);
        code.emitLoad(m);
        code.emitSub(Type.intType);
        code.emitStore(n);
        code.emitElse();
        code.emitLoad(m);
        code.emitLoad(n);
        code.emitSub(Type.intType);
        code.emitStore(m);
        code.emitFi();
        code.emitGoto(bw);
        ew.define(code);
        code.emitLoad(n);
        code.emitReturn();
        code.popScope();
 

Եվ վերջում writeToFile մեթոդով կառուցված դասի պարունակությունը գրվում է class ֆայլի մեջ։

        // write class file
        clo.writeToFile();
    }
}

Հիմա թարգմանեմ այս ֆայլը Java կոմպիլյատորով և գործարկեմ այն, որպեսզի ստանամ Algorithms.class ֆայլը։

$ javac -classpath .:kawa-1.13.jar AlgoEx.java 
$ java -classpath .:kawa-1.13.jar AlgoEx

Այս երկու հրամանների կատարումից հետո գեներացվում է Algorithms.class ֆայլը։ Կարելի է javap դիզասեմբլերով տեսնել այս ֆայլի պարունակությունը։ Բայց ես կգրեմ մի տեստային ֆայլ, որը կօգտագործի Algwrithms դասի factorial և gcd ֆունկցիաները։

public class Test {
    public static void main(String[] args)
    {
        System.out.println(Algorithms.factorial(10));
        System.out.println(Algorithms.gcd(123,31));
    }
}

Այս դասի թարգմանությունն ու կատարումը ցույց է տալիս, որ gnu.bytecode գրադարանի օգնությամբ կառուցված class ֆայլը ճիշտ է․

$ javac Test.java
$ java Test
3628800
1

Մեծ ամբողջ թվերի հաշվարկիչ (Calculator with big integers)

• Հաշվարկիչ կամ արտահայտությունների ինտերպրետատոր
  • Սահմանումներ
  • Աբստրակտ քերականական ծառ
  • Լեքսիկսկան և քերականական վերլուծություն
    • scanner փաթեթը
    • parser փաթեթը
  • Երկխոսություն օգտագործողի հետ
  • Ծրագրի մուտքի կետը և գործարկումը
• Հաշվարկիչ վերագրման և արտածման հրամաններով
  • Նոր քերականությունը
  • Կատարման միջավայր
  • Աբստրակտ քերականական ծառի ընդլայոնում
  • Փոփոխություններ լեքսիկական անալիզատորում
  • Փոփոխություններ քերականական անալիզատորում
  • Երկխոսության ցիկլը
• Հաշվարկիչից դեպի լեզվի ինտերպրետատոր
  • Ծրագրի կոդի ընթերցումը ֆայլից
  • Լեզվի քերականության ընդլայնում
    • Հրամանների հաջորդում
    • Ներածման հրաման
  • Ծրագրի մուտքի կետը
  • Օրինակ
• Համեմատում, ճյուղավորում, կրկնություն
  • Համեմատման գործողություններ
    • Լեքսիկական անալիզատորի փոփոխությունները
    • Աբստրակտ քերականական ծառի փոփոխությունները
    • Քերականական անալիզատորի փոփոխությունները
  • Ճյուղավորման և կրկնման կառուցվածքներ
    • Լեքսիկական անալիզատորի փոփոխությունները
    • Աբստրակտ քերականական ծառի ընդլայոնւմը
    • Քերականական անալիզատորի ընդլայնումը
  • Օրինակներ

Հաշվարկիչ կամ արտահայտությունների ինտերպրետատոր

Ինչպե՞ս գրել տողով տրված մաթեմատիկական արտահայտությունը հաշվարկող ծրագիր։ Կարող է թվալ, թե ավելորդ է գրել այս թեմայով, քանի որ կարելի է գտնել բազմաթիվ ու բազմազան գրականություն՝ հարուստ տեսական ու գործնական նյութով։ Բայց ես որոշեցի սկսել մի շարք, որտեղ կպատմեմ, թե ինչպես նախ կառուցել մի քանի թվաբանական գործողություններ կատարող հաշվարկիչ, ապա դրա հենքի վրա՝ քիչ-քիչ ընդլայնելով, ստեղծել ծրագրավորման լեզվի ինտերպրետատոր։

Որպես իրականացման միջոց ընտրել եմ Go լեզուն՝ երկու պատճառով. ա) ես ուզում եմ ավելի խորն ուսումնասիրել այդ լեզուն, և բ) ուզում եմ իմ կուտակած փորձը կիսել նրանց հետ, ովքեր հետաքրքրվում են Go լեզվով։

Սահմանումներ

Ամենից առաջ պետք է որոշել, թե ի՞նչ ֆունկցիոնալությամբ է օժտված լինելու հաշվարկիչը։ Սկզբի համար ես ընտրել եմ թվաբանական չորս բինար գործողություններ՝ գումարում, հանում, բազմապատկում և բաժանում, մեկ ունար գործողություն՝ բացասում, խմբավորման փակագծեր՝ գործողություններ։ Հաշվարկիչն աշխատելու է մեծ (“անսահմանափակ” երկարությամբ) ամբողջ թվերի հետ։ Օգտագործողի տեսակետից հաշվարկիչը ստանալու է արտահայտության տեքստային ներկայացումը, հաշվելու է նրա արժեքը և վերադարձնելու է պատասխանը՝ նորից տեքստային ներկայացմամբ։

EBNF գրառմամբ հաշվարկիչի լեզուն ներկայացնող քերականությունը կունենա այսպիսի տեսք.

Factor = "Number"
       | "-" Factor
       | "(" Expression ")".
Term = Factor {("*" | "/") Factor}.
Expression = Term {("+" | "-") Term}.

Այս երեք կանոններն ամբողջությամբ նկարագրում են գործողությունների թե՛ առաջայնությունը և թե՛ ասոցիատիվությունը։

Աբստրակտ քերականական ծառ

Քերականությամբ նկարագրված արտահայտությունների մոդելը աբստրակտ քերականական ծառն է (abstract syntax tree, AST)։ Այդ ծառի հանգույցները ներկայացնում են արտահայտության գործողությունները, իսկ տերևները ներկայացնում են տվյալները։ Օրինակ, 123 + 45 * 6 արտահայտության համար պետք է կառուցել հետևյալ ծառը.

    +
   / \
  /   \
123    *
      / \
     45  6

Աբստրակտ քերականական ծառը կառուցվում է քերականական անալիզատորի (parser) կողմից, և օգտագործվում է արտահայտության ինտերպրետացիայի (կամ կոմպիլյացիայի) ժամանակ։

Go լեզվով սահմանենք asteval փաթեթը, որը տրամադրում է ծառի հանգույցների ստրուկտուրան, կոնստրուկտոր ֆունկցիաներ՝ հանգույցներ ու տերևներ ստեղծելու համար, ինչպես նաև ծառի ինտերպրետացիայի ֆունկցիան։ Պրոյեկտի src պանակում ստեղծենք asteval պանակ, իսկ նրա մեջ՝ asteval.go ֆայլը։

Հայտարարենք asteval փաթեթը.

package asteval

Քանի որ մեր արտահայտություններն օգտագործելու են մեծ ամբողջ թվեր, Go լեզվի գրադարանից ներմուծենք big փաթեթը.

import "math/big"

Սահմանենք number = 0, unary = 1, binary = 2 հաստատունները, որոնք ցույց են տալու ծառի հանգույցի տիպը.

const (
  number byte = iota
  unary
  binary
)

Ծառի հանգույցը սահմանենք որպես Expression անունով կառուցվածք։ Նրա class դաշտը ցույց է տալիս հանգույցի տիպը, value դաշտը ցույց է տալիս հանգույցի արժեքը, եթե տիպը number է, operation դաշտը ցույց է տալիս հանգույցում ներկայացված ունար կամ բինար գործողությունը, իսկ first և second դաշտերը ցույց են տալիս հանգույցի ենթածառերը։ Եթե class = unary, ապա second = nil։

type Expression struct {
  class byte
  value *big.Int
  operation rune
  first, second *Expression
}

Ինչպես նշվեց, մենք գործ ենք ունենալու երեք տիպի հանգույցների հետ՝ թիվ, ունար գործողություն և բինար գքործողություն։ Սահմանենք կոնստրուկտոր ֆունկցիաներ նրանց համար։

Թիվ (number) ներկայացնող կոնստրուկտերը արգումենտում ստանում է թվի տեքստային տեսքը, և վերադարձնում է Expression կառուցվածքի նոր ստեղծված նմուշի ցուցիչը, որի class դաշտին վերագրված է number հաստատունը, իսկ value դաշտին՝ big.Int օբյեկտի ցուցիչը։

func Number(num string) *Expression {
  nm := new(big.Int)
  nm.SetString(num, 10)
  return &Expression{class: number, value: nm}
}

ՈՒնար գործողությանը համապատասխանող հանգույց ստեղծելու համար պետք է տալ գործողության նիշը և ենթաարտահայտությունը։ Չնայաց, որ մեր դեպքում կա միայն մեկ ունար գործողություն՝ բացասումը, կոնստրուկտոր ֆունկցիան որպես առաջին արգումենտ ընդունում է նաև գործողության նշանը։

func Unary(op rune, ex *Expression) *Expression {
  return &Expression{class: unary, operation: op, first: ex}
}

Բինար գործողության հանգույցի համար էլ պետք է ունենալ գործողության նշանը, աջ ու ձախ ենթաարտահայտությունները։

func Binary(op rune, exo, exi *Expression) *Expression {
  return &Expression{class: binary, operation: op, first: exo, second: exi}
}

Արտահայտության արժեքը հաշվելու համար պետք է անցում կատարել նրա համար կառուցած աբստրակտ քերականական ծառով՝ ըստ հետևյալ կանոնների.

1. եթե class = number, ապա վերադարձնել նրա value դաշտը,

2. եթե class = unary, ապա այս կանոնների կիրառմամբ հաշվել first ենթաարտահայտությունը և այդ արժեքի վրա կիրառել operation դաշտով որոշվող գործողությունը։

3. եթե class = binary, ապա այս կանոնների կիրառմամբ հաշվել first և second ենթաարտահայտությունները, ապա ստացված արժեքների նկատմամբ կիրառել operation դաշտով որոշվող գործողությունը։

Նշված կանոններն իրականացնելու համար Expression կառուցվածքի ցուցիչի համար սահմանենք Evaluate մեթոդը։

func (e *Expression) Evaluate() *big.Int {
  var res *big.Int = new(big.Int) 

  switch e.class {
    case number:
      res.Set(e.value)
    case unary:
      res = e.first.Evaluate()
      if '-' == e.operation { res.Neg(res) }
    case binary:
      exo := e.first.Evaluate()
      exi := e.second.Evaluate()
      switch e.operation {
        case '+': res.Add(exo, exi)
        case '-': res.Sub(exo, exi)
        case '*': res.Mul(exo, exi)
        case '/': res.Div(exo, exi)
      }
  }

  return res
} 

Ակնհայտ է, որ այս ֆունկցիան ունի թերություն. այն բաժանման գործողությունը կատարելուց առաջ չի ստուգում երկրորդ արգումենտի զրո լինելը։ Բայց այս անգամ անտեսենք այդ թերությունը՝ հետագայում ճշտելու պայմանով։

Ահա և վերջ, ամբողջությամբ սահմանված է asteval փաթեթը։ Այն տրամադրում է Expression կառուցվածքը, Number, Unary, Binary կոնստրուկտորները և Evaluate մեթոդը։

Լեքսիկսկան և քերականական վերլուծություն

Աբստրակտ քերականական ծառն արտահայտության ներքին, օգտագործողին չերևացող մասն է։ Տեքստային ներկայացումից այն ստանալու համար պետք է արտահայտությունը ենթարկել քերականական վերլուծության, և այդ վերլուծությունը պետք է կատարել վերը բերված կանոններով։ Բայց քերականական վերլուծության համար պետք է նախ արտահայտության տեքստը տրոհել տերմինալային տրամաբանական կտորների՝ լեքսեմների և ամենի մի լեքսեմի հետ կապել նրա տիպը (նշանակությունը) ցույց տվող հատկություն՝ թոքեն։ Օրինակ, 123 + 45 * 6 արտահայտության համար տրոհումը կարող է ունենալ այսպիսի տեսք.

Lexeme	Token
"123	Number
“+”	Add
“45”	Number
“*”	Mul
“6”	Number

Լեքսիկական անալիզատորի խնդիրն է հենց այս տրոհումը։ Քերականական անալիզատորն օգտագործում է թոքենները քերականական կանոնն ընտրելու համար, իսկ լեքսեմներն օգտագործում է ծառի հանգույցների պարունակությունը լրացնելու համար։

scanner փաթեթը

Լեքսիկական անլիզատորն իրականացնենք scanner փաթեթում։

package scanner

Ընթերցվող սիմվոլների տիպը որոշելու համար ներմուծենք Go լեզվի գրադարանային unicode փաթեթը։

import "unicode"

Սահմանենք Scanner կառուցվածքը, որի text դաշտը արտահայտության տեքստի նիշերի զանգվածն է, իսկ pos ինդեքսը ցույց է տալիս հերթական ընթերցվող սիմվոլը։

type Scanner struct {
    text []rune
    pos int
}

Scanner կառուցվածքի կոնստրուկտորը ստանում է վերլուծության ենթակա արտահայտության տեքստը, նրա վերջից կցում է “;” նիշը որպես արտահայտության ավարտի նշան, ապա տողը վերածում է նիշերի վեկտորի և վերագրում text դաշտին։

func New(txt string) *Scanner {
  return &Scanner{[]rune(txt+";"), 0}
}

Թոքենների համար սահմանենք հաստատուններ.

const (
  None byte = iota
  Number  // Digit{Digit}
  Add     // '+'
  Sub     // '-'
  Mul     // '*'
  Div     // '/'
  LPar    // '('
  RPar    // ')'
  Eos     // ';'
)

Սահմանենք մի օգնական մեթոդ, որը արտահայտության նիշերի շարքից կարդում է տրված պրեդիկատին բավարարող նիշերի անընդհատ շարք և վերադարձնում է դրանցից կազմած տողը։

func (s* Scanner) scanWith(predicate func(r rune) bool) string {
    k := s.pos
    for predicate(s.text[s.pos]) { s.pos++ }
    return string(s.text[k:s.pos])
}

Scanner կառուցվածքի Next մեթոդը վերադարձնում է երկու արժեք՝ հերթական լեքսեմը և նրան համապատասխանող թոքենը։ Մեթոդը նախ կանչում է scanWith մեթոդը IsSpace պրեդիկատով, որպեսզի դեն նետի բացատնանիշերը։ Այնուհետև, եթե հերթական նիշը թվանշան է, ապա scanWith մեթոդը կանչում է IsDigit պրեդիկատով ստանում է ամբողջ թիվ կազմող թվանշանների շարք։ Այս դեպքում վերադարձվում է թվանշաններից կազմված տողը որպես լեքսեմ և Number հաստատունը որպես թոքեն։ Թվանշաններից բացի դիտարկվում են միայն ‘+’, ‘-’, ‘*’, ‘/’, ‘(’, ‘)’ և ‘;’ նիշերը և ամեն մեկի համար վերադարձվում է համապատասխան թոքենը։ Բոլոր այլ նիշերի համար վերադարձվում է None թոքենը։

func (s *Scanner) Next() (string, byte) {
  s.scanWith(unicode.IsSpace)

  ch := s.text[s.pos]

  if unicode.IsDigit(ch) {
    return s.scanWith(unicode.IsDigit), Number
  }

  var res byte = None
  s.pos++
  switch ch {
    case '+': res = Add
    case '-': res = Sub
    case '*': res = Mul
    case '/': res = Div
    case '(': res = LPar
    case ')': res = RPar
    case ';': res = Eos
  }

  return string(ch), res
}

Սա էլ լեքսիկական անալիզատորի փաթեթեը։ նորից ոչ մի սխալների մշակում չի կարարված զուտ պարզության համար։ Նախագծի հետագա զարգացումներում անպայմանորեն պետք է հաշվի առնել հնարավոր սխալները։

parser փաթեթը

Քերականական անալիզատորն իրականացված է parser փաթեթում։ Այն ըստ քերականական կանոնների վերլուծում է արտահայտության տեքստը և կառուցում է աբստրակտ քերականական ծառը։ Քերականական սխալները չեն մշակվում՝ նորից պարզության համար։

package parser

Ներմուծենք մեր նախապես ստեղծած երկու փաթեթները։

import (
  "scanner"
  "asteval"
)

Parser կառուցվածքը քերականական անալիզատորի մոդելն է։ Նրա look դաշտը ընթացիկ թոքենն է՝ look-a-head սիմվոլը, lexeme դաշտը ընթացիկ լեքսեմն է, scan դաշտը լեքսիկական անալիզատորի ցուցիչն է։

type Parser struct {
  look byte
  lexeme string
  scan *scanner.Scanner
}

Parser կառուցվածքի համար կոնստրուկտոր չենք գրել, քանի որ դրա կարիքը պարզապես չկա։

Միակ միջոցը, որով քերականական անալիզատորը շփվում է արտաքին աշխարհի հետ, դա Parse մեթոդն է։ Այն ստանում է արտահայտության տեքստը և վերադարձնում է աբստրակտ քերականական ծառի արմատը (եթե վերլուծության ընթացքում սխալներ չեն հայտնաբերվել)։

func (p* Parser) Parse(src string) *asteval.Expression {
  p.look = scanner.None
    p.scan = scanner.New(src)
  p.match(scanner.None)
  return p.expr()
}

Parser-ը լեքսիկական անալիզատորից հերթական լեքսեմ-թոքեն զույգը կարդում է match մեթոդի օգնությամբ։ Հետագայում այս մեթոդի մեջ է իրականացվելու որոշ քերականական սխալների մասին ազդարարումը։

func (p *Parser) match(tok byte) bool {
  if tok != p.look { return false }
  p.lexeme, p.look = p.scan.Next()
  return true
}

Դիտարկվող արտահայտություների քերականությունն ունի երեք արտածման կանոն, ըստ որոնց էլ կառուցել եմ քերականական անալիզատորի մեթոդները։

Առաջինը Factor կանոնն է, որն ունի արտածման երեք տարբերակ․

Factor = "Number".
Factor = "-" Factor.
Factor = "(" Expression ")". 

ՈՒշադիր նայելով այս արտածման կանոններին տեսնում ենք, որ Factor կանոնը կարելի է կիրառել միայն այն դեպքում, երբ լեքսիկական անալիզատորի look-a-head սիմվոլը “Number”, “-”, “(” թոքեններից որևէ մեկն է։

Եթե look-a-head = “Number”, ապա ստեղծում և վերադարձնում ենք ծառի նոր տերև՝ ընթացիկ լեքսեմի արժեքով։ Եթե look-a-head = “-”, ապա հանդիպել ենք ունար գործողության։ Ռեկուրսիվ կանչով կառուցում ենք գործողության արգումենտի ծառը, ապա ստեղծում ենք ծառի ունար գործողության հանգույց։ Եթե look-a-head = “(”, ապա ռեկուրսիվ կանչով կառուցում ենք փակագծերի ներսում գրված արտահայտության ծառը, ապա match մեթոդի կանչով համոզվում ենք, որ առկա է փակվող փակագիծը։

func (p *Parser) factor() *asteval.Expression {
  // number
  if p.look == scanner.Number {
    num := p.lexeme
    p.match(scanner.Number)
    return asteval.Number(num)
  }

  // unary operation '-'
  if p.look == scanner.Sub {
    p.match(scanner.Sub)
    ex := p.factor()
    return asteval.Unary('-', ex)
  }

  // expression in parentheses
  if p.look == scanner.LPar {
    p.match(scanner.LPar)
    ex := p.expr()
    p.match(scanner.RPar)
    return ex
  }

  return nil
}

Քերականության հաջորդ կանոնը կառուցում է բազմապատկման ու բաժանման բինար գործողություններին համապատասխանող հանգույցները։ Ըստ քերականական երկրորդ կանոնի, Term-ը կարող է լինել կա՛մ Factor, կա՛մ “*” և “/” նիշերով իրար կցված Factor-ների հաջորդականություն․

Term = Factor {("*" | "/") Factor}.

Քերականական անալիզատորի term մեթոդը այս կանոնի տառացի իրականացումն է։

func (p *Parser) term() *asteval.Expression {
  ex1 := p.factor()
  for p.look == scanner.Mul || p.look == scanner.Div {
    op := rune(p.lexeme[0])
    p.match(p.look)
    ex2 := p.factor()
    ex1 = asteval.Binary(op, ex1, ex2)
  }
  return ex1
}

Երրորդ քերականական կանոնը կառուցում է գումարման ու հանման բինար գործողություններին համապատասխանող հանգույցները։ expr մեթոդը շատ նման է term մեթոդին։ Քանի որ մեր քննարկած արտահայտություններում գումարման ու հանման գործողություններն ունեն ամենացածր նախապատվությունը, հենց այս մեթոդն է կանչվում Parse մեթոդից։

func (p *Parser) expr() *asteval.Expression {
  ex1 := p.term()
  for p.look == scanner.Add || p.look == scanner.Sub {
    op := rune(p.lexeme[0])
    p.match(p.look)
    ex2 := p.term()
    ex1 = asteval.Binary(op, ex1, ex2)
  }
  return ex1
}

Երկխոսություն օգտագործողի հետ

Հաշվարկիչի և օգտագործողի շփումն իրականացված է հրամանային տողի օգնությամբ։ Գործարկումից հետո ծրագիրն արտածում է “>” սիմվոլը և սպասում է, որ օգտագործողը ներմուծի արտահայտության տեքստը։ Արտահայտության ներմուծումից և Enter ստեղնի սեղմումից հետո հաշվարկվում և արտածվում է արտահայտությունը արժեքը։

Փաթեթն անվանված է repl՝ (Read-Evaluate-Print-Loop)։

package repl

Ներմուծենք անհրաժեշտ փաթեթները։

import (
  "fmt"
  "os"
  "bufio"
  "parser"
)

Եվ միակ Run պրոցեդուրան, որը reader-ի միջոցով կարդում է օգտագործողի տված տեքստը, parser-ի միջոցով վերլուծում է այն ու կառուցում է աբստրակտ քերականական ծառ։ Այնուհետև ծառի արմատի համար կանչելով Evaluate մեթոդը՝ հաշվում է արտահայտության արժեքը։ Ցիկլը կատարվում է այնքան ժամանակ, քանի դեռ օգտագործողի ներածած տեքստի առաջին նիշը “.” (կետ) չէ։

func Run() {
  reader := bufio.NewReader(os.Stdin)
  parser := new(parser.Parser)

  for {
    fmt.Printf("> ")
    sr, _ := reader.ReadString('\n')
    ex := string(sr)
    if '.' == ex[0] { break }

    ast := parser.Parse(ex)
    res := ast.Evaluate()
    fmt.Println(">", res.String())
  }
}

Ծրագրի մուտքի կետը և գործարկումը

Go լեզվով գրված ծրագրերի մուտքի կետ է հանդիսանում main փաթեթի main ֆունկցիան։ Այն պարզապես կանչում է repl փաթեթի Run ֆունկցիան։

package main

import "repl"

func main() {
  repl.Run()
}

Հաշվարկիչ վերագրման և արտածման հրամաններով

Այս անգամ ես ներկայացնում եմ հաշվարկիչի մի նոր զարգացում, որտեղ ավելացված են փոփոխականին արժեքի վերագրման և արտահայտության արժեքի արտածման հրամանները։ Ի տարբերություն միայն թվաբանական գործողություններ կատարող հաշվարկիչի, փոփոխականներով հաշվարկիչը հնարավորություն է տալիս պահպանել և կրկին օգտագործել հաշվարկման արդյունքները։ Օրինակ, կարելի է գրել հետևյալ հրամանները․

a = 5
b = 4
print a + 1 + b

որոնց կատարումից հետո հաշվարկիչը կարտածի 10 արդյունքը։

Պետք է նկատի ունենալ, որ վերագրման և արտածման գործողությունները հրամաններ են, այլ ոչ թե արտահայտություններ։

Նոր քերականությունը

Հրամանների ավելացմամբ հաշվարկիչի լեզվի քերականությունն ընդլայնվում է և ստանում է ահա այսպիսի տեսք։

Statement = Assignment 
          | Print.
Assignment = 'Ident' '=' Expr.
Print = 'print' Expr.
Expr = Term {('+' | '-') Term}.
Term = Factor {('*' | '/') Factor}.
Factor = '(' Expr ')'
       | '-' Factor
       | 'Number'
       | 'Ident'.

Կատարման միջավայր

Քանի որ հաշվարկիչը պետք է կարողանա հիշել փոփոխականների արժեքները, սահմանենք Environment կառուցվածքը, որը մասնակցելու է հրամանների կատարման և արտահայտությունների հաշվարկման պրոցեսին և որի միջոցով փոխանցվելու են փոփոխականների արժեքները։

package environ

import "math/big"

Environment կառուցվածքը պարունակում է data դաշտը, որը արտապատկերում է փոփոխականի անունները արժեքներին։ Արտապատկերումը կազմակերպելու համար օգտագործված է Go լեզվի map օբյեկտը։

type Environment struct {
  data map[string]*big.Int
}

Միջավայրի կոնստրուկտորը պարզապես ստեղծում և վերադարձնում է նոր Environment օբյեկտի ցուցիչ։

func New() *Environment {
  return &Environment{data: make(map[string]*big.Int)}
}

Փոփոխականների արժեքները միջավայրում ավելացվում կամ թարմացվում են Set մեթոդով։

func (e *Environment) Set(name string, value *big.Int) {
  e.data[name] = value
}

Որևէ փոփոխականի արժեքը միջավայրից ստանալու համար է նախատեսված Get մեթոդը։

func (e *Environment) Get(name string) *big.Int {
  value, _ := e.data[name]
  return value
}

Աբստրակտ քերականական ծառի ընդլայոնում

Քերականության Factor արտածման կանոնում ավելացել է նոր ճյուղ՝ 'Ident', որը ցույց է տալիս, որ փոփոխականները նույնպես արտահայտություն են։ Ընդլայնենք asteval փաթեթի Expression կառուցվածքն այնպես, որ այն սպասարկի նաև փոփոխականները։

type Expression struct {
  class byte
  value *big.Int
  varname string
  operation rune
  first, second *Expression
}

Իսկ արտահայտության տիպը որոշող հաստատունների ցուցակում ավելացնենք ևս մեկ հաստատուն՝ variable։

const (
  number byte = iota
  variable
  unary
  binary
)

Բնականաբար պետք է ունենալ նաև նոր կոնստրուկտոր, որը կառուցում է փոփոխականին համապատասխան հանգույց.

func Variable(nam string) *Expression {
  return &Expression{class: variable, varname: nam}
}

Փոփոխության է ենթարկվում նաև արտահայտության արժեքը հաշվարկող Evaluate մեթոդը։ Այժմ այն իր արգումենտում ստանում է հաշվարկման միջավայրը՝ Environment կառուցվածքի ցուցիչ, որից վերցնելու ենք փոփոխականի արժեքը։

func (e *Expression) Evaluate(env *environ.Environment) *big.Int {
  var res *big.Int = new(big.Int)

  switch e.class {
    case number:
      res.Set(e.value)
    case variable:
      res.Set(env.Get(e.varname))
    case unary:
      res = e.first.Evaluate(env)
      if '-' == e.operation { res.Neg(res) }
    case binary:
      exo := e.first.Evaluate(env)
      exi := e.second.Evaluate(env)
      switch e.operation {
        case '+': res.Add(exo, exi)
        case '-': res.Sub(exo, exi)
        case '*': res.Mul(exo, exi)
        case '/': res.Div(exo, exi)
      }
  }

  return res
}

Լեզվի քերականության մեջ ավելացել է հրամանի հասկացությունը՝ Statement, իր երկու ներկայացումներով՝ Assignment և Print։ Հրամանների աբստրակտ քերականական ծառը կառուցելու համար ստեղծենք նոր փաթեթ.

package astexec

import (
  "asteval"
  "fmt"
  "environ"
)

Սահմանենք Statement ինտերֆեյսը, որի Execute մեթոդով իրականացնելու ենք տարբեր հրամանների վարքը.

type Statement interface {
  Execute(env *environ.Environment)
}

Վերագրման հրամանն իրականացված է Assignment կառուցվածքով, որի name դաշտը փոփոխականի անունն է, իսկ expr դաշտը այն արտահայտությունն է, որի արժեքը միջավայրում պետք է կապել փոփոխականի հետ։

type Assignment struct {
  name string
  expr *asteval.Expression
}

Կոնստրուկտորը շատ պարզ է։

func NewAssignment(nm string, ex *asteval.Expression) *Assignment {
  return &Assignment{name: nm, expr: ex}
}

Execute մեթոդի իրականացումը նախ հաշվում է expr արտահայտության արժեքը, ապա միջավայրում ավելացնում է նոր համապատասխանություն։

func (a *Assignment) Execute(env *environ.Environment) {
  val := a.expr.Evaluate(env)
  env.Set(a.name, val)
}

Արտածման հրամանի միակ expr դաշտը այն արտահայտությունն է, որի արժեքը պետք է հաշվել ու արտածել։

type Print struct {
  expr *asteval.Expression
}

Print հրամանի կոնստրուկտորն է.

func NewPrint(ex *asteval.Expression) *Print {
  return &Print{expr: ex}
}

Իսկ արտածման հրամանի կատարման համար պետք է պարզապես հաշվել expr արտահայտության արժեքը և fmt.Println ֆունկցիայով արտածել ստանդարտ արտածման հոսքի վրա։

func (p *Print) Execute(env *environ.Environment) {
  val := p.expr.Evaluate(env)
  fmt.Println(val.String())
}

Փոփոխություններ լեքսիկական անալիզատորում

Քերականության մեջ ավելացել են երեք թոքեններ՝ “Ident”, “Print” և “=”։ Իդենտիֆիկատորը դա տառով սկսվող տառաթվային հաջորդականություն է։ ‘print’-ը արտածման հրամանի ծառայողական բառն է։ ‘=’ նիշը վերագրման հրամանի սիմվոլն է։

const (
  None byte = iota
  Number  // Digit{Digit}
  Ident   // Letter{Letter|Digit}
  Add     // '+'
  Sub     // '-'
  Mul     // '*'
  Div     // '/'
  LPar    // '('
  RPar    // ')'
  Equal   // '='
  Print   // 'print', '?'
  Eos     // '@'
)

Ծառայողական բառերի համար սահմանենք մի աղյուսակ, որում իդենտիֆիկատորին համապատասխանեցված է թոքեն։ Այս աղյուսակն օգտագործելու ենք, որպեսզի պարզենք արդոք կարդացած իդենտիֆիկատորը ծառայողական բառ է, թե՝ ոչ։

var keywords = map[string]byte {
  "print": Print }

Սահմանենք նաև մի օգնական ֆունկցիա, որը դրական պատասխան է տալիս այն դեպքում, երբ արգումենտում տրված սիմվոլը տառ է կամ թվանշան։

func isLetterOrDigit(r rune) bool {
  return unicode.IsLetter(r) || unicode.IsDigit(r)
}

Լեքսիկական անալիզատորի Next մեթոդում ավելացնենք մի բլոկ, որը կարդում է տառով սկսվող տառաթվային հաջորդականություն, որոնում է այն ծառայողական բառերի աղյուսակում և, եթե գտնվել է, ապա վերադարձնում է համապատասխան թոքենը, հակառակ դեպքում վերադարձնում է Ident թոքենը։

...
  if unicode.IsLetter(ch) {
    iden := s.scanWith(isLetterOrDigit)
    tok, iskey := keywords[iden]
    if !iskey { tok = Ident }
    return iden, tok
  }
...

Փոփոխություններ քերականական անալիզատորում

Նախ factor մեթոդում ավելացնենք մի ճյուղ, որը վերլուծում է փոփոխականի առկայությունը.

...
  if p.look == scanner.Ident {
    nam := p.lexeme
    p.match(scanner.Ident)
    return asteval.Variable(nam)
  }
...

Քերականական անալիզատորում ավելացնենք երեք նոր մեթոդ՝ քերականության հետևյալ երեք կանոնների համար.

Statement = Assignment 
          | Print.
Assignment = 'Ident' '=' Expr.
Print = 'print' Expr.

Այս պահին մեր հրամանները կարող են սկսվել կա՛մ իդենտիֆիկատորով, կա՛մ print ծառայողական բառով։ Ես ճյուղավորման համար ընտրել եմ switch կառուցվածքը, որպեսզի հետագայում հեշտ լինի նոր հրամանների վերլուծության ճյուղերն ավելացնելը։

func (p *Parser) statement() astexec.Statement {
  switch p.look {
    case scanner.Ident:
      return p.assignment()
    case scanner.Print:
      return p.printexpr()
  }
  return nil
}

Վերագրման հրամանը վերլուծելու համար հերթականությամբ պետք է ճանաչել իդենտիֆիկատորը, հավասարության նշանը և հաջորդող արտահայտությունը։ Ապա կառուցել և վերադարձնել նոր Assignment հանգույց։

func (p *Parser) assignment() astexec.Statement {
  nm := p.lexeme
  p.match(scanner.Ident)
  p.match(scanner.Equal)
  ex := p.expr()
  return astexec.NewAssignment(nm, ex)
}

Արտածման հրամանը վերլուծելիս պետք է ճանաչել print ծառայողական բառը, ապա վերլուծել նրան հաջորդող արտահայտությունը։

func (p *Parser) printexpr() astexec.Statement {
  p.match(scanner.Print)
  ex := p.expr()
  return astexec.NewPrint(ex)
}

Քանի որ նոր քերականության մեջ առաջինը Statement կանոնն է, փոփոխենք Parse մեթոդն այնպես, որ նախ՝ այն վերադարձնի astexec.Statement, ապա՝ վերլուծությունը սկսի ոչ թե expr մեթոդից, այլ statement մեթոդից։

func (p* Parser) Parse(src string) astexec.Statement {
  p.look = scanner.None
  p.scan = scanner.New(src)
  p.match(scanner.None)
  return p.statement()
}

Երկխոսության ցիկլը

Ձևափոխված երկխոսության ցիկլում ստեղծում ենք նոր Environment օբյեկտ, որում պահվելու են փոփոխականների արժեքները։ Երբ Parse մեթոդը վերադարձնում է հրամանին համապատասխան աբստրակտ քերականական ծառը, կանչում ենք նրա Execute մեթոդը՝ արգումենտում տալով env օբյեկտը որպես կատարման միջավայր։

func Run() {
  reader := bufio.NewReader(os.Stdin)
  parser := new(parser.Parser)
  env := environ.New()

  for {
    fmt.Printf("> ")
    sr, _ := reader.ReadString('\n')
    ex := string(sr)
    if '.' == ex[0] { break }

    ast := parser.Parse(ex)
    ast.Execute(env)
  }
}

Հաշվարկիչից դեպի լեզվի ինտերպրետատոր

Հաշվարկիչի այս հերթական զարգացումը նպատակ ունի առաջին քայլն անել պարզագույն REPL ցիկլից դեպի ծրագրավորման լեզվի ինտերպրետատոր։ Նախ՝ լեքսիկական անալիզատորը կփոփոխվի այնպես, որ հրամանային տողի փոխարեն ծրագրի տեքստը ընթերցվի ֆայլից։ Ապա՝ լեզվի հրամանների համակարգը կընդլայնվի ներածման և հաջորդման հրամաններով։

Ծրագրի կոդի ընթերցումը ֆայլից

Ձևափոխենք լեքսիկական անալիզատորն այնպես, որ ծրագրի նիշերն ընթերցվեն ոչ թե տողից, այլ bufio.Reader օբյեկտից։ Scanner կառուցվածքի նոր տեսքն ահա այսպիսինն է.

type Scanner struct {
  source *bufio.Reader
  line int
}

Որտեղ line փոփոխականը նախատեսված է տողի համարը պահելու համար։ Այն մեզ հարկավոր է լինելու քերականական սխալների տեղը նշելիս։

Փոփոխության է ենթարկվում նաև Scanner-ի կոնստրուկտորը.

func New(src *bufio.Reader) *Scanner {
  return &Scanner{src, 1}
}

Հոսքից նիշեր կարդալիս անհրաժեշտ է մի ֆունկցիա, որը վերադարձնում է հերթական նիշը, բայց այն չի հեռացնում հոսքից։ Եթե հոսքն արդեն դատարկ է, ապա վերադարձնում է 0։

func (s *Scanner) peek() rune {
  br, ok := s.source.Peek(1)
  if ok != nil { return 0 }
  return rune(br[0])
}

Մեկ այլ ֆունկցիա կարդում և վերադարձնում է հերթական սիմվոլը։ Այս դեպքում նույնպես, եթե հոսքն արդեն դատարկ է, ապա վերադարձնում է 0։

func (s *Scanner) char() rune {
  ch, _, ok := s.source.ReadRune()
  if ok != nil { return 0 }
  return ch
}

scanWith մեթոդն արդեն ձևափոխված է այնպես, որ օգտագործվի char մեթոդը։ Այստեղ ձևավորվում է նաև line դաշտի ընթացիկ արժեքը։

func (s* Scanner) scanWith(predicate func(r rune) bool) string {
  res := ""
  ch := s.char()
  for predicate(ch) {
    res += string(ch)
    if ch == '\n' { s.line++ }
    ch = s.char()
  }
  s.source.UnreadRune()
  return res
}

Փոքր փոփոխություններ է կրել նաև քերականական անալիզատորը. Parse մեթոդը արգումենտում ստանում է ոչ թե տող, այլ bufio.Reader օբյեկտի ցուցիչ։

func (p* Parser) Parse(src *bufio.Reader) astexec.Statement {
  p.look = scanner.None
  p.scan = scanner.New(src)
  p.match(scanner.None)
  return p.sequence()
}

Այս փոփոխությունները բավական են, որպեսզի ֆայլի դեսկրիպտորից ստեղծվի bufio.Reader օբյեկտ և նրանից ընթերցվի ծրագիրը։

Լեզվի քերականության ընդլայնում

Հաշվարկիչի լեզուն ընդլայնված է երկու նոր հրամաններով՝ տվյալների ներածման և հրամաններ հաջորդման։

Sequence = Statement {';' Statement}.
Input = 'input' 'Ident'.

Հրամանների հաջորդում

Հաջորդման հրաման (կամ հրամանների հաջորդման կառուցվածք) ասելով կհասկանանք ծրագրի տեքստում իրար հետևից գրված հրամանները, որոնք բաժանված են “;” նիշով։ Պետք է ուշադրություն դարձնել, որ ոչ թե ամեն մի հրաման ավարտվում է “;” նիշով, այլ նրանով հրամաններն իրարից բաժանվում են։

Sequence կառուցվածքը պարունակում է միակ children դաշտը, որը պարունակում է հաջորդականություն կազմող հրամանների ցուցիչները։

type Sequence struct {
  children *list.List
}

Կոնստրուկտորը պարզապես արժեքավորում է children դաշտը։

func NewSequence() *Sequence {
  return &Sequence{children: list.New().Init()}
}

Append մեթոդը ցուցակում ավելացնում է հրամանների հաջորդականության հերթական տարրը։

func (q *Sequence) Append(st Statement) {
  q.children.PushBack(st)
}

Կատարման ժամանակ պարզապես հաջորդաբար կատարվում են children ցուցակի հրամանները (ճիշտ կլիներ, իհարկե, այստեղ ստուգել, որ ցուցակի տարրը nil չլինի)։

func (q *Sequence) Execute(env *environ.Environment) {
  for e := q.children.Front(); e != nil; e = e.Next() {
    st := e.Value.(Statement)
    st.Execute(env)
  }
}

Լեքսիկական անալիզատորի թոքենների ցուցակում ավելացնենք Semic թոքենը՝ “;” նիշի համար։

Քերականական անալիզատորում ավելացնենք sequence մեթոդը։ Այն ստեղծում է նոր Sequence օբյեկտ, ապա նրանում ավելացնում է հերծական վերլուծած հրամանները։

func (p *Parser) sequence() astexec.Statement {
  seq := astexec.NewSequence()
  st := p.statement()
  seq.Append(st)
  for p.look == scanner.Semic {
    p.match(scanner.Semic)
    seq.Append(p.statement())
  }
  return seq
}

Եվ նշենք, որ Parse մեթոդը ձևափոխված է այնպես, որ լեզվի վերլուծությունը սկսվի հենց sequence մեթոդից։

Ներածման հրաման

Ներածման հրամանը որոշվում է input ծառայողական բառով և նրան հետևող իդենտիֆիկատորով։ Այն օգտագործողից պահանջում է ստեղնաշարից ներմուծել ամբողջ թվի արժեքը։

Աբստրակտ քերականական ծառում ներածման հրամանի հանգույցն ունի հետևյալ տեսքը, որտեղ name դաշտը այն փոփոխականի անունն է, որի համար պետք է կարդալ արժեքը։

type Input struct {
  name string
}

Կոնստրուկտորը պարզ է.

func NewInput(nm string) *Input {
  return &Input{name: nm}
}

Ներածման հրամանը կատարելու համար ստեղծում ենք bufio.Reader օբյեկտ՝ os.Stdin ֆայլի հետ կապված։ Ապա կարդում ենք տող, նրանով արժեքավորում նոր big.Int օբյեկտ և փոփոխականի անունի հետ միասին ավելացում միջավայրում։

func (i *Input) Execute(env *environ.Environment) {
  reader := bufio.NewReader(os.Stdin)
  num, _ := reader.ReadString('\n')
  value := new(big.Int)
  value.SetString(num, 10)
  env.Set(i.name, value)
}

Parser կառուցվածքի inputval մեթոդը նախ չանաչում է scanner.Input թոքենը, ապա իդենտիֆիկատորը, վերջինիս համապատասխան լեքսեմն էլ օգտագործելով ստեղծում է նոր astexec.Input օբյեկտ։

func (p *Parser) inputval() astexec.Statement {
  p.match(scanner.Input)
  nm := p.lexeme
  p.match(scanner.Ident)
  return astexec.NewInput(nm)
}

Եվ ներածման հրամանը վերլուծության ենթական հրամանների շարքում ավելացնելու համար statement մեթոդում ավելացնում ենք նոր ճյուղ։

func (p *Parser) statement() astexec.Statement {
  switch p.look {
    case scanner.Ident:
      return p.assignment()
    case scanner.Print:
      return p.printexpr()
    case scanner.Input:
      return p.inputval()
  }
  return nil
}

Ծրագրի մուտքի կետը

main փաթեթի main ֆունկցիայում նախ ստուգում ենք, որ հրամանայի տողում տրված արումենտները լինեն ճիշտ երկու հատ՝ len(os.Args) != 2։ Ապա փորձում ենք os.Open ֆունկցիայով բացել ծրագրի ֆայլը՝ անհաջողության դեպքում տալով հաղորդագրություն։

func main() {
  if len(os.Args) != 2 {
    fmt.Println("Source file missing.")
    os.Exit(1)
  }

  fin, err := os.Open(os.Args[1])
  if err != nil {
    fmt.Println("Cannot open input file.")
    os.Exit(2)
  }
  defer fin.Close()

  par := new(parser.Parser)
  ast := par.Parse(bufio.NewReader(fin))
  env := environ.New()
  ast.Execute(env)
}

Օրինակ

Ստեղծենք test0.calc անունով ֆայլ և նրա մեջ գրենք հետևյալը.

input a;
input b;
c = a+b;
print c.

Համեմատում, ճյուղավորում, կրկնություն

Ինտերպրետատորի զարգացման այս քայլում ես պլանավորել էի իրականացնել ճյուղավորման և կրկնման հրամանները։ Բայց, քանի որ համեմատման գործողությունները սերտորեն կապված են դրանց հետ, ես նախ ընդլայնեցի արտահայտություններն այնպես, որ նրանք ընդգրկեն համեմատման վեց գործողություններ, ապա նոր միայն ընդլայնեցի հրամանների համակարգը ճյուղավորման և կրկնման հրամաններով։

Համեմատման գործողություններ

Երկու թվերի համեմատման գործողությունների համար ես ընտրել եմ հետևյալ նշանակումները․

# = - հավասար է, # <> - հավասար չէ, # > - մեծ է, # >= - մեծ է կամ հավասար, # < - փոքր է, # <= - փոքր է կամ հավասար:

Արտահայտությունների քերականությունն ընդլայնվում է և ստանում է այսպիսի տեսք․

Relation = Expr [RelOper Expr].
RelOper = '=' | '<>' | '>' | '>=' | '<' | '<='.
Expr = Term {('+' | '-') Term}.
Term = Factor {('*' | '/') Factor}.
Factor = 'Number'
       | 'Ident'
       | '-' Factor
       | '(' Expr ')'.

Լեքսիկական անալիզատորի փոփոխությունները

Թոքենների ցուցակում ավելացել են հաստատուններ վերը նշված համեմատման գործողությունների համար․

const (
  None byte = iota
  ...
  Equal       // '='
  NotEq       // '<>'
  Great       // '>'
  GrEq        // '>='
  Less        // '<'
  LsEq        // '<='
  ...
)

Քանի որ սրանով թվաբանական ու համեմատման գործողությունների քանակն իրար հետ վերցրած հասավ տասի, ես որոշեցի լեքսեմներին թոքեններ համապատասխանեցնելու համար սահմանել մի հեշ աղյուսակ․

var operations = map[string]byte{
  "+":  Add,
  "-":  Sub,
  "*":  Mul,
  "/":  Div,
  "=":  Equal,
  "<>": NotEq,
  ">":  Great,
  ">=": GrEq,
  "<":  Less,
  "<=": LsEq,
}

Իսկ գործողություններ կազմող սիմվոլները ճանաչելու համար սահմանեցի isOpChar ֆունկցիան, որպեսզի հնարավորություն ունենամ գործողությունների նշաններ կարդալ scanWith մեթոդով․

func isOpChar(r rune) bool {
  return strings.ContainsRune("+-*/=><", r)
}

Համապատախանաբար Next մեթոդի մարմնում ավելացավ մի նոր ճյուղ, որը կարդում և ճանաչում թվաբանական ու համեմատման գործողությունների նշանները․

func (s *Scanner) Next() (string, byte) {
  ...
  // operations
  if isOpChar(ch) {
    str := s.scanWith(isOpChar)
    tok, iskey := operations[str]
    if !iskey {
      tok = None
    }
    return str, tok
  }
  ...
}

Աբստրակտ քերականական ծառի փոփոխությունները

Քանի որ համեմատումները բինար գործողություններ են, նրանց համապատասխան ծառի հանգույցներ կստեղծենք NewBinary կոնստրուկտորով։ Փոփոխություններ կատարվել են միայն Evaluate մեթոդում։ big փաթեթի Int կառուցվածքի համար սահմանված Cmp մեթոդը համեմատում է երկու Big թվեր և վերադարձնում է -1, 0, 1, երբ առաջին թիվը համապատասխանաբար փոքր է, հավասար է կամ մեծ է երկրորդ թվից։

func (e *Expression) Evaluate(env *environ.Environment) *big.Int {
  var res *big.Int = new(big.Int)

  switch e.class {
    ...
    case binary:
      exo := e.first.Evaluate(env)
      exi := e.second.Evaluate(env)
      switch e.operation {
        ...
        case "=":
          u := exo.Cmp(exi)
          res.SetInt64(toInt64(u == 0))
        case "<>":
          u := exo.Cmp(exi)
          res.SetInt64(toInt64(u != 0))
        case ">":
          u := exo.Cmp(exi)
          res.SetInt64(toInt64(u > 0))
        case ">=":
          u := exo.Cmp(exi)
          res.SetInt64(toInt64(u >= 0))
        case "<":
          u := exo.Cmp(exi)
          res.SetInt64(toInt64(u < 0))
        case "<=":
          u := exo.Cmp(exi)
          res.SetInt64(toInt64(u <= 0))
      }
  }
  return res
}

Քերականական անալիզատորի փոփոխությունները

Քերականական անալիզատորում ավելացել է relation մեթոդը, որը տառացիորեն համընկնում է քերականության հետևյալ կանոնին.

Relation = Expr [RelOper Expr].
RelOper = '=' | '<>' | '>' | '>=' | '<' | '<='.

func (p *Parser) relation() *asteval.Expression {
  ex := p.expr()
  if p.look >= scanner.Equal && p.look <= scanner.LsEq {
    op := p.lexeme
    p.match(p.look)
    ex = asteval.Binary(op, ex, p.expr())
  }
  return ex
}

Ճյուղավորման և կրկնման կառուցվածքներ

Երկու նոր հրամանները, որոնք անհրաժեշտ են քիչ թե շատ կարգին ալգորիթմներ գրելու համար դրանք ճյուղավորման ու կրկնման հրամաններն են։ Քերականական տեսակետից նրանք ունեն այսպիսի տեսք.

Statement = ... 
          | Branching
          | Looping.
Branching = 'if' Relation 'then'
              Sequence
           {'elseif' Relation 'then'
              Sequence}
           ['else'
              Sequence]
            'end'.
Looping = 'while' Relation 'do'
            Sequence
          'end'.

Լեքսիկական անալիզատորի փոփոխությունները

Թոքենների ցուցակում պետք է հաստատուններ ավելացնել if, then, elseif, else, while, do և end ծառայողական բառերի համար։

const (
  None   byte = iota
  ...
  If          // 'if'
  Then        // 'then'
  ElseIf      // 'elseif'
  Else        // 'else'
  While       // 'while'
  Do          // 'do'
  End         // 'end'
  ...
)

Ծառայողական բառերը թոքենների արտապատկերող հեշ աղյուսակը նույնպես պետք է ընդլայնել հետևյալ կերպ.

var keywords = map[string]byte{
  ...
  "if":     If,
  "then":   Then,
  "elseif": ElseIf,
  "else":   Else,
  "while":  While,
  "do":     Do,
  "end":    End,
}

Աբստրակտ քերականական ծառի ընդլայոնւմը

astexec փաթեթում ավելանում են Branching և Looping կառուցվածքներն իրենց կոնստրուկտորներով ու Execute մեթոդներով։

Branching կառուցվածքը, որ նախատեսված է ճյուղավորման հրամանի համար, պարունակում է cond դաշտը որպես պայմանի արտահայտություն, thenpart դաշտը որպես հրամանների հաջորդականություն, որոնք պիտի կատարվեն այն դեպքում, երբ cond արտահայտության արժեքը հաշվարկվել է զրոյից տարբեր, և elsepart դաշտը որպես հարմանների հաջորդականություն, որոնք կատարվում են cond արտահայտության զրո հաշվարկված արժեքի դեպքում։

type Branching struct {
  cond *asteval.Expression
  thenpart, elsepart Statement
}

Կոնստրուկտորը ստանում է միայն երկու արգումենտ՝ cond և thenpart դաշտերի համար, իսկ elsepart դաշտն արժեքավորվում է առանձին SetElse մեթոդով։

func NewBranching(cd *asteval.Expression, tp Statement) *Branching {
  return &Branching{cond: cd, thenpart: tp, elsepart: nil}
}

func (b *Branching) SetElse(e Statement) {
  b.elsepart = e
}

Ճյուղավորման հրամանի կատարումը շատ պարզ է։ Նախ հաշվարկվում է cond արտահայտության արժեքը, ապա, եթե այն տարբեր է զրոյից՝ կատարվում է thenpart հրամանների հաջորդականությունը, հակառակ դեպքում՝ elsepart հաջորդականությունը։

func (b *Branching) Execute(env *environ.Environment) {
  ex := b.cond.Evaluate(env)
  if 0 != ex.Cmp(big.NewInt(0)) {
    b.thenpart.Execute(env)
  } else {
    b.elsepart.Execute(env)
  }
}

Կրկնման հրամանը մոդելավորող Looping կառուցվածքում cond դաշտը ցիկլի կատարման պայմանն է, իսկ body դաշտը՝ ցիկլի մարմինը։ Կոնստրուկտորը պարզապես արժեքավորում է այդ դաշտերը։

type Looping struct {
  cond *asteval.Expression
  body Statement
}

func NewLooping(cd *asteval.Expression, bd Statement) *Looping {
  return &Looping{cd, bd}
}

Կրկնման հրամանը կատարելու համար նախ հաշվվում է cond արտահայտությունը։ Եթե նրա արժեքը զրոյից տարբեր է, ապա կատարվում է body հրամանների հաջորդականությունը։ Նույնը կրկնվում է այնքան ժամանակ, քանի դեռ cond արտահայտության արժեքը տարբեր է զրոյից։

func (w *Looping) Execute(env *environ.Environment) {
  zr := big.NewInt(0)
  ex := w.cond.Evaluate(env)
  for 0 != ex.Cmp(zr) {
    w.body.Execute(env)
    ex = w.cond.Evaluate(env)
  }
}

Քերականական անալիզատորի ընդլայնումը

Ճյուղավորման հրամանի քերականական կանոնը պահանջում է, որ հրամանը սկսվի if ծառայողական բառով, որին հետևում է պայմանը ներկայացնող արտահայտությունը, ապա then ծառայողական բառը, որին հետևում են այն հրամանները, որոնք կատարվելու են, երբ պայմանի արտահայտության արժեքը հաշվարկվի զրոյից տարբեր։

func (p *Parser) branching() astexec.Statement {
  p.match(scanner.If)
  ex := p.relation()
  p.match(scanner.Then)
  st := p.sequence()
  res := astexec.NewBranching(ex, st)

Ճյուղավորման հրամանի առաջին պայմանին կարող են հաջորդել անսահմանափակ քանակով elseif կառուցվածքներ՝ իրենց համապատասխան հրամանների հաջորդականություններով։

  t := res
  for p.look == scanner.ElseIf {
    p.match(scanner.ElseIf)
    ex = p.relation()
    p.match(scanner.Then)
    st = p.sequence()
    v := astexec.NewBranching(ex, st)
    t.SetElse(v)
    t = v
  }

Եվ հրամանը կարող է ունենալ միակ else ճյուղ, որում թվարկված հրամանները կկատարվեն, եթե մինչև իրեն նշված բոլոր պայմանների արտահայտությունների հաշվարկը վերադարձրել զրոյական արժեք։

  if p.look == scanner.Else {
    p.match(scanner.Else)
    se := p.sequence()
    t.SetElse(se)
  }

Ճյուղավորման հրամանն ավարտվում է end ծառայողական բառով։

  p.match(scanner.End)
  return res
}

Կրկնման հրամանը սկսվում է while ծառայողական բառով, որին հետևում են կրկնման պայմանի արտահայտությունը, do բառը, հրամանի մարմնի հրամանների հաջորդականությունը և ապա end բառը։

func (p *Parser) looping() astexec.Statement {
  p.match(scanner.While)
  ex := p.relation()
  p.match(scanner.Do)
  st := p.sequence()
  p.match(scanner.End)
  return astexec.NewLooping(ex, st)
}

Բնականաբար branching և looping մեթոդներն իրականացնելուց հետո պետք է statement մեթոդում ավելացնել նրանց համապատասխան ճյուղերը։

Օրինակներ

Հետևյալ երկու օրինակները ցուցադրում են ճյուղավորման ու կրկնման հրամանների օգտագործումը։

Առաջին օգտագործողից հարցնում է ինչ-որ թիվ և ամեն մի թվի համար արտածում է պատասխան։

input x;
if x = 1 then
  print 100
elseif x = 2 then 
  print 200
elseif x = 3 then
  print 300
elseif x = 4 then
  print 400
else
  print 100000
end.

Երկրորդ օրինակը հաշվում է 10-ի ֆակտորիալը։

i = 10;
r = 1;
while i do 
  print i;
  r = r * i;
  i = i - 1
end;
print r.

Լեքսիկական (նիշային) վերլուծություն

Լեքսիկական կամ նիշային վերլուծությունը տեքստի մշակման այն փուլն է, երբ, ըստ նախապես տրված կանոնների, տեստը տրոհվում է առանձին հատվածների և ամեն մի հատվածի վերագրվում է իր տիպին համապատասխան պիտակ։ Օրինակ, թող որ տրված են ինչ-որ ծրագրավորման լեզվի ծրագրերի լեքսիկական վերլուծության հետևյալ մի քանի (ոչ լրիվ) կանոնները․

1. if, then, else, print բառերը ծառայողական բառեր են՝ ամեն մեկն իր անունով,

2. Տառով սկսվող և տառերից ու թվերից բաղկացած սիմվոլների անընդհատ հաջորդականությունը իդենտիֆիկատոր է,

3. Թվանշանների անընդհատ հաջորդականությունը ամբողջ թիվ է,

4. Երկու չակերտներով պարփակված և չակերտ չպարունակող տեքստի հատվածը տող է,

5. >, >=, <, <= և այլն, համեմատման գործողություններ են՝ ամեն մեկն իր անունով։

Եվ պետք է ըստ այս կանոնների լեքսիկական վերլուծության ենթարկել հետևյալ տեքստը․

if num >= 10 then
    print "Test done"

Սիմվոլների առաջին անընդհատ հատվածը if բառն է, որը, ըստ տրված կանոնների, ծառայողական բառ է։ Հաջորդ հատվածը num բառն է, որը չկա ծառայողական բառերի ցուցակում և, ըստ երկրորդ կանոնի, պետք է համարել իդենտիֆիկատոր։ >= սիմվոլների հաջորդականությունը մեծ է կամ հավասար համեմատման գործողությունն է, ըստ հինգերորդ կանոնի։ Ըստ երրորդ կանոնի 10 հաջորդականութթյունը ամբողջ թիվ է։ then և print բառերը նորից ծառայողական բառեր են։ Իսկ Test done հատվածը, ընդ որում՝ առանց ընդգրկող չակերտների, տող է։

Ընդունված տերմինաբանությամբ նախապես տրված տեքստից առանձնացված հատվածները կոչվում են լեքսեմներ (lexeme), իսկ նրանց համապատասխանեցված պիտակները՝ տոկեններ (token) կամ թոքեններ։ Եթե բերված օրինակի համար կազմենք լեքսեմների ու թոքեների աղյուսակը, ապա այն կունենա այսպիսի տեսք․

Լեքսեմ	Թոքեն
if	IF
num	IDENTIFIER
>=	GE
10	INTEGER
then	THEN
print	PRINT
Test done	STRING

Լեքսիկական վերլուծության ժամանակ նիշ առ նիշ անցում է կատարվում վերլուծության ենթական տեքստով և փորձ է կատարվում ճանաչել վերլուծության կանոններին համապատասխանող նիշերի ամենաերկար հաջորդականությունը։ Կարելի է լեքսիկական անալիզատորը ներկայացնել որպես վերջավոր ավտոմատ, և հմնականում հենց այդպես էլ արվում է։ Ավտոմատի սկզբնակական վիճակից, կողմնորոշվելով հերթական սիմվոլով, ընտրվում է վերլուծության համապատասխան կանոնը։ Այնուհետև ավտոմատն աշխատում և փոխում է իր վիճակներն այնքան ժամանակ, քանի դեռ չի հասել վերջնական վիճակի կամ քանի դեռ չի ավարտվել վերլուծության ենթարկվող տողը։ Առաջին դեպքում համարվում է, որ թոքենը ճանաչվել է, և ավտոմատը վերադառնում է սկզբնական վիճակին՝ նոր թոքեն ճանաչելու փորձ կատարելու համար։ Երկրորդ դեպքում, երբ ավարտվել է տողի ընթերցումը, բայց ավտոմատը չի հասել որևէ վերջնական վիճակի, կա՛մ կարելի է տալ սխալի մասին ազդանշան, կա՛մ պահանջել ևս մի տող՝ վերլուծությունը շարունակելու համար։

Ստորև բերված է մի դետերմինացված վերջավոր ավտոմատի (DFA) ուրվապատկեր, որը «կարողանում է ճանաչել» իդենտիֆիկատորները, չակերտների մեջ վերցրած տողերը և ամբողջ թվերը։

Հերթական սիմվոլը կարդալուց հետո «1» համարով վիճակում որոշում է կայացվում, թե որ ուղղությամբ պետք է շարժվել, իսկ «3», «4» և «5» վիճակները ցույց են տալիս, թե ինչ տիպի տեքստ է ճանաչվել։

Լեքսիկական վերլուծության ժամանակ հոսքից տվյալների ընթերցումը կատարվում է նիշ առ նիշ։ Այդ նիշերն իրար կցելու և ամբողջական տող ստանալու համար է սահմանված char-list-to-string ֆունկցիան․

(defun char-list-to-string (chars)
  (apply #'concatenate 'string (mapcar #'string chars)))

Ամենատարածված դեպքերն են, երբ երբ հոսքից պետք է կարդալ կա՛մ որևէ տիպի նիշերի շարք, կա՛մ տրված երկու նիշերի միջև պարփակված տեքստ։ Օրինակ, եթե հոսքի ընթացիկ նիշը տառ է՝ alpha-char-p, ապա պետք կարդալ նրան հաջորդող բոլոր տառերն ու թվանշանները՝ alphanumericp, ապա պարզել կարդացածը իդենտիֆիկատո՞ր է, թե՞ ծառայողական բառ։ Տրված պրեդիկատին բավարարող նիշերի շղթա կարդալու համար սահմանված է scan-sequence ֆունկցիան։

(defun scan-sequence (fu sm)
  (char-list-to-string
    (loop for ch = (read-char sm nil)
          until (null ch)
          while (funcall fu ch)
          collect ch
          finally (when ch (unread-char ch sm)))))

Իսկ տրված երկու նիշերի մեջ պարփակված նիշերի շարքը կարդալու համար սահմանված է scan-quoted ֆունկցիան։

(defun scan-quoted (co ci sm)
  (if (char= co (read-char sm nil))
    (prog1 
      (scan-sequence #'(lambda (c) (char/= c ci)) sm)
      (read-char sm nil))))

Հիմանականում անհրաժեշտ է լինում ընթերցման հոսքից հեռացնել իմաստ չպարունակող բացատանիշերը (white spaces)։ Որպեսզի հնարավոր լինի scan-sequence ֆունկցիայով կարդալ իրարա հաջորդող բացատանիշերը, սահմանված են space-char-p պրեդիկատը և skip-white-spaces ֆունկցիան։

(defun space-char-p (c)
  (or (char= c #\Newline)
      (char= c #\Tab)
      (char= c #\Space)
      (char= c #\Return)))
(defun skip-white-spaces (stream)
  (scan-sequence #'space-char-p stream))

Իդենտիֆիկատորներն ու ծառայողական բառերը կարդացվոլու են նույն կանոնով։ +keywords+ ցուցակում առանձնացված են այն լեքսեմները, որոք ծառայողական բառեր են, և նրանցից ամեն մեկին համապատասխանեցված է իր թոքենը։

(defconstant +keywords+
  '(("if"    . :lex-if)
    ("then"  . :lex-then)
    ("else"  . :lex-then)
    ("for"   . :lex-for)
    ("while" . :lex-while)
    ("input" . :lex-input)
    ("print" . :lex-print)))

oper-char-p պրեդիկատը դրական պատասխան է տալիս իր արգումենտում տրված այն նիշերի համար, որոնցով կարելի է կազմել հարաբերության կամ թվաբանական գործողություններ։

(defun oper-char-p (c)
  (member c '(#\= #\> #\< #\+ #\- #\* #\/ #\%)))

Իսկ +operations+ ցուցակում հավաքված են այն գործողությունների նշանները, որոնք կազմված են open-char-p պրեդիկատին բավարարող նիշերից (կամ դրանց համակցությունից)։

(defconstant +operations+
  '(("="  . :lex-equal)
    ("<>" . :lex-not-equal)
    (">"  . :lex-greater)
    (">=" . :lex-great-equal)
    ("<"  . :lex-lesser)
    ("<=" . :lex-less-equal)
    ("+"  . :lex-add)
    ("-"  . :lex-sub)
    ("*"  . :lex-mul)
    ("/"  . :lex-div)
    ("%"  . :lex-mod)))

Պարզելու համար, թե արդյոք կարդացած լեքսեմը պատկանո՞ւմ է +keywords+ կամ +operations+ ցուցակներից որևէ մեկին, սահմանված է known-lexeme ֆունկցիան։

(defun known-lexeme (lexeme pairs &optional (default :lex-unknown))
  (let ((res (find lexeme pairs :test #'equal :key #'first)))
    (if res res (cons lexeme default))))

Եվ վերջապես, լեքսիկական (նիշային) վերլուծություն կատարող scan-lexeme հիմնական ֆունկցիան։ Այն նախապես ընթերցման հոսքից հեռացնում է բացատանիշերը։ Ապա, ըստ դեն նետված բացատանիշերին հաջորդող առաջին նիշի, որոշում է կայացնում, թե ինչ լեքսեմ պետք է կարդալ։

(defun scan-lexeme (stream)
  (skip-white-spaces stream)
  (let ((ch (peek-char nil stream nil)))
    (cond
      ((null ch)
       (cons "<EOS>" :lex-eos))
      ((alpha-char-p ch)
       (known-lexeme (scan-sequence #'alphanumericp stream)
             +keywords+ :lex-identifier))
      ((digit-char-p ch)
       (cons (scan-sequence #'digit-char-p stream)
         :lex-integer))
      ((oper-char-p ch)
       (known-lexeme (scan-sequence #'oper-char-p stream)
             +operations+))
      ((char= #\" ch)
       (cons (scan-quoted #\" #\" stream)
         :lex-string))
      (t (cons (read-char stream nil) :lex-character)))))

Վերջ։ Հիմա պատրաստենք մի ֆայլ, որ պարունակում է տեստային տվյալներ։ Անվանենք ֆայլը test0.txt և նրանում գրառենք հետևյալը․

" asda asdkak "
1234
abcd3434jf
if
then
=
>
<>
%
$
#

Այնուհետև Common Lisp միջավայրում, հաշվարկենք հետևյալ կոդը․

(with-open-file (inp "test0.txt" :direction :input)
  (loop for lex = (scan-lexeme inp)
        until (eq (cdr lex) :lex-eos)
        do (print lex)))
(terpri)

Կատարման արդյունքում պետք է արտաշվի հետևյալը․

(" asda asdkak " . :LEX-STRING) 
("1234" . :LEX-INTEGER) 
("abcd3434jf" . :LEX-IDENTIFIER) 
("if" . :LEX-IF) 
("then" . :LEX-THEN) 
("=" . :LEX-EQUAL) 
(">" . :LEX-GREATER) 
("<>" . :LEX-NOT-EQUAL) 
("%" . :LEX-MOD) 
(#\$ . :LEX-CHARACTER) 
(#\# . :LEX-CHARACTER) 

Որն էլ ցույց է տալիս, որ կառուցված լեքսիկական (նիշային) վերլուծությունը ճիշտ է աշխատում։

Մի քանի հին ֆայլեր

Ծրագրավորման լեզու վերջավոր ավտոմատների համար

Powered by Issuu

Publish for Free

Բեյսիկ լեզվի ինտերպրետատոր

Powered by Issuu

Publish for Free

Գծապատկերների կառուցման լեզու

Powered by Issuu

Publish for Free

Շատ փոքր ծրագրավորման լեզու

Powered by Issuu

Publish for Free

Tcl պրոցեդուրաները

Tcl լեզվում պրոցեդուրները (կամ ֆունկցիաները) սահմանվում են proc հրամանի միջոցով։ Այն ստանում է երեք արգումենտ. ա) սահմանվող պրոցեդուրայի անունը, բ) արգումենտների ցուցակը, և գ) մարմինը։ Օրինակ, տրված x և y թվերից մեծը որոշող ֆունկցիան կարելի է սահմանել հետևյալ կերպ.

proc max { x y } {
    if { $x > $y } then {
        return $x
    }
    return $y
}

Կամ, եթե չենք ուզում օգտագործել if հրամանը.

proc max { x y } {
    return [expr {$x > $y ? $x : $y}]
}

Այս երկու օրինակներում էլ return հրամանն օգտագործված է ֆունկցիայի մարմնից արժեք վերադարձնելու համար։ Tcl պրոցեդուրաները կառուցված են այնպես, որ եթե նրա մարմնում, կամ կատարման որևէ ճյուղում, որը բերում է պրոցեդուրայի ավարտի, բացակայում է return հրամանը, ապա ֆունկցիայի վերադարձրած արժեք է համարվում դրա կատարման ժամանակ վերջին արտահայտության հաշվարկված արժեքը։ Սա հաշվի առնելով, կարող են նախորդ օրինակը գրել առանց return հրամանի.

proc max { x y } {
    expr {$x > $y ? $x : $y}
}

Եթե պրոցեդուրան սպասում է միայն մեկ արգումենտ, ապա սահմանման ժամանակ այդ միակ ֆորմալ արգումենտի անունը կարելի է գրել առանց ձևավոր փակագծերի։ Օրինակ, Սահմանենք մի պրոցեդուրա, որը ստուգում է տրված բառի պալինդրոմ լինելը.

proc palindrom? str {
    string equal $str [string reverse $str]
}

Իսկ եթե արգումենտների ցուցակում վերջին կամ միակ արգումենտի անունը args է, ապա նրա միջոցով, որպես ցուցակ, պրոցեդուրայի մարմնին են փոխանցվում կամայական թվով արժեքներ։ Օրինակ, ահմանենք մի ֆունկցիա, որը հաշվում է երկու և ավելի թվերի թվաբանական միջինը.

proc average { a b args } {
    set sum [expr {$a + $b}]
    foreach n $args {
        set sum [expr {$sum + $n}]
    }
    return [expr {$sum / (2 + [llength $args])}]
}

Ահա նաև այս պրոցեդուրայի օգտագործման մի քանի օրիակ.

average 1.1 2.2                    ; # => 1.6500000000000001
average 1.1 2.2 5.5 4.4 3.3        ; # => 3.3
average 1.2 2.3 3.4                ; # => 2.3000000000000003

proc հրամանը հնարավորություն է տալիս սահմանել նաև լռելությոն (default) արժեքով արգումենտներ ունեցող պրոցեդուրաներ։ Այդ դեպքում արգումենտը տրվում է երկու տարրերի ցուցակի տեսքով, որոնցից առաջինը ֆորմալ արգումենտի անունն է, իսկերկրորդը՝ նրա լռելության արժեքը։ Օրինակ, սահմանենք մի ֆունկցիա, որը վերադարձնում է $y$ թվի $n$ աստիճանի արմատը՝ $\sqrt[n]{y}$, եթե $n$-ը տրված չէ, այն համարվում է $2$։

proc root { y {n 2} } {
    expr exp(log($y) / $n)
}

Ահա կիրառման օրինակներ.

root 1024           ; # => 32.0
root 1024 5         ; # => 4.0
root 1024 10        ; # => 2.0

Scheme պրոցեդուրաները

Scheme ծրագրավորման լեզվում պրոցեդուրաները սահմանվում են lambda ծառայողական բառով, որին հետևում են արգումենտների ցուցակը և պրոցեդուրայի մարմինը կազմող արտահայտությունները։ Օրինակ, կարող եմ սահմանել տրված երկու թվերի քառակուսիների գումարը հաշվող պրոցեդուրա․

(lambda (x y) (+ (* x x) (* y y)))

Սա x և y ֆորմալ արգումենտներով պրոցեդուրա է։ Եթե ուզենամ այն կիրառել 3 կամ 4 արգումենտների նկատմամբ, ապա պետք է գրեմ․

((lambda (x y) (+ (* x x) (* y y))) 3 4)  ; => 25

Այս անհարմար գրառումից խուսափելու համար կարող եմ պրոցեդուրային անուն տալ՝ define ծառայողական բառի օգնությամբ այն կապելով որևէ սիմվոլի հետ.

(define sum-squares
    (lambda (x y) (+ (* x x) (* y y))))

Եվ արդեն կարող եմ պրոցեդուրան արգումենտների նկատմամբ կիրառել sum-squares անունով։

(sum-squares 3 4)  ; => 25

Պրոցեդուրայի սահմանումն ավելի համառոտ կարելի է գրել առանց lambda ծառայողական բառի օգտագործման՝ define սահմանման առաջին արգումենտը դարձնելով ցուցակ, որի առաջին տարրը սահմանվող պրոցեդուրայի անունն է, իսկ հաջորդողները՝ ֆորմալ արգումենտները։ Օրինակ,

(define (sum-squares x y)
    (+ (* x x) (* y y)))

Ես նախնտրում եմ lambda-ի օգտատգործմամբ տարբերակը։ Կարծում եմ, որ դա ավելի համահունչ է define բառի հետ։

Հիմա, ենթադրենք, պետք է սահմանել պրոցեդուրա, որը իրար է գումարում տրված թվերը։ Առաջին միտքն այն է, որ սհամանել մեկ արգումենտով պրեցեդուրա և նրան փոխանցել թվերի ցուցակը։ Օրինակ այսպես.

(define sum-list
    (lambda (l)
        (if (null? l)
            0
            (+ (car l) (sum-list (cdr l))))))

Սա ռեկուրսիվ պրոցեդուրա է, որ 0 է վերադարձնում դատարկ ցուցակի դեպքում, իսկ ոչդատարկ ցուցակների համար ցուցակի առաջին տարրը գումարում է պոչի տարրերի գումարին։ Այս պրոցեդուրան պետք է կիրառել հետևյալ կերպ.

(sum-list '())         ; => 0
(sum-list '(1))        ; => 1
(sum-list '(1 2 3 4))  ; => 10

Բայց ավելի բնական կլիներ, եթե ես կարողանայի գրել այսպիսի արտահայտություններ.

(sum)          ; => 0
(sum 1)        ; => 1
(sum 1 2 3 4)  ; => 10

Այլ կերպ ասած՝ ունենալ պրոցեդուրա, որի արգումենտների քանակը ֆիքսված չէ. դրանք կարող են կա՛մ բացակայել, կա՛մ լինել անորոշ քանակի։

Երբ lambda կառուցվածքի առաջին արգումենտը տրված է որպես ատոմ (այլ ոչ թե որպես ցուցակ), ապա պրոցեդուրայի արգումենտը համարվում է անորոշ քանակի։ Օրինակ, հիշատակված sum պրոցեդուրան, օգտագործելով sum-list պրոցեդուրան, կարելի է սահմանել հետևյալ կերպ.

(define sum
    (lambda nums
        (sum-list nums)))

Երբ այս կերպ սահմանված պրոցեդուրան կիրառվում է արգումենտների նկատմամբ, այդ արգումենտներից կազմվում է ցուցակ և փոխանցվում է պրոցեդուրային։ Բնականաբար, պրոցեդուրայի մարմնում պետք է ֆորմալ արգումետի հետ աշխատել որպես ֆունկցիա։ Օրինակ, եթե sum պրոցեդուրան սահմանելու լինեի առանց sum-list պրոցեդուրայի օգտագործման, ապա պետք է գրեի.

(define sum
    (lambda nums
        (if (null? nums)
            0
            (+ (car nums) (apply sum (cdr nums))))))

apply հրամանն օգտագործված է այն պատճառով, որ sum պրոցեդուրայի ռեկուրսիվ կանչի ժամանակ (cdr nums) ցուցակը նրան փոխանցվելու է որպես նոր ցուցակի միակ տարր։

Բարձր կարգի ֆունկցիաներ և անանուն ֆունկցիաներ

Երկու սերտ հասկացություններ՝ բարձր կարգի ֆունկցիա և անանուն ֆունկցիա, որոնք լայնորեն կիրառվում են ֆունկցիոնալ ծրագրավորման մեջ, որոնց տրամադրած մեխանիզմները հնարավորություն են տալիս կազմակերպել ավելի բնական, ավելի գեղեցիկ, ավելի ընթեռնելի ծրագրեր։

Ֆունկցիան կոչվում է բարձր կարգի, եթե նրա արգումենտներից գոնե մեկը ֆունկցիա է, կամ նրա վերադարձրած արժեքն է ֆունկցիա։

Ես ուզում եմ բարձր կարգի ֆունկցիաները ցուցադրել տրված ֆունկցիայի որոշյալ ինտեգրալի թվային հաշվման օրինակով։ Ենթադրենք պետք է իրականացնել integral ֆունկցիան, որն արգումենտում ստանում է $f(x)$ ինտեգրվող ֆունկցիան և $[a;b]$ ինտեգրման միջակայքը։ $$\mathrm{integral}(f, a, b)=\int\limits_a^b f(x)dx$$ Այս integral ֆունկցիան երկրորդ կարգի է, որովհետև նրա f արգումենտը առաջին կարգի ֆունկցիա է։

Ինտեգրալի թվային հաշվման համար ընտրենք սեղանների մեթոդը, որի դեպքում ինտեգրման միջակայում $f$ ֆունկցիայի գրաֆիկը մոտարկվում է ուղիղ գծով, իսկ ինտեգրալի արժեքը ընդունվում է $(a,0)$, $(a,f(a))$, $(b,f(b))$ և $(0,b)$ գագաթներով սեղանի մակերեսին հավասար։ $$\mathrm{trapezoid}(f, a, b)=(b-a)\frac{f(a)+f(b)}{2}$$ Common Lisp լեզվով այս բանաձևը ծրագրավորվում է հետևյալ կերպ.

(defun trapezoid (f a b)
  (* (- b a) (/ (+ (funcall f a) (funcall f b)) 2.0)))

integral ֆունկցիայի արգումենտում տրված f ֆունկցիա-արգումենտը ֆունկցիայի մարմնում օգտագործված է funcall ֆունկցիայի միջոցով, որը տրված ֆունկկցիա-օբյեկտը կիրառում է տրված արգումենտների նկատմամբ։

C++11 լեզվով նույն integral ֆունկցիան կարելի է գրել հետևյալ կերպ.

double trapezoid( std::function<double(double)> f, double a, double b )
{
  return (b - a) * ((f(a) + f(b)) / 2);
}

Եթե այս ֆունկցիայով հաշվենք, օրինակ $f(x)=x^2$ ֆունկցիայի ինտեգրալը $[-1;1]$ միջակայքում, ապա կստանանք $2$ արժեքը՝ իրական $2/3$-ի փոխարեն։

Պարզ է, որ սեղանների մեթոդը կարող է բավարար ճշտություն ապահովել միայն այն դեպքում, երբ ինտեգրման միջակայքը շատ փոքր է։ Օգտագործելով այդ փաստը, սահմանեմ integral ֆունկցիան, որի $\varepsilon$ արգումենտը ցույց է տալիս ինտեգրման միջակայքի ամենամեծ թույլատրելի չափը։ Այն դեպքում, երբ $b-a\gt\varepsilon$, միջակայքը կկիսեմ երկու հավասար մասերի և իրար կգումարեմ այդ երկու մասերում հաշված ինտեգրալների արժեքները։ Այլ կերպ ասած, ինտեգրալի հաշվման նոր բանաձևն է հետևյալը. $$\mathrm{integral}(f, a, b, \varepsilon)= \left\{ \begin{array}{ll} \mathrm{trapezoid}(f, a, b), & |b - a|\le\varepsilon, \\ \mathrm{integral}(f, a, \frac{a+b}{2}, \varepsilon) + \mathrm{integral}(f, \frac{a+b}{2}, b, \varepsilon), & |b - a|\gt\varepsilon.\\ \end{array} \right.$$ Այս integral ֆունկցիան նույնպես երկրորդ կարգի է, քանի որ նրա արգումենտներում ամենաբարձր կարգը առաջինն է։ integral ֆունկցիայի սահմանումը Common Lisp լեզվով ունի այսպիսի տեսք.

(defun integral (f a b &optional (eps 0.001))
  (if (<= (- b a) eps)
      (trapezoid f a b)
      (let ((m (/ (+ a b) 2)))
        (+ (integral f a m eps) (integral f m b eps)))))

Նույն ֆունկցիան C++11 լեզվով կունենա հետևյալ տեսքը։

using mathfunc = std::function<double(double)>;

double integral( mathfunc f, double a, double b, double eps = 0.001 )
{
  if( b - a <= eps)
    return (b - a) * ((f(a) + f(b)) / 2);

  auto m((a + b) / 2);
  return integral(f, a, m, eps) + integral(f, m, b, eps);
}

Հիմա, ենթադրենք, ուզում եմ հաշվել $f(x)=x^3$ ֆունկցիայի ինտեգրալը $[0;2]$ միջակայքում: Նախ սահմանեմ այդ ֆունկցիան Lisp լեզվով.

(defun f (x) (* x x x))

Ապա integral ֆունկցիայի օգնությամբ հաշվեմ սրա ինտեգրալը տրված միջակայքում.

(integral #'qub 0 2.0)   ; => 4.0

Եթե պետք լինի հաշվել, օրինակ, $f(x)=x^2-3x$ ֆունկցիայի ինտեգրալը, ապա սա նույնպես պետք է սահմանել

(defun f (x) (- (* x x) (* x 3)))

ապա integral ֆունկցիան կիրառել այս f ֆունկցիայի նկատմամբ։ Բայց անանուն ֆունկցիաների մեխանիզմը հնարավորություն է տալիս խուսափել ինտեգրվող ֆունկցիայի առանձին սահմանումից։ Օրինակ, այս վեջին ֆունկցիան $[-2;1]$ միջակայքում ինտեգրելու համար կարելի է գրել.

(integral #'(lambda (x) (- (* x x) (* x 3))) -2 1)

Այստեղ integral ֆունկցիայի կանչի մեջ lambda մակրոսով ստեղծվել է ինտեգրվող ֆունկցիային համապատասխան անանուն ֆունկցիա։
C++11 լեզվում նույնպես կարելի է գրել համարժեք արտահայտություն.

integral([](double x)->double{ return x*x-3*x;}, -2, 1);

որտեղ անանուն ֆունկցիան սահմանված C++11 լեզվի []()->{} կառուցվածքով։

Բայց սեղանների մեթոդը ինտեգրալի հաշվման միակ մեթոդը չէ։ Օրինակ, $f$ ֆունկցիան $[a;b]$ հատվածի վրա կարելի է մոտարկել ոչ թե ուղիղ գծով, այլ պարաբոլով։ Այս մեթոդը կոչվում է Սիմպսոնի մեթոդ և ներկայանում է հետևյալ բանաձևով. $$\mathrm{simpson}(f, a, b)=\frac{b-a}{6}\left(f(a)+4f\Big(\frac{a+b}{2}\Big)+f(b)\right)$$ Եվ ինտեգրալի հաշվման թվային մեթոդը նույնպես կարելի է տալ integral ֆունկցիային որպես արգումենտ։ Այդ դեպքում կստանանք մի նոր, երրորդ կարգի ֆունկցիա. $$\mathrm{integral}(method, f, a, b, \varepsilon)= \left\{ \begin{array}{ll} method(f, a, b), & |b - a|\le\varepsilon, \\ \mathrm{integral}(f, a, \frac{a+b}{2}, \varepsilon) + \mathrm{integral}(f, \frac{a+b}{2}, b, \varepsilon), & |b - a|\gt\varepsilon.\\ \end{array} \right.$$ Ծրագրավորենք այս ֆունկցիան Common Lisp լեզվով.

(defun integral (method f a b &optional (eps 0.001))
  (if (< (- b a) eps)
      (funcall method f a b)
      (let ((m (/ (+ a b) 2)))
        (+ (integral method f a m eps) 
           (integral method f m b eps)))))

Եվ C++11 լեզվով։

using method = std::function<double(mathfunc,double,double)>>;

double integral( method r, mathfunc f, double a, double b, double delta = 0.001 )
{
  if( b - a < delta )
    return r(f, a, b);

  auto m((a + b) / 2);
  return integral(r, f, a, m, delta) + integral(r, f, m, b, delta);
}

Tcl: Թվերի արտահայտումը բառերով

Այս գրառման մեջ Tcl լեզվով իրականացված է 1-ից 999999 միջակայքի բնական թվերի բառային արտահայտման ալգորիթմը։ (Ամբողջական ֆայլը։)

#
# միավորների անունները հայերեն
#
set ONES {"" մեկ երկու երեք չորս հինգ վեց յոթ ութ ինը}

#
# տասնավորների անունները հայերեն
#
set TENS {"" տաս քսան երեսուն քառասուն հիսուն վաթսուն յոթանասուն ութսուն իննսուն}

#
# n-ը պատկանում է [a; b] միջակայքին
#
proc is_in { n a b } { 
  return [expr {($n >= $a) && ($n <= $b)}]
}

#
# վերադարձնում է երկու տարրերի ցուցակ, որոնցից առաջինը
# (ds / dr) քանորդն է, իսկ երկրորդը՝ (ds % dr) մնացորդը
#
proc divr { ds dr } {
  return [list [expr {$ds / $dr}] [expr {$ds % $dr}]]
}

#
# Հիմնական ձևափոխություն
#
proc number_to_words num {
  # եթե թիվը 0-9 միջակայքում է, ...
  if [is_in $num 0 9] {
    # ... ապա վերադարձնել միավորների ցուցակի համապատասխան տարրը
    return [lindex $::ONES $num]
  }

  # եթե թիվը 10-99 միջակայքում է, ...
  if [is_in $num 10 99] {
    # ... ապա առանձնացնել տասնավորի ու միավորի նիշը, ...
    lassign [divr $num 10] a b
    # ... ՛տաս՛-ով սկսվող բառերի համար տասնավորի ու միավորի 
    # միջև պետք է գրել ՛ն՛ տառը, օրինակ, ՛տասներկու՛, ...
    set s [expr {$a == 1 && $b != 0 ? {ն} : {}}]
    # ... վերադարձնել տասնավորների ու միավորների համապատասխան 
    # տարրերից կազմված արտահայտությունը
    return "[lindex $::TENS $a]${s}[lindex $::ONES $b]"
  }

  # եթե թիվը 100-999 միջակայքում է, ...
  if [is_in $num 100 999] {
    # ... ապա առանձնացնել հարյուրավորի նիշը և 100-ի բաժանելու մնացորդը, ...
    lassign [divr $num 100] a b
    # ... միավորների ցուցակից վերցնել հարյուրավորի նիշին համապատախան բառը,
    # նրան կցել ՛հարյուր՛ բառը, իսկ 100-ի բաժանելու մնացորդի վրա նորից կիրառել
    # number_to_words ֆունկցիան
    return "[lindex $::ONES $a] հարյուր [number_to_words $b]"
  }

  # եթե թիվը 1000-999999 միջակայքում է, ...
  if [is_in $num 1000 999999] {
    # ... ապա այն տրոհել երկու կտորի՝ 1000-ին բաժանելու քանորդ և մնացորդ, ...
    lassign [divr $num 1000] a b
    # ... ստացված կտորները ձևափոխել number_to_words ֆունկցիայով, 
    # և իրար կցել՝ արանքում դնելով ՛հազար՛ բառը
    return "[number_to_words $a] հազար [number_to_words $b]"
  }  

  return ""
}

Տեստավորման փորձ։

#
# գեներացնել [0;N) միջակայքի պատահական ամբողջ թիվ
#
proc random N {
  return [expr {int(rand() * $N)}]
}

#
# number_to_words ֆունկցիան փորձարկել 10 պատահական թվերով
#
for {set i 0} {$i < 10} {incr i} {
  set k [random 1000000]
  set v [number_to_words $k]
  puts "$k -- $v"
}

Ֆայլեր։ Pixmap պատկերի խոշորացում

Ենթադրենք տրված է pixmap պատկեր պարունակող պարզեցված ֆայլ և պահանջվում է գրել մի ծրագիր, որը պատկերը կխոշորացնի տրված գործակցով։ Օրինակ, ստորև բերված են հայերեն "Բ" տառի սկզբնական pixmap պատկերը և նրա երկու անգամ խոշորտացված տարբերակը։

...... ..##.. .#..#. .#..#. .#.... .####. .#.... .#.... .#.... ......

............ ............ ....####.... ....####.... ..##....##.. ..##....##.. ..##....##.. ..##....##.. ..##........ ..##........ ..########.. ..########.. ..##........ ..##........ ..##........ ..##........ ..##........ ..##........ ............ ............

Ծրագիրը պետք կարդա ձախ կողմի պատկերը պարունակող ֆայլը և ստեղծի նոր ֆայլ՝ աջ պատկերի պարունակմամբ։

Թող ամբողջ աշխատանքը կատարող պրոցեդուրան կոչվի enlarge, որը ստանում է երկու արգումենտ. պատկերը պարունակող ֆայլի անունը՝ pixmap և խոշորացման գործակիցը՝ sc։

proc enlarge { pixmap {sc 2} } {

Հետո պետք է բացել ֆայլը, նրա պարունակությունը կարդալ որևէ փոփոխականի մեջ, ապա նորից փակել ֆայլը։ Tcl լեզվում ֆայը բացվում է open պրոցեդուրայով, որի առաջին արգումենտը ֆալի անունն է, իսկ երկրորդով որոշվում է, թե ինչ գործողություն է կատարվելու ֆայլի հետ՝ գրել (w), կարդալ (r) և այլն։ open պրոցեդուրան վերադարձնում է ֆայլային հոսք, որից կարելի է կարդալ, կամ նրա մեջ կարելի է գրել։

  set inp [open $pixmap r]

Ֆայլի պարունակությունը ամբողջությամբ կարդում է read պրոցեդուրան։ Այն ստանում է կարդալու համար բացված ֆայլային հոսք և վերադարձնում է հոսքի ամբողջ պարունակությունը։

  set img [read $inp]

Դե, իսկ close պրոցեդուրան փակում է բացված ֆայլային հոսքը։

  close $inp

Պատկերը $n$ անգամ խոշորացնելու համար պետք է նրա ամեն մի կետը հորիզոնական և ուղղահայաց ուղղություններով ընդարձակել $n$ անգամ։ Դրա համար պետք է վերցնել սկզբնական պատկերի ամեն մի տողը և, $n$ անգամ կրկնելով նրա ամեն մի սիմվոլը, ստանալ նոր տող։ ՈՒղղահայաց ընդարձակման համար պետք է $n$ անգամ կրկնել կառուցված տողը։

Արդյունքը կուտակելու համար նախատեսենք result փոփոխականը որպես դատարկ ցուցակ։

  set result [list]

Քանի որ տրված ֆայլի ամբողջ պարունակությունը կարդացվել էր img փոփոխականի մեջ, պետք է այն split պրոցեդուրայով տրոհել տողերի ու իտերացիա կազմակերպել տողերով։ split պրոցեդուրայի երկրորդ արգումենտով տրվում է այն բաժանիչը, ըստ որի պետք է տողը տրոհել ցուցակի։

  foreach line [split $img \n] {

Տողի սիմվոլներով իտերացիայի համար այն կարող ենք սիմվոլների ցուցակի վերածել split պրոցեդուրայով և ցուցակով անցնել foreach պրոցեդուրայով։ Հերթական սիմվոլը դիտարկելիս string repeat հրամանով այն պետք է բազմապատկել պահանջված քանակով ու կցել կառուցվող տողին՝ str փոփոխականին: Իսկ բոլոր սիմվոլներով անցնելուց հետո կառուցված տողին կցենք նոր տողի սիմվոլը։

    set str {}
    foreach char [split $line {}] {
      append str [string repeat $char $sc]
    }
    append str \n

Կառուցված տողը բազմապատկելու համար նորից օգտագործենք string repeat հրաման հրամանը և result ցուցակին կցենք lappend պրոցեդուրայով։

    lappend result [string repeat $str $sc]
  }

Այս դրությամբ արդեն result փոփոխականը պարունակում է նախնական պատկերի խոշորացված տարբերակը։ open հրամանով բացենք ֆայլ գրելու համար։

  set out [open sc$sc$pixmap w]

Այդ ֆայլի մեջ արտածենք կառուցված տողերի ցուցակը՝ դրանք նախապես իրար կցելով join պրոցեդուրայով։

  puts $out [join $result {}]

ՈՒ փակենք ֆայլը։

  close $out
}

Վերջ։ Հիմա կարող ենք կանչել enlarge պրոցեդուրան՝ նրան տալով pixmap ֆայլը և խոշորացման գործակիցը։

---

Ամբողջական պրոցեդուրան։

proc enlarge { pixmap {sc 2} } {
  set inp [open $pixmap r]
  set img [read $inp]
  close $inp

  set result [list]
  foreach line [split $img \n] {
    set str {}
    foreach char [split $line {}] {
      append str [string repeat $char $sc]
    }
    append str \n
    lappend result [string repeat $str $sc]
  }

  set out [open sc$sc$pixmap w]
  puts $out [join $result {}]
  close $out
}