Sunday, June 3, 2018

JavaScript: Լամբդա լեզվի իրականացում (I)

Փորձեր JavaScript-ի և Node.js-ի հետ

JavaScript-ը հերթական ծրագրավորման լեզուն է, որի ուսումնասիրությամբ որոշեցի զբաղվել վերջին մի քանի շաբաթների հանգստյան օրերին։ Քանի որ ինձ մոտ դեռևս կապակցված պատկերացում չկա WEB տեխնոլոգիաների ու դրանց մեջ նաև JavaScript լեզվի դերի մասին, ես ընտրեցի Node.js®-ը։ Այս ընտրությունը ինձ թույլ է տալիս JavaScript ծրագրերը փորձարկել, աշխատեցնել որպես ինքնուրույն ծրագրեր։

Եվ ինչպես միշտ՝ նոր լեզվի ուսումնասիրությունը սկսում եմ մի որևէ փոքր, ոչ բարդ շարահյուսությամբ լեզվի իրականացումով։ Այս անգամ որպես իրականացվող լեզու ընտրել եմ պարզագույն Լամբդա լեզուն։ Ահա դրա քերականությունը.

expression
    = REAL
    | IDENT
    | '(' expression ')'
    | BUILTIN expression+
    | 'if' expression 'then' expression 'else' expression
    | 'lambda' IDENT+ ':' expression
    | 'apply' expression 'to' expression
    .

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

Շարահյուսական վերլուծություն

Լամբդա լեզվով գրված տեքստի վերլուծության parser.js մոդուլը «արտաքին աշխարհին» տրամադրում է (exports) միակ parse ֆունկցիան։ Վերջինս արգումենտում ստանում է վերլուծվող տեքստը և վերադարձնում է աբստրակտ քերականական ծառը։

Նախ՝ տեքստը տրոհվում է լեքսեմների (lexeme) ցուցակի՝ միաժամանակ ամեն մի լեքսեմին կապելով համապատասխան պիտակը (token)։ Այնուհետև շարահյուսական վերլուծիչը, օգտագործելով լեքսեմների ցուցակը, կառուցում է աբստրակտ քերականական ծառը։

Տեքստը լեքսեմների ցուցակի տրոհող scanOne և scanAll ֆունկցիաները գրել եմ ֆունկցիոնալ մոտեցմամբ։ scanOne ֆունկցիան արգումենտում ստանում է տեքստ, և վերադարձնում է եռյակ՝ տեքստի սկզբից «պոկված» լեքսեմը, դրա պիտակը և տեքստի չտրոհված մասը։ Օրինակ, scanOne('if + a b then a else b') կանչի արժեքն է { token: 'IF', value: 'if', rest: ' + a b then a else b'} օբյեկտը։ Տեքստից ինձ հետաքրքրող մասը պոկում եմ կանոնավոր արտահայտություների օգնությամբ։

Կանոնավոր արտահայտությունները JavaScript-ում կարելի է կառուցել կամ RegExp կոնստրուկտորով, կամ օգտագործել դրանց լիտերալային գրառումները։ Օրինակ, ես իդենտիտիֆիկատորները ճանաչող կանոնավոր արտահայտությունը գրել եմ /^[a-zA-z][0-9a-zA-z]*/ տեսքով։ (Տես ECMAScript ստանդարտի RegExp (Regular Expression) Objects բաժինը, ինչպես նաև MDN Web Docs-ի RegExp բաժինը։)

RegExp օբյեկտի exec մեթոդը փորձում է «ճանաչել» տրված տողը։ Եթե այդ փորձը հաջողվում է, ապա մեթոդը վերադարձնում է արդյունքների զանգվածը, հակառակ դեպքում՝ null։ Քանի որ լեքսեմները միշտ փնտրում եմ տրված տողի սկզբում, ապա exec-ի վերադարձրած զանգվածի առաջին տարրը հենց ինձ հետաքրքրող լեքսեմն է։ Որպես վերադարձվող օբյեկտի value սլոթի արժեք վերցնում եմ այդ առաջին տարրը, իսկ տրված տեքստի սկզբից կտրում ու դեն եմ գցում լեքսեմի երկարությամբ հատված։ «Կտրելը» իրականացրել եմ String օբյեկտի substring մեթոդով։

Ահա scanOne ֆունկցիան՝ համապատասխան մեկնաբանություններով.

// Լեզվի ծառայողական բառերի ցուցակը
const keywords = ['if', 'then', 'else', 'lambda', 'apply', 'to', 'and', 'or']

// Տեքստից կարդալ մեկ (թոքեն, լեքսեմ) զույգ
var scanOne = function(text) {
    // եթե տրված տեքստը դատարկ է, ապա վերադարձնել
    // տեքստի վերջը ցույց տվող օբյեկտ
    if( text == '' ) {
        return { token: 'EOS', value:'EOS', rest: '' }
    }

    // երբ տողը սկսվում է բացատանիշերով, ապա դեն նետել
    // դրանք և նօորից կանչել scanOne ֆունկցիան
    let mc = /^[ \n\t\r]+/.exec(text)
    if( mc != null ) {
        return scanOne(text.substring(mc[0].length))
    }

    // եթե տողը տառով սկսվող տառերի ու թվանշանների հաջորդականություն
    // է, ապա հանդիպել է կամ ծառայողական բառ, կամ էլ իդենտիֆիկատոր։
    // եթե լեքսեմը ծառայողական բառերի keywords ցուցակից է, ապա
    // վերադարձվող օբյեկտի token սլոթիի արժեք որոշվում է այդ բառով,
    // հակառակ դեպքում token-ը ստանում է IDENT արժեքը
    mc = /^[a-zA-z][0-9a-zA-z]*/.exec(text)
    if( mc != null ) {
        return {
            token: keywords.includes(mc[0]) ? mc[0].toUpperCase() : 'IDENT',
            value: mc[0],
            rest: text.substring(mc[0].length)
        }
    }

    // իրական թվեր
    mc = /^[0-9]+(\.[0-9]+)?/.exec(text)
    if( mc != null ) {
        return {
            token: 'REAL',
            value: mc[0],
            rest: text.substring(mc[0].length)
        }
    }

    // ծառայողական սիմվոլներ (մետասիմվոլներ) են խմբավորման
    // փակագծերն ու անանուն ֆունկցիայի պարամետրերը մարմնից
    // անջատող երկու կետը
    mc = /^(\(|\)|:)/.exec(text)
    if( mc != null ) {
        return {
            token: mc[0],
            value: mc[0],
            rest: text.substring(mc[0].length)
        }
    }

    // քանի որ լեզվի քերականությունը ներդրված գործողությունները
    // սահմանում է մեկ արտահայտությամբ, ես որոշեցի, որ թվաբանական
    // ու համեմատման գործողությունների նշաններին համապատասխանեցնել
    // մի ընդհանուր OPER պիտակը
    mc = /^(\+|\-|\*|\/|=|<>|>|>=|<|<=)/.exec(text)
    if( mc != null ) {
        return {
            token: 'OPER',
            value: mc[0],
            rest: text.substring(mc[0].length)
        }
    }

    // եթե տրված տեքստը չի համապատասխանում վերը բերված և ոչ մի
    // կանոնի, վերադարձնում եմ UNKNOWN պիտակով օբյեկտ
    return { token: 'UNKNOWN', value: text[0], rest: text }
}

Իսկ scanAll ֆունկցիան կանչում է scanOne ֆունկցիան այնքան ժամանակ, քանի դեռ հերթական կանչի արդյունքում չի ստացվել token == 'EOS' օբյեկտ։

// Կարդալ բոլոր (թոքեն, լեքսեմ) զույգերն ու վերադարձնել ցուցակ
var scanAll = function(text) {
    let res = []
    let ec = scanOne(text)
    while( ec.token != 'EOS' ) {
        res.push({token: ec.token, value: ec.value})
        ec = scanOne(ec.rest)
    }
    res.push({token: 'EOS', value: 'EOS'})
    return res
}

Այս երկու ֆունկցիաները կազմում են Լամբդա լեզվի բառային վերլուծիչը։ Հիմա՝ շարահյուսական վերլուծության մասին։

parse ֆունկցիան scanAll ֆունկցիայով տրոհում է իր արգումենտում ստացված ծրագիրը և լեքսեմների ցուցակը վերագրում է lexemes գլոբալ զանգվածին։ Ըստ էության այս lexemes-ը լեքսեմներ ստեկ է, որից վերլուծիչը տարրերը դուրս է քաշում (pop) ըստ լեզվի քերականական կանոնների։ index գլոբալ հաշվիչը, որը ծառայում է որպես ստեկկի գագաթի ցուցիչ, ստանում է նախնական 0 արժեքը՝ Լամբդա լեզվի բուն շարահյուսական վերլուծիչն իրականացված է expression ֆունկցիայում. parse ֆունկցիան վերադարձնում է հենց վերջինիս արժեքը։

// (թոքեն, լեքսեմ) զույգերի ցուցակ
var lexemes = []
// ընթացիկ օգտագործվող տարր ինդեքսը
var index = 0;

// ծրագրի տեքստի վերլուծություն
var parse = function(text) {
    lexemes = scanAll(text)
    index = 0
    return expression()
}

Բայց, մինչև expression-ին անցնելը, մի քանի օգնական ֆունկցիաների մասին։ have ֆունկցիան վերադարձնում է true, եթե լեքսեմների ստեկի գագաթի տարրի պիտակը հավասար է արգումենտում տրված պիտակին կամ պիտակներից որևէ մեկին։ Այս ֆունկցիայի արգուենտը կարող է լինել ինչպես առանձին պիտակ, այնպես էլ պիտակների վեկտոր։

// ստուգել ցուցակի ընթացիկ տարրը
var have = function(exp) {
    let head = lexemes[index].token

    if( exp instanceof Array )
        return exp.includes(head)

    return head == exp
}

Հաջորդ, next ֆունկցիան մեկով ավելացնում է լեքսեմների ինդեքսը. մոդելավորում է ստեկի pop գործողությունը՝ դիտարկելի դարձնելով լեքսեմների ցուցակի հաջորդ տարրը։ Բայց վերադարձնում է ստեկից հանված տարրի value սլոթի արժեքը։

// անցնել հաջորդին, և վերադարձնել նախորդի արժեքը
var next = function() {
    return lexemes[index++].value
}

match ֆունկցիան համադրում է have և next ֆունկցիաները. եթե լեքսեմների ցուցակի հերթական դիտարկվող տարրի պիտակը հավասաար է match-ի արգումենտին, ապա դիտարկելի դարձնել հաջորդ տարրը։ Եթե հավասար չէ, ապա ազդարարվում է շարահյուսական սխալի մասին։

// ստուգել և անցնել հաջորդին
var match = function(exp) {
    if( have(exp) )
        return next()
    throw `Syntax error: expected ${exp} but got ${lexemes[index].value}`
}

expression ֆունկցիայի կառուցվածքը ուղղակիորեն արտացոլում է այս գրառման սկզբում բերված քերականությանը։ Ինչպես քերականությունն աջ մասն է բաղկացած յոթ այլընտրանքներից (տարբերակներից), այնպես էլ expression ֆունկցիան է կազմված յոթ տրամաբանական հատվածներից։ Ամեն մի հատվածը ձևավորում ու վերադարձնում է աբստրակտ քերականական ծառի մի որևէ հանգույց։ Այդ հանգույցներն ունեն kind սլոթը, որով որոշվում է հանգույցի տեսակը։ Ստորև բերված է expression ֆունկցիան՝ մանրամասն մեկնաբանություններով.

// Լամբդա լեզվի արտահայտությունները կարող են սկսվել միայն հետևյալ
// պիտակներով։ Գրականության մեջ այս բազմությունը կոչվում է FIRST.
// FIRST(expression)
const exprFirst = ['REAL', 'IDENT', '(', 'OPER', 'IF', 'LAMBDA', 'APPLY']

// Արտահայտությունների վերլուծությունը
var expression = function() {
    // եթե դիտարկվող լեքսեմը իրական թիվ է,
    // ապա վերադարձնել AST-ի հանգույց, որի
    // տիպը REAL է
    if( have('REAL') ) {
        let vl = next()
        return { kind: 'REAL', value: parseFloat(vl) }
    }

    // եթե լեքսեմը իդենտիֆիկատոր է, ապա կառուցել
    // փոփոխականի (անուն) հղում ներկայացնող հանգույց
    if( have('IDENT') ) {
        let nm = next()
        return { kind: 'VAR', name: nm }
    }

    // եթե լեքսեմը բացվող փակագիծ է, ապա վերադարձնել
    // փակագծերի ներսում գրված արտահայտության ծառը
    if( have('(') ) {
        next()
        let ex = expression()
        match(')')
        return ex
    }

    // Լամբդա լեզվի օգտագործումը մի քիչ ավելի հեշտացնելու
    // համար ես դրանում ավելացրել եմ ներդրված գործողություններ։
    // դրանք պրեֆիքսային են, ինչպես Լիսպում՝ ցուցակի առաջին
    // տարրը գործողության նիշն է, որը կարող է լինել թվաբանական,
    // համեմատման կամ տրամաբանական գործողություն
    if( have('OPER') ) {
        // վերցնել գործողության նիշը
        let op = next()
        // վերլուծել առաջին արտահայտությունը
        let args = [ expression() ]
        // քանի դեռ հերթական լեքսեմը պատկանում է FIRST(expression)
        // բազմությանը, վերլուծել հաջորդ արտահայտությունը
        while( have(exprFirst) )
            args.push(expression())
        // կառուցել լեզվի ներդրված գործողության հանգույցը
        return { kind: 'BUILTIN', operation: op, arguments: args }
    }

    // պայմանական արտահայտությունը բաղկացած է if, then, else
    // ծառայողական բառերով բաժանված երեք արտահայտություններից
    if( have('IF') ) {
        next()
        // վերլուծել պայմանի արտահայտությունը
        let co = expression()
        match('THEN')
        // վերլուծել պայմանի ճիշտ լինելու դեպքում
        // հաշվարկվող արտահայտությունը
        let de = expression()
        match('ELSE')
        // պայմանի կեղծ լինելու դեպքում հաշվարկվող
        // արտահայտությունը
        let al = expression()
        // պայմանակա արտահայտության հանգույցը
        return { kind: 'IF', condition: co, decision: de, alternative: al }
    }

    // անանուն ֆունկցիայի սահմանումը սկսվում է lambda
    // բառով, որին հաջորդում են ֆունկցիայի պարամետրերը,
    // (ֆունկցիան պիտի ունենա գոնե մեկ պարամետր), հետո,
    // «:» նիշից հետո ֆուկցիայի մարմինն է
    if( have('LAMBDA') ) {
        next()
        // պարամետրերը
        let ps = [ match('IDENT') ]
        while( have('IDENT') )
            ps.push(next())
        match(':')
        // մարմինը
        let by = expression()
        // անանուն ֆունկցիայի հանգույցը
        return { kind: 'LAMBDA', parameters: ps, body: by, captures: [] }
    }

    // apply գործողությունը իրեն հաջորդող արտահայտությունը
    // կիրառում է to բառից հետո գրված արտահայտություններին
    if( have('APPLY') ) {
        next()
        // վերլուծել կիրառելի աարտահայտությունը
        let fn = expression()
        match('TO')
        // վերլուծել արգումենտները
        let args = [ expression() ]
        while( have(exprFirst) )
            args.push(expression())
        // ֆունկցիայի կիրառման հանգույցը
        return { kind: 'APPLY', callee: fn, arguments: args }
    }

    // բոլոր այլ դեպքերում ազդարարել շարահյուսական սխալի մասին
    throw 'Syntax error.'
}

Վերջում նշեմ, որ Լամբդա լեզվի վերլուծիչն իրականացրել եմ ռեկուրսիվ վայրէջքի եղանակով։ Այդ մասին կարելի է կարդալ ծրագրավորման լեզուների իրականացմանը նվիրված ցանկացած գրքում։

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

Լամբդա լեզվով գրված ծրագրի վերլուծության արդյունքում կառուցվում է աբստրակտ քերականական ծառ, որի հանգույցների տեսակը որոշվում է kind սլոթով։ Օրինակ, parse('3.14') կիրառման արդյունքում կառուցվում է { kind: 'REAL', value: 3.14 } օբյեկտը, որի kind սլոթի REAL արժեքը ցույց է տալիս, որ սա իրական թիվ ներկայացնող հանգույց է, իսկ value սլոթի արժեքն էլ թվի մեծությունն է։

Մեկ այլ օրինակ, parse('+ 3.14 x') ծրագրի վերլության արդյունքում կառուցվում է հետևյալ օբյեկտը.

{ kind: 'BUILTIN',
  operation: '+',
  arguments: [ { kind: 'REAL', value: 3.14 }, { kind: 'VAR', name: 'x' } ] }

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

lambda x : * x x լամբդա արտահայտության վերլուծության արդյունքում կառուցվում է մի օբյեկտ, որում kind == 'LAMBDA', պարամետրերի ցուցակը պարունակում է միայն x փոփոխականի անունը, իսկ մարմինը բազմապատկման ներդրված գործողությունը ներկայացնող հանգույց է (captures սլոթի մասին կխոսեմ լամբդա արտահայտությունների ինտերպրետացիայի բաժնում)։

{ kind: 'LAMBDA',
  parameters: [ 'x' ],
  body:
   { kind: 'BUILTIN',
     operation: '*',
     arguments: [ [Object], [Object] ] },
  captures: {} }

Ինտերպրետացիա

Լամբդա ծրագրի վերլուծության արդյունքում կառուցված ծառի ինտերպրետացիայի evaluate ֆունկցիան նույնպես կառուցված է ռեկուրսիվ սխեմայով։ Դր առաջին արգումենտը ծրագրի աբստրակտ քերականական ծառն է, իսկ երկրորդը՝ հաշվարկման միջավայրը։ Վերջինս մի արտապատկերում է (map), որում փոփոխականներին համապատասխանեցված են ընթացիկ արժեքները։ Քանի որ Լամբդա լեզվում վերագրման գործողություն չկա, փոփոխականներին արժեքներ կարող են կապվել ֆունկցիայի պարամետրերի օգնությամբ։

var evaluate = function(expr, env) { /* ... */ }

Ինչպես երևում է expression ֆունկցիայից, վերլուծության արդյուքնում կառուցվում են վեց տեսակի հանգույցներ. REAL, VAR, BUILTIN, IF, LAMBDA և APPLY։ evaluate ֆունկցիայում դիտարկվում են այս վեց դեպքերը։ Հիմա ես հերթով ու հնարավորինս մանրամասն կներկայացնեմ նշված վեց հանգույցների հաշվարկման եղանակները։

REAL տիպի հանգույցի հաշվարկման արդյունքը դրա value սլոթի արժեքն է։

if( expr.kind == 'REAL' ) {
    return expr.value
}

VAR տիպի հանգույցի հաշվարկման արժեքը ստանալու համար միջավայրից վերադարձնում եմ name սլոթին կապված արժեքը։

if( expr.kind == 'VAR' ) {
    return env[expr.name]
}

BUILTIN տիպի հանգույցի արժեքը ստանալու համար պետք է նախ հաշվարկել arguments ցուցակի արտահայտությունների արժեքները, ապա գրանց նկատմամբ կիրառել operation սլոթում գրանցված գործողությունը։

if( expr.kind == 'BUILTIN' ) {
    let evags = expr.arguments.map(e => evaluate(e, env))
    return evags.reduce(builtins[expr.operation])
}

IF տիպի հանգույցը, որ պայմանական արտահայտության մոդելն է, հաշվարկելու համար նախ հաշվարկվում է condition սլոթի արժեքը՝ պայմանը։ Եթե այն տարբեր է 0.0 թվային արժեքից՝ ճշմարիտ է, ապա հաշվարկվում և վերադարձվում է decision սլոթի արժեքը։ Եթե condition-ի արժեքը զրո է, ապա հաշվարկվում ու վերադարձվում է alternative սլոթին կապված արտահայտության արժեքը։

if( expr.kind == 'IF' ) {
    let co = evaluate(expr.condition, env)
    if( co !== 0.0 )
        return evaluate(expr.decision, env)
    return evaluate(expr.alternative, env)
}

LAMBDA տիպի հանգույցի հաշվարկման արդյունքում պիտի կառուցվի մի օբյեկտ, որը կոչվում է closure (չգիտեմ, թե հայերեն սրան ինչ են ասում)։ Իմաստն այն է, որ LAMBDA օբյեկտի captures սլոթում գրանցվում են body սլոթին կապված արտահայտության ազատ փոփոխականների արժեքները՝ հաշվարկված ընթացիկ միջավայրում։ Այս կերպ լրացված LAMBDA օբյեկտն արդեն հնարավոր կլինի apply գործողության կիրառել արգումենտների նկատմամբ։ (Արտահայտության մեջ մտնող ազատ փոփոխականների բազմությունը հաշվարկող freeVariables ֆունկցիայի մասին քիչ ավելի ուշ)։

if( expr.kind == 'LAMBDA' ) {
    let clos = Object.assign({}, expr)
    let fvs = freeVariables(clos)
    for( let v of fvs )
        clos.captures[v] = env[v]
    return clos
}

Մի օրինակ. թող որ տրված է lambda y : + x y արտահայտությունը և { 'x': 7 } հաշվարկման միջավայրը։ Ինչպես արդեն նշեցի վերլուծության մասին պատմելիս, այս տրված ծրագրի վերլուծությունը կառուցելու է այսպիսի մի օբյեկտ.

{ kind: 'LAMBDA',
  parameters: [ 'y' ],
  body:
   { kind: 'BUILTIN',
     operation: '+',
     arguments: [ [Object], [Object] ] },
  captures: {} }

Երբ այս օբյեկտը հաշվարկում եմ { 'x': 7 } միջավայրում, ստանում եմ նույն օբյեկտը, բայց արդեն լրացված captures սլոթով։

{ kind: 'LAMBDA',
  parameters: [ 'y' ],
  body:
   { kind: 'BUILTIN',
     operation: '+',
     arguments: [ [Object], [Object] ] },
  captures: { x: 7 } }

apply f to e0 e1 ... en արտահայտության հաշվարկման սեմանտիկան (իմաստը) f ֆունկցիայի՝ e0 e1 ... en արտահայտությունների նկատմամբ կիրառելն է։ Քանի որ, ըստ Լամբդա լեզվի քերականության, f-ը նույնպես արտահայտությունը է, ապա նախ՝ պետք է հաշվարկել այն և համոզվել, որ ստացվել է կիրառելի օբյեկտ՝ closure (թող դա կոչվի f'), որի captures-ը պարունակում է լամբդայի մարմնի ազատ փոփոխականների արժեքները (bindings)։ Հետո պետք է հաշվարկել APPLY օբյեկտի arguments սլոթին կապված ցուցակի արտահայտությունները՝ կիրառման արգումենտները, ու դրանք ըստ հերթականության կապել closure-ի պարամետրերին։ Եվ վերջապես, f' օբյեկտի մարմինը հաշվարկել մի միջավայրում, որը կառուցված է closure-ի captures-ի և պարամետրերի ու արգումենտների արժեքների համադրումով։ (Էս պարբերությունը ոնց որ մի քիչ լավ չստացվեց։)

if( expr.kind == 'APPLY' ) {
    let clos = evaluate(expr.callee, env)
    if( clos.kind != 'LAMBDA' )
        throw 'Evaluation error.'
    let nenv = Object.assign({}, clos.captures)
    let evags = expr.arguments.map(e => evaluate(e, env))
    let count = Math.min(clos.parameters.length, evags.length)
    for( let k = 0; k < count; ++k )
        nenv[clos.parameters[k]] = evags[k]
    return evaluate(clos.body, nenv)
}

Օգտագործումը

Ամեն մի իրեն հարգող ինտերպրետատոր, առավել ևս՝ ֆունկցիոնալ լեզվի իրականացում, պետք է ունենա այսպես կոչված REPL (read-eval-print loop, կարդալ-հաշվարկել-արտածել-կրկնել)։ Դրա իրականացումը օգտագործողին առաջարկում է ներմուծել արտահայտություն, ապա հաշվարկում է այն և արտածում է արժեքը։ Այս երեք քայլերը կրկնվում են այնքան ժամանակ, քանի դեռ օգտագործողը, ի որևէ հատուկ հրամանով, չի ընդհատում աշխատանքը։

Որպես հրավերք ես ընտրել եմ հունարեն λάμδα բառը, իսկ որպես աշխատանքի ավարտի ազդանշան՝ /// նիշերը։ Օգտագործող-ինտերպրետատոր երկխոսության կազմակերպման համար օգտագործել եմ Node.js®-ի readline գրադարանը: Ստորև բերված repl ֆունկցիայի կոդի մասին շատ մանրամասներ չեմ կարող ասել, որովհետև ինքս էլ նոր եմ ծանոթանում դրան ու փորձում եմ հասկանալ պատահար-ների (event) հետ աշխատանքի սկզբունքները։

var repl = function() {
    var rr = rl.createInterface({
        input: process.stdin,
        output: process.stdout,
        prompt: 'λάμδα> ',
        terminal: false
    });

    rr.prompt()

    rr.on('line', (line) => {
        if( line == 'end' ) {
            rr.close()
            return
        }

        console.info(ev.evaluate(ps.parse(line), {}))
        rr.prompt()
    }).on('close', () => {
        console.info('Bye')
        process.exit(0)
    });
}

Բացի երկխոսության ռեժիմից, Լամբդայի ինտերպրետատորը կարելի է աշխատեցնել նաև հրամանային տողում տալով լամբդա արտահայտությունը պարունակող ֆայլը։ evalFile ֆունկցիայւոմ նախ ստուգում եմ տրված ֆայլի գոյությունը, ապա readFileSync ֆունկցիայով կարդում եմ դրա ամբողջ պարունակությունը։ Հաշվարկումը կատարվում է ճիշտ այնպես, ինչպես REPL-ում ներմուծված տողի հաշվարկը։

var evalFile = function(path) {
  if( !fs.existsSync(path) ) return;

  let prog = fs.readFileSync(path, {encoding: 'utf-8'})
  console.info(ev.evaluate(ps.parse(prog), {}))
}

Աշխատանքային ռեժիմի ընտրությունը կատարվում է հրամանային տողում տրված արգումենտների քանակը ստուգելով։ Եթե process.argv.length > 2, ապա ենթադրում եմ, որ հրամանային տողում տրված է ծրագիրը պարունակող ֆայլ, և կանչվում է evalFile ֆունկցիան։ Հակառակ դեպքում գործարկվում է REPL-ը։

if( process.argv.length > 2 ) {
    evalFile(process.argv[2])
}
else {
    repl()
}

Ընդլայնումներ

Չնայած որ իրականացված լեզուն բավարար է թվային ալգորիթմների իրականացման համար, այնուամենայնիվ այն դեռ բավականին «անհարմար» գործիք է։ Օրինակ, ես կարող եմ սահմանել անանուն ֆունկցիաներ ու դրանք կիրառել արգումենտների (արտահայտությունների) նկատմամբ, ինչպես նաև (երևի թե) կարող եմ ռեկուրսիայի օգնությամբ, օգտագործելով որևէ ֆիքսված կետի կոմբինատոր, գրել կրկնություն պարունակող ալգորիթմներ, և այլն։ Ավելի մանրամասն տես, օրինակ, The Lambda Calculus tanford Encyclopedia of Philosophy էջում։ Բայց, քիչ թե շատ հարմար, ընթեռնելի ու հասկանալի ծրագրեր գրելու համար ինձ պետք է, առաջին հերթին, ունենալ սահմանումների մեխանիզմ։ Հենց թեկուզ հանրահայտ let-ը։ Լամբդա լեզվում այն կարող է ունենալ այսպիսի տեսք.

let
  pi is 3.1415
in
  lambda r : * pi r r

Այստեղ նախ՝ pi սիմվոլին կապվում է 3.1415 արժեքը, ապա՝ let-ի մարմնում pi-ն օգտագործվում է արտահայտության մեջ։

Մի այլ օրինակ։ Թվի ֆակտորիալը հաշվող պապենական ֆունկցիան կարող է սահմանվել հետևյալ կերպ.

let
  fact is lambda n : if (= n 1) then 1 else * n (apply fact to - n 1)
in
  apply fact to 10

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

Լեզվի մեկ այլ ընդլայնում կարող է լինել նոր տիպերի հետ աշխատանքը. օրինակ, տեքստային տիպ և ցուցակներ։ Հենց թեկուզ այս երկու տիպերը կարող են էապես ընդլայնել Լամբդա լեզվով մոդելավորվող ալգորիթմների շրջանակը։

Վերջ

Վերջ՝ չնայած բոլոր թերություններին ու կիսատ-պռատ իրականացված մասերին։ Մի որոշ ժամանակ անց, երբ ավելի լավ կուսումնասիրեմ JavaScript լեզուն, ես կփորձեմ շտկել պակասող մասերն ու ավելի գրագետ իրականացնել վերլուծիչն ու ինտերպրետատորը։

Աղբյուրներ

Ֆունկցիոնալ լեզվի իրականացման հարցերը քննարկվում են շատ գրքերում ու հոդվածներում։ Ես անհրաժեշտ եմ համարում դրանցից մի քանիսի թվարկումը.

  1. Christian Queinnec, Lisp in Small Pieces, Cambridge University Press, 2003.
  2. Peter Norvig, Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, Morgan Kaufmann, 1991.
  3. Harold Abelson, Jerald Jay Sussman, Julie Sussman, Structure and Interpretation of Computer Programs, 2nd Edition, MIT Press, 1996.
  4. Peter Norvig, (How to Write a (Lisp) Interpreter (in Python)) և (An ((Even Better) Lisp) Interpreter (in Python)).
  5. John McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I.
  6. Paul Graham, The Roots of Lisp.

Saturday, April 21, 2018

Ալգորիթմական լեզվի մասին

Նախաբան

Անցյալ դարի վերջերին միջնակարգ դպրոցի «Ինֆորմատիկա» առարկան, որի լրիվ անունն էր «Ինֆորմատիկայի և հաշվողական տեխնիկայի հիմունքներ», ամբողջությամբ նվիրված էր ծրագրավորմանը։ Իսկ քանի որ դպրոցների հիմնական մասում հմակարգիչներ չկային, մշակվել էր, ինֆորմատիկայի՝ այսպես կոչված «առանց ԷՀՄ»֊ի դասավանդման եղանակը։ Ալգորիթմական մտածելության ու ծրագրավորման հմտությունների զարգացման համար դասագրքերում օգտագործվում էին կա՛մ բլոկ֊սխեմաները, կա՛մ Ալգորիթմական լեզուն։ Առաջինի մասին երևի գիտեն բոլորը, քանի որ նույնիսկ ժամանակակից դասագրքերում դրանք հադիպում են հիմնականում ծրագրավորման լեզուների ղեկավարող կառուցվածքների նշանակությունը բացատրելու համար (այլ ոչ թե ալգորիթմները ներկայացնելու համար)։

Ալգորիթմական լեզուն, թերևս, մոռացվել է այն պատճառով, որ դպրոցներում դրա համար երբեք իրականացում (կոմպիլյատոր, ինկերպրետատոր կամ ծրագրավորման միջավայր) չի եղել։ Միգուցե անհետաքրքիր, անիմաստ կամ պարզապես անհարմար էր հայերեն ծառայողական բառերով լեզու օգտագործելը։ Օրինակ, երկու իրական թվերից մեծագույնը գտնելու ծրագիրը ալգորիթմական լեզվով կարելի է գրել այսպես․

ալգ իրկ մեծը(իրկ ա, բ)
  արգ ա, բ
սկիզբ
  եթե ա > բ
    ապա արժեք := ա
    այլապես արժեք := բ
  ավարտ
վերջ

Կամ, օրինակ, ամբողջ թվերի զանգվածում տրված արժեքի գծային որոնման ալգորիթմը կարելի է գրել մոտավորապես այսպես․

ալգ ամբ որոնել(ամբ գ, աղյուսակ տ[0:u], ք)
  արգ գ, տ, ք
սկիզբ
  թող ի սկսած 0 մինչև ք
  ցս
    եթե գ = տ[ի]
      ապա արժեք := ի
    ավարտ
  ցվ
վերջ

Ընդհանուր առմամբ ալգորիթմական լեզուն Ալգոլ (Algol) լեզվից ժառանգված մի գործիք էր՝ հարմարեցված ուսումնական նպատակների, և հատկապես «առանց ԷՀՄ» մոտեցմամբ դասավանդման համար։

Պետք է նշել, որ Մոսկվայի պետական համալսարանում ստեղծվել է ալգորիթմական լեզվի իրականացում՝ ռուսերեն ծառայողական բառերով։ Ոչ միայն իրականացում, այլև բավականին հարուստ ու հետաքրքիր ծրագրավորման միջավայր։ Արդեն XXI դարում, ինչ֊որ փորձեր եղան վերակենդանացնել այդ լեզուն КуМир համակարգի տեսքով, բայց չեմ կարծում, թե դա հառողություն կունենա։ Այսօր արդեն շատ են մեկը մեկից գեղեցիկ ու նորարարական ուսուցողական համակարգերը։ Դժվար թե որևէ մեկն ուզենա ծրագրավորում սովորել Scratch-ից, Python֊ից, Racket֊ից ու այլ ժամանակակից լեզուներից նախընտրելով Ալգորիթմական լեզուն կամ КуМир֊ը։ Ալգորիթմական լեզուն այսօր կարող է ունենալ միայն պատմական նշանակություն։

Ընթացիկ պլաններ

Իմ, այսպես ասած, անհատական զարգացման ծրագում վաղուց նախատեսել էի ուսումնասիրել Ջավա վիրտուալ մեքենայի (JVM) հրամանների համակարգը, ու գրել կոդի գեներատոր՝ որևէ պարզ լեզվի համար։ Սովորաբար որպես լեզու ընտրում եմ BASIC֊ի մի պարզեցված տարատեսակ, որում թողնում եմ մեկ կամ երկու պրիմիտիվ տիպեր, հիմնական ղեկավարող կառուցվածքներն ու ենթածրագրերը։ Այս անգամ հիշեցի Ալգորիթմական լեզվի մասին։ Ու քանի որ, մինչև JVM֊ի համար կոդի գեներատոր գրելը, պիտի գրեի ալգորիթմական լեզվի վերլուծիչ, որոշեցի, ձեռքի հետ, քչփորել նաև ANTLR4 parser generator֊ը։

Այսպիսով՝ ձևակերպվեցին հետևյալ խնդիրները․

  1. Կազմել ալգորիթմական լեզվի ֆորմալ քերականությունը, համոզվել, որ դրա համար հնարավոր է գրել քիչ֊թե շատ խելքը գլխին վերլուծիչ։ Խնդիրը սկզբից ինչ֊որ անհարմարություններ էր խոստանում, քանի որ Ալգորիթմական լեզուն հին դասագրքերում օգտագործված է որպես «թղթի վրայի» լեզու, և դասագիրք գրողներն ու թարգմանողները, կարծես թե, այնքան էլ չեն մտածել լեզվի ֆորմալ կողմի մասին։
  2. ANTLR4 գործիքի օգտագործմամբ գրել շարահյուսական վերլուծիչը։ Չնայած ANTLR4֊ի օգտագործումը շատ մոտ է Bison/Yacc գործիքների օգտագործմանը, այնուամենայնիվ, պետք է ժամանակ տրամադրել առանձնահատկությունները հասկանալու ու դրանց ընտելանալու համար։
  3. Սահմանել աբստրակտ քերականական ծառի հանգույցների դասերի հիերարխիան։ Բնականաբար, այդ դասերը պետք է հարմար լինեն ինչպես ANTLR4֊ի գեներացրած վերլուծիչում օգտագործելու համար, այնպես էլ դրանցից JVM կոդ գեներացնելու համար։
  4. Եվ հիմնականը՝ Apache BCEL գրադարանի օգտագործմամբ վերլուծության ծառից գեներացնել կոռեկտ *.class ֆայլ՝ Ջավա վիրտուալ մեքենայի բայթ֊կոդ։ Այս խնդիրը պիտի ամենաժամանակատարը լինի։
  5. Ամբողջ նախագիծն իրականացնել այնպես, որ այն օգտակար լինի վերը շարադրված նյութով հետաքրքրվողներին։

Քերականության մշակումը

Ալգորիթմական լեզվի քերականությունը կառուցում եմ հիմնականում ըստ հայերեն դասագրքի առաջին ու երկրորդ մասերում բերված օրինակների, երբեմն փորձում եմ հաշվի առնել նաև տեքստում տրված բացատրությունները։ Քերականությունը գրում եմ EBNF գրառմամբ՝ ANTLR4-ում իրականացված տարբերակով։ * ետածանցային (postfix) գործողությունը նշանակում է, որ տարրը կարող է կրկնվել զրո և ավելի անգամներ։ + ետածանցային գործողությունը կրկնությունները սահմանում է մեկ և ավելի անգամների համար։ ? ետածանցային գործողությունը ցույց է տալիս տարրի ոչ պարտադիր առկայությունը (զրո կամ մեկ անգամ)։ ( և ) փակագծերով տարրերը խմբավորվում են, իսկ | գործողությամբ նշվում են այնըտրանքները։ Քերականական կանոնների ոչ տերմինալային սիմվոլները պետք է սկսել փոքրատառով, իսկ տերմինալայինները՝ մեծատառով։ Քերակականական հավասարման ձախ ու աջ մասերն անջատվում են : նիշով, իսկ հավասարումն ավարտվում է ; նիշով։ Այս բաժինը նաև ANTLR4 գործիքի հետ աշխատանքի փորձի կուտակում է։

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

grammar Alg0;

program
    : NL? algorithm*
    ;

Ալգորիթմը սկսվում է ալգ ծառայողական բառով, որին հաջորդում են վերադարձվող արժեքի տիպը, ալգորիթմի անունը, պարամետրերի ցուցակը և մարմինը։ Եթե ալգորիթմը արժեք չի վերադարձնելու, վերադարձվող արժեքի տիպը պետք է բաց թողնել։ Պարամետրերի ցուցակը նույնպես կարող է դատարկ լինել՝ (), ավելին՝ այն կարող է ընդհանրապես բացակայել։ Ալգորիթմի վերնագրի և մարմնի արանքում թվարկվում են ալգորիթմի արգումենտներն ու արդյունքները։ Մարմինը սկսվում է սկիզբ ծառայողական բառով և ավարտվում է վերջ բառով։ սկիզբ բառից հետո, նույն տողում, գրվում են ալգորիթմի լոկալ փոփոխականների հայտարարությունները։ Հայտարարություններից հետո գրվում են ալգորիթմի մարմնի հրամանները։

algorithm
    : 'ալգ' scalar? IDENT ('(' (parameter (',' parameter)*)? ')')? NL
      arguments? results?
      'սկիզբ' (declaration (',' declaration)*)? NL statement* 'վերջ' NL
    ;

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

scalar
    : 'տրամ' | 'ամբ' | 'իրկ' | 'տեքստ'
    ;

Պարամետրի նկարագրությունը սկսվում է պրիմիտիվ տիպով, որին հետևում է պարամետրի անունների ցուցակ։

parameter
    : scalar paramName (',' paramName)*
    ;

Պարամետրի անունը կարող է լինել կամ իդենտիֆիկատոր՝ պարզ փոփոխականի անուն, կամ աղյուսակի անուն։ Վերջինս սկսվում է աղյուսակ բառով, դրան հետևում է իդենտիֆիկատոր և աղյուսակի չափողականությունների նկարագրությունը։

paramName
    : IDENT
    | 'աղյուսակ' IDENT '[' range (',' range)? ']'
    ;

range
    : (INTEGER | IDENT) ':' (INTEGER | IDENT)
    ;

Ալգորիթմական լեզուն հնարավորություն է տալիս սահմանել միայն միչափանի ու երկչափանի զանգվածներ՝ վեկտորներ և մատրիցներ։ Եվ հնարավորություն է տալիս նշելու տարրերի ինդեքսների միջակայքը։ Օրինակ, հետևյալը ամբողջ թվերի վեկտոր է, որի տարրերն ինդեքսավորվում են 1..8 թվերով․

ամբ աղյուսակ վ[1:8]

Գրքում բերված օրինակներում աղյուսակի ինդեքսների միջակայքը նշելիս հաստատունի հետ միասին օգտագործված է մի որևէ փոփոխական։ Հավանաբար ենթադրվել է, որ «աղյուսակ» օբյեկտից հնարավոր չի ստանալ ինդեքսների միջակայքը։ Օրինակ․

ալգ ֆ(ամբ N, իրկ աղյուսակ ա[2:N])
...

(Սա ավելորդ բան է ու իրականացման անհարմարություններ է ստեղծելու։ Այս մասը պետք է վերանայել ու ավելի հարմար գրառում մշակել։ Հաշվի առնելով նաև այն փաստը, որ աղյուսակները լինելու են ստատիկ և դրանք մոդելավորելու եմ Ջավայի օբյեկտներով, դրանց մասին ամբողջ ինֆորմացիան հնարավոր է լինելու ստանալ հենց աղյուսակի հղումից։)

Արգումենտների թվարկումը սկսվում է արգ բառով, որին հետևում են պարամետրերի ցուցակում թվարկված այն պարամետրերի անունները, որոնք ալգորիթմին են փոխանցվելու ըստ արժեքի (by value)։ Նոր տողից, արդ բառով սկսվում է արդյունք֊պարամետրերի թվարկում, դրան այնպիսիներն են, որոնք ալգորիթմին են փոխանցվելու հղումով (by reference)։

arguments
    : 'արգ' IDENT (',' IDENT)* NL
    ;

results
    : 'արդ' IDENT (',' IDENT)* NL
    ;

(Սա էլ է երևի ավելորդ բան։ Ռուսերեն ավելի ուշ հրատարակված դասագրքերում արգ ու արդ ծառայողական բառերը գրվում են հենց պարամետրերի ցուցակում՝ տիպից առաջ։)

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

declaration
    : scalar declName (',' declName)*
    ;
    
declName
    : IDENT
    | 'աղյուսակ' IDENT '[' INTEGER ':' INTEGER ']'
    | 'աղյուսակ' IDENT '[' INTEGER ':' INTEGER ',' INTEGER ':' INTEGER ']'
    ;

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

statement
    : assign | branch | condLoop | countLoop | select | algCall
    ;

Վերագրման հրամանը թույլ է տալիս := նշանի աջ կողմում գրված արտահայտությոն արժեքը վերագրել փոփոխականին համ զանգվածի տարրին։

assign
    : place ':=' expression NL
    ;

place
    : IDENT
    | IDENT '[' expression ']'
    | IDENT '[' expression ',' expression ']'
    ;

Ճյուղավորման հրամանը սկսվում է եթե բառով և ավարտվում է ավարտ բառով։ Եթե եթե բառին հաջորդող պայմանը ճիշտ է, ապա կատարվում է ապա բառին հաջորդող հրամանների շարքը։ Հակառակ դեպքում կատարվում են այլապես բառին հաջորդող հրամանները։ Հրամանի այլապես բլոկը կարող է բացակայել։

branch
    : 'եթե' expression NL 'ապա' NL? statement* ('այլապես' NL? statement*)? 'ավարտ' NL
    ;

Պայմանով ցիկլը սկսվում է մինչ բառով, որին հետևում է կրկնման պայմանը։ Այնուհետև, նոր տողից ցս (ցիկլի սկիզբ) և ցվ (ցիկլի վերջ) բառերի միջև գրվում են կրկնվող հրամանները։

condLoop
    : 'մինչ' expression NL 'ցս' NL? statement* 'ցվ' NL
    ;

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

countLoop
    : 'թող' IDENT 'սկսած' expression 'մինչև' expression
      ('քայլ' expression)? NL 'ցս' NL? statement* 'ցվ' NL
    ;

Եվ վերջին հրամանը՝ ալգորիթմի կանչը։ Սա ալգորիթմի անունն է, որին հետևում է արգումենտների ցուցակը։ Արգումենտների ցուցակը կարող է դատարկ լինել կամ բացակայել ընդհանրապես։

algCall
    : IDENT ('(' (expression (',' expression)*) ')')? NL
    ;

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

expression
    : simple
    | '(' expression ')'
    | IDENT '[' expression (',' expression)? ']'
    | IDENT '(' (expression (',' expression)*)? ')'
    | ('ոչ' | '-' | '+') expression
    | <assoc=right> expression '**' expression
    | expression ('*' | '/') expression
    | expression ('+' | '-') expression
    | expression ('>' | '>=' | '<' | '<=') expression
    | expression ('=' | '<>') expression
    | expression 'և' expression
    | expression 'կամ' expression
    ;

ANTLR4֊ը պահանջում է, որ արտահայտությունների քերականության մեջ գործողությունները գրվեն ըստ իրենց նախապատվությունների նվազման։ Այս դեպքում, օրինակ, աստիճան բարձրացնելու ** գործողությունն ամենաբարձր նախապատվություն ունեցող բինար գործողությունն է, իսկ ամնեացածր նախապատվություն ունեցողը տրամաբանական կամ գործողությունն է։ Պետք է նկատել նաև, որ <assoc=right> արտահայտությամ ** գործողության համար սահմանվել է աջ բաշխականություն։ Մյուս բինար գործողությունները ձախ֊բաշխական են։

Արտահայտությունների պարզ դեպքերն առանձնացրել եմ simple կանոնի մեջ։ Այստեղ են տեքստային, իրական ամբողջաթիվ ու տրամաբանական լիտերալները, ինչպես նաև պարզ փոփոխականը (IDENT

simple
    : TEXT
    | REAL
    | INTEGER
    | IDENT
    | 'ճիշտ'
    | 'կեղծ'
    ;

Կարծես թե վերջ։ Հիմաա ANTLR4 գործիքով այս քերականությունից պիտի ստանա Ջավա լեզվով գրված կոդ։

Փորձարկում

Բնականաբար, ես չեմ կարծում, թե հենց առաջին փորձից ամեն ինչ աշխատելու է․ կամ ինչ֊որ բան պակաս եմ գրել, կամ ինչ֊որ բան սխալ եմ հասկացել օրինակներից։ Համոզվելու համար պիտի փորձել։

Եվ այսպես, www.antlr.org կայքից ներբեռնում եմ գործիքի 4.7.1 տարբերակը պարունակող antlr-4.7.1-complete.jar ֆայլը ու առայժմ պատճենում եմ այն նույն պանակում, որտեղ քերականության ֆայլն է։ Ի դեպ, քերականությունը պարունակող ֆայլի անունը պետք է համընկնի grammar հրահանգով տրված անվան հետ (իմ դեպքում դա Alg0 է), իսկ ընդլայնումը պետք է լինի *.g4։

Քայլ առաջին։ Ջավայի միջոցով աշխատեցնում եմ ANTLR4 գործիքը․

$ java -cp .:antlr-4.7.1-complete.jar org.antlr.v4.Tool Alg0.g4

Ու միանգամից ստանում եմ հաղորդագրություններ բացթողումների մասին․

warning(125): Alg0.g4:6:6: implicit definition of token NL in parser
warning(125): Alg0.g4:10:20: implicit definition of token IDENT in parser
warning(125): Alg0.g4:29:7: implicit definition of token INTEGER in parser
warning(125): Alg0.g4:108:6: implicit definition of token TEXT in parser
warning(125): Alg0.g4:109:6: implicit definition of token REAL in parser

Իմաստն այն է, որ քերականության կանոններում օգտագործել եմ NL, IDENT, INTEGER, TEXT և REAL տերմինալային սիմվոլները, բայց դրանց տեսքը չեմ սահմանել։ Վերադառնում եմ Alg0.g4 ֆայլին ու դրա պոչից ավելացնում եմ հետևյալ մի քանի սահմանումները։

Իդենտիֆիկատորը հայերեն կամ լատիներեն փոքրատառով սկսվող և նույն տառերից ու թվանշաններց բաղկացած հաջորդականություն է։

IDENT
    : [ա-ևa-z][ա-ևa-z0-9]*
    ;

Իրական թիվը սահմանել եմ որպես . նիշը պարունակող թվանշանների հաջորդականություն։ Սա, իհարկե, լրիվ սահանումը չէ, բայց տվյալ գործի համար լրիվ հերիք է։

REAL
    : [0-9]+'.'[0-9]+?
    ;

Ամբողջ թիվը պարզապես թվանշանների հաջորդականություն է․

INTEGER
    : [0-9]+
    ;

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

TEXT
    : '"'~('"')*'"'
    ;

Ալգորիթմական լեզվում ; նիշն ու նոր տողի անցման նիշը համարժեք են։

NL
    : [\n;]+
    ;

ANTLR4֊ի հետևյալ կանոնն էլ ասում է, որ բացատանիշերի հաջորդականությունը պետք է անտեսել։

WS : [ \t\r]+ -> skip
    ;

ANTLR4 գործիքի հաջորդ գործարկումն արդեն հաջող է անցնում, ու գեներացվում են *.java ֆայլերը, որոնք կարելի է կոմպիլյացնել ու ստանալ *.class ֆայլեր։ (Այդ գեներացված ֆայլերի մեջ են Alg0Lexer.java բառային վերլուծիչը, Alg0Parser.java շարահյուսական վերլուծիչը և այլն։ Դրանք բավականին կոկիկ ու ընթեռնելի ծրագրեր են, հետաքրքրության համար կարելի է բացել ու ուսումնասիրել։)

$ javac -cp .:antlr-4.7.1-complete.jar Alg0*.java

Իսկ ինչպե՞ս ստուգել։ ANTLR4֊ն իր մեջ պարունակում է TestRig կոչված ծրագիրը։ Ես դեռ լավ չեմ հասկանում, թե դա ինչ է, բայց կարող եմ ցույց տալ դրա հետ աշխատելու ձևը։ Բայց նախ պատրաստեմ մի օրինակ (դասագրքից), ու այն գրեմ case02.alg ֆայլում։

ալգ փոքրտարր(ամբ k, n, իրկ աղյուսակ a[k:n], ամբ l)
  արգ k, n, a
  արդ l
սկիզբ ամբ i, իրկ փոքր
  փոքր := a[k]
  l := k
  i := k + 1
  մինչ i <= n
  ցս
    եթե փոքր > a[i]
      ապա 
        փոքր := a[i]
        l := i
    ավարտ
    i := i + 1
  ցվ
վերջ

Հետո աշխատեցնում եմ արդեն TestRig֊ը։

$ java -cp .:antlr-4.7.1-complete.jar org.antlr.v4.gui.TestRig Alg0 program -tree < case02.alg

Հրամանում տրված -tree պարամետրը վերլուծության ծառն արտածում է Լիսպ֊ի ցուցակների տեսքով․

(program \n (algorithm ալգ փոքրտարր ( (parameter (scalar ամբ) (paramName k) , (paramName n)) , (parameter (scalar իրկ) (paramName աղյուսակ a [ (range k : n) ])) , (parameter (scalar ամբ) (paramName l)) ) \n (arguments արգ k , n , a \n) (results արդ l \n) սկիզբ (declaration (scalar ամբ) (declName i)) , (declaration (scalar իրկ) (declName փոքր)) \n (statement (assign (place փոքր) := (expression a [ (expression (simple k)) ]) \n)) (statement (assign (place l) := (expression (simple k)) \n)) (statement (assign (place i) := (expression (expression (simple k)) + (expression (simple 1))) \n)) (statement (condLoop մինչ (expression (expression (simple i)) <= (expression (simple n))) \n ցս \n (statement (branch եթե (expression (expression (simple փոքր)) > (expression a [ (expression (simple i)) ])) \n ապա \n (statement (assign (place փոքր) := (expression a [ (expression (simple i)) ]) \n)) (statement (assign (place l) := (expression (simple i)) \n)) ավարտ \n)) (statement (assign (place i) := (expression (expression (simple i)) + (expression (simple 1))) \n)) ցվ \n)) վերջ \n\n))

TestRig֊ին -tree֊ի փոխարեն -gui տալով վերլուծության ծառը կտեսնենք բացված գրաֆիկական պատուհանում։

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

Բայց այդ մասին, ինչպես ասում է կենդանի դասականը, հաջորդ դասին։

Tuesday, December 19, 2017

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

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

Խնդիրը։ Տրված է ինչ-որ արտահայտություն, օրինակ, «Միացյալ ազգերի կազմակերպություն» և պահանջվում է սրանից ստանալ «ՄԱԿ» հապավումը։

Դպրոցականը կամ ուսանողը, հավանաբար, առաջին լուծումը կտանի այսպես. տողը դարձնել ցուցակ, հետո անցնել տողի վրայով ու հավաքել բոլոր այն տառերը, որոնց նախորդում են տառ չհանդիսացող այլ սիմվոլներ։ Հետո՝ հավաքած տառերը դարձնել մեծատառ ու միավորել մեկ տողի մեջ։

Տողից նիշերի ցուցակ ստացվում է 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;
}


 

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

Խնդիրը։ Ստուգել, թե արդյոք s0 ցուցակը s1 ցուցակի ենթացուցակն է։ Օրինակ, [3, 4, 5] ցուցակը [1, 2, 3, 4, 5, 6] ցուցակի ենթացուցակ է։

Միանգամից «ֆունկցիոնալ» լուծումը. s0s1-ի ենթացուցակ է, եթե կա՛մ s0-ն համընկնում է s1-ի սկիզբի հետ՝ նրա պրեֆիքսն է, կա՛մ s0s1-ի պոչի ենթացուցակն է։

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);
}

Tuesday, December 13, 2016

Միակապ ցուցակի կարգավորումը (Insertion sort)

Վերջերս մի հարցազրույցի ժամանակ խնդիր առաջադրվեց C լեզվով իրականացնել միակապ ցուցակի (singly linked list) կարգավորման ալգորիթմը՝ անպայման ռեկուրսիայի օգտագործմամբ։ Ես ընտրեցի տեղադրումով կարգավորման (insertion sort) մեթոդը։ Ստորև ներկայացնում եմ դա։

Նախ՝ ցուցակի հանգույցի (node) սահմանումը, որտեղ բանալին double տիպի է․
typedef struct _node node;
struct _node {
    double data; /* բանալի */
    node* next;  /* կապ */
};
Հիմա տեղադրումով կարգավորման մասին։ Ալգորիթմի էությունն այն է, որ ամեն մի քայլում հերթական տարրը (իմ դեպքում՝ հանգույցը) տեղադրվում է իր ճիշտ տեղում։ Բնականաբար բուն տեղադրման գործողությունը կարևոր գործողություն է։ Սահմանում եմ insert_into() ֆունկցիան, որը տրված հանգույցը տեղադրում է տրված ցուցակի իր ճիշտ տեղում և վերադարձնում է ձևաձոխված ցուցակը։
node* insert_into( node* n, node* l )
{
    /* եթե ցուցակը դատարկ է, ապա տրված հանգույցը 
       վերադարձնել որպես կարգավորված ցուցակ */
    if( NULL == l ) {
        n->next = NULL;
        return n;
    }

    /* եթե տրված հանգույցի բանալին փոքր է տրված ցուցակի 
       առաջին հանգույցի բանալու արժեքից, ապա տրված 
       հանգույցը կցել ցուցակի սկզբից */
    if( n->data <= l->data ) {
        n->next = l;
        return n;
    }

    /* ռեկուրսիվ կանչով տրված հանգույցը տեղադրել ցոցակի 
       պոչի մեջ, ապա նախնական ցուցակի առաջին հանգույցը 
       կապել ձևափոխված պոչին */
    l->next = insert_into(n, l->next);
    return l;
}
Ցուցակը կարգավորող sort_list() ֆունկցիան պարզապես կանչում է insert_into() ֆունկցիան․
node* sort_list( node* l )
{
    /* ցուցակը դատարկ լինելու դեպքը */
    if( NULL == l )
        return NULL;

    /* ցուցակի առաջին հանգույցը տեղադրել կարգավորված 
       պոչի մեջ՝ ճիշտ տեղում */
    return insert_into(l, sort_list(l->next));
}
Այսքանը։

Friday, December 9, 2016

Թվի երկուական ներկայացման ևս մի մեթոդի մասին

Մի անգամ արդեն ես առիթ եմ ունեցել գրելու ամբողջ թիվը տասական ներկայացումից երկուական ներկայացման ձևափոխելու մասին։ ՀայIT.orgԹվի ձևափոխումը տասականից երկուական տեսքի հոդվածում գրել եմ ձևափոխության ռեկուրսիվ եղանակի մասին, որտեղ օգտագործել եմ ծրագրավորման լեզվում տողերի կոնկատենացիայի հնարավորությունը։

Հիմա ուզում եմ խոսել այն մասին, թե ինչպես կառուցել թվի երկուական ներկայացումը, երբ լեզվում տողերի կցման հնարավորություն չկա, և արդյունքը պետք է գրել սիմվոլների բուֆերի մեջ։ Ընդունված մեթոդն այն է, որ տրված տասական թիվը, քանի դեռ այն զրո չի դարձել, հաջորդաբար բաժանվում է `2`֊ի, և բաժանումից ստացված մնացորդները գրառվում են հակառակ կարգով։ Այստեղ խնդիրն այն է, որ կամ պետք է հենց սկզբից մնացորդները բուֆերի մեջ գրառել հակառակ հաջորդականությամբ՝ նախապես իմանալով երկուական տեսքի զբաղեցրած նիշերի քանակը, կամ մնացորդները գրառել դրանց ստացվելու ուղիղ հաջորդականությամբ և վերջում վերադասավորել հակառակ կարգով։ Թվի երկուական տեսքի զբաղեցրած նիշերի քանակը կարելի է ստանալ լոգարիթմի օգնությամբ․ \(length=\lceil\log_2{n}\rceil\)
// տարբերակ I
void bin_a( int num, char* res )
{
  size_t length = log(num)/log(2);
  while( num ) {
    res[length--] = "01"[num & 0x01];
    num >>= 1;
  }
}

// տարբերակ II
void bin_b( int num, char* res )
{
  char* p = res;
  while( num ) {
    *p++ = "01"[num & 0x01];
    num >>= 1;
  }

  while( p > res ) {
    char t = *(--p);
    *p = *res;
    *res = t;
    ++res;
  }
}
Թե զբաղեցնելիք նիշերի քանակը, և թե մնացորդները հակառակ գրելուց հետո դրանք շրջելը ես համարում եմ ավելորդ աշխատանք։ Ստորև ցուցադրում եմ մի եղանակ, որում թվի տասական տեսքից երկուական տեսքի կառուցումը կատարվում է առանց վերը նշված «ավելորդ» (կամ ոչ ցանկալի) գործողությունների։

Եվ այսպես, int bin( int num, char* res ) ֆունկցիան արգումենտում ստանում է ձևափոխվելիք թիվը և արդյունքը գրառելու տեղը (նիշերի բուֆեր), իսկ վերադարձնում է երկուական ներկայացման նիշերի քանակը։ Սա ինտերֆեյսը։ Իսկ իրականացումը ռեկուրսիվ է․ բազա) եթե num֊ը փոքր է 2֊ից, ապա բուֆերի սկզբում գրել '0' կամ '1' համապատասխան նիշը, քայլ) եթե num֊ը մեծ է կամ հավասար երկուսի, ապա bin() ֆունկցիան ռեկուրսիվ կանչել num / 2 քանորդով ու ստանալ len թիվը, որը բուֆերում այդ քանորդի զբաղեցրած նիշերի քանակն է, ապա բուֆերի len + 1 դիրքում գրել num % 2 մնացորդին համապատասխան '0' կամ '1' նիշը։ Ռեկուրսիայի բազային ճյուղում որպես արդյունք ֆունկցիան պետք է վերադարձնի 1, քայլի ճյուղում՝ len + 1։

Ահա իրականացումը C լեզվով․
int bin( int num, char* res )
{
  if( num < 2 ) {
    *res = "01"[num];
    return 1;
  }

  int len = bin(num >> 1, res);
  *(res + len) = "01"[num & 0x01];
  return 1 + len;
}
Նկարագրված երեք ֆունկցիաների արդյունքները համեմատելու համար օգտագործում եմ test_bin() ֆունկցիան․
bool test_bin( int num )
{
  char res_a[32] = { 0 };
  bin_a(num, res_a);

  char res_b[32] = { 0 };
  bin_b(num, res_b);

  char res[32] = { 0 };
  bin(num, res);

  bool pass = 0 == strcmp(res, res_a);
  pass = pass && (0 == strcmp(res, res_b));
  
  if( !pass )
    printf("| num = %d\tres = %s\tres_a = %s\tres_b = %s\n",
           num, res, res_a, res_b);
  else
    printf("| num = %d\tres= %s\n", num, res);

  return pass;
}

Tuesday, November 15, 2016

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

Ես պատմում եմ ծրագրավորման լեզվի շարահյուսական վերլուծիչի իրականացման մասին։ Պատմությունս հնարավորին պարզ պահելու համար ցույց կտամ, թե ինչպես, օրինակ, պարզեցված Բեյսիկ (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
    }
  }
}