sublime text -ում նավիգացիա ստեղնաշարով : ՀայIT.org

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

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

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

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

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

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

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

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

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

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

Program → FunctionList

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

FunctionList → FunctionList Function
             | ε

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

Function → Declaration
         | Definition

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

Declaration → DECLARE FunctionHeader

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

Definition → FunctionHeader StatementList END FUNCTION

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

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

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

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

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

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

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

StatementList → StatementList Statement NewLines
              | ε

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

Statement → INPUT IDENT

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

Statement → PRINT Expression

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

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

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

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

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

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

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

Statement → WHILE Expression NewLines StatementList END WHILE

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

Statement → CALL IDENT ArgumentList
ArgumentList → ExpressionList
             | ε

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

ExpressionList → ExpressionList ',' Expression
               | Expression

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

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

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

GNU Bison֊ի ֆայլը

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

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

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

%token xNumber
%token xIdent

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

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

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

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

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

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

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

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

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

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

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

ArgumentList
    : ExpressionList
    | %empty
    ;

ExpressionList
    : ExpressionList ',' Expression
    | Expression
    ;

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

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

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

/* parser.y */

%token xIdent
%token xNumber

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

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

%token xEol

%start Program
%%
Program
    : FunctionList
    ;

FunctionList
    : FunctionList Function
    | %empty
    ;

Function
    : xDeclare FunctionHeader
    | FunctionHeader StatementList xEnd xFunction NewLines
    ;

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

ParameterList
    : IdentifierList
    | %empty
    ;

NewLines
    : NewLines xEol
    | xEol
    ;

IdentifierList
    : IdentifierList ',' xIdent
    | xIdent
    ;

StatementList
    : StatementList Statement NewLines
    | %empty
    ;

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

LetOpt
    : xLet
    | %empty
    ;

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

ElsePart
    : xElse NewLines StatementList
    | %empty */
    ;

StepOpt
    : xStep Expression
    | %empty
    ;

ArgumentList
    : ExpressionList
    | %empty
    ;

ExpressionList
    : ExpressionList ',' Expression
    | Expression
    ;

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

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

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

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

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

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

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

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

pattern     action

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

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

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

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

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

{ident}     { return xIdent; }

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

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

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

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

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

$ flex scanner.l

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

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

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

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

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

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

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

$ bison -d parser.y

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

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

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

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

%option noyywrap

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

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

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

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

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

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

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

%token xIdent
%token xNumber
....

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

%%

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

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

%{
#include <stdio.h>

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

%token xIdent
%token xNumber
....

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

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

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

' case01.bas

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

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

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

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

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

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

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

%option noyywrap
%option yylineno

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

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

%%

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

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

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

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

Program
    : FunctionList
    ;

FunctionList
    : FunctionList Function
    | /* empty */
    ;

Function
    : xDeclare FunctionHeader
    | FunctionHeader StatementList xEnd xFunction NewLines
    ;

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

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

Program
    : NewLinesOpt FunctionList
    ;

NewLinesOpt
    : NewLines
    | /* empty */
    ;

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

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

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

' case02.bas

DECLARE FUNCTION Gcd(n, m)

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

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

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

$ ./basic-s < case02.bas

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

extern void expression_as_json( expression*, FILE* );

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

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

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

extern void statement_as_json( statement*, FILE* );

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

extern void function_as_json( function*, FILE* );

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

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

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

extern void program_as_json( program*, FILE* );

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

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

Statement
    : xWhile Expression NewLines StatementList xEnd xWhile
    ;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ExpressionList
    : Expression ',' ExpressionList
    | Expression
    ;

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

ExpressionList
    : ExpressionList ',' Expression
    | Expression
    ;

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

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

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

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

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

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

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

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

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

/* main.c */

#include <stdio.h>

#include <gc.h>

#include "ast.h"

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

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

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

  return ok;
}

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

# Makefile

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

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

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

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

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

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

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

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

armenbadal | Նոյեմբեր 28, 2016 | Մեկնաբանված չէ |

Ողջույն

Առաջին անգամ ե՞ք այստեղ

Մեր կայքի բաժինները

Հղումներ

Հատուկ էջեր

ՏՏ թարգմանիչներին

Օգտակար հղումներ

sublime text -ում նավիգացիա ստեղնաշարով

ՀուՊ (Հարց ու Պատասխան, ֆորում)

Վերջին նյութերը

Բաժիններ

Գնահատվածները (անցյալ 7 օրվա ընթացքում)

Ֆեյսբուք և Գ+

System Administration

Ծրագրավորում