Vous ne pouvez pas sélectionner plus de 25 sujets
Les noms de sujets doivent commencer par une lettre ou un nombre, peuvent contenir des tirets ('-') et peuvent comporter jusqu'à 35 caractères.
462 lignes
11 KiB
462 lignes
11 KiB
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
typedef struct Node Node;
|
|
typedef struct Array Array;
|
|
typedef struct Symbol Symbol;
|
|
typedef struct SymbolTable SymbolTable;
|
|
|
|
struct Array {
|
|
Node **elements;
|
|
int length;
|
|
};
|
|
|
|
struct Symbol {
|
|
char *name;
|
|
int value;
|
|
};
|
|
|
|
struct SymbolTable {
|
|
Symbol **elements;
|
|
int length;
|
|
};
|
|
|
|
#define SymbolTable_initialiser {0,0}
|
|
SymbolTable symbolTable= SymbolTable_initialiser;
|
|
|
|
Symbol *createSymbol(char *name) {
|
|
Symbol *symbol= calloc(1, sizeof(Symbol));
|
|
symbol->name= strdup(name);
|
|
return symbol;
|
|
}
|
|
|
|
Symbol *intern(char *name){
|
|
int left=0,right=symbolTable.length-1;
|
|
|
|
while(left<=right){
|
|
int middle=(left+right)/2;
|
|
int comp=strcmp(name,symbolTable.elements[middle]->name);
|
|
|
|
if(comp<0){
|
|
right=middle-1;
|
|
}
|
|
else if(comp>0){
|
|
left=middle+1;
|
|
}
|
|
else{
|
|
return symbolTable.elements[middle];
|
|
}
|
|
}
|
|
|
|
symbolTable.elements= realloc(symbolTable.elements,sizeof(symbolTable.elements[0]) * (symbolTable.length+1));
|
|
memmove(symbolTable.elements+left+1,symbolTable.elements+left,(symbolTable.length-left)*sizeof(symbolTable.elements[0]));
|
|
symbolTable.length++;
|
|
return symbolTable.elements[left]=createSymbol(name);
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/*
|
|
void addSymbol(SymbolTable *symbolTable, Symbol *symbol) {
|
|
|
|
if(symbolTable->length==0){
|
|
symbolTable->length++;
|
|
symbolTable->elements= realloc(symbolTable->elements,sizeof(Symbol) * symbolTable->length);
|
|
symbolTable->elements[0]=symbol;
|
|
}
|
|
else{
|
|
printf("taille>0\n");
|
|
|
|
symbolTable->length++;
|
|
symbolTable->elements= realloc(symbolTable->elements,sizeof(Symbol*) * symbolTable->length);
|
|
int j=0;int k=0;int indice =0;
|
|
while(j<symbolTable->length-1 && k==0){
|
|
|
|
if(strcmp(symbol->name,symbolTable->elements[j]->name)<=0){
|
|
|
|
printf("plus petit que le reste\n");
|
|
k=k+1;
|
|
}
|
|
else{
|
|
printf("plus grand\n");
|
|
j=j+1;indice=j;
|
|
}
|
|
|
|
}
|
|
|
|
for(k=symbolTable->length-1;k>indice;k--){
|
|
symbolTable->elements[k]=symbolTable->elements[k-1];
|
|
}
|
|
symbolTable->elements[indice]=symbol;
|
|
|
|
}
|
|
|
|
}
|
|
*/
|
|
int binary_search(SymbolTable *st, char *c){
|
|
int start=0,end=st->length-1;
|
|
int m=0;
|
|
while(end-start>1){
|
|
|
|
m=(end+start)/2; //printf("char : %s\n %s",c,st->elements[m]->name);
|
|
// printf("start : %i End : %i\n Compare : %i\n",start,end,strcmp(c,st->elements[m]->name));/**/
|
|
if(strcmp(c,st->elements[m]->name)==0){
|
|
return m;
|
|
}
|
|
else if(strcmp(c,st->elements[m]->name)<0){
|
|
end=m-1;
|
|
}
|
|
else{
|
|
start=m+1;
|
|
}
|
|
m=(end+start)/2;
|
|
}
|
|
// printf("Start : %i, m : %i, end : %i char : %s size :%i\n",start,m,end,c,st->length);
|
|
if(strcmp(c,st->elements[m]->name)<0){
|
|
return start;
|
|
}
|
|
else{
|
|
return end;
|
|
}
|
|
|
|
}
|
|
|
|
|
|
void addSymbol(SymbolTable *symbolTable, Symbol *symbol) {
|
|
|
|
if(symbolTable->length==0){
|
|
|
|
symbolTable->length++;
|
|
symbolTable->elements= realloc(symbolTable->elements,sizeof(Symbol) * symbolTable->length);
|
|
symbolTable->elements[0]=symbol;//printf("indice de %s = %i\n",symbolTable->elements[0]->name,0);
|
|
return;
|
|
}
|
|
else{
|
|
|
|
|
|
symbolTable->length++;
|
|
symbolTable->elements= realloc(symbolTable->elements,sizeof(Symbol*) * symbolTable->length);
|
|
int indice=binary_search(symbolTable, symbol->name);
|
|
|
|
for(int k=symbolTable->length-1;k>indice;k--){
|
|
symbolTable->elements[k]=symbolTable->elements[k-1];
|
|
}
|
|
symbolTable->elements[indice]=symbol;//printf("indice de %s = %i\n",symbolTable->elements[indice]->name,indice);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
void arrayAppend(Array *array, Node *statement) {
|
|
array->length++;
|
|
array->elements= realloc(array->elements,sizeof(Node*) * array->length);
|
|
array->elements[array->length-1] = statement;
|
|
}
|
|
|
|
/*
|
|
void fusion(SymbolTable symbTable,int n, int d, int f){
|
|
char *r[f-d+1];
|
|
int m =(d+f)/2;
|
|
int i1=d,i2=m,k=0;
|
|
while(i1<=m && i2<=f){
|
|
if(strcmp(symbTable.elements[i1]->name,symbTable.elements[i2]->name)<0){
|
|
r[k]=symbTable.elements[i1]->name;
|
|
i1++;
|
|
|
|
}
|
|
else{
|
|
r[k]=symbTable.elements[i2]->name;
|
|
i2++;
|
|
}
|
|
k=k+1;
|
|
}
|
|
while(i1<=m){
|
|
r[k]=symbTable.elements[i1]->name;
|
|
i1++;
|
|
k++;
|
|
}
|
|
while(i2<=f){
|
|
r[k]=symbTable.elements[i2]->name;
|
|
i2++;
|
|
k++;
|
|
}
|
|
for(k=0;k<=f-d;k++){
|
|
symbTable.elements[d+k]->name=r[k];
|
|
}
|
|
}
|
|
|
|
|
|
void fusion(SymbolTable symbTable,int n, int d, int f){
|
|
char *r[f-d+1];
|
|
int m =(d+f)/2;
|
|
int i1=d,i2=m,k=0;
|
|
while(i1<=m && i2<=f){
|
|
if(strcmp(symbTable.elements[i1]->name,symbTable.elements[i2]->name)<0){
|
|
r[k]=symbTable.elements[i1]->name;
|
|
i1++;
|
|
|
|
}
|
|
else{
|
|
r[k]=symbTable.elements[i2]->name;
|
|
i2++;
|
|
}
|
|
k=k+1;
|
|
}
|
|
while(i1<=m){
|
|
r[k]=symbTable.elements[i1]->name;
|
|
i1++;
|
|
k++;
|
|
}
|
|
while(i2<=f){
|
|
r[k]=symbTable.elements[i2]->name;
|
|
i2++;
|
|
k++;
|
|
}
|
|
for(k=0;k<=f-d;k++){
|
|
symbTable.elements[d+k]->name=r[k];
|
|
}
|
|
}
|
|
|
|
|
|
void triFusion(SymbolTable symbTable,int n,int d,int f){
|
|
int m=(d+f)/2;
|
|
triFusion(symbTable,n,d,m);
|
|
triFusion(symbTable,n,m+1,f);
|
|
fusion(symbTable,n,d,f);
|
|
}
|
|
*/
|
|
|
|
enum opcode {
|
|
PRINT,
|
|
INT,
|
|
VAR,
|
|
ADD,
|
|
REPEAT,
|
|
ASSIGN,
|
|
BLOC
|
|
};
|
|
|
|
|
|
struct Node
|
|
{
|
|
enum opcode type;
|
|
union {
|
|
Symbol *symbol;
|
|
Array statement;
|
|
Node *children[2];
|
|
int intValue;
|
|
int index;
|
|
};
|
|
};
|
|
|
|
|
|
Node *mkNode(enum opcode type)
|
|
{
|
|
Node *node= calloc(1, sizeof(Node));
|
|
node->type= type;
|
|
return node;
|
|
}
|
|
|
|
Node *mkPrint(Node *expr)
|
|
{
|
|
Node *node= mkNode(PRINT);
|
|
node->children[0]= expr;
|
|
return node;
|
|
}
|
|
|
|
Node *mkInt(int value)
|
|
{
|
|
Node *node= mkNode(INT);
|
|
node->intValue= value;
|
|
return node;
|
|
}
|
|
|
|
Node *mkVar(Symbol *symbol)
|
|
{
|
|
Node *node= mkNode(VAR);
|
|
node->symbol= symbol;
|
|
return node;
|
|
}
|
|
|
|
Node *mkAdd(Node *lhs, Node *rhs)
|
|
{
|
|
Node *node= mkNode(ADD);
|
|
node->children[0]= lhs;
|
|
node->children[1]= rhs;
|
|
return node;
|
|
}
|
|
|
|
Node *mkRepeat(Node *count, Node *body)
|
|
{
|
|
Node *node= mkNode(REPEAT);
|
|
node->children[0]= count;
|
|
node->children[1]= body;
|
|
return node;
|
|
}
|
|
|
|
Node *mkAssign(Symbol *symbol, Node *assignable)
|
|
{
|
|
Node *node= mkNode(ASSIGN);
|
|
node->symbol= symbol;
|
|
node->children[1]= assignable;
|
|
return node;
|
|
}
|
|
|
|
Node *mkBloc(void)
|
|
{
|
|
Node *node= mkNode(BLOC);
|
|
node->statement.length= 0;
|
|
node->statement.elements= 0;
|
|
return node;
|
|
}
|
|
void blocAppend(Node *bloc, Node *statement) {
|
|
arrayAppend(&bloc->statement, statement);
|
|
}
|
|
|
|
|
|
|
|
|
|
int variables[26];
|
|
|
|
int evaluate(Node *node)
|
|
{
|
|
switch (node->type) {
|
|
case PRINT: {
|
|
int value= evaluate(node->children[0]);
|
|
printf("PRINT %i\n", value);
|
|
return value;
|
|
}
|
|
case INT: {
|
|
return node->intValue;
|
|
}
|
|
case VAR: {
|
|
return node->symbol->value;
|
|
}
|
|
case ADD: {
|
|
int lhs= evaluate(node->children[0]);
|
|
int rhs= evaluate(node->children[1]);
|
|
return lhs + rhs;
|
|
}
|
|
case REPEAT: {
|
|
int count= evaluate(node->children[0]);
|
|
Node *body= node->children[1];
|
|
int result= 0;
|
|
while (count-- > 0) result= evaluate(body);
|
|
return result;
|
|
}
|
|
case ASSIGN: {
|
|
int assignable= evaluate(node->children[1]);
|
|
node->symbol->value= assignable;
|
|
return assignable;
|
|
}
|
|
case BLOC: {
|
|
int Nb_instruction= node->statement.length;
|
|
int result= 0;
|
|
for(int i=0; i < Nb_instruction; i++) {
|
|
result= evaluate(node->statement.elements[i]);
|
|
}
|
|
return result;
|
|
}
|
|
}
|
|
printf("this cannot happen\n");
|
|
abort();
|
|
}
|
|
|
|
int findS(SymbolTable *st, char *c){
|
|
int i=0;
|
|
while(i<st->length){
|
|
if (strcmp(c,st->elements[i]->name)==0){
|
|
return st->elements[i]->value;
|
|
}
|
|
else{
|
|
i=i+1;
|
|
}
|
|
}
|
|
addSymbol(st,createSymbol(c));
|
|
return 0;
|
|
}
|
|
|
|
|
|
|
|
int main(int argc, char **argv)
|
|
{
|
|
printf("%p\n",intern("red"));
|
|
printf("%p\n",intern("red"));
|
|
printf("%p\n",intern("red"));
|
|
printf("%p\n",intern("yellow"));
|
|
printf("%p\n",intern("yellow"));
|
|
printf("%p\n",intern("red"));
|
|
printf("%p\n",intern("black"));
|
|
printf("%p\n",intern("white"));
|
|
printf("%p\n",intern("red"));
|
|
printf("%p\n",intern("yellow"));
|
|
printf("%p\n",intern("black"));
|
|
printf("%p\n",intern("white"));
|
|
printf("%p\n",intern("red"));
|
|
printf("%p\n",intern("yellow"));
|
|
printf("%p\n",intern("black"));
|
|
printf("%p\n",intern("white"));
|
|
/* int valeur1=findS(&symbolTable, "black");
|
|
printf("Valeur de black : %i \n",valeur1);*/
|
|
|
|
|
|
for(int i= 0; i<symbolTable.length; i++) {
|
|
printf("number : %i, value : %s\n",i, symbolTable.elements[i]->name);
|
|
}
|
|
|
|
//findS(SymbolTable *st, char *c) trouve un symbole dans la table, retourne la valeur, sinon cr�e une nouveau symbole dans la table
|
|
//d'abord lin�aire
|
|
//int strcmp(char *a, char *b) 0 if theyr are the same - if a <b + if a>b
|
|
|
|
variables[0]= 1;
|
|
variables[1]= 2;
|
|
variables[2]= 40;
|
|
intern("cyan")->value=40;
|
|
|
|
|
|
/*Node *program=
|
|
mkRepeat(mkAdd(mkVar(0), mkVar(1)),
|
|
mkPrint(mkInt(42)));
|
|
|
|
|
|
REPEAT A+B {
|
|
PRINT C = C + 1
|
|
}
|
|
|
|
Node *program=
|
|
mkRepeat(mkAdd(mkVar(0), mkVar(1)),
|
|
mkPrint(mkAssign(mkInt(2),
|
|
mkAdd(mkVar(2),
|
|
mkInt(1)))));*/
|
|
|
|
Node *bloc = mkBloc();
|
|
blocAppend(bloc, mkPrint(mkAssign(intern("purple"),
|
|
mkAdd(mkVar(intern("purple")),
|
|
mkInt(1)))));
|
|
|
|
blocAppend(bloc,mkPrint(mkAssign(intern("cyan"),
|
|
mkAdd(mkVar(intern("cyan")),
|
|
mkInt(1)))));
|
|
|
|
/*Node *instruction[2];
|
|
instruction[0] = mkPrint(mkAssign(mkInt(2),
|
|
mkAdd(mkVar(2),
|
|
mkInt(1))));
|
|
|
|
instruction[1] = mkPrint(mkAssign(mkInt(1),
|
|
mkAdd(mkVar(1),
|
|
mkInt(1))));*/
|
|
|
|
Node *program=
|
|
mkRepeat(mkInt(3),
|
|
bloc);
|
|
|
|
int result= evaluate(program);
|
|
|
|
printf("finished with result %i\n", result);
|
|
|
|
return 0;
|
|
}
|