c++ parser, wo versteckelt sich der Fehler?

jkallup

Erfahrenes Mitglied
Code:
#include <stdio.h>

#include <iostream>
#include <vector>

#include <QString>
#include <QVariant>
#include <QVector>
#include <QMessageBox>
#include <QRegExp>

#include <QDebug>

int line_no  = 1;
int file_eof = 0;
int last_op  = 0;

const int cmd_invalid     = 0;
const int cmd_assign      = 1;  // var = 12
const int cmd_assign_plus = 2;  // var = 12 + 44
const int cmd_assign_new  = 3;  // var = new ...

enum SymbolType_ {
    NoError,
    NumberError,
    EndOfText
};
SymbolType_ SymbolType;

// -------------------
// our AST struct ...
// -------------------
struct MyNode {
public:
    int      command;
    QVariant value;
    MyNode * lhs;
    MyNode * rhs;
};
QVector<MyNode> eval_ast;

QString newnum;
QString number, ident;

int pos = -1; // buffer position
bool in_comment  = false;
bool end_of_file = false;

int SkipWhitespaces(char *buffer)
{
    int c = 0;
    while (1) {
        c = buffer[pos++];
        if (isspace(c))
        continue;
        break;
    }
    return c;
}

QString GetIdent(char *buffer)
{
    int c = 0;
    while (1) {
        c = buffer[pos++];
        if (isalpha(c)) {
            ident += c;
            continue;
        }   break;
    }
    return ident;
}

QString GetNumber(char *buffer)
{
    int c = 0;
    while (1) {
        c = buffer[pos];
        if (isdigit(c)) {
            number += c;
            ++pos;
            continue;
        }
        else if (c == '.') {
            number += '.';
            ++pos;
            continue;
        }
        else if (c == '+' || c == '-'
             ||  c == '*' || c == '/') {
            last_op = c;
            return number;
        }
        else if (c == EOF || c == 0) {
            last_op = c;
            return number;
        }
        else if (isspace(c)) {
            return number;
        }
        else {
            throw QString("number expected, wrong type: >>%1<<").arg(c);
            break;
        }
    }
    return number;
}

int Match(char *buffer, char expected)
{
    if (SkipWhitespaces(buffer) == expected)
    return expected;
    throw QString("Expected token '%1' at position: %2")
        .arg(expected)
        .arg(pos);
}

// --------------------------
// execute collected data ...
// --------------------------
bool evaluate(void)
{
    MyNode ptr;
    int c = 0;
    while (!eval_ast.isEmpty()) {
        ptr = eval_ast.at(c++);
        if (ptr.value == QChar('+')) {
            double lv = ptr.lhs->value.toDouble();
            double rv = ptr.rhs->value.toDouble();
            double sv = lv + rv;
            qDebug() << "res: " << sv;
        }
        if (c+1 >= eval_ast.size())
        break;
    }
    /*
    MyNode ptr1, ptr2, ptr3;
    double val1, val2, res;

    while (!eval_stack.isEmpty()) {
        ptr1 = eval_stack.pop(); qDebug() << ptr1.oper;
        ptr2 = eval_stack.pop(); qDebug() << ptr2.value;
        ptr3 = eval_stack.pop(); qDebug() << ptr3.value;

        val1 = ptr2.value.toDouble();
        val2 = ptr3.value.toDouble();

        if (ptr1.oper == '+')
        res = val1 + val2;

        ptr1.oper  = 'N';
        ptr2.value = res;

        qDebug() << ":= " << res;
        if (eval_stack.isEmpty())
        break;

        ptr1 = eval_stack.pop/
        eval_stack.push(ptr1);
        eval_stack.push(ptr2);
        eval_stack.push(ptr3);
    }*/
    return true;
}

bool parseText(char *buffer)
{
    int flag = 0;
    double res1;
    ident .clear();
    number.clear();

    eval_ast.clear();
    MyNode ptr;

    int c;
    while (1) {
        c = SkipWhitespaces(buffer);
        if (c == 0) {
            if (SymbolType == EndOfText)
            break;
        }
        else if ((c >= 'a') && (c <= 'z')) {
            --pos;
            ident = GetIdent(buffer);
            Match(buffer,'=');
            while (1) {
                c = SkipWhitespaces(buffer);
                if (isdigit(c)) {
                    number += c;
                    number = GetNumber (buffer); okk:
                    c = SkipWhitespaces(buffer);
                    if (c == '+') { nextp:
                        QString num = number;
                        double  val1;
                        double  val2;
                        number.clear();
                        c = SkipWhitespaces(buffer);
                        if (isdigit(c)) {
                            number += c;
                            number = GetNumber(buffer);
                        }
                        else
                        throw QString("number or ident expected.");

                        val1 = number.toDouble();
                        val2 = num   .toDouble();
                        res1 = val1  + val2;

                        //ptr      = new MyNode;
                        ptr.rhs = new MyNode;
                        ptr.lhs = new MyNode;

                        ptr.value = '+';

                        if (val1 < val2) {
                            ptr.rhs->value = val2;
                            ptr.lhs->value = val1;
                        }
                        else {
                            ptr.lhs->value = val2;
                            ptr.rhs->value = val1;
                        }
                        eval_ast.append(ptr);

                        c = SkipWhitespaces(buffer);
                        if (c == '+') {
                            number.clear();
                            c = SkipWhitespaces(buffer);
                            if (isdigit(c)) {
                                number += c;
                                number = GetNumber(buffer);
                                qDebug() << number;
                                val1 = number.toDouble();
                                double re  = val1 + res1;
                                qDebug() << "re: " << re;
                                goto okk;
                            }
                            else {
                                if (c == EOF || c == 0)
                                break;
                            }
                        }   else {
                            if (c == EOF || c == 0)
                            break;
                        }
                    }
                    if (c == EOF || c == 0) {
                        if (flag == 0)
                        break;
                    }
                }
                else if (c == '+' || c == '-'
                     ||  c == '*' || c == '/') {
                     goto nextp;
                }
                else if (c == EOF || c == 0) {
                    if (flag > 0)
                    break;
                    throw QString("number or ident expected.");
                }
            }
        }
        if (flag > 0 || c == 0 || c == EOF)
        break;
    }   return evaluate();
}

bool parseText(QString str)
{
    char buffer[str.size()+1];
    bool r = false;
    try {
        line_no = 1;
        pos = 0;
        file_eof = 0;

        ident .clear();
        number.clear();

        strcpy(buffer,str.toLatin1().data());
        std::cout << buffer << "\n";

        r = parseText((char*)buffer);
        if (r == false) {
            QMessageBox::critical(0,"Error",
            QString("Syntax Error in line: %1").arg(line_no));
            return false;
        }
        QMessageBox::information(0,"Info","SUCCESS");
        //evaluate();

        return true;
    }
    catch (QString &e) {
        QMessageBox::critical(0,"Error",
        QString("Error in line: %1\n%2")
        .arg(line_no)
        .arg(e));
    }
    catch (int &e) {
        if (e > 0) {
            if (e == 2)
            QMessageBox::critical(0,"Error",
            QString("Error in line: %1").arg(line_no));
            r = false;
        }
    }

    return r;
}
 

Endurion

Erfahrenes Mitglied
Äh, geht es etwas genauer?
Es kompiliert nicht?
Du machst etwas, es passiert etwas, aber du erwartest etwas anderes? Die drei Etwasse im Satz davor bitte erläutern.
 

jkallup

Erfahrenes Mitglied
Hallo,
ich möchte sowas wie einen AST abstract syntax tree basteln und habe mich da irgendwie verzettelt:
wie ich das aber verstanden habe, wird der kleinste Wert links, der größte rechts angeknubbelt.

Code:
typedef struct _MyNode {
public:
    int      command;
    QChar    op;
    QVariant value;
    struct _MyNode * lhs;
    struct _MyNode * rhs;
}
MyNode;
MyNode *eval_ast = nullptr;

void add_astnode(MyNode **root, double val1, double val2)
{
    MyNode *tmp, *new_node;
    bool found = false;

    tmp = (*root);
    while (!found) {
        if (val1 < tmp->value.toDouble()) {
            if (tmp->lhs != nullptr)
            tmp = tmp->lhs; else
            found = true;
        }
        else if (val1 == tmp->value.toDouble())
        found = true;
        else {
            if (tmp->rhs != nullptr)
            tmp = tmp->rhs; else
            found = true;
        }
    }
    if (val1 != tmp->value.toDouble()) {
        new_node = new MyNode;
        new_node->lhs   = nullptr;
        new_node->rhs   = nullptr;
        new_node->value = val1;
        if (val1 < tmp->value.toDouble())
        tmp->lhs = new_node; else
        tmp->rhs = new_node;
    }
}

    eval_ast = new MyNode;
    eval_ast->lhs = nullptr;
    eval_ast->rhs = nullptr;
    eval_ast->value = "Root";
 

Endurion

Erfahrenes Mitglied
Ich meinte das ganz penibel genau :)

Das sind bisher nur Ausschnitte, mit denen man nichts machen kann, ausser rumraten, weil wir nicht wissen, wie du diese aufrufst.

Wie sieht das komplette Programm aus? Wie rufst du die Routinen auf? Was erwartest du, das passiert? Was passiert tatsächlich?

Schon mal mit dem Debugger reingegangen, um zu sehen, ob der Ablauf so ist, wie du es erwartest?
 

jkallup

Erfahrenes Mitglied
der Quellcode oben (_MyNode) stellt ja einen binären Baum dar.
man kann ihn befüllen mit:

add_astnode(&eval_ast,12);
add_astnode(&eval_ast,1);
...

aber er stellt doch somit keinen AST dar - oder?
und genau das brauche ich - einen AST.
mir geht es jetzt nicht darum, hier einen kompletten Parser aufzustellen.
Sondern vielmehr dadrum, wie ein AST befüllt und iteriert werden kann.

um das Programm ablauffähig zu machen, kannst doch die Zeilen 43-46 in ein main Block setzen.
Er funktioniert, aber halt auf BT Ebene.
 

jkallup

Erfahrenes Mitglied
so update:
jetzt bleibt nur noch die frage, wie der ast durchlaufen werden kann ...
ich erhalte nach einen Schritt einen Speicherfehler.
hab im Code ein Kommentar gesetzt

Code:
typedef struct _MyNode {
public:
    SymbolType_      command;
    QChar            op;
    QVariant         value;
    _MyNode * parent;
    _MyNode * lhs;
    _MyNode * rhs;
}
MyNode;
MyNode *eval_ast = nullptr;

void print_ast()
{
    MyNode * tmp = eval_ast;
    while (1) {
        if (tmp->lhs == nullptr) break;
        if (tmp->rhs == nullptr) break;
        qDebug() << "res: " << tmp->value;
        if (tmp->lhs != nullptr)   {
            qDebug() << "1111";  // dabach crash
            tmp = tmp->lhs;
        }
        if (tmp->rhs != nullptr) {
            qDebug() << "222";
            tmp = tmp->rhs;
        }
    }
}

void add_astnode(QChar op, double val1, double val2)
{
    MyNode * tmp, *new_node;

    //tmp = (*root);
    tmp = eval_ast;

    new_node = new MyNode;
    new_node->lhs   = nullptr;
    new_node->rhs   = nullptr;

    if (op == QChar('+'))
    new_node->op = QChar('+');

    if (val1 < val2) {
        new_node->lhs = new MyNode;
        new_node->lhs->value = val2;
        tmp = new_node->lhs;
    }
    else {
        qDebug() << "A: " << val1;
        qDebug() << "B: " << val2;

        new_node->rhs = new MyNode;
        new_node->rhs->value = val1;
        tmp = new_node->rhs;
    }

    tmp->parent        = new MyNode;
    tmp->parent->value = QString("assign");

    eval_ast = tmp;

    qDebug() << "C:> " << tmp->value;
}

bool test()
{
    eval_ast = new MyNode;
    eval_ast->lhs = nullptr;
    eval_ast->rhs = nullptr;

    eval_ast->parent = new MyNode;
    eval_ast->parent->value = "root";

    eval_ast->op  = QChar('+');

    add_astnode('+', 3, 2);
    qDebug() << "printer1";
    print_ast  ();
    qDebug() << "printer2";
    return true;

/* output:
$ ./keyBase
A:  3
B:  2
C:>  QVariant(double, 3)
printer1
res:  QVariant(double, 3)
1111
Speicherzugriffsfehler
*/
}
 

Endurion

Erfahrenes Mitglied
Blind geraten würde ich sagen, das Problem liegt an den Zeilen hier.

Du gibst "1111" aus, tmp wird auf tmp->lhs gesetzt. Meine Vermutung: tmp ist danach NULL (oder nullptr)

Jetzt läufst du in die zweite If-Schleife und greifst ohne Prüfung auf tmp->rhs zu, Null-Pointer-Zugriff, crash.

An der Stelle musst du dich wohl entscheiden: Wenn du zwei Stränge hast, kannst du nur einen entlang laufen. Und/oder die Prüfung auf den rhs-Zweig nur dann angehen, wenn der lhs-Zweig nicht gesetzt ist.


Mit einem Debugger hättest du das übrigens auch sofort gesehen, Null-Pointer-Zugriff, Cursor wird auf betroffen Befehl gesetzt, Variablen ansehen, aha!

Code:
if (tmp->lhs != nullptr)   {
            qDebug() << "1111";  // dabach crash
            tmp = tmp->lhs;
        }
        if (tmp->rhs != nullptr) {
            qDebug() << "222";
            tmp = tmp->rhs;
        }