[առաջարկ] արժի՞ մեդեավիկիյով ՏՏ ոլորտի կայք բացել

Ասք BSD֊ում CARP֊ով ծանրաբեռնուածութեան հաւասարակշռող կարգաւորելու մասին

CARP֊ի մասին CARP-ը, նոյն ինքը Common Address Redundancy Protocol-ը, ցանցային արձանագրութիւն է, որը թոյլ է տալիս մի քանի հանգոյց նոյն ցանցում ունենան նոյն ԱյՓին :) CARP-ի գլխաւոր նպատակն է ֆեյլօվերների ժամանակ ապահովել կապը։ ճիշտ կարգաւորումով այն կարող է օգտագործուել որպէս ծանրաբեռնուածութեան հաւասարակշռող (Load Balancer)։ CARP-ը ստեղծուել OpenBSD-ի կողմից է որպէս Ցիսկոյի VRRP-ի ու HSRP-ի ազատ եւ անպատենտ տարբերակ :) Ինչու (Free|Open)BSD֊ի վրայ։ ահաւոր յարմար է, հեշտ, տեղակայումը տեւում է չորս րոպէ ։պ Օկ, հիմա կարգաւորենք։ Այս փորձարկման համար սարքել եմ երկու վիրտուալ մեքենայ, hosta եւ hostb, որտեղ, hosta-ն լինելու է գլխաւոր մեքենան, իսկ hostb-ն լինելու է backup-ը։ օքեյ, հիմա։ CARP-ի համար պէտք են հետեւեալ բաները՝ Մեքենաներ, ամէն մէկն ունենում է իր իրական ԱյՓին (Real IP), եւ բոլորը միասին սպասարկում են Shared IP որն ունի իր Virtual Host ID :)) օկ, նախ կարգաւորենք իրական այփիները, եւ տեսնենք որ մէկը միւսին հասանելի է։ hosta.carp: ifconfig em1 inet 192.168.69.10/24 ապա hostb.carp: ifconfig em1 inet 192.168.69.20/24 եւ իրար պինգենք (։ ահա, հիմա երկուսն էլ իրար հասանելի են։ հիմա արդէն կարգաւորենք VHID-ն եւ shared IP-ն (։ hosta.carp: ifconfig em1 inet vhid advskew 100 pass mypassword alias 192.168.69.50/24 hostb.carp: ifconfig em1 inet vhid advskew 200 pass mypassword alias 192.168.69.50/24 advskew-ն որն աւելի ցածր է, դա աւելի բարձր priority ունի։ ես չուզեցի հրաման աշխատեցնել, նախընտրում եմ սկրիպտ գրել, ահա եւ դա։ յուշում, չմոռանալ միացնել միջուկի մոդուլը՝ kldload carp ահա եւ երկու մեքենաները, ոնց տեսնում էք, մէկը master իսկ միւսը backup :) լաւ, հիմա արդէն փորձարկում անենք։ դրա համար ես կը քաշեմ երկուսի վրայ էլ վեբ սերվեր, ապա ամէն մէկի մէջ գրենք թէ ինքը ով է ։) հիմա, մաաաարդ ես, եթէ HostA-ին ինչ որ բան լինի, (էս դէպքում ես Reboot արեցի) ապա HostB-ն է արդէն պատասխանում :) լաւ, հիմա միքիչ աւելի հետաքրքիր բան։ շատ ժամանակ ուզում ենք մեր միջավայրը փոխել, ասենք Dev վերսիան release անել, բայց երբէք downtime չենք ուզում։ հիմա ունեմ HostDev, որը ունի Dev վերսիան, հիմա դա պէտք է Release անել։ նախ իհարկէ դա կարգաւորում ենք CARP-ով (իհարկէ իր իրական այփին կարգաւորելուց յետոյ)։ ifconfig em1 inet 192.168.69.32/24 ifconfig em1 inet vhid 1 advskew 99 pass mypassword alias 192.168.69.50/25 ապա իրեն դնում ենք MASTER ifconfig em1 vhid 1 state master ու ֆսյո (։ ասանկ բաներ :) աղբիւր՝ Ասք BSD֊ում CARP֊ով ծանրաբեռնուածութեան հաւասարակշռող կարգաւորելու մասին | Ազատութիւն Ամենեցուն

Ասք Բաշով Սոքեթ Ծրագրաւորման Մասին

Արդէն քանի ամիս է Սերթում եմ աշխատում, իրականում կէս տարի է արդէն, երեւի աւելի, ինչեւէ։ չնայած, ինչքանով որ հասկացայ, Հայաստանում ադմինների մեծ մասը պատրաստի թուլեր են օգտագործում, շատ քչերն են ձեռով սկրիպտներ գրում, անգամ ծրագրեր, բայց դէ նորմալ ա, ինչ որ լուրջ պահանջ էլ չկայ, բացի եթէ մեծ ընկերութեան մէջ ես աշխատում։ բայց մեծ ընկերութիւններում էլ եթէ ծրագիր գրել պէտք լինի ադմինի համար, հաւանաբար ծրագրաւորող կը լինի։ Սերթում տենց չի, չգիտեմ լաւ է թէ չէ, բայց միայն ես եմ տեխնիկական գործեր անում (իրար վրայ երկու հոգի ենք թիմում), ու ամէն ինչ պէտք է ես անեմ։ չգիտեմ ոնց եղաւ, բայց ինձ պէտք էր, որ socket ծրագրաւորում անեմ, ինչ որ ռաութերների հետ շփուելու, ու հասկանալու թէ ոնց ա վիճակը Հայաստանում (վերջում պարզուեց որ վատ ա)։ Ադմիններին հենց ասում ես սոքեթ ծրագրաւորում, առաջին բանը որ ասում ենք դա netcat-ն է, որն ի դէպ շատ լաւն է։ մարդիկ էլ ովքեր ծրագրաւորում գիտեն, նախընտրում են իհարկէ արագի մէջ փայթնի սոքեթով անել։ շատ քիչ մարդիկ սիրում են նաեւ էկզոտիկ լեզուներով անել (օրինակ ոնց կ'անէինք ես ու նորայրը)։ Ինչեւէ, netcat-ը ինձ հերիքում էր, Պասկալն էլ չասեմ։ բայց ես մի քանի սարք ունեմ, որոնց վրայ չկայ netcat, իսկ ես ուզում էի ծրագիրս ամէն տեղ աշխատի, բա ի՞նչ անեմ։ (* չնայած ամէն տեղ voc ունեմ, բայց աւաղ, այդքան լաւ չեմ կարողանում դեռ ծրագրաւորել Օբերոնով, որ մի անգամից պէտք եղածն անեմ *) օրերն անցան, խնդիրը մնաց։ Մի օր աւտօբուսում նստած կպել էի սերւերիս ու մանուալներ էի կարդում, ինչ որ բաշ սկրիպտ էի գրում, որ խնդիր կար, մէկ էլ սենց հաւէս բան տեսայ՝ առաջին պահին ուրախացայ, երկրորդ պահին, ըստ սովորութեան, որոշեցի սորսերը կարդալ ։Ճ ահա եւ գտայ՝ redir.c հաւէ՜ս, ես ամէն տեղ բաշ ունեմ, նոյնիսկ այնտեղ որ չպէտք է լինի, քանի որ ash-ով է գալիս ։Ճ լաւ, հիմա փորձենք, պայմանս շատ պարզ էր, մի տեղից պէտք է լսեմ, միւս տեղից պէտք է բաշով ուղարկեմ եւ ստանամ (։ ահա եւ վիդեոն՝ ու տենց (։ աղբիւրը՝ աստեղէն

FreeNAS – Բաց կոդով ցանցային պահոց (տեղադրում)

FreeNAS-ը հանդիսանում է բաց կոդով ինձ հանդիպած ցանցային պահոցներից ամենաստաբիլը։ FreeNAS-ը կարելի է տեղադրել կոշտ սկավառակի, կամ այլ հիշողության սարքերի վրա, նույնիսկ խորհուրդ է տրվում տեղադրել USB ֆլեշի վրա, ընդ որում FreeNAS-ը զբաղեցնելու է տվյալ կրիչի ամբողջ ծավալը, կարևոր չի կտեղադրեք 4GB USB ֆլեշ թե 500GB կոշտ սկավառակ։ Այնպես որ ֆինանսապես նպատակահարմար է օգտագործել USB ֆլեշ։ Գրառմանս ընթացքում կնկարագրեմ FreeNAS-ի տեղադրման գործընթացը։ Գրառումս անելու պահին վերջին տարբերակը հանդիսացել է 9.3-ը։Եւ այսպես առաջին իսկ քայլով մտնում են բեռնումների էջը և քաշում ենք վերջին ստաբիլ տարբերակը և քաշած *.iso ֆայլը գրում ենք CD-ի վրա։Բեռնվելով CD-ից կբացվի հետևյալ գործողությունների ցանկը՝ Որից հետո կտեսնենք՝ Ընտրելով առաջին տարբերակը կհաստատենք FreeNAS-ի տեղադրումը մեր համակարգի վրա։ Այնուհետև ընտրում ենք կրիչը որի վրա պետք է տեղադրվի FreeNAS-ը Պատասխանում ենք [Yes] որով համաձայնվում ենք մաքրել տվյալները տվյալ կրիչի վրայից։ ..և շնորհավորում եմ, սկզբնական տեղադրումը ավարտված է Սեղմելով [OK] համակարգիչը (սերվերը) կվերսկսի (ռեստարտ)։ Սկզնբաղբյուր

Երեք պատահական խնդիր

Արտահայտության հապավում

Խնդիրը։ Տրված է ինչ-որ արտահայտություն, օրինակ, «Միացյալ ազգերի կազմակերպություն» և պահանջվում է սրանից ստանալ «ՄԱԿ» հապավումը։ Դպրոցականը կամ ուսանողը, հավանաբար, առաջին լուծումը կտանի այսպես. տողը դարձնել ցուցակ, հետո անցնել տողի վրայով ու հավաքել բոլոր այն տառերը, որոնց նախորդում են տառ չհանդիսացող այլ սիմվոլներ։ Հետո՝ հավաքած տառերը դարձնել մեծատառ ու միավորել մեկ տողի մեջ։ Տողից նիշերի ցուցակ ստացվում է coerce ֆունկցիայով.

(coerce "abcd" 'list)    ; => (#\a #\b #\c #\d)

Նույն coerce ֆունկցիայով նիշերի ցուցակից ստացվում է տող.

(coerce '(#\a #\b #\c #\d) 'string)    ; => "abcd"

Նիշերի ցուցակից բառերի առաջին տառերն ընտրող ֆունկցիան կարելի է գրել ռեկուրսիվ եղանակով։

(defun select-first-letters (sl)
    (if (endp sl)
        '()
        (if (and (not (alpha-char-p (car sl))) (alpha-char-p (cadr sl)))
            (cons (cadr sl) (select-first-letters (cddr sl)))
            (select-first-letters (cdr sl)))))

Դե իսկ հապավում կառուցող ֆունկցիան արդեն կարելի է կառուցել այսպես․

(defun acronym-of (s)
    (string-upcase (coerce (select-first-letters (coerce s 'list)) 'string)))

Բայց այս ֆունկցիան ճիշտ չի աշխատելու, որովհետև տողի առաջին տառը, որը պետք է լինի հապավման առաջին տառը, չի բավարարում select-first-letters ֆունկցիայի 4֊րդ տողում գրված պայմանին։ Այդ թերությունը շտկելու համար պետք է պարզապես տողը նիշերի ցուցակ դարձնելուց հետո դրա սկզբից կցել մի որևէ նիշ։ Այսինքն acronym-of ֆունկցիան սահմանել հետևյալ կերպ․

(defun acronym-of (s)
    (string-upcase (coerce (select-first-letters (cons #\Space (coerce s 'list)) 'string))))

Սրա հետևանքով select-first-letters ֆունկցիայի երկրերդ տողում գրված պայմանը կձևափոխվի․

(defun select-first-letters (sl)
    (if (or (endp sl) (endp (cdr sl)))
        '()
        (if (and (not (alpha-char-p (car sl))) (alpha-char-p (cadr sl)))
            (cons (cadr sl) (select-first-letters (cddr sl)))
            (select-first-letters (cdr sl)))))

* * *

Փորձառու ծրագրավորողն այսպիսի բան, իհարկե, չի գրի։ Նա միանգամից կնկատի, որ արտահայտության հապավումը կառուցելու համար բավական է մեծատառ դարձնել բառերի միայն առաջին տառերը, իսկ մնացածները թողնել փոքրատառ։ Հետո դեն գցել ամեն ինչ՝ բացի մեծատառերից։

(defun acronym (text)
    (remove-if-not #'upper-case-p (string-capitalize text)))

Սա Արդեն ֆունկցիոնալ լուծում է։ string-capitalize ֆունկցիան վերադարձնում է տողը՝ որում բառերի միայն առաջին տառերն են մեծատառ։ remove-if-not ֆունկցիան ֆիլտրող ֆունկցիա է. այն իր երկրորդ արգումենտում տրված հաջորդականությունից դեն է գցում իր առաջին արգումենտում տրված պրեդիկատին չբավարարող տարրերը։

* * *

Տիպիկ C-ական լուծումն էլ այսպիսին կլինի.

void acronym(const char *text, char *acr)
{
    *acr++ = toupper(*text++);
    while( *text != '\0' ) {
        if( isalpha(*text) && !isalpha(*(text-1)) )
            *acr++ = toupper(*text);
        ++text;
    }
    *acr = '\0';
}

 

Բառերի հեմինգյան հեռավորություն

Խնդիրը։ Երկու նույն երկորությունն ունեցող բառերի հեմինգյան հեռավորություն է կոչվում դրանց նույն դիրքերում տարբերվող տառերի քանակը։ Օրինակ, abc և abc բառերի հեմինգյան հեռավորությունը զրո է, իսկ abc և aec բառերի հեմինգյան հեռավորությունը մեկ է, և այլն։ Իտերատիվ լուծումը կարող է լինել loop մակրոսի օգտագործմամբ։ Երկու զուգահեռ հաշվիչներ անցնում են տողերի վրայով և համեմատում են նույն դիրքում գտնվող տառերը։ Եթե դրանք տարբեր են, ապա հաշվարկման արդյունքին գումարվում է մեկ։

(defun hamming-distance (so si)
    (loop for x across so
          for y across si
          when (char-not-equal x y)
          sum 1))

Ֆունկցիոնալ լուծման առաջին մոտարկումը կարող է լինել այսպես. map ֆունկցիայով տրված բառերից կառուցվում է մի ցուցակ, որի i-րդ դիրքում գրված է 0` եթե բառերի i-րդ դիրքերի տառերը հավասար են, և 1՝ հակառակ դեպքում։ Այնուհետև apply ֆունկցիայով + գործողությունը կիրառվում է այդ ցուցակի նկատմամբ՝ վերադարձնելով տարբերվող տառերի քանակը։

(defun hamming-distance (so si)
    (apply #'+ (map 'list #'(lambda (x y) (if (char-equal x y) 0 1))
           so si)))

Վերջնական ֆունկցիոնալ լուծումն ավելի լավն է. նույն map ֆունկցիայով ստեղծվում է char-not-equal ֆունկցիայի արդյունքների ցուցակ՝ կազմված t-երից և nil-երից։ Իսկ հետո count ֆունցիայով հաշվվում է t-երի քանակը, որն էլ հենց տրված բառերի հեմինգյան հեռավորությունն է։

(defun hamming-distance (so si)
    (count t (map 'list #'char-not-equal so si)))

* * *

C-ական իրականացումը պարզապես հաշվում է բառերի նույն դիրքում տարբերվող տառերի քանակը.

unsigned int hamming_distance(const char *so, const char *si)
{
    unsigned int dist = 0;
    while( *so != '\0' && *si != '\0' )
        if( *so++ != *si++ )
            ++dist;
            
    return dist;
}

 

Ենթացուցակի ստուգում

Խնդիրը։ Ստուգել, թե արդյոք s₀ ցուցակը s₁ ցուցակի ենթացուցակն է։ Օրինակ, [3, 4, 5] ցուցակը [1, 2, 3, 4, 5, 6] ցուցակի ենթացուցակ է։ Միանգամից «ֆունկցիոնալ» լուծումը. s₀-ն s₁-ի ենթացուցակ է, եթե կա՛մ s₀-ն համընկնում է s₁-ի սկիզբի հետ՝ նրա պրեֆիքսն է, կա՛մ s₀-ն s₁-ի պոչի ենթացուցակն է։ Common Lisp լեզվով գրառումը.

(defun is-sublist (so si)
    (or (is-prefix so si)
        (is-sublist so (cdr si))))

is-prefix ֆունկցիայի իրականացումն էլ շատ հետաքրքիր է.

(defun is-prefix (so si)
    (not (member nil (mapcar #'eq so si))))

mapcar ֆունկցիայով կառուցվում է երկու ցուցակների համապատասխան տարրերի՝ իրար հավասար լինելու (կամ չլինելու) ցուցակը։ member ֆունկցիայով այդ ցուցակում որոնվում է որևէ nil արժեք, իսկ not ֆունկցիայով էլ պահանջվում է, որ nil չլինի։ C լեզվով պրեֆիքսի և ենթացուցակի ստուգման ֆունկցիաները կունենան հետևյալ ոչ պակաս հետաքրքիր տեսքը. Եթե, օրինակ, ցուցակի հանգույցը սահմանված է այսպես.

struct node {
    char data;
    struct node *next; 
};

ապա s ցուցակի՝ l ցուցակի պրեֆիքս լինելը կաստուգվի այսպես.

bool is_prefix(const struct node *s, const struct node *l)
{
    while( NULL != s && NULL != l && s->data == l->data ) {
        s = s->next;
        l = l->next;
    }
    
    return NULL == s;
}

իսկ s ցուցակի՝ l ցուցակի ենթացուցակ լինելն էլ այսպես.

bool is_sublist(const struct node *s, const struct node *l)
{
    if( NULL == s )
        return true;

    if( NULL == l )
        return false;

    return is_prefix(s, l) || is_sublist(s, l->next);
}

Կոտրում ենք quadcopter֊ի ip camera-ն reverse engineering -ի մեթոդներով

Դրոնների թեման ինձ վաղուց էր հետաքրքրում ու քանի որ կային մի շարք մտքեր կապված դրանց հետ, որոշեցի վերջապես սկսել ինչ֊որ բան անել։ Գնեցի Overmax X-Bee drone 5.2, որը կարելի է կառավարել ինչպես rc֊ով, այնպես էլ android application-ով։ Բայց դա այն չէր ինչն ինձ պետք էր, իսկ ինձ պետք էր ստանալ video stream֊ն այնպես, որպեսզի հետագայում հնարավոր լիներ այն մշակել. ո՛չ rc -ն և ո՛չ էլ android application֊ը նման հնարավորություն չեն տալիս։     Առաջինը ինչից սկսեցի, դա արտադրողի դոկումենտացիայի ուսումնասիրությունն էր, բայց այնտեղից ոչ մի օգտակար բան չհաջողվեց պարզել․ այնտեղ տեխնիկական իրականացման վերաբերյալ ոչ մի ինֆորմացիա չկար ու պարզ չէր, թե ինչ պետք էր անել։ Մի լավ խոսք կա, ասում է "when in doubt, go old school", կոնկրետ էս դեպքում դա նշանակում է reverse engineering: Պատկերավոր ասած, reverse engineering ֊ն այն է, երբ ունես սև արկղ և պետք է պարզես թե դրա ներսում ինչ կա, այսինքն եթե ինչ֊որ բան արտադրելիս առանձին դետալները կոնկրետ մեթոդներով և տեխնոլոգիաներով միացնում են իրար և ստանում են վերջնական արտադրանք, ապա այս դեպքում, պետք է վերջնական արտադրանքից ստանալ առանձին դետալները, մեթոդներն ու տեխնոլոգիաները։ Այս փուլում մեր խնդիրն է պարզել հնարավորինս շատ ինֆորմացիա, այսպես ասած գծել տեղանքի նախնական քարտեզն ու պարզել ուժերի բաշխվածությունը :D Դրա համար play market-ից քաշեցի drone֊ի LS_Model_v1.6_apkpure.com.apk ֆայլն ու decompile արեցի այն։ Դրա համար պետք  է․

1. cd /home
2. mkdir LS_Model_v1.6
3. unzip LS_Model_v1.6_apkpure.com.apk -d LS_Model_v1.6
4. cd LS_Model_v1.6
5. ~vardan/rev_eng/dex2jar-2.0/d2j-dex2jar.sh classes.dex

Էս հրամանից հետո ստանում ենք classes-dex2jar.jar ֆայլը, որն անհրաժեշտ է բացել jd-gui ծրագրով source֊երը տեսնելու համար։

sudo ~vardan/rev_eng/jd-gui-0.3.5.linux.i686\ \(1\)/jd-gui classes-dex2jar.jar 

Տեսնում ենք, որ source֊երում ոչ մի հետաքրքիր բան էլ չկա և պարզ է դառնում, որ պետք է այդ ինֆորմացիան փնտրել *.so ֆայլերի մեջ։ Դրա համար տեսնենք, թե ինչ ինֆորմատիվ տողեր կան դրանցում։ Դա կանենք հետևյալ հրամանով։

strings lib/armeabi/libmain.so > str 

Առաջին հերթին այսեղից մեզ հետաքրքրում է ip ֊ն, պորտի համարը և թե ինչ կոդեկ է օգտագործվում video streaming֊ի համար։ ip գտնելու համար grep ենք անում.

grep -o '[0-9]\{1,3\}\.[0-9]\{1,3\}\.[0-9]\{1,3\}\.[0-9]\{1,3\}' str

և տեսնում ենք 172.16.10.1 ինչն էլ ամենայն հավանականությամբ drone ֊ի ստատիկ ip֊ն է։ Քանի֊որ video streaming֊ի համար առավել հաճախ օգտագործվում է h264 կոդեկը, ապա str ֊ի մեջ grep-ով փնտրում ենք h264 բառ պարունակող տողեր

grep "h264" str 

և տեսնում ենք, որ այդպիսի տողեր շատ կան, դա նշանակում է, որ մեծ հավանականությամբ հենց h264 ֊ն էլ օգտագործվում է։ Ինչպես տեսնում ենք մեր բախտը շատ բերեց․ հաջողվեց hard code տողեր գտնել, քանզի հակառակ դեպքում ստիպված էինք լինելու disassembly անել *․so֊ները, այնպես չէ որ չէինք կարող, ուղղակի դա ամենահաճելի զբաղմունքը չէր լինի։ Հիմա, ինչպես տեսանք մեզ հաջողվեց գտնել (այս փուլում ուղղակի համարենք) ip֊ն և codec֊ի տեսակը․ մեզ մնաց պարզել մեր device֊ի վրա եղած open port֊երը, դրա համար գործի մեջ ենք դնում իմ ամենասիրած tool֊երից մեկը nmap֊ը։

nmap -p 0-10000 172.16.10.1

Սյստեղ սկանավորում ենք 172.16.10.1 ip֊ի 0-10000 սահմանում open port֊երը և տեսնում ենք, որ 8888 պորտը բաց է։ Շատ լավ, հիմա նաև ունենք նաև port number֊ը: Փորձենք telnet֊ով կպնել դրոնին, եթե հաջողվեց, ապա կկարողանանք remote հրամաներ կատարել և էլ ավելի շատ ինֆորմացիա հավաքել սարքի վերաբերյալ

telnet 176.16.10.1 8888

Տերմինալը մնում է կախված վիճակում, նույնն է նաև ssh֊ի դեպքում։ Սա նշանակում է, որ մենք չենք կարող անմիջապես սարքի վրա հրամաններ կատարել և պետք է wifi ցանցի միջոցով մտնել կոմունիկացիայի մեջ։ Այս պահին մենք գիտենք դրոնի ip֊ն, port number֊ը և video streaming֊ի codec֊ը։ Սարքը իր application֊ի հետ խոսում է wifi֊ի միջոցով և պետք է պարզել, արդո՞ք փոխանցվող ինֆորմացիան encrypt֊արվում է, թ՞ե ոչ։ Եթե encrypt է արվում, ապա ամենայն հավանականությամբ դա wep/wpa֊ով է արվում, որը կարող ենք կոտրել, ուղղակի լավ կլինի որ ստիպված չլինենք դա անել :D : Դրա համար նախ ստանում ենք մեր wifi ընդունիչի անունը։

iwconfig

Հիմա անհրաժեշտ է այն switch անել monitor mode-ի, դա կանենք Aircrack-ng ծրագրային փաթեթի airodump tool֊ի միջոցով

airmon-ng start wlx30b5c2125754

Դրանից հետո նորից ենք անում՝

iwconfig

և ստանում ենք Հիմա airodump-ng tool֊ով պարզում ենք՝ արդյո՞ք տվյալները encrypt եղած են փոխանցվում։

sudo airodump-ng mon0

Նկարից տեսնում ենք, որ տվյալները կոդավորված չեն (ENC ֊ի տակ գրված է OPN, այսինքն open), դա մեզ ազատում է ավելորդ գլխացավանքից։ Բայց հիմա մի ուրիշ խնդիր ունենք․ պետք է պարզել ինչ protocol֊ով են տվյալները փոխանցվում tcp թե udp?: Դրա համար մեզ պետք է sniff անել դրոնի և android application֊ի կոմունիկացիան։ Դրա համար մեզ պետք կգա root արված android os ֊ով հեռախոս, որի վրա տեղադրված են busybox ֊ն ու android terminal emulator֊ը։ Հեռախոսը root անելու, busybox և android terminal emulator install անելու վերաբերյալ 10T ինֆորմացիա կարելի է գտնել համացանցից :) Միացնում ենք drone֊ը, android application֊ը (այնպես, որ հեռախոսի էկրանին տեսնենք դրոնի տեսախցիկից ուղարկված վիդեոն) և android terminal emulator֊ում կատարում ենք հետևյալ հրմանաը

tcpdump -vv -s 0 -w /sdcard/tcap.cap 

Սպասում ենք 3-4 րոպե և ընդհատում ենք tcpdump֊ը volume down & c ֊ով։ Հիմա դրոնի և application֊ի միջև ողջ կոմունիկացիան raw ձևով ունենք tcap.cap ֆայլում, մնում է դրանից բան հասկանալ ։) Այդ tcap․cap ֆայլը բացելու համար խաղի մեջ ենք մտցնում մեր ծանր հրետանին՝ Wireshark֊ը։ Բացում ենք Wireshark -ը

sudo wireshark

Տալիս ենք File->Open և ընտրում ենք մեր tcap.cap ֆայլը։ Այս նկարից տեսնում ենք, որ application֊ը դրոնի հետ կոմունիկացիայի մեջ է մտնում 4 անգամ՝ տարբեր պորտերով.

Source ip,         source port      packet type   direction       destination ip,   destination port

172.16.72.109      53383              SYN             ->          172.16.10.1       8888                
172.16.72.109      53383              SYN, ACK        <-          172.16.10.1       8888
172.16.72.109      53383              ACK             ->          172.16.10.1       8888
172.16.72.109      53383              PSH, ACK        ->          172.16.10.1       8888
172.16.72.109      53383              PSH, ACK        <-          172.16.10.1       8888
172.16.72.109      53383              ACK             ->          172.16.10.1       8888

Source ip,         source port      packet type   direction       destination ip,   destination port

172.16.72.109      39159              SYN             ->          172.16.10.1       8888                
172.16.72.109      39159              SYN, ACK        <-          172.16.10.1       8888
172.16.72.109      39159              ACK             ->          172.16.10.1       8888
172.16.72.109      39159              PSH, ACK        ->          172.16.10.1       8888
172.16.72.109      39159              PSH, ACK        <-          172.16.10.1       8888
172.16.72.109      39159              ACK             ->          172.16.10.1       8888

Source ip,         source port      packet type   direction       destination ip,   destination port

172.16.72.109      59472              SYN             ->          172.16.10.1       8888                
172.16.72.109      59472              SYN, ACK        <-          172.16.10.1       8888
172.16.72.109      59472              ACK             ->          172.16.10.1       8888
172.16.72.109      59472              PSH, ACK        ->          172.16.10.1       8888
172.16.72.109      59472              PSH, ACK        <-          172.16.10.1       8888
172.16.72.109      59472              ACK             ->          172.16.10.1       8888

Source ip,         source port      packet type   direction       destination ip,   destination port

172.16.72.109      41942              SYN             ->          172.16.10.1       8888                
172.16.72.109      41942              SYN, ACK        <-          172.16.10.1       8888
172.16.72.109      41942              ACK             ->          172.16.10.1       8888
172.16.72.109      41942              PSH, ACK        ->          172.16.10.1       8888
172.16.72.109      41942              PSH, ACK        <-          172.16.10.1       8888
172.16.72.109      41942              ACK             ->          172.16.10.1       8888

ի՞նչ է այստեղ տեղի ունենում։ Սա TCP 3-way handshaking֊ն է։ Սկզբում մեր android application֊ը (կլիենտ) ուղարկում է կոմունիկացիայի հաստատման SYN packet դրոնին (սերվեր), որին սերվերը պատասխանում է SYN, ACK packet֊ով, հետո կլինետը ACK packet֊ով տեղեկացնում է սերվերին, որ ստացել է դրա կողմից ուղարկված պատասխանը։ Դրանից հետո կլիենտը PSH, ACK packet֊ով ուղարկում է ինչ֊որ data, սերվերը պատասխանում է PSH, ACK packet-ով և դրան ի պատասխան կլիենտը ուղարկում է ACK packet֊ը։ Եվ նույնը արվում է մնացած բոլոր 3 կոմունիկացիաներում էլ։ Այստեղ մնացածից բացի կան նաև երկու շատ կարևոր թվեր․ դրանք ենք seq (sequence number) և ack (acknowledgment number)։ Երբ կլիենտը SYN packet֊ով initiate֊է անում կոմունիկացիա սերվերի հետ, այն (կլիենտը) գեներացնում է seq = 0 և ack = 0 թվերը (իրականում դրանք պատահական գեներացված թվեր են, որոնք սկզբում պայմանականորեն համարում ենք 0)։ Սերվերը դրան պատասխանում է SYN, ACK packet֊ով, որտեղ seq ֊ը նույնպես 0 ֊է (պայմանական 0, իրականում 0 ֊ 4,294,967,295 միջակայքից պատահական թիվ), իսկ ահա ack֊ն հավասար է նախորդ packet֊ի seq + 1 (կլիենտից սերվերին ուղարկված packet֊ի մասին է խոսքը)։ Դրանից հետո կլիենտը սերվերին է ուղարկում ACK packet֊ը, որտեղ seq -ը հավասար է նախորդ packet֊ի ack֊ին, իսկ ack֊ն հավասար է packet֊ի seq + 1: Դրանից հետո նորից է կլիենտը PSH, ACK packet ուղարկում սերվերին, բայց այս անգամ այն ունի payload, այսինքն օգտակար, ինֆորմատիվ տվյալներ, այս դեպքում seq֊ն ու ack֊ն համապատասխանաբար հավասար են նախորդ packet ֊ի համապատասխան թվերին (նախորդ packet ֊ում նույնպես կլիենտն էր սերվերին packet ուղարկել)։ Սրան սերվերը պատասխանում է PSH, ACK packet֊ով, որտեղ seq֊ը հավասար է նախորդ packet֊ի (կլիենտից սերվերին ուղարկված packet-ի) ack-ին, իսկ ack֊ն հավասար է նախորդ packet ֊ի seq + length of payload data և այսպես շարունակ։ Այսինքն սա միջոց է հանդիսանում կլիենտի և սերվերի միջև համոզվելու, որ ոչ մի ուղարկված packet չի կորել ճանապարհին։ Փաստորեն տեսնում ենք, որ video streaming֊ը initiate է արվում 4 հատ կոմունիկացիաների միջոցով, որոնցում app֊ն ու drone֊ը փոխանակվում են ինչ֊որ data֊ով, այստեղ data ասելով պետք է հասկանալ PSH,ACK packet֊ներով փոխանակումը, քանի որ մնացած SYN, SYN ACK և ACK packet֊ները ընդամենը սինխրոնիզացիայի համար են։ Այսինքն հերիք է մեզ պարզել, թե դրանք ինչ data֊ներ են, բացել 4 հատ socket և վերջ :) Բացում ենք wireshark֊ը, open tcap.cap file, նշում ենք application֊ից դրոն գնացող 160 երկարությամբ packet֊ը, ներքևի պատուհանում քլիք ենք անում data ֊ի վրա, հիմա աջ քլիք և ընտրում ենք "Show Packet Bytes ..." Բացված պատուհանի ներքևի "Shown as" դաշտում ընտրում ենք "raw" և copy ենք անում data֊ն (նշված է նկարում կապույտով) և այդպես բոլոր 4 կոմունիկացիաների համար։ Սկզբնական pin-աչի (փորձարարական) կոդեր գրելու համար բավական է python ֊ը :D

import pdb
import select
import socket
import sys

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM, 0)
s1 = socket.socket(socket.AF_INET, socket.SOCK_STREAM, 0)
s2 = socket.socket(socket.AF_INET, socket.SOCK_STREAM, 0)
s3 = socket.socket(socket.AF_INET, socket.SOCK_STREAM, 0)
s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
s1.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
s2.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
s3.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)

s.connect(('172.16.10.1', 8888))
s1.connect(('172.16.10.1', 8888))
s2.connect(('172.16.10.1', 8888))
s3.connect(('172.16.10.1', 8888))
socks = [s, s1, s2, s3]

magic_word='4954640000005200000005a7a90fb36ecd3fa2ca7ec48ca36004acef63f77157ab2f53e3f768ecd9e18547b8c22e21d01bfb6b3de325a27b8fb3acef63f77157ab2f53e3f768ecd9e185b7330fb7c95782fc3d67e7c3a66728dad8b59848c7670c94b29b54d2379e2e7a'.decode('hex')

magic_word1 = "495464000000520000007298c0389bc372a71a174bd1b514b3adacef63f77157ab2f53e3f768ecd9e18547b8c22e21d01bfb6b3de325a27b8fb3acef63f77157ab2f53e3f768ecd9e185b7330fb7c95782fc3d67e7c3a66728dad8b59848c7670c94b29b54d2379e2e7a".decode('hex')

magic_word2 = "4954640000005200000021e0c477c77394e85d66a98c2c922cc5acef63f77157ab2f53e3f768ecd9e18547b8c22e21d01bfb6b3de325a27b8fb3acef63f77157ab2f53e3f768ecd9e185b7330fb7c95782fc3d67e7c3a66728dad8b59848c7670c94b29b54d2379e2e7a".decode('hex')

magic_word3 = "495464000000580000009bf89049c926884d4f922b3b33ba7eceacef63f77157ab2f53e3f768ecd9e18547b8c22e21d01bfb6b3de325a27b8fb3acef63f77157ab2f53e3f768ecd9e185eb20be383aab05a8c2a71f2c906d93f72a85e7356effe1b8f5af097f9147f87e".decode('hex')

s.send(magic_word)
data = s.recv(106) 
sys.stdout.write(data)

s1.send(magic_word1)
data = s1.recv(300) 
sys.stdout.write(data)


s2.send(magic_word2)
data = s2.recv(300) 
sys.stdout.write(data)


s3.send(magic_word3)
sys.stdout.write(data)

try:
   while True:
      data = s3.recv(300) 
      sys.stdout.write(data)
except KeyboardInterrupt:
   s.close()
   s1.close()
   s2.close()
   s3.close()
sys.exit(0)

Կոդը թողարկում ենք հետևյալ կերպ․

sudo python get_stream.py > video_stream.raw

Արդյունքում ստանում ենք video_stream.raw վիդեո file֊ը, որը կարող ենք բացել ffplay ֊ով․

ffplay -f h264 video_stream.raw

Մնում է կատարել վերջին քայլը․ կոդերը պորտ անել C++ (հետագայում պետք է, որ կոդը շատ ավելի արագ աշխատի), գտնել real-time play անելու միջոց։ Ինչպես տեսնում ենք h264 codec֊ի հարցում չէինք սխալվել։ Իսկ դրսում մութ էր և համարյա ոչինչ չէր երևում, բայց կարևորն ամենևին էլ դա չէր :)[video width="720" height="576" mp4="http://hy-it.org/wp-content/uploads/2017/04/video_stream.mp4"][/video]

Yacc֊ի և Lex֊ի մասին

• Ովքե՞ր են այդ Yacc֊ն ու Lex֊ը
• Ի՞նչ է լեզվի քերականությունը
• Լեզվի սահմանում
• GNU Bison֊ի ֆայլը
• Քերականության ստուգումը Bison֊ի միջոցով
• Բառային վերլուծություն Flex֊ի միջոցով
• Գործարկման առաջին փորձ
• Թեսթավորում․ առաջին մաս
• Արվածի ամփոփում և հետագա քայլերի մշակում
• Աբստրակտ քերականական ծառ
• Bison նկարագրության ընդլայնում
• Գործարկման երկրորդ փորձ

Ես պատմում եմ ծրագրավորման լեզվի շարահյուսական վերլուծիչի իրականացման մասին։ Պատմությունս հնարավորին պարզ պահելու համար ցույց կտամ, թե ինչպես, օրինակ, պարզեցված Բեյսիկ (BASIC) լեզվով գրված ծրագիրը թարգմանել JSON լեզվով գրված ծրագրի։ Բեյսիկն ընտրել եմ իր հայտնիության ու քերականության պարզության համար։ JSON-ն ընտրել եմ ներկայացման պարզության համար, և ծրագրի հիերարխիկ (ծառաձև) կառուցվածքն ուղղակիորեն արտացոլելու համար։ Այս գրառման մեջ օգտագործված կոդն ու օրինակները իմ GitHub էջում են։

Ովքե՞ր են այդ Yacc֊ն ու Lex֊ը

Yacc֊ը, որ այժմ ավելի հայտնի է GNU Bison իրականացմամբ, շարահյուսական վերլուծիչների գեներատոր է։ Այն հնարավորություն է տալիս դեկլարատիվ լեզվով սահմանել լեզվի շարահյուսական վերլուծիչը, ամեն մի քերականական կանոնի համար սահմանել համապատասխան գործողություններ, նկարագրել հնարավոր շարահյուսական սխալները և այլն։ Yacc֊ը նկարագրությունից գեներացնում է C (կամ մի ուրիշ՝ Go, SML և այլ) լեզվով գրված արդյունավետ ծրագիր։ Գեներացված ծրագիրն արդեն կոմպիլյացվում և կապակցվում (link) է լեզվի իրականացման հիմնական կոդի հետ։ Lex֊ը, որ այժմ հայտնի է GNU Flex իրականացմամբ, նախատեսված է բառային վերլուծիչի գներացման համար։ Սրա համար նույնպես դեկլարատիվվ լեզվով սահմանվում է լեզվի բառային կառուցվածքը, իսկ Lex֊ը գեներացնում է բառային վերլուծիչի արդյունավետ իրականացում C (կամ այլ) լեզվով։ Այս գործիքների մասին մանրամասն կարելի է կարդալ «Doug Brown, John Levine, Tony Mason, lex & yacc, 2nd Edition, O'Reilly Media, 1992» և «John Levine, flex & bison, O'Reilly Media, 2009» գրքերում։

Ի՞նչ է լեզվի քերականությունը

Քանի որ և՛ վերլուծվող Բեյսիկ լեզուն սահմանելու համար, և՛ շարահյուսական վերլուծիչը GNU Bison ֆայլում կոդավորելու համար օգտագործելու եմ Բեկուսի֊Նաուրի գրառումը (BNF ― Backus-Naur Form), լավ կլինի, որ շատ կարճ խոսեմ նաև դրա մասին։ L լեզվի G(L) քերականությունը ⟨T,N,R,S⟩ քառյակն է, որտեղ T֊ն տերմինալային սիմվոլների բազմությունն է, N֊ը՝ ոչ տերմինալային սիմվոլներինը, R քերականական կանոնների (կամ հավասարումների) բազմությունն է և S֊ն էլ սկզբնական սիմվոլն է։ Տերմինալային սիմվոլները լեզվի քերականության անտրոհելի, ատոմար տարրերն են։ Օրինակ, ծառայողական բառերը, թվային ու տեքստային լիտերալները, մետասիմվոլները և այլն։ Ոչ տերմինալային սիմվոլները լեզվի առանձին տարրերի սահմանումներին տրված անուններն են։ Քերականական կանոնը լեզվի քերականության կառուցման հիմնական միավորն է, դրանով է որոշվում լեզվական կառուցվածքի տեսքը։ Քերականական կանոնը → (սլաք) նիշով բաժանված է ձախ ու աջ մասերի։ Ձախ կողմում սահմանվող ոչ տերմինալային սիմվոլն է, իսկ աջում՝ սահմանումը որոշող տերմինալային և ոչ տերմինալային սիմվոլների շարքը։ Օրինակ, Բեյսիկ լեզվի վերագրման հրամանը սահմանող երկու քերականական կանոններն ունեն այսպիսի տեսք․

Assignment  → LetOpt IDENT '=' Expression
LetOpt → LET | ε

Այստեղ գլխատառերով գրված են տերմինալային սիմվոլները՝ IDENT և LET, իսկ Pascal-Case կանոնով՝ ոչ տերմինալայինները՝ Assignment, Exprsssion և LetOpt։ Առաջին կանոնն «ասում է», որ վերագրման հրամանը (Assignment) բաղկացած է իրար հաջորդող LET սիմվոլից, իդենտիֆիկատորից, = վերգրման նշանից և վերագրվող արտահայտությունից (Expression)։ Երկրորդ կանոնով սահմանվում է LET սիմվոլի ոչ պարտադիր լինելը՝ LetOpt֊ը կամ LET սիմվոլն է, կամ դատարկ է՝ ε։ Քերականական կանոնի աջ կողմում այլընտրանքային տերբերակները (alternatives) իրարից անջատվում են | նիշով։ Սկզբնական սիմվոլն այն ոչ տերմինալային սիմվոլն է, որից պետք է սկսել լեզվի վերլուծությունը։ Քերականության ավելի ճշգրիտ ու մանրամասն սահմանման համար տես, օրինակ. «Alfred Aho, Monica Lam, Ravi Sethi, Jeffrey Ullman, Compilers: Principles, Techniques, and Tools, 2nd edition, Pearson/Addison-Wesley, 2006»։

Լեզվի սահմանում

Այստեղ քննարկվող Բեյսիկ լեզուն ունի տվյալների միայն մեկ տիպ՝ իրական թիվ։ Ծառայողական բառերը գրվում են միայն գլխատառերով, իդենտիֆիկատորներում մեծատառերն ու փոքրատառերը տարբերվում են (case sensitive)։ Բեյսիկի քերականությունը ես կսահմանեմ «վերևից֊ներքև»։ Այսինքն, նախ կսահմանեմ լեզվի «խոշոր» բաղադրիչները, ապա հերթականությամբ կսահմանեմ կանոններում հանդիպող բոլոր չսահմանված ոչ տերմինալային սիմվոլները։ Բեյսիկ լեզվով գրված ծրագիրը ֆունկցիաների հաջորդականություն է․

Program → FunctionList

Ֆունկցիաների հաջորդականությունը, որ կարող է նաև դատարկ լինել, սահմանված է ռեկուրսիվ եղանակով (ընդհանրապես ցուցակներ, հաջորդականություններ, կրկնություններ պարունակող քերականական տարրերը սահմանված են ռեկուրսիայի միջոցով).

FunctionList → FunctionList Function
             | ε

Ֆունկցիայի կանոնով որոշվում է և՛ ֆունկցիայի հայտարարությունը, և՛ ֆունկցիայի սահմանումը․

Function → Declaration
         | Definition

Ֆունկցիայի հայտարարությունը սկսվում է DECLARE ծառայողական բառով, որին հետևում է ֆունկցիայի վերնագիրը․

Declaration → DECLARE FunctionHeader

Ֆունկցիայի սահմանումը սկսվում է վերնագրով, որին հաջորդում է հրամանների ցուցակ, և ավարտվում է END և FUNCTION ծառայողական բառերով․

Definition → FunctionHeader StatementList END FUNCTION

Ֆունկցիայի վերնագիրը սկսվում է FUNCTION ծառայողական բառով, որին հետևում է ֆունկցիայի անունը որոշող իդենտիֆիկատոր, ապա՝ ( և ) փակագծերի մեջ վերցրած պարամետրերի ցուցակ։

FunctionHeader → FUNCTION IDENT '(' ParameterList ')' NewLines

Պարամետրերի ցուցակը կամ դատարկ է, կամ էլ ստորակետով իրարից բաժանված իդենտիֆիկատորների հաջորդականություն է․

ParameterList → IdentifierList
              | ε
IdentifierList → IdentifierList ',' IDENT
               | IDENT

NewLines ոչ տերմինալային սիմվոլով որոշվում է նոր տողի անցման մեկ և ավելի նիշերի շարքը․

NewLines → NewLines '\n'
         | '\n'

Հրամանների ցուցակը կամ դատարկ է, կամ նոր տողերի նիշերով վերջացող հրամանների շարք է.

StatementList → StatementList Statement NewLines
              | ε

Բեյսիկի հրամաններն են․ ներմուծում, արտածում, վերագրում, ճյուղավորում, պարամետրով ցիկլ, նախապայմանով ցիկլ, ենթածրագրի կանչ։ Դրանք բոլորը սահմանված են որպես Statement կանոնի այլընտրանքներ։ Ներմուծման հրամանը սկսվում է INPUT ծառայողական բառով, որին հաջորդում է ներմուծվող փոփոխականի անունը.

Statement → INPUT IDENT

Արտածման հրամանը սկսվում է PRINT բառով, որին հետևում է արտածվող արտահայտությունը․

Statement → PRINT Expression

Վերագրման հրամանն արդեն սահմանել եմ վերևում, այստեղ պարզապես կրկնեմ այն․

Statement → LetOpt IDENT '=' Expression
LetOpt → LET | ε

Ճյուղավորման հրամանը բոլորիս լավ հայտնի IF կառուցվածքն է։ Այն բաղկացած է երեք կարևոր բլոկներից, որոնցից միայն առաջինն է պարտադիր։ Առաջին և պարտադիր բլոկը սկսվում է IF ծառայողական բառով, որին հետևում է ճյուղավորման պայմանի արտահայտությունը, հետո՝ THEN ծառայողական բառը, նոր տողերի նիշեր և պայմանի ճշմարիտ լինելու դեպքում կատարվող հրամանների ցուցակը։ Երկրորդ և ոչ պարդադիր բլոկը այլընտրանքային պայմանները որոշող ElseIfPartList ցուցակն է, որի ամեն մի էլեմենտը սկսվում է ELSEIF ծառայողական բառով, ապա՝ պայմանի արտահայտությունը, THEN ծառայողական բառը, նոր տողի նիշեր և պայմանի ճշմարիտ լինելու դեպքում կատարվող հրամանների ցուցակ։ Երրորդ և ոչ պարտադիր բլոկը սկսվում է ELSE ծառայողական բառով, որին հաջորդում են նոր տողի նիշեր և հրամանների շարք։ Ճյուղավորման ամբողջ կառուցվածքն ավարտվում է END և IF ծառայողական բառերով։

Statement → IF Expression THEN NewLines StatementList ElseIfPartList ElsePart END IF
ElseIfPartList → ElseIfPartList ELSEIF Expression THEN NewLines StatementList
               | ε
ElsePart → ELSE StatementList
         | ε

Պարամետրով ցիկլի հրամանը սկսվում է FOR ծառայողական բառով, որին հաջորդում են ցիկլի պարամետրի իդենտիֆիկատորը, = նիշը, պարամետրի սկզբնական արժեքը որոշող արտահայտությունը, TO բառը, պարամետրի արժեքի վերին սահմանի արտահայտությունը, STEP բառը, պարամետրի քայլը որոշող արտահայտությունը, նոր տողի նիշեր, ցիկլի մարմինը որոշող հրամանների ցուցակ։ Պարամետրով ցիկլի հրամանն ավարտվում է END և FOR բառերով։

Statement → FOR IDENT '=' Expression TO Expression StepOpt NewLines StatementList END FOR
StepOpt → STEP Expression

Նախապայմանով ցիկլի հրամանը սկսվում է WHILE ծառայողական բառով, որին հետևում են ցիկլի կրկնման պայմանի արտահայտությունը, նոր տողի նիշեր, ցիկլի մարմնի հրամանների շարք։ Հրամանն ավարտվում է END և WHILE բառերով։

Statement → WHILE Expression NewLines StatementList END WHILE

Ենթածրագրի կանչը սկսվում է CALL բառով, որին հետևում են ֆունկցիայի անունի իդենտիֆիկատորը և արգումենտների ցուցակը (այն կարող է և դատարկ լինել)․

Statement → CALL IDENT ArgumentList
ArgumentList → ExpressionList
             | ε

Արտահայտությունների ցուցակը ստորակետով իրարից անջատված արտահայտություննների շարք է․

ExpressionList → ExpressionList ',' Expression
               | Expression

Հրամաններն այսքանն էին։ Անցնեմ արտահայտությունների սահմանմանը։ Դրանք կարող են պարունակել թվաբանական, տրամաբանական ու համեմատման գործողություններ, ինչպես նաև ֆունկցիայի կանչ։ Բացի բացասման ու ժխտման ունար գործողություններից, մյուս գործողությունները բինար են։ Որպեսզի արտահայտության քերականության մեջ արտացոլվի գործողությունների բնական (ընդունված) բաշխականությունն (associativity) ու նախապատվությունը (precedence), քերականությունը բաժանված է մի քանի մակարդակների։

Expression     → Conjunction OR Conjunction
Conjunction    → Equality AND Equality
Equality       → Comparison ('='|'<>') Comparison
Comparison     → Addition ('>'| '>=' | '<' | '<=') Addition
Addition       → Multiplication ('+'|'-') Multiplication
Multiplication → Power ('*' | '/') Power
Power          → Factor ['^' Power]
Factor         → IDENT '(' ArgumentList ')'
               | '(' Expression ')'
               | '-' Factor
               | NOT Factor
               | NUMBER
               | IDENT

Ես այստեղ շեղվեցի BNF֊ի սովորական գրառումից, պարզապես արտահայտություններում հանդիպող գործողությունների բաշխականությունն ու նախապատվությունը ցույց տալու համար։ Սակայն Bison֊ը հնարավորություն է տալիս նույն հասկացությունները սահմանել ավելի հարմր մեխանիզմներով։ Այդ մասին՝ իր տեղում։ Այսքանը լեզվի սահմանման մասին։ Կարծում եմ, որ ավելի մանրամասն նկարագրությունը պարզապես ավելորդ կլիներ։

GNU Bison֊ի ֆայլը

Yacc֊ի և GNU Bison֊ի մուտքին տրվող ֆայլը սովորաբար ունի .y վերջավորությունը (երբեմն օգտագործում են նաև .yacc, բայց ինձ .y ձևն ավելի է դուր գալիս)։ Այդ ֆայլը բաղկացած է երեք հատվածներից, որոնք իրարից բաժանվում են %% նիշերը պարունակող տողերով։

սահմանումներ
%%
քերականական կանոններ
%%
օժանդակ ֆունկցիաներ

Առաջին հատվածում սահմանումներն են, մասնավորապես, այստեղ են սահմանվում տերմինալային սիմվոլները, և սկզբնական սիմվոլը։ Երկրորդ բաժնում թվարկվում են քերականական կանոնները։ Իսկ երրորդն էլ C լեզվով գրված օժանդակ ֆունկցիաների համար է։ Առայժմ ես ցուցադրեմ միայն առաջին ու երկրորդ բաժինները։ Որպես օրինակ ցույց տամ միայն արտահայտությունների վերլուծիչի համար գրված .y ֆայլը։ Այն պարունակում է վերը նկարագրված Բեյսիկ լեզվի արտահայտությունների քերականությունը և դրանում օգտագործված տերմինալային սիմվոլների թվարկումը։ Ստեղծում եմ expr.y ֆայլը և %% նիշերով այն բաժանում եմ երկու մասի։ Առաջին մասում %token, %left, %right և %nonassoc հրահանգներով թվարկում եմ տերմինալային սիմվոլները։ %token֊ը պարզապես հայտարարում է տերմինալային սիմվոլ։ (Bison֊ի ֆայլի ընթեռնելիությունը պարզեցնելու համար ես տերմինալային սիմվոլները գրելու եմ ոչ թե գլխատառերով, այլ x տառով սկսվող camel-case֊ով։)

%token xNumber
%token xIdent

%left֊ը և %right֊ը ցուց են տալիս, որ իրենց սահմանած տերմինալային սիմվոլը (տվյալ դեպքում, գործողության անունը) ունի համապատասխանաբար ձախ կամ աջ բաշխականություն։ %nonassoc հրահանգի սահմանած տերմինալային սիմվոլները բաշխականություն չունեն։ Գործողությունների նախապատվությունը սահմանվում է ըստ դրանց թվարկման կարգի՝ ցածրից դեպի բարձր։ Հետևյալ սահմանումներում ձախ բաշխականություն ունեն կոնյունկցիան, դիզյունկցիան, գումարման, հանման, բազմապատկման ու բաժանման գործողությունները։ Համեմատման վեց ործողությունները բաշխականություն չունեն։ Աստիճան բարձրացնելու բինար գործողությունը և ժխտման ունար գործողությունն ունեն աջ բաշխականություն։

%left xOr
%left xAnd
%nonassoc xEq xNe
%nonassoc xGt xGe xLt xLe
%left xAdd xSub
%left xMul xDiv
%right xPow
%right xNot

Թվարկված գործողություններից ամենացածր նախապատվությունն ունի դիզյունկցիայի OR գործողությունը, իսկ ամենաբարձրը՝ NOT գործողությունը։ Նույն տողի վրա գրված են հավասար նախապատվություն ունեցող գործողությունները։ Հիմա գրում եմ .y ֆայլի երկրորդ բաժինը։ Այստեղ պարզապես պետք է քերականական կանոններով սահմանել, թե ինչպես են արտահայտությունները գործողություններով կապված իրար։ Bison֊ի ֆայլում քերականական կանոնների ձախ ու աջ մասերն իրարից բաժանվում են : նիշով, և ամեն մի կանոն ավարտվում է ; նիշով։

Expression
    : Expression xOr Expression
    | Expression xAnd Expression
    | Expression xEq Expression
    | Expression xNe Expression
    | Expression xGt Expression
    | Expression xGe Expression
    | Expression xLt Expression
    | Expression xLe Expression
    | Expression xAdd Expression
    | Expression xSub Expression
    | Expression xMul Expression
    | Expression xDiv Expression
    | Expression xPow Expression
    | '(' Expression ')'
    | xIdent '(' ArgumentList ')'
    | '-' Expression %prec xNot
    | xNot Expression
    | xNumber
    | xIdent
    ;

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

Expression : ...
           | '-' Expression %prec xNot

բայց դրա բացատրությունն էլ է պարզ։ Այստեղ %prec հրահանգով նշված է, որ բացասման (ունար մինուս) գործողությունը պետք է ունենա նույն բաշխականությունը, ինչ որ ժխտման NOT գործողությունը։ Մի քիչ առաջ անցնելով նշեմ, որ Bison֊ի ամեն մի քերեկանական կանոնին (իսկ ավելի ճիշտ՝ կանոնի աջ մասի ամեն մի տարրին) կարելի է համապատասխանեցնել գործողություն (action)՝ C կոդի բլոկ։ Օրինակ, Բեյսիկ լեզվի քերականության կանոնը Bison֊ի համար կարելի է գրել․

Program
    : FunctionList
    {
      puts("PARSED");
    }
    ;

Սա նշանակում է, որ ֆունկցիաների ցուցակի վերլուծությունից հետո պետք է արտածել PARSED բառը։ Հիմա expr.y ֆայլը տամ Bison֊ի մուտքին․

$ bison expr.y
expr.y:31.22-33: error: symbol ArgumentList is used, but is not defined as a token and has no rules
         | xIdent '(' ArgumentList ')'
                      ^^^^^^^^^^^^

Սխալի մասին հաղորդագրությունն ասում է, որ ArgumentList սիմվոլն օգտագործված է առանց սահմանման։ Լրացնեմ այդ սահմանումը ևս․ ֆունկցիայի կանչի արգումենտների ցուցակը կամ դատարկ է, կամ ստորակետով իրարից անջատված արտահայտությունների ցուցակ է․

ArgumentList
    : ExpressionList
    | %empty
    ;

ExpressionList
    : ExpressionList ',' Expression
    | Expression
    ;

Bison-ը թույլ է տալիս դատարկ կանոն սահմանելու համար օգտագործել %empty հատուկ սիմվոլը (BNF֊ում այդ դերը կատարում է ε տառը)։ Այս վերջն լրացումից հետո expr.y ֆայլը նորից Bison֊ի մուտքին տալով տեսնում եմ, որ գոնե քերականության տեսակետից ամեն ինչ կարգին է․ Bison-ը այլևս բողոքներ չունի։

Քերականության ստուգումը Bison֊ի միջոցով

Վերադառնամ իմ հիմնական գործին։ Երբ Բեյսիկ լեզվի սահմանման հետ արդեն ամեն ինչ պարզ է, ես պիտի փորձեմ դրա քերականությունը ստուգել Bison֊ի միջոցով (ինչպես դա արեցի արտահայտությունների համար)։ Ստեղծում եմ parser.y ֆայլը (սա արդեն լինելու է Բեյսիկի շարահյուսական վերլուծիչի հիմնական նկարագրությունը) և դրա մեջ Bison֊ի BNF կանոններով գրառում եմ Բեյսիկի ամբողջ քերականությունը։ Ահա այն․

/* parser.y */

%token xIdent
%token xNumber

%token xDeclare
%token xFunction
%token xLet
%token xInput
%token xPrint
%token xIf
%token xThen
%token xElseIf
%token xElse
%token xEnd
%token xFor
%token xTo
%token xStep
%token xWhile
%token xCall

%left xOr
%left xAnd
%nonassoc xEq xNe
%nonassoc xGt xGe xLt xLe
%left xAdd xSub
%left xMul xDiv
%right xPow
%right xNot

%token xEol

%start Program
%%
Program
    : FunctionList
    ;

FunctionList
    : FunctionList Function
    | %empty
    ;

Function
    : xDeclare FunctionHeader
    | FunctionHeader StatementList xEnd xFunction NewLines
    ;

FunctionHeader
    : xFunction xIdent '(' ParameterList ')' NewLines
    ;

ParameterList
    : IdentifierList
    | %empty
    ;

NewLines
    : NewLines xEol
    | xEol
    ;

IdentifierList
    : IdentifierList ',' xIdent
    | xIdent
    ;

StatementList
    : StatementList Statement NewLines
    | %empty
    ;

Statement
    : xInput xIdent
    | xPrint Expression
    | LetOpt xIdent xEq Expression
    | xIf Expression xThen NewLines StatementList ElseIfPartList ElsePart xEnd xIf
    | xFor xIdent xEq Expression xTo Expression StepOpt NewLines StatementList xEnd xFor
    | xWhile Expression NewLines StatementList xEnd xWhile
    | xCall xIdent ArgumentList
    ;

LetOpt
    : xLet
    | %empty
    ;

ElseIfPartList
    : ElseIfPartList xElseIf Expression xThen NewLines StatementList
    | %empty
    ;

ElsePart
    : xElse NewLines StatementList
    | %empty */
    ;

StepOpt
    : xStep Expression
    | %empty
    ;

ArgumentList
    : ExpressionList
    | %empty
    ;

ExpressionList
    : ExpressionList ',' Expression
    | Expression
    ;

Expression
    : Expression xOr Expression
    | Expression xAnd Expression
    | Expression xEq Expression
    | Expression xNe Expression
    | Expression xGt Expression
    | Expression xGe Expression
    | Expression xLt Expression
    | Expression xLe Expression
    | Expression xAdd Expression
    | Expression xSub Expression
    | Expression xMul Expression
    | Expression xDiv Expression
    | Expression xPow Expression
    | '(' Expression ')'
    | xIdent '(' ArgumentList ')'
    | xSub Expression %prec xNot
    | xNot Expression
    | xNumber
    | xIdent
    ;

Նորություն է միայն ֆայլի առաջին բաժնի վերջում գրված %start Program հրահանգը։ Սրանով նշվում է, որ սահմանված քերականության սկզբնական սիմվոլը Program ոչ տերմինալային սիմվոլն է։ Եթե քերականության սկզբնական սիմվոլն առանձնացված չէ %start հարահանգով, ապա առաջին սահմանված ոչ տերմինալային սիմվոլն է համարվում սկզբնական սիմվոլ։ parser.y ֆայլը Bison֊ի մուտքին տալու հենց առաջին փորձից պարզվում է, որ ամեն ինչ կարգին է, Bison֊ը քերականության տեսակետից բողոքներ չունի։ __* * *__ Ի՞նչ ունեմ այս պահին։ Bison֊ի լեզվով գրված Բեյսիկի քերականությունը, որ հակասություններ կամ սխալներ չի պարունակում, և պատրաստ է վերածվելու լիարժեք շարահյուսական վերլուծիչի։ Ո՞րն է իմ հաջորդ քայլը և ի՞նչ է պակասում դրան անցնելու համար։ Հիմա ես պետք է գրեմ բառային վերլուծիչ (կամ՝ լեքսիկական անալիզատոր, lexical analyzer, scanner), որը Bison֊ին է «մատակարարելու» սահմանված տերմինալային սիմվոլները։ Ապա բառային ու շարահյուսական վերլուծիչների համադրմամբ ստանամ մի նախնական ծրագիր, որը «հաստատում» է (accepts), որ Բեյսիկ լեզվով գրված ծրագրերը կարող են վերլուծվել, իսկ եթե չեն կարող՝ տեղեկացնի սխալների մասին։ Այլ կերպ ասած՝ իմ առաջիկա նպատակը Բեյսիկով գրված ծրագրի՝ Բեյսիկի քերականությանը համապատասխանող լինելը ստուգող գործիքն է։

Բառային վերլուծություն Flex֊ի միջոցով

GNU Flex գործիքը նախատեսված է բառային վերլուծիչի դեկլարատիվ նկարագրությունից արդյունավետ իրականացում գեներացնելու համար։ Թեև Flex֊ն ինքնուրույն գործիք է և կարող է օգտագործվել առանձին խնդիրների համար, այն հիմնականում օգտագործվում է Bison֊ի գեներացրած շարահյուսական վերլուծիչներին բառային վերլուծիչ տրամադրելու համար։ Flex֊ի համար գրված նկարագրության ֆայլերն ունենում են .l վերջավորությունը (երբեմն նաև՝ *.lex)։ Bison֊ի ֆայլի պես Flex֊ի ֆայլն էլ է %% նիշերով բաժանվում երեք հատվածների։ Առաջինում սահմանումներն են, երկրորդում՝ թոքենները (տերմինալային սիմվոլներ) ճանաչելու կանոնները, երրորդում՝ օժանդակ ֆունկցիաները։

սահմանումներ
%%
կանոններ
%%
ֆունկցիաներ

Սահմանումների հատվածն օգտագործվում է բարդ կանոնավոր արտահայտություններին կարճ անուններ տալու համար։ Այսպես․

number      [0-9]+(\.[0-9]+)?
ident       [a-zA-Z][a-zA-Z0-9]*
comment     \'.*$

Այստեղ numebr֊ը սահմանված է որպես տասնորդական կետ պարունակող իրական թիվ, ident֊ը՝ որպես տառով սկսվող և կառերից ու թվերից բաղկացած հաջորդականություն, իսկ comment֊ը ' նիշով սկսվող և մինչև տողի վերջը շարունակվող նիշերի հաջորդականություն։ Երկրորդ բաժնում գրվում են թոքենները ճանաչող կանոնները։ Flex֊ի կանոնը բաղկացած է երկու մասից․ թոքենի նկարագրիչ (pattern) և գործողություն (action)։

pattern     action

Նկարագրիչը կամ կանոնավոր արտահայտություն է, կամ սահմանումների բաժնում սահմանված անուն։ Երկրորդ դեպքում անունը պետք է վերցնել { և } փակագծերի մեջ։ Այսպես․

[ \t]       { /**/ }
{comment}   { /**/ }
{number}    { return xNumber; }

Առաջին ու երկրորդ կանոններն «ասում են», որ պետք է անտեսել բացատանիշերն ու մեկնաբանությունները։ Երրորդ կանոնն «ասում է», որ պետք է վերադարձնել xNumber թոքենը, եթե հանդիպել է number սահմանումով նկարագրիչը (number֊ը և comment֊ը սահմանվել են ֆայլի առաջին բաժնում)։ Ծառայողական բառերից ամեն մեկի համար վերադարձվում են իրենց համապատասխան թոքենները․

"DECLARE"   { return xDeclare; }
"FUNCTION"  { return xFunction; }
"LET"       { return xLet; }
"INPUT"     { return xInput; }
"PRINT"     { return xPrint; }
"IF"        { return xIf; }
"THEN"      { return xThen; }
"ELSEIF"    { return xElseIf; }
"ELSE"      { return xElse; }
"END"       { return xEnd; }
"FOR"       { return xFor; }
"TO"        { return xTo; }
"STEP"      { return xStep; }
"WHILE"     { return xWhile; }
"CALL"      { return xCall; }
"OR"        { return xOr; }
"AND"       { return xAnd; }
"NOT"       { return xNot; }

Քանի որ Flex֊ը թոքենների նկարագրիչները ստուգում է վերևից ներքև, իդենտիֆիկատորները ճանաչող կանոնը պետք է գրել ծառայողական բառերից հետո․

{ident}     { return xIdent; }

Հաջորդ խմբում գործողությունների նշանակումները ճանաչող կանոններն են, որոնք նույպես վերադարձնում են ամեն մի գործողությանը համապատասխանեցված թոքենը։

"="         { return xEq; }
"<>"        { return xNe; }
">"         { return xGt; }
">="        { return xGe; }
"<"         { return xLt; }
"<="        { return xLe; }
"+"         { return xAdd; }
"-"         { return xSub; }
"*"         { return xMul; }
"/"         { return xDiv; }
"^"         { return xPow; }
\n          { return xEol; }

Flex֊ի կանոնավոր արտահայտություններում . (կետ) նիշը համապատասխանում է կամայական նիշի, բացի նոր տողի նիշից։ Գրելով հետևյալ կանոնը․

.           { return (int)yytext[0]; }

որպես թոքեն վերադարձնում եմ տվյալ նիշի համապատասխան ASCII կոդը։ yytext-ը այն բուֆերն է, որի մեջ Flex-ը պահում է ճանաչված տեքստը՝ լեքսեմը։ Քիչ հետո այս բուֆերի օգտագործման այլ օրինակներ էլ ցույց կտամ։ Հիմա արդեն ժամանակն է Flex֊ի միջացով ստուգել նկարագրված բառային վերլուծիչի ճշտությունը։ Դրա համար պետք է scanner.l ֆայլը տալ Flex֊ի մուտքին․

$ flex scanner.l

Եթե Flex֊ը սխալների մասին հաղորդագրություններ չի արտածում, ապա ամեն ինչ կարգին է։ Գեներացվել է բառային վերլուծիչի իրականացումը պարունակող lex.yy.c ֆայլը, որը պարունակում է int yylex() ֆունկցիան։ Լռելությամբ գեներացված բառային վերլուծիչը նիշերի հաջորդականությունը կարդում է ներմուծման ստանդարտ հոսքից՝ stdin։ Ավելի ուշ ցույց կտամ, թե ինչպես կարդալ տրված ֆայլը։

Գործարկման առաջին փորձ

Bison֊ն իրեն տրված քերականության նկարագրությունից գեներացնում է C կոդ։ Եթե .y ֆայլն ունի ⟨name⟩ անունը, ապա Bison֊ը լռելությամբ գեներացնում է ⟨name⟩.tab.c ֆայլը։ Գեներացրած շարահյուսական վերլուծիչի մուտքի կետը int yyparse() ֆունկցիան է։ Flex-ն էլ իրեն տրված նկարագրությունից գեներացնում է C կոդ։ Նրա գեներացրած ֆայլը լռելությամբ ունի lex.yy.c անունը, բայց ես սովորություն ունեմ Flex֊ի -o պարամետրով ⟨name⟩ անունի համար գեներացնել ⟨name⟩.yy.c ֆայլը։ Flex֊ի գեներացրած բառային վերլուծիչի մուտքի կետը yylex() ֆունկցիան է։ yyparse() ֆունկցիան իրեն անգհրաժեշտ հերթական թոքենը ստանալու համար պարբերաբար կանչում է հենց այդ yylex() ֆունկցիան։ Bison֊ի և Flex֊ի գեներացրած ֆայլերն իրար հետ կոմպիլյացնելու ու կատարվող մոդուլ ստանալու համար պետք է պիտի գրեմ նաև main() ֆունկցիա, որում կանչվում է yyparse() ֆունկցիան։ Ահա այն․

/* main.c */
int main()
{
  extern int yyparse();
  int ok = yyparse();
  return ok;
}

Երբ GNU GCC կոմպիլյատորորով փորձում եմ թարգմանել (compile) ու կապակցել (link) parser.tab.c, scanner.yy.c և main.c ֆայլերը, ստանում եմ սխալների հաղորդագրությունների մի շարք։ Ահա դրանցից առաջին չորսը․

scanner.l: In function ‘yylex’:
scanner.l:9:10: error: ‘xNumber’ undeclared (first use in this function)
 {number}    { return xNumber; }
          ^
scanner.l:9:10: note: each undeclared identifier is reported only once for each function it appears in
scanner.l:10:10: error: ‘xDeclare’ undeclared (first use in this function)
 "DECLARE"   { return xDeclare; }
          ^
scanner.l:11:10: error: ‘xFunction’ undeclared (first use in this function)
 "FUNCTION"  { return xFunction; }
          ^
scanner.l:12:10: error: ‘xLet’ undeclared (first use in this function)
 "LET"       { return xLet; }
          ^
....

Տեսնում եմ, որ կոմպիլյատորը չի գտնում yylex() ֆունկցիայում օգտագործված թոքենները (դրանք սահմանված էին parser.y ֆայլում)։ Բանն այն է, որ Flex֊ի և Bison֊ի գեներացրած C ֆայլերը կոմպիլյացիայի տարբեր միավորներ (compilation unit) են, և բնական է, որ կոմպիլյատորը չի կարող դրանցից մեկը թարգմանելիս «տեսնել» մյուսում սահմանված անունները։ Bison֊ի հրամանային տողի -d պարամետրը ⟨name⟩.y ֆայլի համար գեներացնում է նաև ⟨name⟩.tab.հ ֆայլը, որը պարունակում է ⟨name⟩.y֊ում հայտարարված թոքենների (նաև այլ օբյեկտների) հայտարարությունները։ Ուրեմն parser.y ֆայլը պետք է Bison֊ով թարգմանել հետևյլ հրամանով․

$ bison -d parser.y

որի արդյունքում կգեներացվեն parser.tab.h և parser.tab.c ֆայլերը։ Հետո պետք է parser.tab.h ֆայլը կցել scanner.l ֆայլին։ Ե՛վ Bison֊ի, և՛ Flex֊ի համար նախատեսված ֆայլերի սկզբում թույլատրվում է ունենալ C լեզվով գրված կոդի բլոկ։ Այդ բլոկը սկսվում է %{ նիշերով և վերջանում է %} նիշերով և առանց փոփոխության պատճենվում է գեներացված .c ֆայլի մեջ։ Այսինքն, .l և .y ֆայլերը ունեն հետևյալ տեսքը․

%{
C կոդ
%}
սահմանումներ
%%
քերականական/լեքսիկական կանոններ
%%
օժանդակ C ֆունկցիաներ

Հենց այս %{...%} բլոկում էլ պետք է #include հրահանգով scanner.l ֆայլին կցել parser.tab.h ֆայլը։ Այսինքն, scanner.l ֆայլի սկիզբը պետք է ունենա հետևյալ տեսքը․

%{
#include "parser.tab.h"
%}

%option noyywrap

number      [0-9]+(\.[0-9]+)?
ident       [a-zA-Z][a-zA-Z0-9]*
comment     \'.*$
....

Քանի որ խոսք է բացվել scanner.l ֆայլը լրացնելու մասին, բացատրեմ նաև %option noyywrap տողը։ Երբ Flex֊ի գեներացրած բառային վերլուծիչը կարդում է վերլուծվող ֆայլը և հասնում է դրա վերջին, այն կանչում է yywrap() ֆունկցիան։ Եթե վերջինս վերադարձնում է 0, ապա վերլուծությունը շարունակվում է, իսկ եթե վերադարձնում է 1, ապա yylex()-ը վերադարձնում է 0 արժեք և վերլուծությունը դադարեցվում է։ %option noyywrap հրահանգով Flex֊ին խնդրում ենք ֆայլի վերջին հասնելիս վերադարձնել 0 և չկանչել yywrap() ֆունկցիան։ scanner.l ֆայլում ուղղումներ անելուց հետո նորից փորձեմ կառուցել կատարվող մոդուլը․

$ bison -d parser.y
$ flex -oscanner.yy.c scanner.l
$ gcc *.c

Կոմպիլյատորը նորից տեղեկացնում է սխալների մասին։

parser.tab.c: In function ‘yyparse’:
parser.tab.c:1259:16: warning: implicit declaration of function ‘yylex’ [-Wimplicit-function-declaration]
       yychar = yylex ();
                ^
parser.tab.c:1388:7: warning: implicit declaration of function ‘yyerror’ [-Wimplicit-function-declaration]
       yyerror (YY_("syntax error"));
       ^

Առանց սահմանվելու (կամ հայտարարվելու) օգտագործվել են yylex() և yyerror() ֆունկցիաները։ yylex()֊ի դեպքում ամեն ինչ պարզ է․ այն գտնվում է ուրիշ կոմպիլյացիայի միավորում։ Պարզապես պետք է parser.y ֆայլի սկզբում հայտարարել yylex()ֆունկցիան։ yyerror() ֆունկցիան օգտագործվում է սխալների մասին ազդարարելու համար․ այն ևս պետք է հայտարարել parser.y ֆայլի սկզբում։

%{
extern int yylex();
static int yyerror( const char* );
%}

%token xIdent
%token xNumber
....

Դե, yylex() ֆունկցիան գեներացվում է Flex֊ի օգնությամբ, իսկ yyerror()֊ը պետք է սահամանի ծրագրավորողը։ parser.y ֆայլի օժանդակ ֆունկցիաների բաժինը ճիշտ այն տեղն է, որտեղ պետք է սահմանել շարահյուսական վերլուծիչում օգտագործվող yyerror() ֆունկցիան։

%%

static int yyerror( const char* message )
{
  fprintf(stderr, "ՍԽԱԼ։ %s\n", message);
  return 1;
}

Հա, չմոռանամ նաև parser.y ֆայլի սկզբում կցել stdio.h ֆայլը՝ C լեզվի ստանդարտ գրադարանի ներմուծման֊արտածման գործողությունների համար։

%{
#include <stdio.h>

extern int yylex();
static int yyerror( const char* );
%}

%token xIdent
%token xNumber
....

Կատարվող մոդուլը հիմա արդեն պետք է հաջողությամբ կառուցվի։ Դրա համար պետք է նորից կոմպիլյացնել ու կապակցել ֆայլերը․

$ bison -d parser.y
$ flex -oscanner.yy.c scanner.l
$ gcc -obasic-s *.c

Ստեղծվում է basic-s մոդուլը։ Բայց ի՞նչ կարող եմ անել սրանով։ Փորձեմ այս ծրագրի մուտքին տալ մի Բեյսիկ ծրագիր ու տեսնել, թե ինչ պատասխան է տալիս։ Թող փորձարկվողը լինի հետևյալ պարզագույն ծրագիրը՝ գրված case01.bas ֆայլում․

' case01.bas

' պարզ ծրագիր
FUNCTION Main()
  PRINT 3.14
END FUNCTION

Այն basic-s վերլուծիչի մուտքին տամ ներմուծման հասքի վերաուղղորդման միջոցով․

$ ./basic-s < case01.bas
ՍԽԱԼ։ syntax error

Ստանում եմ սխալ։ Չնայած ամեն ինչ պիտի որ կարգին լիներ, բայց ծրագրավորման գեղեցկությունը հենց այն է, որ սխալներ կարող են հանդիպել ամենաանսպասելի պահերին։ Ի՞նչն է այս սխալի պատճառը։ Ոչ տողի համար կա, ոչ էլ քիչ թե շատ կոնկրետ բացատրություն․ «syntax error» ու վերջ։ Բարեբախտաբար Bison֊ն ունի ավելի մանրամասն սխալների հաղորդագրություններ արտածելու հնարավորություն։ Այն ակտիվացնելու համար պետք է parser.y ֆայլի հայտարարությունների (առաջին) բաժնում ավելացնել %error-verbose հրահանգը։ Դրանից հետո, երբ նորից ստեղծում եմ basic-s կատարվող մոդուլը ու դրա մուտքին տալիս եմ թեսթային ֆայլը, ստանում եմ սխալի համեմատաբար ավելի հստակ նկարագրություն։

$ ./basic-s < case01.bas
ՍԽԱԼ։ syntax error, unexpected xEol, expecting $end

Այստեղ ասված է, որ շարահյուսական վերլուծիչը բառային վերլուծիչից ստացել է xEol, թեև սպասում էր $end հատուկ սիմվոլը։ Չնայած, որ արդեն գուշակում եմ, թե սխալը ինչումն է, վատ չէր լինի սխալի հաղորդագրության հետ նշվեր նաև սխալը պարունակող տողի համարը։ Flex֊ի %option yylineno հրահանգը բառային վերլուծիչի ֆայլում հայտարարում է yylineno գլոբալ հաշվիչը, որը հենց հերթական վերլուծվող տողի համարն է։ Դա պետք է պարզապես ավելացնել scanner.l ֆայլի սահմանումների (առաջին) բաժնում, օրինակ, %option noyywrap հրահանգից հետո։

%{
#include "parser.tab.h"
%}

%option noyywrap
%option yylineno

number      [0-9]+(\.[0-9]+)?
ident       [a-zA-Z][a-zA-Z0-9]*
comment     \'.*$
....

Իսկ parser.y ֆայլի yyerror() ֆունկցիայում պետք է հայտարարել yylineno փոփոխականը, և այն օգտագործել սխալի մասին հաղորդագրությունն արտածելիս։ (Ես սովորություն ունեմ yylineno փոփոխականը հայտարարել parser.y ֆայլի %{...%} բլոկում, որպեսզի կարողանամ այն ազատ օգտագործել ոչ միայն սխալների մասին ազդարարելիս, այլ նաև շարահյուսական վերլուծիչի այլ հատվածներում։)

%%

static int yyerror( const char* message )
{
  extern int yylineno;
  fprintf(stderr, "ՍԽԱԼ։ [%d] %s\n", yylineno, message);
  return 1;
}

Երբ նորից կառուցում եմ basic-s մոդուլը ու դրա մուտքին տալիս եմ թեսթային ծրագիրը, տեսնում եմ, որ սխալի մասին հաղորդագրության մեջ հիմա արդեն նշված է շարահյուսական սխալը պարունակող տողը։

$ ./basic-s < case01.bas
ՍԽԱԼ։ [2] syntax error, unexpected xEol, expecting $end

Հիմա սխալի մասին։ Բանն այն է, որ ըստ իմ սահմանած քերականության ֆայլի սկզբում նր տողի անցման նիշեր թույլատրված չեն։ Դա երևում է քերականության առաջին մի քանի կանոններից․

Program
    : FunctionList
    ;

FunctionList
    : FunctionList Function
    | /* empty */
    ;

Function
    : xDeclare FunctionHeader
    | FunctionHeader StatementList xEnd xFunction NewLines
    ;

FunctionHeader
    : xFunction xIdent '(' ParameterList ')' NewLines
    ;

Իսկ թեսթային օրինակում Main() ֆուկցիայի սահմանմանը նախորդում են մեկնաբանություններ և դատարկ տող։ Մեկնաբանություններն ու բացատանիշերն անտեսվում են բառային վերլոծիչի կողմից։ Մնում են նոր տողի նիշերը։ Որպեսզի վերլուծիչը կարողանա տեսնել ու անտեսել ֆայլի սկզբում հանդիպող նոր տողի նիշերը, Program կանոնում պետք է ավելացնել զրո կամ ավելի նոր տողերի նիշերի կանոնը․

Program
    : NewLinesOpt FunctionList
    ;

NewLinesOpt
    : NewLines
    | /* empty */
    ;

Նորից եմ փորձում կառուցել կատորվող մոդուլը և դրան տալ թեսթային Բեյսիկ ծրագիրը։

$ bison -d parser.y
$ flex -oscanner.yy.c scanner.l
$ gcc -obasic-s scanner.yy.c parser.tab.c main.c
$
$ ./basic-s < case01.bas

Վա՛հ։ Սխալի հաղորդագրություն չկա։ Մի՞թե ամեն ինչ հաջող է արդեն։ Մի թեսթային օրինակ էլ պատրաստեմ, որում ֆունկցիայի մի հայտարարություն է և երկու սահմանում․

' case02.bas

DECLARE FUNCTION Gcd(n, m)

FUNCTION Main()
  PRINT Gcd(152, 21)
END FUNCTION

' մեծագույն ընդհանուր բաժանարար
FUNCTION Gcd(n, m)
  WHILE n <> m 
    IF n > n THEN
      n = n - m
    ELSE
      m = m - n
    END IF
  END WHILE
  LET Gcd = n
END FUNCTION

Ու այս օրինակն էլ տամ իմ կառուցած վերլուծիչին, որն, իհարկե, այս պահին ոչ թե վերլուծիչ ― parser է, այլ՝ «ճանաչիչ» ― recognizer, կամ «հաստատիչ» — acceptor (եթե կարելի է այդպիսի բառեր հորինել)․

$ ./basic-s < case02.bas

Նորից սխալի հաղորդագրություն չկա։ Սա երկու բան կարող է նշանակել․ կամ վերլուծիչը «ճանաչեց» թեսթային օրինակը, կամ էլ այն ընդհանրապես չաշխատեց։ Վերջին ստուգումն անելու համար քերականության Program կանոնի աջ կողմում ավելացնեմ վերլուծությունը ճիշտ ավարտելու մասին հաղորդագրություն․

Program
    : FunctionList
    {
      puts("Parsed");
    }
    ;

Կատարվող մոդուլի կառուցումից հետո, երբ դրա մուտքին տալիս եմ թեսթային ֆայլերը, վերլուծիչն արտածում է երկար սպասված Parsed բառը։

$ ./basic-s < case01.bas
Parsed
$ ./basic-s < case02.bas
Parsed

__* * *__ Այս պահին արդեն կարող եմ ասել, որ Բեյսիկ լեզվի համար շարահյուսական վերլուծիչ գրելու իմ առաջին փորձը հաջողվել է։

Թեսթավորում․ առաջին մաս

Իմ հաջորդ քայլն ավելի շատ թեսթային օրինակների կառուցումն է, որոնցում ներառված են Բեյսիկ լեզվի արտահայտությունների բոլոր տեսակներն ու բոլոր ղեկավարող կառուցվածքները։ Դրանց օգնությամբ պիտի համոզվեմ, որ իմ կառուցած վերլուծիչն ընդունակ է ճանաչել ամբողջ Բեյսիկ լեզուն։ Սկսեմ արտահայտություններից։ Դրանք երեք տեսակի էին․ թվաբանական, համեմատման և տրամաբանական։ case03.bas թեսթում սահմանված երեք ֆունկցիաներում ես ծրագրավորել եմ արտահայտությունների բոլոր հնարավոր դեպքերը։

' case03.bas
' գործողություններ

' թվաբանական
FUNCTION Arithmetic(x, y)
  PRINT x + y
  PRINT x - y
  PRINT x * y
  PRINT x / y
  PRINT x ^ y
  PRINT y
  PRINT -x
  PRINT 3.14
  PRINT (x + y) * (x - y)
END FUNCTION

' համեմատման
FUNCTION Comparison(x, y)
  PRINT x = y
  PRINT x <> y
  PRINT x > y
  PRINT x >= y
  PRINT x < y
  PRINT x <= y
END FUNCTION

' տրամաբանական
FUNCTION Logical(x, y)
  PRINT x OR y
  PRINT x AND y
  PRINT NOT x
END FUNCTION

' ֆունկցիաների ստուգում
FUNCTION Main()
  CALL Arothmetical 1.2, 777
  CALL Comparison 18, -5
  CALL Logical 1, 0
END FUNCTION

Թեսթերում ես միշտ գրում եմ Main() ֆունկցիան, որպեսզի կարողանամ նույն ֆայլերը հետո օգտագործել թարգմանիչի թեսթավորման համար։ Չնայած կարծում եմ, որ թարգմանիչի ֆունկցիոնալության թեսթավորման համար պետք կլինի խմբագրել այս թեսթերը և գրել նորերը։ Հաջորդ թեսթը ներմուծման ու արտածման հրամանների համար է։ Ներմուծման ստանդարտ հոսքից կարդում եմ r թիվը և արտածում եմ 3.1415 * r^2 արժեքը։

' case04.bas
' ներմուծման ու արտածման հրամաններ

FUNCTION Main()
  INPUT r
  PRINT 3.1415 * r^2
END FUNCTION

Վերագրման հրամանի թեսթում պետք է հաշվի առնել նաև, որ այն կարող է սկսվել ոչ պարտադիր LET բառով։

' case05.bas
' վերագրման հրաման

FUNCTION Main()
  x = 1 + 2 * 3
  LET y = x^2
END FUNCTION

Պայմանի կամ ճյուղավորման հրամանը ունի բավականին բարդ տեսք։ Հետևյալ թեսթը պարունակում է IF հրամանի բոլոր հնարավոր տարբերակները։

' case06.bas
' պայմանի կամ ճյուղավորմն հրաման

FUNCTION Main()
  x = 77
  y = 0
  
  ' պարզ դեպք
  IF x > y THEN
    PRINT x
  END IF

  ' մեկ այլընտրանք
  IF x <> y THEN
    PRINT y
  ELSE
    PRINT x
  END IF

  ' շատ այլընտրանքներ
  IF x = y THEN
    PRINT x + y
  ELSEIF x < y THEN
    PRINT x - y
  ELSEIF x > y THEN
    PRINT x * y
  END IF

  ' լրիվ տեսք
  IF x * y <> 0 THEN
    PRINT y + 1
  ELSEIF x / y < 0 THEN
    PRINT x + 1
  ELSEIF x + y > 0 THEN
    PRINT y + 2
  ELSEIF x - y = 0 THEN
    PRINT x^y
  ELSE
    PRINT y^2
  END IF
END FUNCTION

Հաջորդը թեսթը պարամետրով ցիկլի FOR հրամանի համար է (դրա STEP մասնիկը կարող է բացակայել)։

' case07.bas
' պարամետրով ցիկլի հրաման

FUNCTION Main()
  ' առաջին տարբերակ
  FOR i = 7 TO 16
    PRINT i^2
  END FOR

  ' երկրորդ տարբերակ
  FOR i = 0 TO 12 STEP 3
    PRINT i * 3
  END FOR
END FUNCTION

Նախապայմանով ցիկլի հրամանը թերևս ամենապարզերից է։ Դրա թեսթը նկարագրում է մի պարզ դեպք։

' case08.bas
' նախապայմանով ցիկլ

FUNCTION Main()
  LET a = 100
  WHILE a > 0
    PRINT a
    a = a - 1
  END WHILE
END FUNCTION

Հրամանների հաջորդման, ֆունկցիայի հայտարարման ու սահմանման առանձին թեսթեր չեմ գրում, քանի որ այդ կառուցվածքները շատ անգամներ հանդիպում են արդեն գրված օրինակներում։ Բոլոր թեսթերը հավաքում եմ tests պանակում, որտեղ հետագայում ավելացնելու եմ նաև թարգմանության ակնկալվող արդյունքները։ Հենց այդտեղ էլ պետք է գրել թեսթավորող սցենարը (script)։

Արվածի ամփոփում և հետագա քայլերի մշակում

Հիմա կոմպյուտերից հնչում է Չայկովսկու «Դաշնամուրային առաջին կոնցերտը»՝ Ալիս Սառա Օտտի կատարմամբ։ Եվ ես ուզում եմ այս հանգիստ պահն օգտագործել արված ամփոփելու և հետագա անելիքներս պլանավորելու համար։ Ի՞նչ ունեմ այս պահին։ Ունեմ մի գործիք, որի մուտքին տալիս եմ բեյսիկ լեզվով գրված ծրագիր և այն պատասխանում է, թե կարողացա՞վ արդյոք Բեյսիկի քերականական կանոններին համապատասխանեցնել տրված ծրագիրը։ Եթե կարողանում է ծրագիրն ամբողջությամբ վերլուծել, ապա արտածում է «Parsed» բառը, հակառակ դեպքում արտածվում է Bison-ի սովորական սխալի հաղորդագրություն։ Նշեմ, որ ես որևէ սխալների մշակում չեմ նախատեսել․ ինչ որ արվում է, արվում է Bison֊ի կողմից։ Ո՞րն էր իմ նպատակը։ Հիշեցնեմ, որ իմ նպատակը Բեյսիկ-JSON թարգմանիչի իրականացումն էր։ Թարգմանության համար որոշել եմ Բեյսիկ ծրագիրը վերլուծել ու կառուցել աբստրակտ քերականական ծառ, ապա այդ ծառից գեներացնել JSON կոդը։ Ի՞նչ է մնում անելու։ Նախ՝ պետք է իրականացնեմ աբստրակտ քերականական ծառի հանգույցների մոդելները և թեսթավորեմ դրանք։ Այդ գործը անմիջական կապ չունի Bison/Flex գործիքների աշխատանքի հետ, և ես առանձին մանրամասնությունների մեջ չեմ մտնի։ Ցանկության դեպքում ընթերցողը կարող է ինքնուրույն ուսումնասիրել այդ կոդը։ Այնուհետև՝ parser.y նկարագրության քերականական կանոնները (rules) պետք է ընդլայնեմ աբստրակտ քերականական ծառը կառուցող գործողություններով (actions)։ Վերջում՝ Բեյսիկ ծրագրի կարդալը և JSON կոդի արտածումը պետք է կազմակերպեմ ֆայլերից։ Իհարկե, այս բոլոր քայլերը պետք է համապատասխան ձևով թեսթավորվեն։

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

Ըստ Բեյսիկ լեզվի քերականության աբստրակտ քերականական ծառը կարող է ունենալ երեք տիպի հանգույցներ․ արտահայտություններ, հրամաններ և ֆունկցիաներ։ ast.h ֆայլում սահմանված են այս երեք տիպերն ու դրանց ենթատիպերը։ ast.c ֆայլում համապատասխան «կոնստրուկտորներն» են և թարգմանության ֆունկցիաները։ Արտահայտությունները հինգ տեսակի են․ իրական թիվ, փոփոխական, ունար գործողություն, բինար գործողություն և ֆունկցիայի կանչ։ Բոլոր այդ տարատեսակները մոդելավորել եմ միակ _expression ստրուկտուրայով, որի kind դաշտը ցույց է տալիս, թե դրա նմուշն ինչ արտահայտություն է ներկայացնում։

/* արտահայտություններ */
typedef struct _expression expression;
struct _expression {
  // արտահայտության տեսակը
  enum {
    NUMBER,
    VARIABLE,
    UNARY,
    BINARY,
    APPLY,
  } kind;
  double number; // իրական թիվ
  char* name; // իդենտիֆիկատոր
  // գործողությունների կոդերը
  enum {
    OR, AND, EQ, NE, GT, GE,
    LT, LE, ADD, SUB, MUL,
    DIV, POW, NOT, NEG 
  } oper;
  expression* exo; // ենթաարտահայտություն
  expression* exi; // ենթաարտահայտություն
  function* func; // կիրառվող ֆունկցիա
  node* args; // ֆունկցիայի կիրառման արգումենտներ
};

Արտահայտության հինգ ենթատիպերի համար նախատեսված են համապատասխան կոնստրուկտորները։

extern expression* create_number( double );
extern expression* create_variable( const char* );
extern expression* create_unary( int, expression* );
extern expression* create_binary( int, expression*, expression* );
extern expression* create_apply( function*, node* );

Արտահայտությունները JSON ներկայացման թարգմանելու համար է expression_as_json() ֆունկցիան։ Սրա առաջին արգումենտը արտահայտության ցուցիչն է, իսկ երկրորդը՝ արտածման ֆայլային հոսքինը։

extern void expression_as_json( expression*, FILE* );

Հրամանների ենթատեսակները ութն են. ներմուծում, արտածում, վերագրում, ճյուղավորում, պարամետրով ցիկլ, նախապայմանով ցիկլ, պրոցեդուրայի կանչ և հրամանների հաջորդում։ Կառուցվածքային բազմազանության պատճառով չուզեցի բոլոր հրամանների համար սահմանել մեկ ստրուկտուրա (ինչպես դա արել եմ արտահայտությունների համար)։ Փոխարենը սահմանել եմ _statement ստրուկտուրան՝ kind տեսակի դաշտով, և կոնկրետ հրամանի child ունիվերսալ ցուցիչը։

/* հրամաններ */
typedef struct _statement statement;
struct _statement {
  // հրամանի տեսակը
  enum {
    INPUT, PRINT, ASSIGN, IF,
    FOR, WHILE, CALL, SEQ,
  } kind;
  void* child; // հրամանի ցուցիչ
};

Հրամանն էլ JSON ներկայացման է թարգմանվում statement_as_json() ֆունկցիայով։

extern void statement_as_json( statement*, FILE* );

Բեյսիկի բոլոր ութ հրամանները մոդելավորող ստրուկտուրաները դուրս են բերված դրանց շարահյուսական տեսքերից՝ դեն նետելով ծառայողական բառերն ու մետասիմվոլները։ Այսպես, ներմուծման հրամանը բաղկացած է INPUT ծառայողական բառից և ներմուծվող փոփոխականի անունից։ Այն ներկայացնող ստրուկտուրան ունի միայն փոփոխականի անունը պարունակող vari դաշտը։ create_input կոնստրուկտորը ստեղծում և վերադարձնում է _statement ստրուկտուրայի նմուշը, որի kind դաշտում INPUT արժեքն է, իսկ child դաշտը կապված է _input_s ստրուկտուրայի նմուշի հետ։

/* ներմուծում */
typedef struct _input_s input_s;
struct _input_s {
  char* vari;
};
extern statement* create_input( const char* );

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

typedef struct _print_s print_s;
struct _print_s {
  expression* valu;
};
extern statement* create_print( expression* );

Վերագրման հրամանի _assign_s ստրուկտուրան երկու դաշտ ունի՝ vari և valu, դրանք համապատասխանաբար կապված են վերագրվող փոփոխականի անունին և վերագրվող արտահայտության ծառին։

typedef struct _assign_s assign_s;
struct _assign_s {
  char* vari;
  expression* valu;
};
extern statement* create_assign( const char*, expression* );

Ճյուղավորման հրամանի _if_s կառուցվածքում երեք դաշտեր են՝ cond ― պայման, thenp ― պայմանի ճշմարիտ լինելու դեպքում կատարվող ճյուղը և elsep ― պայմանի կեղծ լինելու դեպքում կատարվող ճյուղը։ (Միայն այս դեպքում եմ շեղվել շարահյուսությունից և ճյուղավորման հրամանի մոդելը կառուցել եմ ավելի պարզ, քան նկարագրված շարահյուսական կանոնում։ Կարծում եմ, որ ընթերցողն առանց մեկնաբանությունների էլ կհասկանա այդ պարզեցման հարմարությունը։)

typedef struct _if_s if_s;
struct _if_s {
  expression* cond;
  statement* thenp;
  statement* elsep;
};
extern statement* create_if( expression*, statement*, statement* );

Պարամետրով ցիկլի հրամանի _for_s մոդելն ունի հինգ դաշտ՝ FOR հրամանի բաղադրիչներին համապատասխան։

typedef struct _for_s for_s;
struct _for_s {
  char* param;
  expression* start;
  expression* stop;
  expression* step;
  statement* body;
};
extern statement* create_for( const char*, expression*, expression*, expression*, statement* );

Նախապայմանով ցիկլի մոդելի _while_s ստրուկտուրան ունի երկու դաշտ՝ ցիկլի պայմանի և ցիկլի մարմնի համար։

typedef struct _while_s while_s;
struct _while_s {
  expression* cond;
  statement* body;
};
extern statement* create_while( expression*, statement* );

Պրոցեդուրայի կանչի CALL հրամանը նման է արտահայտություններում ֆունկցիայի կիրառմանը։ _call_s ստրուկտուրայի դաշտերից մեկը կանչվող պրոցեդուրան է, մյուսը արգումենտների ցուցակը.

typedef struct _call_s call_s;
struct _call_s {
  char* func;
  node* argus;
};
extern statement* create_call( const char*, node* );

Հրամանների հաջորդումն էլ պարզապես ցուցակ է։ _sequence_s ստրուկտուրայի elems դաշտը

typedef struct _sequence_s sequence_s;
struct _sequence_s {
  node* elems;
};
extern statement* create_sequence( node* );

Բեյսիկ լեզվի ֆունկցիան բաղկացած է ֆունկցիայի անունից, պարամետրերի ցուցակից և մարմնի հրամաններից։ _function ստրուկտուրան

typedef struct _function function;
struct _function {
  char* name;
  node* parameters;
  statement* body;
};

Ֆունկցիայի JSON ներկայացումը կառուցվում է function_as_json() ֆունկցիայով.

extern void function_as_json( function*, FILE* );

Ամբողջ ծրագրի ծառը պահելու համար նախատեսել եմ _program ստրուկտուրան, որի subs դաշտը ծրագրի ֆունկցիաների ցուցակն է.

typedef struct _program program;
struct _program {
  node* subrs;
};

Իսկ program_as_json() ֆունկցիան ամբողջ ծրագիր ծառից ստանում է դրա JSON ներկայացումը.

extern void program_as_json( program*, FILE* );

Bison նկարագրության ընդլայնում

Երբ արդեն պատրաստ են աբստրակտ քերականական ծառի բաղադրիչները, պետք է դրա ինտերֆեյսն օգտագործել վերլուծիչում և տրված Բեյսիկ ծրագրի համար կառուցել վերլուծության ծառը։ Բայց, մինչև այդ հիմնական գործին անցնելը, ես պետք է մի քանի բաներ պատմեմ Bison֊ի քերկանական կանոնների մասին․ ցույց տամ, թե ինչպես են քերականական կանոնի տարրերի արժեքները (լեքսեմներ) օգտագործվում ԱՔԾ֊ի հանգույցների կոնստրուկտորների համար։ Bison֊ում քերականական կանոնը բաղկացած է : նիշով իրարից բաժանված ձախ ու աջ մասերից։ Ձախ մասում ոչ տերմինալային սիմվոլ է, աջ մասում՝ տերմինալային և ոչ տերմինալային սիմվոլների հաջորդականություն։ Օրինակ, WHILE հրամանի շարահյուսական տեսքն այսպիսինն է․

Statement
    : xWhile Expression NewLines StatementList xEnd xWhile
    ;

Քերականական կանոնի անդամներից ամեն մեկի արժեքը ստանալու համար Bison֊ը դրա սիմվոլներին կցում է փսևդոփոփոխականներ։ Քերականական կանոնի ձախ մասին համապատասխանեցվում է $$ անունը, իսկ աջ մասի տարրերին՝ $1, $2, ..., $n հաջորդական անունները։ WHILE հրամանի կանոնի համար․

   $$
Statement
        $1       $2        $3         $4        $5    $6
    : xWhile Expression NewLines StatementList xEnd xWhile
    ;

Հենց այս փոփոխականների միջոցով են քերականական սիմվոլների արժեքներն օգտագործվում աբստրակտ քերականական ծառի հանգույցները կառուցելու (կամ վերլուծության ընթացքում հաշվարկներ կատարելու) համար։ Օրինակ, WHILE հրամանին համապատասախան օբյեկտը կառուցելու համար պետք է վերը բերված կանոնը լրացնել գործողությամբ․

Statement
    : xWhile Expression NewLines StatementList xEnd xWhile
    {
      $$ = create_while($2, $4);
    }
    ;

Սակայն այստեղ մի խնդիր կա։ Քերականական սիմվոլների լռելության տիպը int է, իսկ, օրինակ, create_while() կոնստրուկտորը սպասում է expression* ու statement* և վերադրձնում է statement*։ Bison֊ի %union կառուցվածքը հնարավորություն է տալիս քերականական սիմվոլների տիպը սահմանել միավորման միջոցով։ Այսպես, վերլուծելով Բեյսիկի քերականությունը, տեսնում եմ, որ քերականական սիմվոլները վեց տիպի են․ թվային հաստատուն (double), իդենտիֆիկատոր (char*), արտահայտություն (expression*), հրաման (statement*), ֆունկցիա (function*) և զանազան ցուցակներ (node*)։ Bison֊ի նկարագրության ֆայլի առաջին՝ հայտարարությունների բաժնում սահմանում եմ %union կառուցվածքը՝ չմոռանալով %{...%} սեգմենտում կցել ast.h ֆայլը․

%union {
  double number;    // իրական թիվ
  char* name;       // իդենտիֆիկատոր
  expression* expr; // արտահայտություն
  statement* stat;  // հրաման
  function* func;   // ֆունկցիա
  node* list;       // ցուցակ
}

Իսկ %type հրահանգով յուրաքանչյուր քերականական սիմվոլի համապատասխանեցնում եմ %union տիպի մի դաշտ։

%type <func> Function
%type <func> FunctionHeader

%type <stat> Statement
%type <stat> ElsePart

%type <expr> Expression
%type <expr> StepOpt

%type <list> ParameterList
%type <list> IdentifierList
%type <list> StatementList
%type <list> ElseIfPartList
%type <list> ArgumentList
%type <list> ExpressionList

Տերմինալային սիմվոլների համար %union֊ի դաշտը կարելի է նշել հենց %token հրահանգով։ xIdent և xNumber սիմվոլների համար պետք է գրել․

%token <name> xIdent
%token <number> xNumber

Երբ այս լրացումներից հետո parser.y ֆայլը տալիս եմ Bison֊ի մուտքին, ստանում եմ սխալների մասին հաղորդագրությունների մի երկար շարք։ Ահա այդ հաղորդագրություններից մի քանիսը․

parser.y:90.7-29: warning: type clash on default action: <func> != <> [-Wother]
     : xDeclare FunctionHeader
       ^^^^^^^^^^^^^^^^^^^^^^^
parser.y:95.7-53: warning: type clash on default action: <func> != <> [-Wother]
     : xFunction xIdent '(' ParameterList ')' NewLines
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
parser.y:100.11-16: warning: empty rule for typed nonterminal, and no action [-Wother]
    | %empty
           ^^^^^^

Առաջին հաղորդագրությունն ասում է, թե Function : xDeclare FunctionHeader կանոնի համար տիպերի անհամապատասխանություն է լռելության գործողության (default action) ժամանակ․ <func> != <>։ Ի՞նչ է այդ default action֊ը։ Բանն այն է, որ եթե Bison֊ի որևէ քերականական կանոնի համար գործողություն տրված չէ, ապա լռելության գործողություն է համարվում $$ = $1; վերագրումը։ Իմ դեպքում Function֊ի տիպը սահմանված է որպես function* (նրա համար նշված է %union֊ի func դաշտը), իսկ xDeclare տերմինալային սիմվոլի համար տիպ տրված չէ։ Հետևաբար $$ = $1; վերագրման ժամանակ ծագելու է տիպերի անհամապատասխանություն։ Սխալների այս խմբաքանակն ուղղելու (իսկ ավելի ճիշտ՝ լռեցնելու) համար պարզապես պետք է Bison֊ի նշած սխալ պարունակող կանոնների համար գրել «փուչ» կանոններ։ Օրինակ, վերը բերված մի քանի սխալների համար․

...
Function
    : xDeclare FunctionHeader
    {}
    | FunctionHeader StatementList xEnd xFunction NewLines
    ;
FunctionHeader
    : xFunction xIdent '(' ParameterList ')' NewLines
    {}
    ;
ParameterList
    : IdentifierList
    | %empty
    {}
    ;
...

Նույնն անելով Bison֊ի ազդարարած մյուս սխալների համար, ստանում եմ «մաքուր» նկարագրություն, որտեղ տիպերի տեսակետից ամեն ինչ համաձայնեցված է, բայց դեռ օգտակար գործողություններ չկան։ Անցնեմ առաջ։ Ես սովորություն ունեմ աբստրակտ քերականական ծառի կառուցումը սկսել «ամենամանր» տարրերից։ Տվյալ դեպքում սկսում եմ արտահայտություններից։ Նախ՝ պարզ տարրերը․ թվերի ու փոփոխականների համար ծառի տերևներ են կառուցվում համապատասխանաբար create_number() և create_variable() կոնստրուկտորներով․

Expression
    : ....
    | xNumber
    {
      $$ = create_number($1);
    }
    | xIdent
    {
      $$ = create_variable($1);
    }
    ;

Պարզ է, որ xNumber և xIdent տերմինալային սիմվոլների արժեքը պետք է փոխանցվի բառային վերլուծիչից։ Տվյալ երկու կանոններից առաջինի դեպքում $1 փսևդոփոփոխականը պետք է պարունակի բառային վերլուծիչի կարդացած լեքսեմի թվային արժեքը, իսկ երկրորդի դեպքում՝ yytext բուֆերի պատճենը։ Bison֊ի գեներացրած ֆայլում քերականական սիմվոլի տիպ ունեցող yylval (lexeme value) փոփոխականը նախատեսված է բառային վերլուծիչից շարահյուսական վերլուծիչ արժեքներ փոխանցելու համար։ Ֆունկցիայի կիրառման և ունար գործողությունների հանգույցները կառուցվում են համապատասխանաբար create_apply() և create_unary() կոնստրուկտորներով․

Expression
    : ....
    | xIdent '(' ArgumentList ')'
    {
      $$ = create_apply($1, $3);
    }
    | xSub Expression %prec xNot
    {
      $$ = create_unary(NEG, $2);
    }
    | xNot Expression
    {
      $$ = create_unary(NOT, $2);
    }
....

Գործողությունների նախապատվության բարձրացման ու խմբավորման համար օգտագործվող ( և ) փակագծերի մշակումը պարզից էլ պարզ է․

Expression
    : ....
    | '(' Expression ')'
    {
      $$ = $2;
    }
....

Բինար գործողություններին համապատասխանող բոլոր հանգույցները կառուցվում են նույն create_binary() կոնստրուկտորով, որի առաջին պարամետրը գործողության անունն է։ Այդ անունները սահմանված են _expression ստրուկտուրայի մեջ՝ որպես անանուն թվարկման անդամներ։

Expression
    : Expression xOr Expression
    {
      $$ = create_binary(OR, $1, $3);
    }
    ...
    | Expression xEq Expression
    {
      $$ = create_binary(EQ, $1, $3);
    }
    | Expression xNe Expression
    {
      $$ = create_binary(NE, $1, $3);
    }
    ...
    | Expression xAdd Expression
    {
      $$ = create_binary(ADD, $1, $3);
    }
    ...
    | Expression xMul Expression
    {
      $$ = create_binary(MUL, $1, $3);
    }
....

Աբստրակտ քերականական ծառում հրամաններին (ղեկավարող կառուցվածքներին) համապատասխանող հանգույցները կառուցվում են համապատասխան կոնստրուկտորներով։

Statement
    : xInput xIdent
    {
      $$ = create_input($2);
    }
    | xPrint Expression
    {
      $$ = create_print($2);
    }
    | LetOpt xIdent xEq Expression
    {
      $$ = create_assign($2, $4);
    }
    | xIf Expression xThen NewLines StatementList ElseIfPartList ElsePart xEnd xIf
    {
      $$ = create_if($2, create_sequence($5), $6, $7);
    }
    | xFor xIdent xEq Expression xTo Expression StepOpt NewLines StatementList xEnd xFor
    {
      $$ = create_for($2, $4, $6, $7, create_sequence($9));
    }
    | xWhile Expression NewLines StatementList xEnd xWhile
    {
      $$ = create_while($2, create_sequence($4));
    }
    | xCall xIdent ArgumentList
    {
      $$ = create_call($2, $3);
    }
    ;

Այստեղ միայն IF կառուցվածքի կոնստրուկտորն է, որ պարունակում է ավելի շատ դաշտեր, քան _if_s ստրուկտուրան։ _if_s ստրուկտուրան ես գրել եմ երեք դաշետերով՝ cond, thenp elsep։ Նույն IF կառուցվածքի ElseIfPartList տարրը սահմանված է որպես IF֊երի հաջորդականություն, որտեղ ամեն մի հաջորդ IF֊ը կապված է նախորդի elsep անդամին։ Սկզբում ElseIfPartList֊ը սահմանել էի ձախ֊ռեկուրսիվ եղանակով, ու գրել էի մի քիչ երկար կոդ, որը հերթական ELSEIF֊ի համար կառուցած _if_s նմուշը կապում է իրեն նախորդող ELSEIF֊երից վերջինի elsep անդամին։

ElseIfPartList
    : ElseIfPartList xElseIf Expression xThen NewLines StatementList
    {
      statement* anif = create_if($3, create_sequence($6), NULL, NULL);
      if( $1 == NULL )
        $$ = anif;
      else {
        if_s* heif = (if_s*)($1->child);
        while( heif->elsep != NULL )
          heif = (if_s*)(heif->elsep->child);
        heif->elsep = anif;
        $$ = $1;
      }
    }
    | %empty
    {
      $$ = NULL;
    }
    ;

Հետո որոշեցի ձախ֊ռեկուրսիան փոխարինել աջ֊ռեկուրսիայով ու ստացա ավելի պարզ կոդ․

ElseIfPartList
    : xElseIf Expression xThen NewLines StatementList ElseIfPartList 
    {
      $$ = create_if($2, create_sequence($5), $6, NULL);
    }
    | %empty
    {
      $$ = NULL;
    }
    ;

Չնայած, որ Bison֊ը նույն հաջողությամբ ու արդյունավետությամբ մշակում է ձախ ու աջ ռեկուրսիաները, սակայն կա տարբերություն։ Իր աշխատանքում Bison֊ը օգտագործում է երկու կարևոր գործողություններ՝ Shift և Reduce։ Shift գործողության ժամանակ քերականական սիմվոլն ավելացվում է Bison֊ի աշխատանքային ստեկում, իսկ Reduce գործողության շամանակ ստեկից հեռացվում են քերականական կանոնի աջ մասին համապատասխան տարրերը և դրանց փոխարեն ստեկում ավելացվում է նույն կանոնի աջ կողմի ոչ տերմինալային սիմվոլը։ Երբ կանոնը գրված է աջ֊ռեկուրսիվ տեսքով.

ExpressionList
    : Expression ',' ExpressionList
    | Expression
    ;

Bison֊ը նախ կատարում է բոլոր Shift գործողությունները և ստեկում ավելացնում է Expression և , սիմվոլները, ապա վերջում ստեկը Reduce գործողությամբ «կրճատում» է ըստ ExpressionList սիմվոլի սահմանման։ Ստացվում է, որ աջ֊ռեկուրսիվ կանոնները մշակելիս ավելի շատ ստեկ է «ծախսվում»։ Իսկ երբ կանոնն ունի ձախ֊ռեկուրսիվ սահմանում․

ExpressionList
    : ExpressionList ',' Expression
    | Expression
    ;

ապա Reduce գործողություններն ավելի շուտ են կատարվում, և, տվյալ օրինակի դեպքում, «ծախսվում» է ստեկի ամենաշատը երեք տարր։ Ավելի մանրամասն տես John Levine, flex & bison, O'Reilly Media, 2009 գրքում։ Բեյսիկի քերականության այն ձախ֊ռեկուրսիվ կանոնները, որոնք պիտի ցուցակ կառուցեն, ես ձևափոխեցի աջ֊ռեկուրսիվի։ Դա հեշտացնում է կապակցված ցուցակի կառուցումը։ Օրինակ, իդենտիֆիկատորների ցուցակ կառուցելու համար․

IdentifierList
    : xIdent ',' IdentifierList
    {
      $$ = create_node($1, $3);
    }
    | xIdent
    {
      $$ = create_node($1, NULL);
    }
    ;

Լավ, արտահայտություններին ու հրամաններին համապատասխան հանգույցների կառուցման հետ կապված ամենի ինչ, կարծես թե, պարզ է։ Ընթերցողին առաջարկում եմ կարդալ parser.y ֆայլ ու ինքնուրույն հասկանակ այն հատվածները, որոնց մասին ես այս տեքստում չեմ գրել։ Իսկ ես անցնեմ առաջ ու խոսեմ ֆունկցիաներին համապատասխան հանգույցների կառուցման մասին։ Երբ վերլուծիչը հանդիպում է ֆունկցիայի վերնագրի՝ FunctionHeader, ստեղծվում է _function ստրուկտուրայի նմուշ, որտեղ create_function() կոնստրուկտորի երրորդ արգումենտը՝ ֆունկցիայի մարմնի ցուցիչը, NULL է։

FunctionHeader
    : xFunction xIdent '(' ParameterList ')' NewLines
    {
      $$ = create_function($2, $4, NULL);
    }
    ;

Եթե ֆունկցիայի վերնագիրը հանդիպել է որպես ֆունկցիայի հայտարարություն (DECLARE), ստեղծված _function օբյեկտն ավելացվում է ծրագրի ենթածրագրերի ցուցակին։ Ավելորդ չէր լինի, իհարկե, այստեղ ստուգել ֆունկցիայի՝ արդեն մեկ անգամ հայտարարված լինելը։ Իսկ եթե ֆունկցիայի վերնագիրը ֆունկցիայի սահմանման մաս է, ապա նախ՝ տվյալ անունով ֆունկցիան որոնվում է ծրագրի ենթածրագրերի ցուցակում և, եթե այն արդեն հայտարարված է եղել, ապա այդ հայտարարությանն ավելացվում է սահմանվող ֆունկցիայի մարմինը։ Եթե արդեն գոյություն ունեցող ֆունկցիան մարմին ունի, ապա, թերևս, արժե ազդարաել, որ տվյալ անունով ֆունկցիան արդեն սահմանված է։ Այդ բոլոր ստուգումներն ու լրացումները թողնում եմ որպես վարժություն ընթերցողի համար։ (Ստորև բերված երկու կանոններում prog֊ը _program ստրուկտուրայի ինչ֊որ մի տեղ (կետո կասեմ, թե որտեղ) սահմանված ցուցիչ է։)

Function
    : xDeclare FunctionHeader
    {
      $$ = $2;
      prog->subrs = append_to(prog->subrs, $$);
    }
    | FunctionHeader StatementList xEnd xFunction NewLines
    {
      function* fp = function_by_name(prog, $1->name);
      if( fp == NULL )
        prog->subrs = append_to(prog->subrs, $1);
      $1->body = create_sequence($2);
      $$ = $1;
    }
    ;

Bison նկարագրության ընդլայնման մասին այսքանը։ Հիմա իսկը ժամանակն է իրար վրա հավաքելու ամբողջ արված գործն ու տեսնել թե ինչպես է իմ տրանսլյատորը Բեյսիկ լեզվով գրված ծրագիրը թարգմանում JSON ներկայացման։

Գործարկման երկրորդ փորձ

Տրանսլյատորի մուտքի կետը պարունակող main.c ֆայլում պետք է ավելացնել վերը հիշատակված prog օբյեկտի ցուցիչի հայտարարությունը։ Իսկ main() ֆունկցիայում պետք ստեղծել _program ստրուկտուրայի նմուշ ու կապել prog ցուցիչին։ Այնուհետև պետք է ստուգել yyparse() ֆունկցիայի վերադարձրած արժեքը. եթե այն 0 է, ապա վերլուծությունը հաջող է անցել և կարելի է կառուցել JSON ներկայացումը։

/* main.c */

#include <stdio.h>

#include <gc.h>

#include "ast.h"

program* prog = NULL; // ծրագրի ցուցիչը

int main()
{
  prog = GC_MALLOC(sizeof(program));

  extern int yyparse();
  int ok = yyparse();
  if( 0 == ok )
    program_as_json(prog, stdout);

  return ok;
}

Ամբողջ ծրագրի կառուցումը հեշտացնելու համար էլ պատրաստել եմ մի պարզ Makefile.

# Makefile

SOURCES=main.c scanner.yy.c parser.tab.c slist.c ast.c

all: $(SOURCES)
    gcc --std=gnu11 -gdwarf-2 -obasic-s $(SOURCES) -lgc

scanner.yy.c: scanner.l
    flex -oscanner.yy.c scanner.l

parser.tab.c parser.tab.h: parser.y
    bison -d parser.y

clean:
    rm -f *.tab.*
    rm -f *.yy.c
    rm -f *.o
    rm -f basic-s

Հիմա պետք է պարզապես bash հրամանային ինտերպրետատորում ներմուծել make հրամանն ու ստանալ basic-o կատարվող մոդուլը։ Այս basic-o մոդուլը Բեյսիկ ծրագիր տեքստը կարդում է ներմուծման ստանդարտ հոսքից, իսկ կառուցված JSON կոդը դուրս է բերում արտածման ստանդարտ հոսքին։ Ահա գործարկման մի օրինակ․

$ ./basic-s < ../tests/case01.bas
{
  "function" : {
    "name" : "Main",
    "parameters" : {},
    "print" : {
      "number" : 3.140000
    }
  }
}

---

Սկզբնաղբյուր. Yacc֊ի և Lex֊ի մասին