Սկիզբ » Ուսումնական նյութեր » Ծրագրավորում » Ծրագրավորման լեզուներ » PROLOG » Պատմություն այն մասին, թե ինչպես ես PROLOG լեզվով գրեցի մի պարզ կոմպիլյատոր

Պատմություն այն մասին, թե ինչպես ես PROLOG լեզվով գրեցի մի պարզ կոմպիլյատոր

| Սեպտեմբեր 21, 2012 | Մեկնաբանված չէ |

Ներածություն

Պատմության դեպքերը, որ ես պատրաստվում եմ շարադրել, տեղի են ունեցել քսանմեկերորդ դարի դարասկզբին` Երևանի Պետական Համալսարանում: Ես այդ համալսարանում գործող Ինֆորմացիոն տեխնոլոգիաների մշակման և կառավարման կենտրոնի ուսանողն եմ: Կա մի դասընթաց, որի վերնագիրը չեմ հիշում, բայց գիտեմ, որ դրա շրջանակներում դասավանդում են PROLOG լեզուն: Եվ ահա, մի սովորական աշնանային օր, պարապող դասախոսը հայտարարեց, որ ամեն մի ուսանող պետք է մի որևէ նախագիծ իրականացնի PROLOG լեզվով և ներկայացրեց իր կողմից առաջարկվող խնդիրների ցուցակը: Այդ ցուցակի վերջին խնդիրը ձևակերպված էր հետևյալ կերպ. “Պարզագույն կոմպիլյատորի կառուցում”: Ես ընտրեցի այդ խնդիրը:

Հիմնական աշխատանքը բաժանեցի երեք մասերի և որոշեցի կատարել հետևյալլ հաջորդականությամբ.

  1. քերականական անալիզ և աբստրակտ քերականական ծառի կառուցում,
  2. նպատակային կոդի գեներացիա` վիրտուալ մեքենայի համար,
  3. մուտքային տեքստի լեքսիկական անալիզ:

 

Իսկ աշխատանքը կատարելու համար ինքս ինձ տվեցի երեք շաբաթ ժամանակ:

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

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

Program : CommandList '.' 
CommandList : Command ';' CommandList
    | Command
Command : IDENT ':=' SimExpr
    | IF Expr THEN CommandList FI
    | IF Expr THEN CommandList ELSE CommandList FI
    | FOR IDENT FROM SimExpr TO SimExpr DO CommandList OD
    | WHILE Expr DO CommandList OD
    | PRINT SimExpr
    | INPUT IDENT
Expr : SimExpr RelOp SimExpr
    | SimExpr
RelOp : = | <> | > | >= | < | <=
SimExpr  SimExpr MulOp Term
    | Term
MulOp : * | / | \ | AND
Term  Term AddOp Fact
    | Fact
AddOp : + | - | OR
Fact: IDENT
    | NUMBER
    | - SimExpr
    | NOT Expr
    | '(' Expr ')'

իրականացնում էի այն, ապա ժամանակ առ ժամանակ անդրադառնալով՝ դրան էի ավելացնում ծրագրավորման լեզուներին հատուկ այլ կառուցվածքներ։ Օրինակ, զանգվածներ, տիպեր, ենթածրագրեր և այլն։ Բայց այս աշխատանքի շրջանակներում ես որոշեցի իրականացնել միայն նախնական մասը, որը սկակայն հանդիսանում է ամբողջական ծրագրավորման լեզու և նրանով կարելի է արտահայտել բավականին հետաքրքիր ալգորիթմներ (տես Տեստային օրինակներ)։

Քերականական անալիզ և աբստրակտ քերականական ծառի կառուցում

Քանի որ ես բացարձակ ոչ մի գաղափար չունեի այն մասին, թե ինչպե՞ս պետք է իրականացնել քերականական անալիզը PROLOG լեզվով, նույնիսկ չէի հասկանում, թե որտեղի՞ց պետք է սկսել և ի՞նչ ուղղությամբ պետք է գնալ, ապա սկսեցի ինտերնետում որոնել և կարդալ ցանկացած նյութ, որտեղ խոսվում էր PROLOG-ում կոնտեքստից ազատ քերականությունների հետ աշխատանքի մասին: Վերջապես ես գտա [1] հոդվածը, որտեղ շատ լավ բացատրված են PROLOG լեզվում վերլուծության և թարգմանության համար նախատեսված միջոցները: Այնուհետև փորձեցի հասկանալ, թե ինչպե՞ս է օգտագործվում PROLOG-ի DCG [4] նախապրոցեսորը վերլուծության և աբստրակտ քերականական ծառի կառուցման համար:

Ստորև բերված ծրագրային կոդը ամբողջությամբ իրականացնում է մուտքային լեզվի քերականությունը: Պետք է ասել, որ սա իսկապես պարզագույն անալիզատոր է, որտեղ բացակայում է սխալների մշակումը կամ դրանց առկայության մասին իրազեկումը: Այն իր մուտքում պետք է ստանա միայն և միայն քերականապես ճիշտ տվյալներ, հակառակ դեպքում… Աբմողջ ծրագիրը բաժանված է երկու հիմնական մասերի. արտահայտությունների թարգմանություն և հրամանների թարգմանություն: Թարգմանության արդյունքում կառուցվում է ծառ, որի հիման վրա էլ հետագայում կատարվում է նպատակային մեքենայի կոդի գեներացիան:

Օրինակ,
FOR a FROM 1 TO 20 DO PRINT a * a OD 
ծրագրի հատվածին համարժեք ծառը հետևյալն է.
for(ident(a),int(1),int(20),print(mul(ident(a),ident(a)))):
mce

Այս օրինակի նմանությամբ էլ կառուցվում են լեզվական մյուս կառուցվածքների աբստրակտ քերականական ծառերը:

%------------ PROGRAM -----------------------------
program(prog(P)) --> comseq(P),[.].

%------------ PROGRAM STATEMENTS ------------------
comseq(seq(S1,S2)) --> command(S1),[;],comseq(S2),!.
comseq(S0) --> command(S0),!.

command(assign(V,E)) --> ident(V),[:=],simexpr(E).
command(if(C,B,E)) --> [if],expr(C),[then],comseq(B),[else],comseq(E),[fi].
command(if(C,B)) --> [if],expr(C),[then],comseq(B),[fi].
command(for(V,S,E,B)) --> [for],ident(V),[from],simexpr(S),[to],simexpr(E),[do],comseq(B),[od].
command(while(C,B)) --> [while],expr(C),[do],comseq(B),[od].
command(print(A)) --> [print],simexpr(A).
command(input(V)) --> [input],ident(V).

%------------ ARITHMETIC EXPRESSIONS ------------
expr(eq(E1,E2)) --> simexpr(E1),[=],simexpr(E2).
expr(ne(E1,E2)) --> simexpr(E1),[<>],simexpr(E2).
expr(gt(E1,E2)) --> simexpr(E1),[>],simexpr(E2).
expr(ge(E1,E2)) --> simexpr(E1),[>=],simexpr(E2).
expr(lt(E1,E2)) --> simexpr(E1),[<],simexpr(E2).
expr(le(E1,E2)) --> simexpr(E1),[<=],simexpr(E2).
expr(E) -->
  simexpr(E).

simexpr(add(E1,E2)) --> term(E1),[+],simexpr(E2).
simexpr(sub(E1,E2)) --> term(E1),[-],expr(E2).
simexpr(or(E1,E2)) --> term(E1),[or],expr(E2).
simexpr(E) --> term(E).

term(mul(E1,E2)) --> fact(E1),[*],term(E2).
term(div(E1,E2)) --> fact(E1),[/],term(E2).
term(mod(E1,E2)) --> fact(E1),[\],term(E2).
term(and(E1,E2)) --> fact(E1),[and],term(E2).
term(E) --> fact(E).

fact(E) --> ['('],expr(E),[')'].
fact(not(E)) --> [not],expr(E).
fact(neg(E)) --> [-],simexpr(E).
fact(F) --> ident(F).
fact(C) --> const(C).

ident(ident(N)) --> [N], {atom(N)}.

const(int(C)) --> [C], {integer(C)}.
%-------------------------------------------------------------------

PROLOG-ի DCG մեխանիզմն այնքան պարզ է, որ կարիք էլ չկա մեկնաբանել բերված ծրագրի ամեն մի հատվածը։

Կոդի գեներացիա նպատակային մեքենայի համար

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

 

Կառուցվածքը Թարգմանությունը
CommandList '.' <EOF>
generate(CommandList)
STOP
Command ';' CommandList
generate(Command)
generate(CommandList)
IDENT ':=' Expr
generate(Expr)
POP IDENT
IF Cond THEN 
  CommandList
FI
generate(Cond)
JZ <label x>
generate(CommandList)
LABEL <label x>
IF Cond THEN
  CommandList1
ELSE
  CommandList2
FI
generate(Cond)
JZ <label x>
generate(CommandList1)
JUMP <label y>
LABEL <label x>
generate(CommandList2)
LABEL <label y>
FOR IDENT FROM SimExpr TO SimExpr DO
  CommandList
OD
generate(Expr1)
POP IDENT
LABEL <label x>
generate(Expr2)
PUSH IDENT
GT
JNZ <label y>
generate(CommandList)
PUSH IDENT
PUSH 1
ADD
POP IDENT
JUMP <label x>
LABEL <label y>
WHILE Cond DO
  CommandList
OD
LABEL <label x>
generate(Cond)
JZ <label y>
generate(CommandList)
JUMP <label x>
LABEL <label y>
PRINT Expr
generate(Expr)
PRINT
INPUT IDENT
INPUT
POP IDENT

Մաթեմատիկական արտահայտությունների և համեմատման գործողությունների թարգմանության ժամանակ նախ գեներացվում են գործողության աջ ու ձախ կողմերը, ապա կցվում է գործողությանը համապատասխանող հրամանը։ Եթե արտահայտության մեջ հանդիպել է հաստատուն կամ իդենտիֆիկատոր, ապա այն PUSH հրամանի միջոցով ավելացվում է ստեկին։

%

% all program
%
gener(prog(P),Res,Lo,Li) :-
  gener(P,R0,Lo,Li),
  append(R0,['STOP'],Res).

%
% statement sequence
%
gener(seq(F,S),Res,Lo,Li) :-
  gener(F,Fg,Lo,Lx),
  gener(S,Sg,Lx,Li),
  append(Fg,Sg,Res).

%
% assignment
%
gener(assign(ident(V),E),Res,Lo,Li) :-
  generex(E,Eg),
  atom_concat('POP ',V,S1),
  append(Eg,[S1],Res),
  Li is Lo.

%
% condition
%
gener(if(C,B),Res,Lo,Li) :-
  generex(C,Cg),
  Lx is Lo + 1,
  atom_concat('JZ ',Lx,T1),
  append(Cg,[T1],So),
  gener(B,Bg,Lx,Li),
  append(So,Bg,Si),
  atom_concat('LABEL ',Lx,T2),
  append(Si,[T2],Res).

%
% condition + else part
%
gener(if(C,B,E),Res,Lo,Li) :-
  generex(C,Cg),
  Lx is Lo + 1, Ly is Lx + 1,
  atom_concat('JZ ',Lx,T1),
  append(Cg,[T1],So),
  gener(B,Bg,Ly,Lz),
  append(So,Bg,Si),
  atom_concat('JUMP ',Ly,T3),
  atom_concat('LABEL ',Lx,T2),
  append(Si,[T3,T2],Sii),
  gener(E,Eg,Lz,Li),
  append(Sii,Eg,Siii),
  atom_concat('LABEL ',Ly,T4),
  append(Siii,[T4],Res).

%
% loop with counter 'for'
%
gener(for(ident(V),S,E,B),Res,Lo,Li) :-
  Lx is Lo + 1, Ly is Lx + 1,
  generex(S,Sg),
  atom_concat('POP ',V,T0),
  atom_concat('LABEL ',Lx,T1),
  append(Sg,[T0,T1],T2),
  generex(E,Eg),
  atom_concat('PUSH ',V,T3),
  atom_concat('JZ ',Ly,T4),
  append(Eg,[T3,'GT',T4],T5),
  append(T2,T5,T6),
  gener(B,Bg,Ly,Li),
  append(T6,Bg,T7),
  append(T7,[T3,'PUSH 1','ADD',T0],T8),
  atom_concat('JUMP ',Lx,T9),
  atom_concat('LABEL ',Ly,T10),
  append(T8,[T9,T10],Res).

%
% conditional loop 'while'
%
gener(while(C,B),Res,Lo,Li) :-
  Lb is Lo + 1,
  atom_concat('LABEL ',Lb,S1),
  generex(C,Cg),
  Le is Lo + 2,
  atom_concat('JZ ',Le,S3),
  gener(B,Bg,Le,Li),
  atom_concat('JUMP ',Lb,S4),
  atom_concat('LABEL ',Le,S5),
  append([S1],Cg,T0),
  append(T0,[S3],T1),
  append(T1,Bg,T2),
  append(T2,[S4,S5],Res).

%
% input
%
gener(input(ident(V)),['INPUT',S1],Lo,Li) :-
  atom_concat('POP ',V,S1),
  Li is Lo.

%
% output
%
gener(print(E),Res,Lo,Li) :-
  generex(E,Eg), Li is Lo,
  append(Eg,['PRINT'], Res).

%
%
%
generex(eq(Lp,Rp),Res) :-
  gensides(Lp,Rp,R0),
  append(R0,['EQ'],Res).

generex(ne(L,R),Res) :-
  gensides(L,R,R0),
  append(R0,['NE'],Res).

generex(gt(L,R),Res) :-
  gensides(L,R,R0),
  append(R0,['GT'],Res).

generex(ge(L,R),Res) :-
  gensides(L,R,R0),
  append(R0,['GE'],Res).

generex(lt(L,R),Res) :-
  gensides(L,R,R0),
  append(R0,['LT'],Res).

generex(le(L,R),Res) :-
  gensides(L,R,R0),
  append(R0,['LE'],Res).

generex(mul(L,R),Res) :-
  gensides(L,R,R0),
  append(R0,['MUL'],Res).

generex(div(L,R),Res) :-
  gensides(L,R,R0),
  append(R0,['DIV'],Res).

generex(mod(L,R),Res) :-
  gensides(L,R,R0),
  append(R0,['MOD'],Res).

generex(and(L,R),Res) :-
  gensides(L,R,R0),
  append(R0,['MUL'],Res).

generex(add(L,R),Res) :-
  gensides(L,R,R0),
  append(R0,['ADD'],Res).

generex(sub(L,R),Res) :-
  gensides(L,R,R0),
  append(R0,['SUB'],Res).

generex(or(L,R),Res) :-
  gensides(L,R,R0),
  append(R0,['ADD'],Res).

generex(not(E),Res) :-
  generex(E,Eg),
  append(Eg,['NEG'],Res).

generex(neg(E),Res) :-
  generex(E,Eg),
  append(Eg,['NEG'],Res).

generex(ident(I),[Res]) :-
  atom_concat('PUSH ',I,Res).

generex(int(I),[Res]) :-
  atom_concat('PUSH ',I,Res).

%
gensides(S0,S1,R) :-   generex(S0,S0g),
  generex(S1,S1g),
  append(S0g,S1g,R).

 

Մուտքային ֆայլի լեքսիկական անալիզ

Լեքսիկական անալիզ կատարող ծրագիրն ամբողջությամբ վերցրած է [3] հոդվածից: Նրանում ես միայն կատարել եմ չնչին փոփոխություն` իմ լեզվին համապատասխանացնելու համար:

% File sampleproj.pl - M. Covington - 2001 April 21
% A tokenizer using DCG rules.

%
token_list([T|Rest]) --> blank0,token(T),!,token_list(Rest).
token_list([]) --> blank0.

%
blank0 --> [C],{chartype(C,blank)},!,blank0.
blank0 --> [].

%
token(T) --> dispec(L), {atom_codes(T,L)}.
token(T) --> special(L), {atom_codes(T,L)}.
token(T) --> word(W), {atom_codes(T,W)}.
token(T) --> numeral(N), {number_codes(T,N)}.

%
word([L|Rest]) --> letter(L),word(Rest).
word([L]) --> letter(L).

%
numeral([C1,C2,C3|N]) --> ",", digit(C1), digit(C2), digit(C3), numeral(N).
numeral([C1,C2,C3]) --> ",", digit(C1), digit(C2), digit(C3).
numeral([C|N]) --> digit(C), numeral(N).
numeral([C]) --> digit(C).
numeral(N) --> decimal_part(N).
decimal_part([46|Rest]) --> ".", digit_string(Rest).
digit_string([D|N]) --> digit(D),digit_string(N).
digit_string([D]) --> digit(D).

%
dispec(E) --> special(S0), special(S1), {append(S0,S1,E)}.

%
digit(C) --> [C], {chartype(C,numeric)}.
special([C]) --> [C], {chartype(C,special)}.
letter(C) --> [C], {chartype(C,lowercase)}.
letter(C) --> [U], {chartype(U,uppercase), C is U+32}.

%
chartype(Code,Y):- Code =< 32,!,Y = blank.
chartype(Code,Y):- 48 =< Code,Code =< 57,!,Y = numeric.
chartype(Code,Y):- 97 =< Code,Code=< 122,!,Y = lowercase.
chartype(Code,Y):- 65 =< Code,Code=< 90,!,Y = uppercase.
chartype(_,special).

 

Նպատակային մեքենան

 

Հրամանները

Նպատակային մեքենան ստեկային մեքենա է, որի մոլոր հրամանները թվարկված են ստորև բերված աղյուսակում.

Հրամանը Պարամետրերը Ֆունկիոնալ իմաստը
PUSH integer, identifier Արգումենտում տրված թիվը կամ փոփոխականն ավելացնում է ստեկի գագաթում
POP identifier Ստեկի գագաթի արժեքը վերագրում է արգումենտում նշված փոփոխականին
DUP Կրկնապատկում է ստեկի գագաթի արժեքը
EXCH Տեղափոխում է ստեկի գագաթի երկու արժեքները
INPUT Ստեղնաշարից ներածած թիվը գրում է ստեկի գագաթում
PRINT Ստեկի գագաթի թիվն արտածում է էկրանին
LABEL integer Ծրագրում սահմանում է անցման կետ
JUMP integer Առանց պայմանի անցման հրաման
JZ, JNZ integer Անցում է կատարում, եթե ստեկի գագաթի թիվը զրո է (JZ), կամ զրո չէ (JNZ)
STOP Ավարտում է մեքենայի աշխատանքը
ADD Գումարում
SUB Հանում
MUL Բազմապատկում
DIV Բաժանման քանորդի որոշում
MOD Բաժանման մնացորդի որոշում
EQ Հավասարություն
NE Անհավասարություն
GT Մեծ
GE Մեծ կամ հավասար
LT Փոքր
LE Փոքր կամ հավասար

 

Տեստային օրինակներ

Օրինակ 1։ Գտնել տրված երկու թվերից ամենամեծի և ամենափոքրի գումարը։ Թարգմանություն              

  

Ծրագիր
INPUT a;
INPUT b;
IF a > b THEN
  m := a;
  n := b
FI;
IF a <= b THEN
  m := b;
  n := a
FI;
s := m + n;
PRINT s.
	
	INPUT
	POP a
	INPUT
	POP b
	PUSH a
	PUSH b
	GT
	JZ 1
	PUSH a
	POP m
	PUSH b
	POP n
	LABEL 1
	PUSH a
	PUSH b
	LE
	JZ 2
	PUSH b
	POP m
	PUSH a
	POP n
	LABEL 2
	PUSH m
	PUSH n
	ADD
	POP s
	PUSH s
	PRINT
	STOP

Օրինակ 2։ Երկու թվերի ամենամեծ ընդհանուր բաժանարարը որոշող Էվկլիդեսի ալգորիթմը։

Ծրագիր Թարգմանություն
INPUT a;
INPUT b;
WHILE a * b <> 0 DO
  IF a > b THEN
	a := a \ b
  ELSE
	b := b \ a
  FI
OD;
PRINT a + b.
	PUSH 5
	POP a
	PUSH 7
	POP b
	LABEL 1
	PUSH a
	PUSH b
	MUL
	PUSH 0
	NE
	JZ 2
	PUSH a
	PUSH b
	GT
	JZ 3
	PUSH a
	PUSH b
	MOD
	POP a
	JUMP 4
	LABEL 3
	PUSH b
	PUSH a
	MOD
	POP b
	LABEL 4
	JUMP 1
	LABEL 2
	PUSH a
	PUSH b
	ADD
	PRINT
	STOP

Օրինակ 3։ Ֆիբոնաչիի հաջորդականության առաջին 20 տարրերը։

Ծրագիր Թարգմանություն
a := 1;
b := 1;
i := 1;
WHILE i <> 20 DO
  c := a + b;
  PRINT c;
  a := b;
  b := c;
  i := i + 1
OD.
	
	PUSH 1
	POP a
	PUSH 1
	POP b
	PUSH 1
	POP i
	LABEL 1
	PUSH i
	PUSH 20
	NE
	JZ 2
	PUSH a
	PUSH b
	ADD
	POP c
	PUSH c
	PRINT
	PUSH b
	POP a
	PUSH c
	POP b
	PUSH i
	PUSH 1
	ADD
	POP i
	JUMP 1
	LABEL 2
	STOP

Օրինակ 4։ Տրված թվի ֆակտորիալի հաշվարկ։

Ծրագիր Թարգմանություն
INPUT a;
p := 1;
WHILE a > 0 DO
  p := a * p;
  a := a - 1
OD;
PRINT p.
	INPUT
	POP a
	PUSH 1
	POP p
	LABEL 1
	PUSH a
	PUSH 0
	GT
	JZ 2
	PUSH a
	PUSH p
	MUL
	POP p
	PUSH a
	PUSH 1
	SUB
	POP a
	JUMP 1
	LABEL 2
	PUSH p
	PRINT
	STOP

Օգտագործված աղբյուրներ

1. Jacques Cohen, Timothy J. Hickey, Parsing and Compiling Using Prolog,ACM Transactions on Programming Languages and Systems, Vol. 9, No. 2, April 1967, Pages 125-163.
2. W.F. Clocksin and C.S. Mellish, Programming in Prolog, Springer Verlag 1981.
3. Michael A. Covington, Tokenization using DCG Rules, Arti cial Intelligence Center, The University of Georgia, Athens, Georgia 30602-7415 U.S.A., 2000 April 21.
4. http://www.amzi.com/manuals/amzi6/pro/ref_dcg.htm

 

Պատմություն այն մասին, թե ինչպես ես PROLOG լեզվով գրեցի մի պարզ կոմպիլյատոր, 9.8 out of 10 based on 9 ratings

Նշագրեր: , , ,

Բաժին: PROLOG, Կոմպիլյատորներ

Կիսվել , տարածել , պահպանել

VN:F [1.9.20_1166]
Rating: 9.8/10 (9 votes cast)

Մեկնաբանեք

Կհաստատվեն միայն մեսրոպատառ հայերենով գրած մեկնաբանությունները

218