MODUS : yeni bir yarı derleme özellikli simgesel yorumlayıcı

Abstract

Bu projenin amacı, bir simgesel yorumlayıcının çalışma ilkelerini anla mak ve çalışabilir bir kodunu elde etmektir. Simgesel yorumlayıcılar yazılımın ve bilgi işlem biliminin ana çalışma alanlarından birini oluşturmaktadır. Bu projenin gelişimi şu şekilde özetlenebilir: Yorumlayıcı tanımı, C programlama dili, veri yapıları, MODUS'ün grameri, sözdizimi ve anlambilimi, simgesel ya pay ağaç kurma, simgelere ayırma, ilk geçiş hata kontrolü, polish notasyonu, ikinci geçiş hata kontrolü, gerçek ağaç kurma, çekirdek fonksiyonların tanımı ve çalışma şekilleri, simgesel türev alma ve indirgeme.

This project is aimed at the understanding of the parts of a symbolic interpreter and to develope its executable code. Symbolic interpreters form the main part of the computer software and one of the basic areas in computer science. The parts of the project are given as follows. Definitions of the interpreters: An interpreter is a program such that it fetchs a string from console or from a file and splits its tokens and runs the codes fitting its grammars. There are two types of interpreters. First one is the code interpreter while the other one is symbolic interpreter. The code interpreters run the code as soon as they fetch the code. They do not store the informations like function structures, but hold the contents of the simple elements. BASIC, MATLAB, PROLOG can be given as examples for code interpreters. The symbolic interpreters interpret the codes, then store the result to the data base and run the code if necessary. The kinds of the elements to be stored are the not only the simple structures but also complex entities like functions or operators. MATHEMATICA, REDUCE, MAPLE would be given as examples for symbolic interpreters. MODUS which is the name of this project, is also a symbolic interpreter. The C programming language: MODUS is written in the C programming language. The use of the C language has the following advantages; i- The C language has the largest application area in the computer science. Because, the UNLX operating system was constructed in the C language and it is sold including the C language as a part. Recently, the firms which develope compilers for the personal computers tend to the utilization of the C programming language. ii- The C language is a middle level language. Hi- The C language is a machine independent language if it is used with ANSI-C rules. iv- The C language has a flexible structure. v- Programs are easily designed if the C language is employed. vi- Low level functions facilities can be reached by the C language. vii- The C language has pointers and dynamic memory allocations. viii- Type declarations are easily defined and used in the C language. vi ix- The C language has I/O process with disk environment as low as the operating system layer level. Data structures: The main data structures and their simple definitions are as follows; Stack: It is a kind of data structure such that it works through the last-in-first-out principle. Queue: It is a kind of data structure such that it works through the first-in-first-out principle. Linked list: It is a kind of data structure such that it has only one pointer to point to the same structures. Double linked list: It is a kind of data structure such that it has two pointers to point to the same structures. Multi- linked list: It is a kind of data structure such that it has many pointers to point to the same structures. Tree: It is a kind of data structure such that it has many single direction pointers to point to the same structures. Binary tree: It is a kind of data structure such that it has two single direction pointers to point to the same structures. Binary search tree: It is a kind of data structure such that it has two single direction pointers to point to the same structures and it is sorted by the given key. AVL tree: It is a kind of data structure such that it has two single directions pointers to point to the same structures and it is sorted by the given key and balanced. The grammar of the MODUS: A programming language is a notation to establish communications from algorithms to the computers. Syntax: The rules which tell to the people whether a string is a valid program or is not suitable to the syntax of the language. The syntax of the MODUS is given bellow; The alphabet table : "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz 0123456789." The special character table : "+-7(H}!-;,0<>-&?@#" i- The string which begins with an element in the alphabet table, includes the elements of the aphabet table only. ii- The string that begins with an element in the special character table includes the elements of the special character table only. iii- Space is a certain separator. vii iv- The length of the string which begins with an element in the alphabet table is measused up to the first element which is not in the alphabet table. v- The length of the string which begins with an element in the special character table is measured up to the first element which is not in the special character table. Semantic: The rules which give meaning to the programs are called the semantics of the programming language. The semantics of the MODUS as follows; i- The operators in the family of types yfx, xfy or xfx: They are binary op erators and they are separated from each other with respect to its priority ward. ii- The operators in the family of types fx or fy: They are unary operators and they are separated from each other with respect to its priority ward. iii- The operators in the family of types xf or yf: They are unary operators and they are separated from each other with respect to its priority ward. iv- The operator in the family of types LP and RP: They open and close the paranthesis. The used types in MODUS: i- xfx, yfx, xfx: binary operators. ii- fx, fy, xf yf: unary operators. iii- LP, RP: paranthesis. iv- VAR: variable. v- Short, UShort, Integer, Ulnteger, Longlnt, ULonglnt, Float, Double: constant number. vi- String: character string. vii- Unknown. viii- Undefined. ix- None: the type which does not included any tokens. x- ADDR: the type which includes physical address. xi- Comma. Artficial Tree Generation: The artificial tree includes the symbolic elements and generates executable codes of MODUS by its stored informations but does not interface with the data base of the MODUS. The steps of the generating artificial tree as follows. i- Spliting the tokens. ii- First pass error detection. iii- Polish notation for the MODUS. iv- Second pass error detection. Real Tree Generation: After the artificial tree generations, it is needed to tie the variables and functions in the artificial tree to the data base of the MODUS and to regenerate viii some parts of the artificial tree if necessary. The resulting three after this process, is called real tree. Kernel functions of the MODUS: Kernel functions are the inner functions of the compilers and interpreters. The kernel functions of the MODUS as follows; Let: It lets the symbolic structures. Fit: It fits the symbolic structures to their numerical equivalents. Print: It prints the symbolic structures to the output environment. Compute: It computes the numerical equivalents of the symbolic struc tures and prints the result to the output environment. For: It makes the loop for the iterative processes. While: It also makes the loop for the iterative processes. If: It logically compares the symbolic structures. Push: It pushes an element to the stack. Pop: It pops an element from the stack. Free: It releases the informations of the elements. Run: It runs the part of the program in the disk environment. System: It processes the operating system functions. Symbolic derivations for the MODUS: The symbolic derivations get the symbolic expression after its derivations for the given variable. MODUS can do this succesfully. Examples for the MODUS language: MODUS.MDS: x := y*z; f(x,y) := x*y - Sin(x) ; Ti := f(t,z); g(t) := f(t,u) * t; c(u,v) := f(u+v, u-v) ; Print c (x, y+z) ; Print c(f(x,y), f(u,v)) + x; x = 3; Compute 4*x + 5; Compute f (x, 2) ; Free x; Print Deriv(f (x,y), x) ; Print Deriv(Deriv(4*x*x+3, x), x) ; d := Deriv(Sin(x), x) ; Print Deriv(d, x) ; $ ix MODUS.OUT: IN: Run "mtez.mds"; OUT: lone IK: x := y*z; OUT: None IN: f(x,y) := x*y - Sin(x) ; OUT: None IN: u : = f(t,z); OUT: None IN: g(t) := f(t,u) * t; OUT: None IN: c(u,v) := f(u+v, u-v) ; OUT: None IN: Print c(x, y+z) ; OUT: ( ( ( (y*z) + (y + z) ) *((y*z) - (y+z)))-(Sin((y*z)+(y+z)))) II: Print c(f(x,y), f(u,v)) + x; OUT: (((((((y*z)*y)-(Sin((y*z))))+ ( ( ( ( t * z ) - ( Sin ( t ) ) ) * v ) - ( Sin ( ((t*z)-(Sin(t)))))))*((((y*z)* y)-(Sin((y*z))))-((((t*z)- ( Sin ( t ) ) ) * v ) - ( Sin ( ( ( t * z) - ( Sin ( t ) ) ))))))-( Sin (((( y * z ) * y ) - ( Sin ( ( y * z ) ) ) ) + ( ( ( ( t * z ) - ( Sin ( t ) ) ) * v ) - ( Sin ( ( ( t * z ) - ( Sin ( t ) ) ))))))) + (y*z)); XI IN: Print Deriv(f (x,y), x) ; OUT: ( ( y ) ) - ( ( Cos ( x ) ) ) ) j IN: Print Deriv(Deriv(x*x*4+3, x), x) ; OUT: ( ( ( 8.000000 ) ) ) ) ; IN: d := Deriv(Sin(x), x) ; OUT: None IN: Print Deriv(d, x) ; OUT: ( ( - ( Sin ( x ) ) ) ) ;