Recursion Issues with operator comma.

Charlie_Hdz

Hi developers.

I'm working in a PROPCompiler, where I created a Syntactic Tree and a few traslators to make some outputs such ((a->b)&(b->c)->(a->c)).

Well, I was testing with a simple proposition:

int root= p.And(p.If(p.atom("A"),p.atom("B")),p.Not(p.atom("C")));

this isn't very relevant, but the problem here is that should be as this:

(A->B)&!C

but the output is :

((B->!(C) ) &!(C) )

I tested the code in Windows (Vs13) and works very fine.

But in Linux (Qt 5.3) isn't working.

In the book of Deitel & Deiltel, I was looking for some information about recursion and I found this setence:

Programs that depend on the order of evaluation of the operands of operators other than &&, ||, ?: and the comma (,) operator can function differently with different compilers.

I'm very confused and I suspect that there's a difference with Gcc compiler.

Would you like to help me?

Thanks yall.

Rondog

I think this is more about operator precidence (maybe ?). A comma has low precidence. When you combine brackets or other operators you might end up with something unexpected.

Regarding your comment:
Programs that depend on the order of evaluation of the operands of operators other than &&, ||, ?: and the comma (,) operator can function differently with different compilers.

The order operators are evaluated is well defined (defacto or actual standard) and I am pretty sure every compiler will follow the same rules. If there is an example of a difference between VS and GCC I for one would like to know more about it.

Do you have an example of your code (not pseudo code). I don't see how a recursive call fits into this.

Charlie_Hdz

Before all, Thanks Rondog for you reply.

Let's start. From PROPCompiler (Statically Linked Library) , there are traslate functions(Spanish Traslate, Infix Traslate x86Traslate, ect) , they intepret the table of the tree, for example...

void InfixTranslator::translate(int entry){

PROPNode Node=m_pTreeBuilder->getTree().at(entry);
switch (Node.getType()) {
case PROPNode::ATOM:
    cout<<m_pTreeBuilder->getSymbols().at(Node.first());
    cout.flush();
    break;

case PROPNode::IF:
    cout<<"(";
    translate(Node.first());
    cout<<"->";
    translate(Node.second());
    cout<<") ";
    cout.flush();
    break;

case PROPNode::IFF:
    cout<<"(";
    translate(Node.first());
    cout<<"<->";
    translate(Node.second());
    cout<<") ";
    cout.flush();
    break;

case PROPNode::OR:
    cout<<"(";
    translate(Node.first());
    cout<<" | ";
    translate(Node.second());
    cout<<") ";
    cout.flush();
    break;

case PROPNode::AND:
    cout<<"(";
    translate(Node.first());
    cout<<"&";
    translate(Node.second());
    cout<<") ";
    cout.flush();
    break;

case PROPNode::NOT:
    cout<<"!(";
    translate(Node.first());
    cout<<") ";
    cout.flush();
    break;
}

}

The tree interface is as next:

#include <QList>
#include <QString>
#include <QMap>
#include "propnode.h"

class PROPTreeBuilder
{
private:
QList<PROPNode> m_lstTree;
QList<QString> m_lstSymbol;
QMap<QString,int> m_mapSymbol2Entry;
QMap<int,QString> m_mapEntry2Symbol;
public:
PROPTreeBuilder();
int atom(QString string);
int Not(int first);
int If(int first,int second);
int And(int first, int second);
int Iff(int first,int second);
int Or(int first, int second);
QList<PROPNode> getTree(){return this->m_lstTree;}
QList<QString> getSymbols(){return this->m_lstSymbol;}
};

Next the tree implementation:

PROPTreeBuilder::PROPTreeBuilder()
{
m_lstTree.clear();
m_lstSymbol.clear();
}

int PROPTreeBuilder::atom(QString strId){
QMap<QString,int>::const_iterator it=m_mapSymbol2Entry.find(strId);
if(it != m_mapSymbol2Entry.end())
return it.value();
else{
m_mapSymbol2Entry.insert(strId,m_lstTree.size());
m_mapEntry2Symbol.insert(m_lstTree.size(),strId);
m_lstTree.push_back(PROPNode(PROPNode::ATOM,m_lstSymbol.size(),-1));
m_lstSymbol.push_back(strId);
return m_lstSymbol.size()-1;
}
}

int PROPTreeBuilder::Not(int first){
m_lstTree.push_back(PROPNode(PROPNode::NOT,first,-1));
return m_lstTree.size()-1;
}

int PROPTreeBuilder::And(int first, int second){
m_lstTree.push_back(PROPNode(PROPNode::AND,first,second));
return m_lstTree.size()-1;
}

int PROPTreeBuilder::If(int first, int second){
m_lstTree.push_back(PROPNode(PROPNode::IF,first,second));
return m_lstTree.size()-1;
}

int PROPTreeBuilder::Iff(int first, int second){
m_lstTree.push_back(PROPNode(PROPNode::IFF,first,second));
return m_lstTree.size()-1;
}

int PROPTreeBuilder::Or(int first, int second){
m_lstTree.push_back(PROPNode(PROPNode::OR,first,second));
return m_lstTree.size()-1;
}

And finally the main.cpp from testbed:

#include <QCoreApplication>
#include "proptreebuilder.h"
#include "translator.h"
#include "spanishtraslator.h"
#include "infixtranslator.h"
#include "x86translator.h"
#include"rpntranslator.h"

int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
PROPTreeBuilder p;
SpanishTraslator s;
InfixTranslator i;
X86Translator x;
RPNTranslator r;
r.setTreeBuilder(&p);
s.setTreeBuilder(&p);
i.setTreeBuilder(&p);
x.setTreeBuilder(&p);

int root= p.And(p.If(p.atom("A"),p.atom("B")),p.Not(p.atom("C")));
x.translate(root);
i.translate(root);
s.translate(root);
r.translate(root);
return a.exec();

}

The problems raise when if the second parameter of a binary operation (AND, OR, IF,IFF) is a binary operation too.

int root= p.And(p.If(p.atom("A"),p.atom("B")),p.atom("C")); Works Fine

int root= p.And(p.If(p.atom("A"),p.atom("B")),p.Not(p.atom("C"))); Changes the parameter takes .

Inteand of taking A and B as parameters, IF() takes B and !C, and I dont know why!!

Rondog

Okay, I understand your question. You are writing an expresson compiler (evaluator) and you are having problems with operator precidence.

I don't have any suggesting for in-fix processing of expressions. I have written expression parsers before but these rely on converting into post-fix notation and from what I have read in-fix expression parsing isn't so easy.

Maybe something along these lines: Shunting Yard Algorithm

Charlie_Hdz

Hi Rondog, I'm sorry to reply later...

I resolved the problem already.

It's about implementation of the PROPTree...

The function of the PROPTree what create and return the elements of the tree must return the last index of the tree, and I return a m_Symbol.size() in the PROPTree::atom(), so that was the error.

I'm very grateful about your help.

Thank You.