CppGen.cpp

/*
* Copyright 2023 Rochus Keller <mailto:me@rochus-keller.ch>
*
* This file is part of the EbnfStudio application.
*
* The following is the license that applies to this copy of the
* application. For a license to use the application under conditions
* other than those described here, please email to me@rochus-keller.ch.
*
* GNU General Public License Usage
* This file may be used under the terms of the GNU General Public
* License (GPL) versions 2.0 or 3.0 as published by the Free Software
* Foundation and appearing in the file LICENSE.GPL included in
* the packaging of this file. Please review the following information
* to ensure GNU General Public Licensing requirements will be met:
* http://www.fsf.org/licensing/licenses/info/GPLv2.html and
* http://www.gnu.org/copyleft/gpl.html.
*/

#include "CppGen.h"
#include "GenUtils.h"
#include "FirstFollowSet.h"
#include "EbnfAnalyzer.h"
#include "LaParser.h"
#include <QFile>
#include <QTextStream>
#include <QDir>
#include <QtDebug>

CppGen::CppGen():d_tbl(0),d_syn(0),d_pseudoKeywords(false),d_genSynTree(false)
{

}

bool CppGen::generate(const QString& ebnfPath, EbnfSyntax* syn, FirstFollowSet* tbl)
{
    if( syn == 0 || syn->getOrderedDefs().isEmpty() )
        return false;

    Q_ASSERT( syn != 0 );
    tbl->setSyntax(syn);

    const QByteArray nameSpace = syn->getPragmaFirst("%namespace").toBa();
    // const QByteArray nameSpace2 = nameSpace.isEmpty() ? nameSpace : ( nameSpace + "::" );
    QString module = syn->getPragmaFirst("%module").toStr();
    if( !module.isEmpty() )
        module = module + "/";
    // const EbnfSyntax::SymList suppress = syn->getPragma("%suppress");
    d_pseudoKeywords = !syn->getPragma("%pseudo_keywords").isEmpty(); // exact value doesn't matter
    d_genSynTree = syn->getPragma("%no_syntree").isEmpty(); // exact value doesn't matter
    const EbnfSyntax::SymList suppress = syn->getPragma("%suppress");

    d_tbl = tbl;
    d_syn = syn;

    const Ast::Definition* root = syn->getOrderedDefs()[0];

    QDir dir = QFileInfo(ebnfPath).dir();

    QFile header( dir.absoluteFilePath( nameSpace + "Parser.h") );
    header.open( QIODevice::WriteOnly );
    QTextStream hout(&header);
    hout.setCodec("utf-8");

    const QByteArray stopLabel = "__" + nameSpace.toUpper() + ( !nameSpace.isEmpty() ? "_" : "" ) + "PARSER__";
    hout << "#ifndef " << stopLabel << endl;
    hout << "#define " << stopLabel << endl;
    hout << "// This file was automatically generated by EbnfStudio; don't modify it!" << endl;
    hout << endl;
    if( d_genSynTree )
        hout << "#include <" << module << nameSpace << "SynTree.h>" << endl;
    else
        hout << "#include <" << module << nameSpace << "Token.h>" << endl
             << "#include <QList>" << endl;
    hout << endl;

    if( !nameSpace.isEmpty() )
        hout << "namespace " << nameSpace << " {" << endl;

    hout << endl;
    hout << "\t" << "class Scanner {" << endl;
    hout << "\t" << "public:" << endl;
    hout << "\t\t" << "virtual Token next() = 0;" << endl;
    hout << "\t\t" << "virtual Token peek(int offset) = 0;" << endl;
    hout << "\t" << "};" << endl << endl;

    hout << "\t" << "class Parser {" << endl;
    hout << "\t" << "public:" << endl;
    hout << "\t\t" << "Parser(Scanner* s):scanner(s) {}" << endl;
    hout << "\t\t" << "void RunParser();" << endl;
    if( d_genSynTree )
        hout << "\t\t" << "SynTree root;" << endl;
    hout << "\t\t" << "struct Error {" << endl;
    hout << "\t\t" << "    QString msg;" << endl;
    hout << "\t\t" << "    int row, col;" << endl;
    hout << "\t\t" << "    QString path;" << endl;
    hout << "\t\t" << "    Error( const QString& m, int r, int c, const QString& p)"
            ":msg(m),row(r),col(c),path(p){}" << endl;
    hout << "\t\t" << "};" << endl;
    hout << "\t\t" << "QList<Error> errors;" << endl;

    hout << "\t" << "protected:" << endl;
    for( int i = 0; i < syn->getOrderedDefs().size(); i++ )
    {
        const Ast::Definition* d = syn->getOrderedDefs()[i];

        if( d->d_tok.d_op == EbnfToken::Skip || ( i != 0 && d->d_usedBy.isEmpty() ) )
            continue;
        if( d->d_node == 0 ) // || d->d_tok.d_op == EbnfToken::Transparent )
            continue;

        hout << "\t\t" << "void " << d->d_tok.d_val.toStr() << (d_genSynTree ? "(SynTree*);": "();") << endl;
    }

    hout << "\t" << "protected:" << endl;
    hout << "\t\t" << "Token cur;" << endl;
    hout << "\t\t" << "Token la;" << endl;
    hout << "\t\t" << "Scanner* scanner;" << endl;
    hout << "\t\t" << "void next();" << endl;
    hout << "\t\t" << "Token peek(int off);" << endl;
    hout << "\t\t" << "void invalid(const char* what);" << endl;
    hout << "\t\t" << "bool expect(int tt, bool pkw, const char* where);" << endl;
    if( d_genSynTree )
        hout << "\t\t" << "void addTerminal(SynTree* st);" << endl;

    hout << "\t" << "};" << endl;

    if( !nameSpace.isEmpty() )
        hout << "}" << endl;

    hout << "#endif // include" << endl;

    QFile body( dir.absoluteFilePath( nameSpace + "Parser.cpp") );
    body.open( QIODevice::WriteOnly );
    QTextStream bout(&body);
    bout.setCodec("utf-8");

    bout << "// This file was automatically generated by EbnfStudio; don't modify it!" << endl;
    bout << "#include \"" << nameSpace << "Parser.h\"" << endl;
    if( !nameSpace.isEmpty() )
        bout << "using namespace " << nameSpace << ";" << endl;
    bout << endl;

    for( int i = 0; i < syn->getOrderedDefs().size(); i++ )
    {
        const Ast::Definition* d = syn->getOrderedDefs()[i];

        if( d->d_tok.d_op == EbnfToken::Skip || ( i != 0 && d->d_usedBy.isEmpty() ) )
            continue;
        if( d->d_node == 0 ) // || d->d_tok.d_op == EbnfToken::Transparent )
            continue;

        bout << "static inline bool FIRST_" << d->d_tok.d_val.toStr() << "(int tt) {" << endl;
        //EbnfAnalyzer::LlkNodes firsts;
        //EbnfAnalyzer::calcLlkFirstSet(1,firsts,d->d_node,tbl);
        Ast::NodeRefSet ns = tbl->getFirstSet(d->d_node);
#if 0
        const bool same = firsts.first() == ns;
        if( !same )
        {
            qDebug() << "diff in" << d->d_tok.d_val.toBa().constData() << ns.size() << firsts.first().size();
            QStringList sort;
            Ast::NodeRefSet::const_iterator j;
            for( j = ns.begin(); j != ns.end(); ++j )
                sort << (*j).d_node->d_tok.d_val.toStr();
            sort.sort(Qt::CaseInsensitive);
            qDebug() << sort.join(' ');
            sort.clear();
            for( j = firsts.first().begin(); j != firsts.first().end(); ++j )
                sort << (*j).d_node->d_tok.d_val.toStr();
            sort.sort(Qt::CaseInsensitive);
            qDebug() << sort.join(' ');
        }
#endif
#if 0
        qDebug() << d->d_tok.d_val.toBa();
        QStringList sort;
        Ast::NodeRefSet::const_iterator j;
        for( j = ns.begin(); j != ns.end(); ++j )
            sort << "T_"+GenUtils::symToString((*j).d_node->d_tok.d_val.toStr());
        sort.sort(Qt::CaseInsensitive);
        qDebug() << "First:" << sort.join(' ');
        sort.clear();
        Ast::NodeRefSet follow = tbl->getFollowSet(d->d_node);
        for( j = follow.begin(); j != follow.end(); ++j )
            sort << "T_"+GenUtils::symToString((*j).d_node->d_tok.d_val.toStr());
        sort.sort(Qt::CaseInsensitive);
        qDebug() << "Follow:" << sort.join(' ');
        qDebug() << "";
#endif
        if( ns.isEmpty() )
            bout << "\t" << "return false;" << endl;
        else if( ns.size() <= 5 )
        {
            bout << "\t" << "return ";
            for( Ast::NodeRefSet::const_iterator j = ns.begin(); j != ns.end(); ++j )
            {
                if( j != ns.begin() )
                    bout << " || ";
                const Ast::Node* n = (*j).d_node;
                bout << "tt == Tok_" << GenUtils::symToString(n->d_tok.d_val.toStr());
            }
            bout << ";" << endl;
        }else
        {
            bout << "\t" << "switch(tt){" << endl;
            for( Ast::NodeRefSet::const_iterator j = ns.begin(); j != ns.end(); ++j )
            {
                const Ast::Node* n = (*j).d_node;
                bout << "\t" << "case Tok_" << GenUtils::symToString(n->d_tok.d_val.toStr()) << ":" << endl;
            }
            bout << "\t\t" << "return true;" << endl;
            bout << "\t" << "default: return false;" << endl;
            bout << "\t" << "}" << endl;
        }
        bout << "}" << endl << endl;
    }

    bout << "void Parser::RunParser() {" << endl;
    if( d_genSynTree )
        bout << "\t" << "root = SynTree();" << endl;
    bout << "\t" << "errors.clear();" << endl;
    bout << "\t" << "next();" << endl;
    if( !syn->getOrderedDefs().isEmpty() )
    {
        const Ast::Definition* d = syn->getOrderedDefs().first();
        bout << "\t" << d->d_tok.d_val.toBa() << (d_genSynTree?"(&root);":"();") << endl;
    }
    bout << "}" << endl << endl;

    bout << "void Parser::next() {" << endl;
    bout << "\t" << "cur = la;" << endl;
    bout << "\t" << "la = scanner->next();" << endl;
    bout << "\t" << "while( la.d_type == Tok_Invalid ) {" << endl;
    bout << "\t\t" << "errors << Error(la.d_val, la.d_lineNr, la.d_colNr, la.d_sourcePath);" << endl;
    bout << "\t\t" << "la = scanner->next();" << endl;
    bout << "\t" << "}" << endl;
    bout << "}" << endl << endl;

    bout << "Token Parser::peek(int off) {" << endl;
    bout << "\t" << "if( off == 1 )" << endl;
    bout << "\t\t" << "return la;" << endl;
    bout << "\t" << "else if( off == 0 )" << endl;
    bout << "\t\t" << "return cur;" << endl;
    bout << "\t" << "else" << endl;
    bout << "\t\t" << "return scanner->peek(off-1);" << endl;
    bout << "}" << endl << endl;

    bout << "void Parser::invalid(const char* what) {" << endl;
    bout << "\t" << "errors << Error(QString(\"invalid %1\").arg(what),"
                    "la.d_lineNr, la.d_colNr, la.d_sourcePath);" << endl;
    bout << "}" << endl << endl;

    bout << "bool Parser::expect(int tt, bool pkw, const char* where) {" << endl;
    bout << "\t" << "if( la.d_type == tt";
    if( d_pseudoKeywords )
        bout << " || la.d_code == tt";
    bout << ") { next(); return true; }" << endl;
    bout << "\t" << "else { errors << Error(QString(\"'%1' expected in %2\")"
            ".arg(tokenTypeString(tt)).arg(where),"
            "la.d_lineNr, la.d_colNr, la.d_sourcePath); return false; }" << endl;
    bout << "}" << endl << endl;

    bout << "static inline void dummy() {}" << endl << endl;

    if( d_genSynTree )
    {
        bout << "\t" << "void Parser::addTerminal(SynTree* st) {" << endl;

        if( !suppress.isEmpty() )
        {
            bout << "\t\t" << "if( ";
            for( int i = 0; i < suppress.size(); i++ )
                bout << ( i == 0 ? "" : "&& " ) << "cur.d_type != " << "Tok_"
                    << GenUtils::symToString(suppress[i].toStr()) << " ";
            bout << "){" << endl << "\t";
        }
        bout << "\t\t" << "SynTree* tmp = new SynTree( cur ); st->d_children.append(tmp);" << endl;
        if( !suppress.isEmpty() )
            bout << "\t\t}" << endl;
        bout << "\t}" << endl;
    }


    for( int i = 0; i < syn->getOrderedDefs().size(); i++ )
    {
        const Ast::Definition* d = syn->getOrderedDefs()[i];

        if( d->d_tok.d_op == EbnfToken::Skip || ( i != 0 && d->d_usedBy.isEmpty() ) )
            continue;
        if( d->d_node == 0 ) // || d->d_tok.d_op == EbnfToken::Transparent )
            continue;

        bout << "void Parser::" << d->d_tok.d_val.toStr() << (d_genSynTree ?"(SynTree* st) {":"() {") << endl;
        if( d_genSynTree && d->d_tok.d_op != EbnfToken::Transparent )
        {
            bout << "\t" << "{ SynTree* tmp = new SynTree(SynTree::R_" << d->d_tok.d_val.toStr() << ", la); ";
            bout << "st->d_children.append(tmp); st = tmp; }" << endl;
        }
        writeNode( bout, d->d_node, 0 );
        bout << "}" << endl << endl;
    }


    return true;
}

static inline QByteArray ws(int level)
{
    return QByteArray(level+1,'\t');
}

bool CppGen::writeVisitor(const QString& path, EbnfSyntax* syn, FirstFollowSet* tbl)
{
    if( syn == 0 || syn->getOrderedDefs().isEmpty() )
        return false;

    Q_ASSERT( syn != 0 );
    tbl->setSyntax(syn);

    const QByteArray nameSpace = syn->getPragmaFirst("%namespace").toBa();

    d_tbl = tbl;
    d_syn = syn;

    QFile body( path );
    body.open( QIODevice::WriteOnly );
    QTextStream bout(&body);
    bout.setCodec("utf-8");

    bout << "// This file was automatically generated by EbnfStudio; any modifications will be overwritten!" << endl;
    bout << "#include \"" << nameSpace << "SynTree.h\"" << endl;
    if( !nameSpace.isEmpty() )
        bout << "using namespace " << nameSpace << ";" << endl;
    bout << endl;

    bout << "class Visitor {" << endl;
    bout << "public:" << endl << endl;

    bout << "\t" << "static inline void dummy() {}" << endl << endl;

    for( int i = 0; i < syn->getOrderedDefs().size(); i++ )
    {
        const Ast::Definition* d = syn->getOrderedDefs()[i];

        if( d->d_tok.d_op == EbnfToken::Skip || ( i != 0 && d->d_usedBy.isEmpty() ) )
            continue;
        if( d->d_node == 0 || d->d_tok.d_op == EbnfToken::Transparent )
            continue;

        bout << ws(0) << "void " << d->d_tok.d_val.toStr() << "(SynTree* st) {" << endl;
        bout << ws(1) << "Q_ASSERT(st && st->d_tok.d_type == SynTree::R_" << d->d_tok.d_val.toStr() << ");" << endl;
        bout << ws(1) << "for(int i = 0; i < st->d_children.size(); i++ ) {" << endl;
        bout << ws(2) << "SynTree* sub = st->d_children[i];" << endl;
        bout << ws(2) << "switch(sub->d_tok.d_type) {" << endl;
        QSet<EbnfToken::Sym> unique;
        writeNode2( bout, d->d_node, unique );
        bout << ws(2) << "}" << endl;
        bout << ws(1) << "}" << endl;
        bout << ws(0) << "}" << endl << endl;
    }

    bout << "};" << endl;

    return true;
}

static inline bool containsNoPseudoKeyword( const Ast::NodeSet& ns )
{
    foreach( const Ast::Node* n, ns)
    {
        if( n->d_literal && GenUtils::looksLikeKeyword(n->d_tok.d_val.toStr()) )
            return false;
    }
    return true;
}

void CppGen::writeCond( QTextStream& out, bool loop, const QList<const Ast::Node*>& firsts )
{
    out << (loop ? "while" : "if") << "( ";
    for( int i = 0; i < firsts.size(); i++ )
    {
        if( i != 0 )
            out << " || ";
        const Ast::Node* n = firsts[i];
        switch( n->d_type )
        {
        case Ast::Node::Terminal:
            if( d_pseudoKeywords && n->d_literal && GenUtils::looksLikeKeyword(n->d_tok.d_val.toStr()) )
                out << "la.d_code == Tok_" << GenUtils::symToString( n->d_tok.d_val.toStr() );
            else
                out << "la.d_type == Tok_" << GenUtils::symToString( n->d_tok.d_val.toStr() );
            break;
        case Ast::Node::Nonterminal:
            if( n->d_def == 0 || n->d_def->d_node == 0 )
                // this looks like a nt but is actually a terminal,
                // e.g. a token like ident, unsigned_real, decimal_int, etc.
                out << "la.d_type == Tok_" << GenUtils::symToString( n->d_tok.d_val.toStr() );
            else
            {
                out << "FIRST_" << GenUtils::symToString( n->d_tok.d_val.toStr() ) << "(la.d_type)";
                if( d_pseudoKeywords && !containsNoPseudoKeyword(d_tbl->getFirstNodeSet(n)) )
                    out << " || FIRST_" << GenUtils::symToString( n->d_tok.d_val.toStr() ) << "(la.d_code)";
                    // NOTE about adding "&& la.d_code == 0":
                    // with this a simple_statement like "inc(result);" doesn't work
                    // without this "public" in class_type is interpreted as field_definition
                    // so we leave it out and add an \LA to avoid eating pseudo keywords as idents where necessary
            }
            break;
        case Ast::Node::Predicate:
            handlePredicate(out, n);
            break;
        default:
            break;
        }
    }
    out << " ) {" << endl;
}

void CppGen::writeNode(QTextStream& out, Ast::Node* node, int level)
{
    if( node == 0 )
        return;

    if( node->d_tok.d_op == EbnfToken::Skip )
        return;
    if( node->d_def && node->d_def->d_tok.d_op == EbnfToken::Skip )
        return;

#if 0
    if( !node->d_tok.d_val.isEmpty() )
        qDebug() << "writeNode" << node->d_tok.d_val.toBa() << level;
    else
        qDebug() << "writeNode <" << Ast::Node::s_typeName[node->d_type] << ">";
#endif
    switch( node->d_quant )
    {
    case Ast::Node::One:
        break;
    case Ast::Node::ZeroOrOne:
        out << ws(level);
        writeCond(out, false, findFirstsOf(node));
        level++;
        break;
    case Ast::Node::ZeroOrMore:
        out << ws(level);
        writeCond(out, true, findFirstsOf(node));
        level++;
        break;
    }

    switch( node->d_type )
    {
    case Ast::Node::Terminal:
        out << ws(level) << ( d_genSynTree ? "if( ": "" )
            << "expect(Tok_" << GenUtils::symToString( node->d_tok.d_val.toStr() )
            << ", " << ( node->d_literal && GenUtils::looksLikeKeyword(node->d_tok.d_val.toStr()) ? "true" : "false" )
            << ", \"" << node->d_owner->d_tok.d_val.toBa() << "\")"
            << ( d_genSynTree ? " ) addTerminal(st)":"" )
            << ";" << endl;
        break;
    case Ast::Node::Nonterminal:
        if( node->d_def == 0 || node->d_def->d_node == 0 )
            // this looks like a nt but is actually a terminal,
            // e.g. a token like ident, unsigned_real, decimal_int, etc.
            out << ws(level) << ( d_genSynTree ? "if( ": "" )
                << "expect(Tok_" << GenUtils::symToString( node->d_tok.d_val.toStr() )
                << ", false, \"" << node->d_owner->d_tok.d_val.toBa() << "\")"
                << ( d_genSynTree ? " ) addTerminal(st)":"" )
                << ";" << endl;
        else
            out << ws(level) << GenUtils::symToString(node->d_tok.d_val.toStr())
                << (d_genSynTree?"(st);":"();") << endl;
        break;
    case Ast::Node::Alternative:
        for( int i = 0; i < node->d_subs.size(); i++ )
        {
            if( i != 0 )
                out << ws(level) << "} else ";
            else
                out << ws(level);
            writeCond(out, false, findFirstsOf(node->d_subs[i], true));
            writeNode( out, node->d_subs[i], level+1 );
        }
        out << ws(level) << "} else" << endl;
        out << ws(level+1) << "invalid(\"" << node->d_owner->d_tok.d_val.toBa() << "\");" << endl;
        break;
    case Ast::Node::Sequence:
        for( int i = 0; i < node->d_subs.size(); i++ )
            writeNode( out, node->d_subs[i], level );
        break;
    case Ast::Node::Predicate:
        // qWarning() << "Coco::writeNode: Ast::Node::Predicate";
        break;
    }

    switch( node->d_quant )
    {
    case Ast::Node::One:
        break;
    case Ast::Node::ZeroOrMore:
    case Ast::Node::ZeroOrOne:
        out << ws(level-1) << "}" << endl;
        break;
    }
}

void CppGen::writeNode2(QTextStream& out, Ast::Node* node, QSet<EbnfToken::Sym>& unique)
{
    if( node == 0 )
        return;

    if( node->d_tok.d_op == EbnfToken::Skip )
        return;
    if( node->d_def && node->d_def->d_tok.d_op == EbnfToken::Skip )
        return;

    const int level = 2;
    switch( node->d_type )
    {
    case Ast::Node::Terminal:
        if( unique.contains(node->d_tok.d_val) )
            return;
        unique.insert(node->d_tok.d_val);
        out << ws(level) << "case Tok_" << GenUtils::symToString( node->d_tok.d_val.toStr() ) << ":" << endl;
        out << ws(level+1) << "break;" << endl;
        break;
    case Ast::Node::Nonterminal:
        if( node->d_def == 0 || node->d_def->d_node == 0 )
        {
            if( unique.contains(node->d_tok.d_val) )
                return;
            unique.insert(node->d_tok.d_val);
            out << ws(level) << "case Tok_" << GenUtils::symToString( node->d_tok.d_val.toStr() ) << ":" << endl;
            out << ws(level+1) << "break;" << endl;
        }else
        {
            if( node->d_def->d_tok.d_op == EbnfToken::Transparent )
            {
                writeNode2( out, node->d_def->d_node, unique );
                //for( int i = 0; i < node->d_def->d_node->d_subs.size(); i++ )
                //    writeNode2( out, node->d_def->d_node->d_subs[i], unique );
            }else
            {
                if( unique.contains(node->d_tok.d_val) )
                    return;
                unique.insert(node->d_tok.d_val);
                out << ws(level) << "case SynTree::R_" << node->d_tok.d_val.toStr() << ":" << endl;
                out << ws(level+1) << node->d_tok.d_val.toStr() << "(sub);" << endl;
                out << ws(level+1) << "break;" << endl;
            }
        }
        break;
    case Ast::Node::Alternative:
    case Ast::Node::Sequence:
        for( int i = 0; i < node->d_subs.size(); i++ )
            writeNode2( out, node->d_subs[i], unique );
        break;
    case Ast::Node::Predicate:
        // qWarning() << "Coco::writeNode: Ast::Node::Predicate";
        break;
    }
}

static void renderLaSub( QTextStream& out, const LaParser::Ast* ast, EbnfSyntax* syn, int la, bool pseudoKeywords )
{
    switch( ast->d_type )
    {
    case LaParser::Ast::Ident:
        out << "peek(" << la << ").d_type == " << "Tok_" << GenUtils::symToString(ast->d_val) << " ";
        break;
    case LaParser::Ast::Literal:
        if( pseudoKeywords && GenUtils::looksLikeKeyword(ast->d_val) )
            out << "peek(" << la << ").d_code == " << "Tok_" << GenUtils::symToString(ast->d_val) << " ";
        else
            out << "peek(" << la << ").d_type == " << "Tok_" << GenUtils::symToString(ast->d_val) << " ";
        break;
    case LaParser::Ast::Not:
        out << "!( ";
        renderLaSub(out,ast->d_subs.first().data(),syn,la, pseudoKeywords);
        out << ") ";
        break;
    case LaParser::Ast::Or:
        if( ast->d_subs.size() > 1 )
            out << "( ";
        for( int i = 0; i < ast->d_subs.size(); i++ )
        {
             if( i != 0 )
                 out << "|| ";
             renderLaSub(out,ast->d_subs[i].data(),syn, la, pseudoKeywords);
        }
        if( ast->d_subs.size() > 1 )
            out << ") ";
        break;
    case LaParser::Ast::And:
        for( int i = 0; i < ast->d_subs.size(); i++ )
        {
             if( i != 0 )
                 out << "&& ";
             renderLaSub(out,ast->d_subs[i].data(),syn,la, pseudoKeywords);
        }
        break;
    default:
        Q_ASSERT( false );
        break;
    }
}

static void renderLaExpr( QTextStream& out, const LaParser::Ast* ast, EbnfSyntax* syn, bool pseudoKeywords )
{
    switch( ast->d_type )
    {
    case LaParser::Ast::La:
        renderLaSub( out,ast->d_subs.first().data(),syn,ast->d_val.toInt(), pseudoKeywords );
        break;
    case LaParser::Ast::Or:
        if( ast->d_subs.size() > 1 )
            out << "( ";
        for( int i = 0; i < ast->d_subs.size(); i++ )
        {
             if( i != 0 )
                 out << "|| ";
             renderLaExpr(out,ast->d_subs[i].data(),syn, pseudoKeywords);
        }
        if( ast->d_subs.size() > 1 )
            out << ") ";
        break;
    case LaParser::Ast::And:
        for( int i = 0; i < ast->d_subs.size(); i++ )
        {
             if( i != 0 )
                 out << "&& ";
             renderLaExpr(out,ast->d_subs[i].data(),syn, pseudoKeywords);
        }
        break;
    default:
        Q_ASSERT( false );
        break;
    }
}

void CppGen::handlePredicate(QTextStream& out, const Ast::Node* pred)
{
    const QByteArray la = pred->getLa();
    if( !la.isEmpty() )
    {
        LaParser p;
        if( !p.parse(la) )
            return; // error was already reported

        out << "( ";
        renderLaExpr( out, p.getLaExpr().constData(), d_syn, d_pseudoKeywords );
        out << ") ";

        return;
    }
    int ll = pred->getLlk();
    if( ll > 0 )
    {
        EbnfAnalyzer::LlkNodes llkNodes;
        EbnfAnalyzer::calcLlkFirstSet( ll, llkNodes,pred->d_parent, d_tbl );
        if( llkNodes.isEmpty() )
            return;
        out << "( ";
        for( int i = 0; i < llkNodes.size(); i++ )
        {
            if( i != 0 )
                out << "&& ";
            if( llkNodes[i].size() > 1 )
                out << "( ";
            QMap<QString,const Ast::Node*> names;
            Ast::NodeRefSet::const_iterator j;
            for( j = llkNodes[i].begin(); j != llkNodes[i].end(); ++j )
                names.insert("Tok_" + GenUtils::symToString( (*j).d_node->d_tok.d_val.toStr() ), (*j).d_node );
            if( names.isEmpty() )
                out << "false ";
            else
            {
                QMap<QString,const Ast::Node*>::const_iterator j;
                for( j = names.begin(); j != names.end(); ++j )
                {
                    if( j != names.begin() )
                        out << "|| ";
                    if( d_pseudoKeywords && j.value()->d_literal && GenUtils::looksLikeKeyword(j.value()->d_tok.d_val.toStr()) )
                        out << "peek(" << i+1 << ").d_code == " << j.key() << " ";
                    else
                        out << "peek(" << i+1 << ").d_type == " << j.key() << " ";
                }
            }
            if( llkNodes[i].size() > 1 )
                out << ") ";
        }
        out << ") ";
        return;
    }
#if 0
    ll = pred->getLl();
    if( ll > 0 )
    {
        // TODO: this is unfinished work
        Ast::NodeTree nt;
        EbnfAnalyzer::calcLlkFirstSet(ll, &nt, pred->d_parent, d_tbl );
    }
#endif
    else
        qWarning() << "CppGen unknown predicate" << pred->d_tok.d_val.toStr();
}

QList<const Ast::Node*> CppGen::findFirstsOf(Ast::Node* node, bool checkFollowSet) const
{
    QList<const Ast::Node*> res;
    // TODO why not just d_tbl->getFirstNodeSet(node).toList() ?
    if( node->d_type == Ast::Node::Terminal || node->d_type == Ast::Node::Nonterminal )
    {
        res.append(node);
    }else
    {
        Q_ASSERT( node->d_type == Ast::Node::Alternative || node->d_type == Ast::Node::Sequence );
        for( int i = 0; i < node->d_subs.size(); i++ )
        {
            Ast::Node* sub = node->d_subs[i];

            if( sub->d_tok.d_op == EbnfToken::Skip )
                continue;
            if( sub->d_def && sub->d_def->d_tok.d_op == EbnfToken::Skip )
                continue;

            switch( sub->d_type )
            {
            case Ast::Node::Predicate:
                Q_ASSERT( node->d_type == Ast::Node::Sequence && res.isEmpty() );
                res.append(sub);
                return res;
            case Ast::Node::Terminal:
            case Ast::Node::Nonterminal:
                res.append(sub);
                break;
            case Ast::Node::Alternative:
            case Ast::Node::Sequence:
                res += findFirstsOf(sub);
                break;
            }

            if( node->d_type == Ast::Node::Sequence && !sub->isNullable() )
                break; // stop after the first non-optional
        }
    }
    if( checkFollowSet && node->isNullable() )
    {
        // if an option in an alternative is nullable then the the stuff behind the alternative must
        // be visible otherwise no option of the alternative might fit.
        res += d_tbl->getFollowNodeSet(node).toList();
    }
    return res;
}