next up previous
Nächste Seite: Re: Aufgaben und Übungen, Aufwärts: Graphen, Schaltwerke und Zahlen Vorherige Seite: Re: Aufgaben und Übungen,

Re: Aufgaben und Übungen, 

/*
Grammatik

Sporadische Sammlung
- Zuweisung
- Addition
if
- Vergleiche
    - <=, >=, ==, !=, <, >
- Subtraktion
- Shift
    << >>
- Null setzen

Operationen
    - Mathematische:
        + (Addition)
        - (Subtraktion)
    - Verschieben
        >> Rechtsshift
        << Linksshift
    - 0 setzen
Vergleiche
    - <=, >=, ==, !=, <, >
Zuweisung
    <-

Zeichensatz: Variablen, Register, Operatoren und Konstante Werte

Operand ::= <Register> | <Const>
CMP ::= <= | >= | == | != | < | >
MathOperator ::= + | - | << | >>
BitBooleanOperator ::= '\&amp;\&amp;' | '||' | '!'
Operator ::= <MathOperator> | <BitBooleanOperator>
Expr ::= <Register> <- <Operand> | <Operand> <Operator> <Operand> | 0
Condition ::= IF <Register> <CMP> <Operand> THEN <Program> FI

Programm ::= <Expr> | <Condition> <Program>
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define     MAX_STATES                              1024
#define     MAX_EXPR_CONST_VAL                      128
#define     MAX_EXPR_REG_VAL                        4
#define     FIRST_REG_VAL                           'a'
#define     MAX_EXPR_OPERATOR_VAL                   6
#define     MAX_EXPR_CMP_OPERATOR_VAL               5
#define     RAND_OPERAND_CONST_REGISTER             2
#define     RAND_EXPR_OPERATOR_OPERAND_FOLLOW       2
#define     RAND_COND_TRUE_FALSE_DESICION           2
#define     RAND_PROGRAM_COND_EXPR_DESICION         4
#define     IF_ELSE_DEPTH                           3
#define     STD_PROGRAM_N                           6
#define     STD_PROGRAM2_N                          4
#define     RAND_COND_END_OR_GO_ON                  3

FILE *fout = NULL;

int lineelse [MAX_STATES];
int lineif [MAX_STATES];
int linegoto1 [MAX_STATES];
int linegoto2 [MAX_STATES];
int stateif = 0;
int stateelse = 0;
int stategoto1 = 0;
int stategoto2 = 0;
int stategotodst = 0;
int gotodst [MAX_STATES];

int line = 0;
int nline = 0;
int maxstate = 0;
int realyusedstaten = 1;

char *opstr [] = {"+", "-", "<<", ">>", "\&amp;\&amp;", "||", "!"};
char *cmpstr [] = {"<=", ">=", "==", "!=", "<", ">"};

void operator (void);
void cmp (void);
void operand (void);
void expr (int);
void condition (int, int, int, int);
void condition2 (int, int, int, int);
void program (int, int, int, int);
void program2 (int, int, int, int);
void registr (void);
void cnst (void);
void operator (void);
void printemptyspace (int);

void printemptyspace (int n) {
    int i;

    for (i = 0;  i < n*2;  i++)
        fprintf (fout, " ");
}


void registr (void) {
    fprintf (fout, " %c ", (rand () % MAX_EXPR_REG_VAL) + FIRST_REG_VAL);
return;
}

void cnst (void) {
    fprintf (fout, " %i ", rand () % MAX_EXPR_CONST_VAL);
return;
}

void operator (void) {
    fprintf (fout, " %s ", opstr [rand () % MAX_EXPR_OPERATOR_VAL]);
return;
}

void cmp (void) {
    fprintf (fout, " %s ", cmpstr [rand () % MAX_EXPR_CMP_OPERATOR_VAL]);
return;
}

void operand (void) {
    if ((rand () % RAND_OPERAND_CONST_REGISTER) == 0)
        cnst ();
    else
        registr ();
return;
}

void expr (int emptyspacen) {
    fprintf (fout, "%4i:", line++);
    printemptyspace (emptyspacen);
    registr ();
    fprintf (fout, " <- ");
    operand ();
    if ((rand () % RAND_EXPR_OPERATOR_OPERAND_FOLLOW) == 0) {
        operator ();
        operand ();
    }
    fprintf (fout, "n");
return;
}

void condition (int n, int i, int emptyspacen, int depth) {
    int goto1or2;


    lineif [stateif++] = line;
    fprintf (fout, "%4i:", line++);
    printemptyspace (emptyspacen);
    fprintf (fout, " IF ", line);
    registr ();
    cmp ();
    operand ();
    fprintf (fout, " THEN n", line);
    program (n, i+1, emptyspacen+1, depth+1);
    linegoto1 [stategoto1++] = line;
    fprintf (fout, "%4c ", ' ');
    printemptyspace (emptyspacen+1);
    fprintf (fout, "      %4cn", ' ');
    lineelse [stateelse++] = line;
    fprintf (fout, "%4c ", ' ');
    printemptyspace (emptyspacen);
    fprintf (fout, " ELSE n", line);
    program (n, i+1, emptyspacen+1, depth+1);
    linegoto2 [stategoto2++] = line;
    fprintf (fout, "%4c ", ' ');
    printemptyspace (emptyspacen+1);
    fprintf (fout, "      %4cn", ' ');
    fprintf (fout, "%4c ", ' ');
    printemptyspace (emptyspacen);
    fprintf (fout, " FI n", ' ');
return;
}


void condition2 (int n, int i, int emptyspacen, int depth) {
    int goto1or2;


    lineif [stateif++] = line;
    fprintf (fout, "%4i:", line++);
    printemptyspace (emptyspacen);
    fprintf (fout, " IF ", line);
    registr ();
    cmp ();
    operand ();
    fprintf (fout, " THEN n", line);
    program2 (n, i+1, emptyspacen+1, depth+1);
    linegoto1 [stategoto1++] = line;
    fprintf (fout, "%4c ", ' ');
    printemptyspace (emptyspacen+1);
    fprintf (fout, " GOTO %in", lineif [gotodst[stategotodst++%(realyusedstaten)]]);
    lineelse [stateelse++] = line;
    fprintf (fout, "%4c ", ' ');
    printemptyspace (emptyspacen);
    fprintf (fout, " ELSE n", line);
    program2 (n, i+1, emptyspacen+1, depth+1);
    linegoto2 [stategoto2++] = line;
    fprintf (fout, "%4c ", ' ');
    printemptyspace (emptyspacen+1);
    fprintf (fout, " GOTO %in", lineif [gotodst[stategotodst++%(realyusedstaten)]]);
    fprintf (fout, "%4c ", ' ');
    printemptyspace (emptyspacen);
    fprintf (fout, " FI n", ' ');
return;
}


void program2 (int n, int i, int emptyspacen, int depth) {
    if (((rand () % RAND_PROGRAM_COND_EXPR_DESICION) == 0))
        expr (emptyspacen);
    if (i < n) {
        program2 (n, i+1, emptyspacen, depth);
    }
return;
}

void program (int n, int i, int emptyspacen, int depth) {
    program2 (STD_PROGRAM2_N, 0, emptyspacen, depth);
    if ((rand () % RAND_COND_END_OR_GO_ON) == 0)
        condition2 (n, i+1, emptyspacen, depth+1);
    else if ((i < n) \&amp;\&amp; (depth < IF_ELSE_DEPTH))
        condition (n, i+1, emptyspacen, depth+1);
    else {
        linegoto1 [stategoto1++] = line;
        fprintf (fout, "%4c ", ' ');
        printemptyspace (emptyspacen);
        fprintf (fout, " GOTO %in", lineif [gotodst[stategotodst++%(realyusedstaten)]]);
        return;
    }
}


void connect (int n) {
    int i;
    int j;
    int t;

    gotodst [0] = rand () % n;
    for (i = 1;  i < n; ) {
        t = rand () % n;
        for (j = 0;  j < i;  j++) {
            if (gotodst [j] == t) {
                t = rand () % n;
                j = 0;
            }
        }
        if (t != i) {
            gotodst [i] = t;
            i++;
        }
    }

return;
}

int main (void) {
    time_t t;
    int j;
    srand (t = time(NULL));
    fout = stderr;
    program (STD_PROGRAM_N, 0, 0, 0);
    maxstate = line;
    srand (t);
    fout = stdout;
    /*for (j = 0;  j < stateif; j++) {
        fprintf (fout, "If %in", lineif [j]);
        fprintf (fout, "Else %in", lineelse [j]);
        fprintf (fout, "Goto 1 %in", linegoto1 [j]);
        fprintf (fout, "Goto 2 %in", linegoto2 [j]);
        }*/
    if (stateif != 0) {
        connect (stateif);
        realyusedstaten = stateif;
    }
    nline = line;
    line = 0;
    stategotodst = 0;
    srand (t);
    fprintf(stderr, "%i stategotodstn", stategotodst);
    fprintf(stderr, "%i stateifn", stateif);
    program (STD_PROGRAM_N, 0, 0, 0);
return 0;
}


/*
expr ::= expr + term | term
term ::= term * factor | factor
factor ::= '(' expr ')' | const

Bzw.

expr ::= term | term '+' expr
term ::= factor | factor '*' term
factor ::= '(' expr ')' | const

const ::= '9', '8', ..., '0'
*/

/* Lexer */
let i = 0;
let s = "((4+5*(4+2))+1)*3";

function nexttoken () {
    return s [i++];
}

function tokenback () {
    i--;
}

function expr () {
    let x;
    let y = 0;

    x = term ();
    if (nexttoken () == '+')  {
        y = expr ();
    }
    else
        tokenback ();
return x + y;
}

function term () {
    let x;
    let y = 1;

    x = factor ();
    if (nexttoken () == '*')
        y = term ();
    else
        tokenback ();
return x * y;
}

function factor () {
    let s = nexttoken ();
    let x1 = parseInt (s);
    let x;

    if (s == '(') {
        x = expr ();
        if (nexttoken () != ')')
            throw new Error("Missing closing bracket");
    }
    else if ((x1 >= 0) \&amp;\&amp; (x1 <= 9))
        x = x1;
    else
        throw new Error("Unknown or wrong character");
return x;
}

console.log (expr ());
console.log (((4+5*(4+2))+1)*3);

Sorry, dass das so lange gedauert hat, eine Variable war falsch benannt 

# expr ::= expr + term | term
# term ::= term * factor | factor
# factor ::= '(' expr ')' | const

# Bzw.

# expr ::= term | term '+' expr
# term ::= factor | factor '*' term
# factor ::= '(' expr ')' | const

# const ::= '9', '8', ..., '0'

i=0
s = "((4+5*(4+2))+1)*3";

def nexttoken ():
    global i
    j = i
    if i >= len(s):
        return 'e'
    i = i+1
    return s[j]

def tokenback ():
    global i
    i = i-1

def expr ():
    y = 0

    x = term()
    s = nexttoken ()
    if s == '+':
        y = expr()
    elif s == 'e':
        return x+y
    else:
        tokenback()
    return x+y

def term ():
    y = 1

    x = factor()
    s = nexttoken ()
    if s == '*':
        y = term ()
    elif s == 'e':
        return x*y
    else:
        tokenback()
    return x*y

def factor ():
    s = nexttoken ()
    if s.isdigit ():
        y = int(s)

    if s == '(':
        x = expr()
        if nexttoken () != ')':
            exit ()
    elif s == 'e':
        return 0
    elif (y >= 0) and (y <= 9):
        x = y
    else:
        exit ()
    return x

print(expr())

Diese Compiler habe ich selber geschrieben, entsprechend der Bakus-Naur Normalform ohne Linksrekursion - parsen sie arithmetische Terme. Zu Aussagen, kommen wir schnell - indem wir das 

>==