#include "builtin.hpp"
#include "array.hpp"
#include "itertools.hpp"
#include "math.hpp"
#include "sys.hpp"
#include "heapq.hpp"
#include "plcfrs.hpp"

/**
A natural language parser for PLCFRS (probabilistic linear context-free
rewriting systems). PLCFRS is an extension of context-free grammar which
rewrites tuples of strings instead of strings; this allows it to produce
parse trees with discontinuous constituents.

Copyright 2011 Andreas van Cranenburgh <andreas@unstable.nl>
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

namespace __plcfrs__ {

str *const_0, *const_1, *const_10, *const_11, *const_12, *const_13, *const_14, *const_15, *const_16, *const_17, *const_18, *const_19, *const_2, *const_20, *const_21, *const_22, *const_23, *const_24, *const_25, *const_26, *const_27, *const_28, *const_29, *const_3, *const_30, *const_31, *const_32, *const_33, *const_34, *const_35, *const_36, *const_37, *const_38, *const_39, *const_4, *const_40, *const_41, *const_42, *const_43, *const_44, *const_45, *const_46, *const_47, *const_48, *const_49, *const_5, *const_50, *const_51, *const_52, *const_53, *const_54, *const_55, *const_56, *const_57, *const_58, *const_59, *const_6, *const_60, *const_61, *const_62, *const_63, *const_64, *const_65, *const_66, *const_67, *const_68, *const_69, *const_7, *const_70, *const_71, *const_8, *const_9;

using __math__::exp;
using __math__::log;
using __array__::array;
using __heapq__::heappush;
using __heapq__::heappop;

list<str *> *argv;
str *__name__;
__ss_int INVALID;
file *__ss_stderr;


static inline list<dict<ChartItem *, Edge *> *> *list_comp_0(dict<str *, __ss_int> *toid);
class list_comp_1 : public __iter<tuple2<__ss_int, ChartItem *> *> {
public:
    __iter<ChartItem *> *__75;
    dict<ChartItem *, list<Edge *> *>::for_in_loop __77;
    __ss_int __76;
    ChartItem *a;
    dict<ChartItem *, list<Edge *> *> *__74;

    dict<ChartItem *, list<Edge *> *> *chart;
    int __last_yield;

    list_comp_1(dict<ChartItem *, list<Edge *> *> *chart);
    tuple2<__ss_int, ChartItem *> * __get_next();
};

static inline list<list<str *> *> *list_comp_2(str *rulefile);
static inline list<list<str *> *> *list_comp_3(str *lexiconfile);
class list_comp_4 : public __iter<tuple2<__ss_int, __ss_int> *> {
public:
    list<str *> *__101;
    list<str *>::for_in_loop __104;
    __iter<str *> *__102;
    str *__106, *b;
    __ss_int __103;
    void *__105;

    list<str *> *a;
    int __last_yield;

    list_comp_4(list<str *> *a);
    tuple2<__ss_int, __ss_int> * __get_next();
};

static inline list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *list_comp_5(list<list<str *> *> *srules);
static inline list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *> *list_comp_6(list<list<str *> *> *slexicon);
class list_comp_7 : public __iter<str *> {
public:
    tuple2<str *, str *>::for_in_loop __120;
    list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *>::for_in_loop __116;
    __iter<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *__114;
    tuple2<str *, str *> *__117, *rule;
    double weight;
    str *nt;
    tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *__111;
    __iter<str *> *__118;
    list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *__113;
    tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *__112;
    __ss_int __115, __119;
    tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *yf;

    list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *grammar;
    int __last_yield;

    list_comp_7(list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *grammar);
    str * __get_next();
};

class list_comp_8 : public __iter<tuple2<str *, __ss_int> *> {
public:
    list<tuple2<__ss_int, str *> *> *__122;
    tuple2<__ss_int, str *> *__121;
    str *lhs;
    __ss_int __124, n;
    list<tuple2<__ss_int, str *> *>::for_in_loop __125;
    __iter<tuple2<__ss_int, str *> *> *__123;

    list<tuple2<__ss_int, str *> *> *nonterminals;
    int __last_yield;

    list_comp_8(list<tuple2<__ss_int, str *> *> *nonterminals);
    tuple2<str *, __ss_int> * __get_next();
};

class list_comp_9 : public __iter<tuple2<__ss_int, str *> *> {
public:
    list<tuple2<__ss_int, str *> *> *__127;
    tuple2<__ss_int, str *> *__126;
    str *lhs;
    __ss_int __129, n;
    list<tuple2<__ss_int, str *> *>::for_in_loop __130;
    __iter<tuple2<__ss_int, str *> *> *__128;

    list<tuple2<__ss_int, str *> *> *nonterminals;
    int __last_yield;

    list_comp_9(list<tuple2<__ss_int, str *> *> *nonterminals);
    tuple2<__ss_int, str *> * __get_next();
};

static inline list<list<Rule *> *> *list_comp_10(list<tuple2<__ss_int, str *> *> *nonterminals);
static inline list<list<Rule *> *> *list_comp_11(list<tuple2<__ss_int, str *> *> *nonterminals);
static inline list<list<Rule *> *> *list_comp_12(list<tuple2<__ss_int, str *> *> *nonterminals);
static inline list<list<Rule *> *> *list_comp_13(list<tuple2<__ss_int, str *> *> *nonterminals);
class list_comp_14 : public __iter<__ss_bool> {
public:
    tuple2<__ss_int, __ss_int> *a;
    tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *__162;
    __iter<tuple2<__ss_int, __ss_int> *> *__163;
    __ss_int __164;
    tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *>::for_in_loop __165;

    __ss_int vecsize;
    tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *yf;
    int __last_yield;

    list_comp_14(__ss_int vecsize, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *yf);
    __ss_bool __get_next();
};

class list_comp_15 : public __iter<__ss_int> {
public:
    tuple2<__ss_int, __ss_int> *__170, *__174;
    __iter<tuple2<__ss_int, __ss_int> *> *__171, *__172;
    __ss_int __173, b, n;
    __iter<tuple2<__ss_int, __ss_int> *>::for_in_loop __175;

    tuple2<__ss_int, __ss_int> *a;
    int __last_yield;

    list_comp_15(tuple2<__ss_int, __ss_int> *a);
    __ss_int __get_next();
};

static inline list<__ss_int> *list_comp_16(tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *yf);
class list_comp_17 : public __iter<__ss_int> {
public:
    __ss_int __184, __185, m;

    __ss_int a;
    __ss_int n;
    int __last_yield;

    list_comp_17(__ss_int a, __ss_int n);
    __ss_int __get_next();
};

class list_comp_18 : public __iter<tuple2<__ss_int, __ss_int> *> {
public:
    tuple2<__ss_int, __ss_int> *__176;
    __array__::array<__ss_int> *__180, *__181;
    list<tuple2<__ss_int, __ss_int> *>::for_in_loop __183;
    list<tuple2<__ss_int, __ss_int> *> *__177;
    __iter<tuple2<__ss_int, __ss_int> *> *__178;
    __ss_int __179, __182, a, n;

    __array__::array<__ss_int> *lengths;
    __array__::array<__ss_int> *args;
    int __last_yield;

    list_comp_18(__array__::array<__ss_int> *lengths, __array__::array<__ss_int> *args);
    tuple2<__ss_int, __ss_int> * __get_next();
};

static inline list<list<str *> *> *list_comp_19(str *sent);
static inline list<list<list<str *> *> *> *list_comp_20(list<str *> *lines);
static inline list<str *> *list_comp_21(list<list<str *> *> *wordstags);
static inline list<str *> *list_comp_22(list<list<str *> *> *wordstags);
static inline __ss_int __lambda2__(tuple2<__ss_int, __ss_int> *a);
static inline __ss_int __lambda0__(list<Edge *> *a);
static inline __ss_int __lambda1__(str *a);

static inline list<dict<ChartItem *, Edge *> *> *list_comp_0(dict<str *, __ss_int> *toid) {
    dict<str *, __ss_int> *__3;
    __iter<str *> *__4;
    __ss_int __5;
    dict<str *, __ss_int>::for_in_loop __6;
    str *_;

    list<dict<ChartItem *, Edge *> *> *__ss_result = new list<dict<ChartItem *, Edge *> *>();

    __ss_result->resize(len(toid));
    FOR_IN(_,toid,3,5,6)
        __ss_result->units[__5] = (new dict<ChartItem *, Edge *>());
    END_FOR

    return __ss_result;
}

list_comp_1::list_comp_1(dict<ChartItem *, list<Edge *> *> *chart) {
    this->chart = chart;
    __last_yield = -1;
}

tuple2<__ss_int, ChartItem *> * list_comp_1::__get_next() {
    if(!__last_yield) goto __after_yield_0;
    __last_yield = 0;

    FOR_IN(a,chart,74,76,77)
        __result = (new tuple2<__ss_int, ChartItem *>(2,bitcount(a->vec),a));
        return __result;
        __after_yield_0:;
    END_FOR

    __stop_iteration = true;
}

static inline list<list<str *> *> *list_comp_2(str *rulefile) {
    file *__89;
    __iter<str *> *__90;
    __ss_int __91;
    str *line;
    file::for_in_loop __92;

    list<list<str *> *> *__ss_result = new list<list<str *> *>();

    __89 = open(rulefile);
    FOR_IN(line,__89,89,91,92)
        __ss_result->append((line->__slice__(2LL, 0LL, (len(line)-1LL), 0LL))->split(const_0));
    END_FOR

    return __ss_result;
}

static inline list<list<str *> *> *list_comp_3(str *lexiconfile) {
    __iter<str *> *__94;
    str *line;
    __ss_int __95;
    file *__93;
    file::for_in_loop __96;

    list<list<str *> *> *__ss_result = new list<list<str *> *>();

    __93 = open(lexiconfile);
    FOR_IN(line,__93,93,95,96)
        __ss_result->append((line->__slice__(2LL, 0LL, (len(line)-1LL), 0LL))->split(const_0));
    END_FOR

    return __ss_result;
}

list_comp_4::list_comp_4(list<str *> *a) {
    this->a = a;
    __last_yield = -1;
}

tuple2<__ss_int, __ss_int> * list_comp_4::__get_next() {
    if(!__last_yield) goto __after_yield_0;
    __last_yield = 0;

    __101 = (a->__getfast__((len(a)-2LL)))->split(const_1);
    FOR_IN(b,__101,101,103,104)
        __result = (new tuple2<__ss_int, __ss_int>(map(1, __lambda1__, b)));
        return __result;
        __after_yield_0:;
    END_FOR

    __stop_iteration = true;
}

static inline list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *list_comp_5(list<list<str *> *> *srules) {
    list<str *> *a;
    __iter<list<str *> *> *__98;
    list<list<str *> *> *__97;
    __ss_int __99;
    list<list<str *> *>::for_in_loop __100;

    list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *__ss_result = new list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *>();

    __ss_result->resize(len(srules));
    FOR_IN(a,srules,97,99,100)
        __ss_result->units[__99] = (new tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double>(2,(new tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *>(2,(new tuple2<str *, str *>(a->__slice__(2LL, 0LL, (len(a)-2LL), 0LL))),(new tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *>(new list_comp_4(a))))),__float(a->__getfast__((len(a)-1LL)))));
    END_FOR

    return __ss_result;
}

static inline list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *> *list_comp_6(list<list<str *> *> *slexicon) {
    list<str *> *a;
    __iter<list<str *> *> *__108;
    list<list<str *> *> *__107;
    __ss_int __109;
    list<list<str *> *>::for_in_loop __110;

    list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *> *__ss_result = new list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *>();

    __ss_result->resize(len(slexicon));
    FOR_IN(a,slexicon,107,109,110)
        __ss_result->units[__109] = (new tuple2<tuple2<tuple2<str *, str *> *, str *> *, double>(2,(new tuple2<tuple2<str *, str *> *, str *>(2,(new tuple2<str *, str *>(a->__slice__(2LL, 0LL, (len(a)-2LL), 0LL))),a->__getfast__((len(a)-2LL)))),__float(a->__getfast__((len(a)-1LL)))));
    END_FOR

    return __ss_result;
}

list_comp_7::list_comp_7(list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *grammar) {
    this->grammar = grammar;
    __last_yield = -1;
}

str * list_comp_7::__get_next() {
    if(!__last_yield) goto __after_yield_0;
    __last_yield = 0;

    FOR_IN(__111,grammar,113,115,116)
        __111 = __111;
        __112 = __111->__getfirst__();
        rule = __112->__getfirst__();
        yf = __112->__getsecond__();
        weight = __111->__getsecond__();
        FOR_IN(nt,rule,117,119,120)
            __result = nt;
            return __result;
            __after_yield_0:;
        END_FOR

    END_FOR

    __stop_iteration = true;
}

list_comp_8::list_comp_8(list<tuple2<__ss_int, str *> *> *nonterminals) {
    this->nonterminals = nonterminals;
    __last_yield = -1;
}

tuple2<str *, __ss_int> * list_comp_8::__get_next() {
    if(!__last_yield) goto __after_yield_0;
    __last_yield = 0;

    FOR_IN(__121,nonterminals,122,124,125)
        __121 = __121;
        n = __121->__getfirst__();
        lhs = __121->__getsecond__();
        __result = (new tuple2<str *, __ss_int>(2,lhs,n));
        return __result;
        __after_yield_0:;
    END_FOR

    __stop_iteration = true;
}

list_comp_9::list_comp_9(list<tuple2<__ss_int, str *> *> *nonterminals) {
    this->nonterminals = nonterminals;
    __last_yield = -1;
}

tuple2<__ss_int, str *> * list_comp_9::__get_next() {
    if(!__last_yield) goto __after_yield_0;
    __last_yield = 0;

    FOR_IN(__126,nonterminals,127,129,130)
        __126 = __126;
        n = __126->__getfirst__();
        lhs = __126->__getsecond__();
        __result = (new tuple2<__ss_int, str *>(2,n,lhs));
        return __result;
        __after_yield_0:;
    END_FOR

    __stop_iteration = true;
}

static inline list<list<Rule *> *> *list_comp_10(list<tuple2<__ss_int, str *> *> *nonterminals) {
    list<tuple2<__ss_int, str *> *> *__131;
    __ss_int __133;
    list<tuple2<__ss_int, str *> *>::for_in_loop __134;
    __iter<tuple2<__ss_int, str *> *> *__132;
    tuple2<__ss_int, str *> *_;

    list<list<Rule *> *> *__ss_result = new list<list<Rule *> *>();

    __ss_result->resize(len(nonterminals));
    FOR_IN(_,nonterminals,131,133,134)
        __ss_result->units[__133] = (new list<Rule *>());
    END_FOR

    return __ss_result;
}

static inline list<list<Rule *> *> *list_comp_11(list<tuple2<__ss_int, str *> *> *nonterminals) {
    list<tuple2<__ss_int, str *> *>::for_in_loop __138;
    __ss_int __137;
    list<tuple2<__ss_int, str *> *> *__135;
    tuple2<__ss_int, str *> *_;
    __iter<tuple2<__ss_int, str *> *> *__136;

    list<list<Rule *> *> *__ss_result = new list<list<Rule *> *>();

    __ss_result->resize(len(nonterminals));
    FOR_IN(_,nonterminals,135,137,138)
        __ss_result->units[__137] = (new list<Rule *>());
    END_FOR

    return __ss_result;
}

static inline list<list<Rule *> *> *list_comp_12(list<tuple2<__ss_int, str *> *> *nonterminals) {
    list<tuple2<__ss_int, str *> *> *__139;
    __ss_int __141;
    list<tuple2<__ss_int, str *> *>::for_in_loop __142;
    tuple2<__ss_int, str *> *_;
    __iter<tuple2<__ss_int, str *> *> *__140;

    list<list<Rule *> *> *__ss_result = new list<list<Rule *> *>();

    __ss_result->resize(len(nonterminals));
    FOR_IN(_,nonterminals,139,141,142)
        __ss_result->units[__141] = (new list<Rule *>());
    END_FOR

    return __ss_result;
}

static inline list<list<Rule *> *> *list_comp_13(list<tuple2<__ss_int, str *> *> *nonterminals) {
    list<tuple2<__ss_int, str *> *> *__143;
    __ss_int __145;
    list<tuple2<__ss_int, str *> *>::for_in_loop __146;
    tuple2<__ss_int, str *> *_;
    __iter<tuple2<__ss_int, str *> *> *__144;

    list<list<Rule *> *> *__ss_result = new list<list<Rule *> *>();

    __ss_result->resize(len(nonterminals));
    FOR_IN(_,nonterminals,143,145,146)
        __ss_result->units[__145] = (new list<Rule *>());
    END_FOR

    return __ss_result;
}

list_comp_14::list_comp_14(__ss_int vecsize, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *yf) {
    this->vecsize = vecsize;
    this->yf = yf;
    __last_yield = -1;
}

__ss_bool list_comp_14::__get_next() {
    if(!__last_yield) goto __after_yield_0;
    __last_yield = 0;

    FOR_IN(a,yf,162,164,165)
        __result = ___bool((len(a)<=vecsize));
        return __result;
        __after_yield_0:;
    END_FOR

    __stop_iteration = true;
}

list_comp_15::list_comp_15(tuple2<__ss_int, __ss_int> *a) {
    this->a = a;
    __last_yield = -1;
}

__ss_int list_comp_15::__get_next() {
    if(!__last_yield) goto __after_yield_0;
    __last_yield = 0;

    FOR_IN_ENUM(b,a,174,173)
        n = __173;
        if (b) {
            __result = (1LL<<n);
            return __result;
            __after_yield_0:;
        }
    END_FOR

    __stop_iteration = true;
}

static inline list<__ss_int> *list_comp_16(tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *yf) {
    tuple2<__ss_int, __ss_int> *a;
    tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *>::for_in_loop __169;
    __iter<tuple2<__ss_int, __ss_int> *> *__167;
    __ss_int __168;
    tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *__166;

    list<__ss_int> *__ss_result = new list<__ss_int>();

    __ss_result->resize(len(yf));
    FOR_IN(a,yf,166,168,169)
        __ss_result->units[__168] = __sum(new list_comp_15(a));
    END_FOR

    return __ss_result;
}

list_comp_17::list_comp_17(__ss_int a, __ss_int n) {
    this->a = a;
    this->n = n;
    __last_yield = -1;
}

__ss_int list_comp_17::__get_next() {
    if(!__last_yield) goto __after_yield_0;
    __last_yield = 0;

    FAST_FOR(m,0,n,1,184,185)
        __result = ((((a)&((1LL<<m))))?(1LL):(0LL));
        return __result;
        __after_yield_0:;
    END_FOR

    __stop_iteration = true;
}

list_comp_18::list_comp_18(__array__::array<__ss_int> *lengths, __array__::array<__ss_int> *args) {
    this->lengths = lengths;
    this->args = args;
    __last_yield = -1;
}

tuple2<__ss_int, __ss_int> * list_comp_18::__get_next() {
    if(!__last_yield) goto __after_yield_0;
    __last_yield = 0;

    __177 = __zip(2, lengths, args);
    FOR_IN(__176,__177,177,179,183)
        __176 = __176;
        n = __176->__getfirst__();
        a = __176->__getsecond__();
        __result = (new tuple2<__ss_int, __ss_int>(new list_comp_17(a, n)));
        return __result;
        __after_yield_0:;
    END_FOR

    __stop_iteration = true;
}

static inline list<list<str *> *> *list_comp_19(str *sent) {
    list<str *> *__203;
    list<str *>::for_in_loop __206;
    __iter<str *> *__204;
    str *__208, *a;
    __ss_int __205;
    void *__207;

    list<list<str *> *> *__ss_result = new list<list<str *> *>();

    __203 = sent->split();
    __ss_result->resize(len(__203));
    FOR_IN(a,__203,203,205,206)
        __ss_result->units[__205] = a->split(const_2);
    END_FOR

    return __ss_result;
}

static inline list<list<list<str *> *> *> *list_comp_20(list<str *> *lines) {
    list<str *> *__199;
    list<str *>::for_in_loop __202;
    __iter<str *> *__200;
    __ss_int __201;
    str *sent;

    list<list<list<str *> *> *> *__ss_result = new list<list<list<str *> *> *>();

    __ss_result->resize(len(lines));
    FOR_IN(sent,lines,199,201,202)
        __ss_result->units[__201] = list_comp_19(sent);
    END_FOR

    return __ss_result;
}

static inline list<str *> *list_comp_21(list<list<str *> *> *wordstags) {
    list<str *> *a;
    __iter<list<str *> *> *__214;
    list<list<str *> *> *__213;
    __ss_int __215;
    list<list<str *> *>::for_in_loop __216;

    list<str *> *__ss_result = new list<str *>();

    __ss_result->resize(len(wordstags));
    FOR_IN(a,wordstags,213,215,216)
        __ss_result->units[__215] = a->__getfast__(0LL);
    END_FOR

    return __ss_result;
}

static inline list<str *> *list_comp_22(list<list<str *> *> *wordstags) {
    list<str *> *a;
    __iter<list<str *> *> *__218;
    list<list<str *> *> *__217;
    __ss_int __219;
    list<list<str *> *>::for_in_loop __220;

    list<str *> *__ss_result = new list<str *>();

    __ss_result->resize(len(wordstags));
    FOR_IN(a,wordstags,217,219,220)
        __ss_result->units[__219] = a->__getfast__(1LL);
    END_FOR

    return __ss_result;
}

static inline __ss_int __lambda2__(tuple2<__ss_int, __ss_int> *a) {
    
    return len(a);
}

static inline __ss_int __lambda0__(list<Edge *> *a) {
    
    return len(a);
}

static inline __ss_int __lambda1__(str *a) {
    
    return __int(a);
}

tuple2<dict<ChartItem *, list<Edge *> *> *, ChartItem *> *parse(list<str *> *sent, Grammar *grammar, list<str *> *tags, __ss_int start, __ss_bool exhaustive) {
    /**
     parse sentence, a list of tokens, optionally with gold tags, and
    produce a chart, either exhaustive or up until the viterbi parse.
    */
    list<str *> *__11, *__23;
    __iter<ChartItem *> *__35, *__45;
    list<Rule *>::for_in_loop __29, __33, __43;
    dict<ChartItem *, list<Edge *> *> *C;
    __iter<Rule *> *__27, *__31, *__41;
    Terminal *terminal;
    __ss_int Epsilon, __10, __15, __28, __32, __36, __42, __46, blocked, i, maxA;
    list<Rule *> *__26, *__30, *__40;
    list<list<Rule *> *> *lbinary, *rbinary, *unary;
    double z;
    list<Terminal *> *__13;
    agenda *A;
    dict<str *, __ss_int> *toid;
    dict<ChartItem *, Edge *>::for_in_loop __37, __47;
    __iter<Terminal *> *__14;
    Edge *e, *edge;
    ChartItem *I, *goal, *item, *sibling;
    list<dict<ChartItem *, Edge *> *> *Cx;
    __ss_bool __19, __20, __38, __39, __48, __49, recognized;
    str *w;
    tuple2<__ss_int, str *> *__7;
    Rule *rule;
    dictentry<str *, list<Terminal *> *> *__17;
    list<Terminal *>::for_in_loop __16;
    dict<ChartItem *, Edge *> *__25, *__34, *__44;
    tuple2<ChartItem *, Edge *> *__24;
    dict<str *, list<Terminal *> *> *__18, *lexical;
    __iter<tuple2<__ss_int, str *> *>::for_in_loop __12;
    void *__21, *__22;
    dict<__ss_int, str *> *tolabel;
    __iter<tuple2<__ss_int, str *> *> *__8, *__9;

    unary = grammar->unary;
    lbinary = grammar->lbinary;
    rbinary = grammar->rbinary;
    lexical = grammar->lexical;
    toid = grammar->toid;
    tolabel = grammar->tolabel;
    goal = (new ChartItem(start, ((1LL<<len(sent))-1LL)));
    maxA = 0LL;
    blocked = 0LL;
    Cx = list_comp_0(toid);
    C = (new dict<ChartItem *, list<Edge *> *>());
    A = (new agenda(1));
    Epsilon = toid->__getitem__(const_3);

    FOR_IN_ENUM(w,sent,11,10)
        i = __10;
        recognized = False;

        FOR_IN(terminal,lexical->get(w, (new list<Terminal *>())),13,15,16)
            if ((__NOT(___bool(tags)) or __eq(tags->__getfast__(i), ((tolabel->__getitem__(terminal->lhs))->split(const_4))->__getfast__(0LL)))) {
                item = (new ChartItem(terminal->lhs, (1LL<<i)));
                I = (new ChartItem(Epsilon, i));
                z = terminal->prob;
                A->__setitem__(item, (new Edge(z, z, z, I, NULL)));
                C->__setitem__(item, (new list<Edge *>()));
                recognized = True;
            }
        END_FOR

        if ((__NOT(recognized) and ___bool(tags) and (toid)->__contains__(tags->__getfast__(i)))) {
            item = (new ChartItem(toid->__getitem__(tags->__getfast__(i)), (1LL<<i)));
            I = (new ChartItem(Epsilon, i));
            A->__setitem__(item, (new Edge(0.0, 0.0, 0.0, I, NULL)));
            C->__setitem__(item, (new list<Edge *>()));
            recognized = True;
        }
        else if (__NOT(recognized)) {
            print2(NULL,0,2, const_5, ((___bool(tags))?(tags->__getfast__(i)):(w)));
            return (new tuple2<dict<ChartItem *, list<Edge *> *> *, ChartItem *>(2,C,NULL));
        }
    END_FOR


    while (___bool(A)) {
        __24 = A->popitem();
        item = __24->__getfirst__();
        edge = __24->__getsecond__();
        (C->__getitem__(item))->append(edge);
        Cx->__getfast__(item->label)->__setitem__(item, edge);
        if (__eq(item, goal)) {
            if (exhaustive) {
                continue;
            }
            else {
                break;
            }
        }

        FOR_IN(rule,unary->__getfast__(item->label),26,28,29)
            blocked = (blocked+process_edge((new ChartItem(rule->lhs, item->vec)), (new Edge((edge->inside+rule->prob), (edge->inside+rule->prob), rule->prob, item, NULL)), A, C, exhaustive));
        END_FOR


        FOR_IN(rule,lbinary->__getfast__(item->label),30,32,33)

            FOR_IN(sibling,Cx->__getfast__(rule->rhs2),34,36,37)
                e = (Cx->__getfast__(rule->rhs2))->__getitem__(sibling);
                if (((((item->vec)&(sibling->vec))==0LL) and concat(rule, item->vec, sibling->vec))) {
                    blocked = (blocked+process_edge((new ChartItem(rule->lhs, ((item->vec)^(sibling->vec)))), (new Edge(((edge->inside+e->inside)+rule->prob), ((edge->inside+e->inside)+rule->prob), rule->prob, item, sibling)), A, C, exhaustive));
                }
            END_FOR

        END_FOR


        FOR_IN(rule,rbinary->__getfast__(item->label),40,42,43)

            FOR_IN(sibling,Cx->__getfast__(rule->rhs1),44,46,47)
                e = (Cx->__getfast__(rule->rhs1))->__getitem__(sibling);
                if (((((sibling->vec)&(item->vec))==0LL) and concat(rule, sibling->vec, item->vec))) {
                    blocked = (blocked+process_edge((new ChartItem(rule->lhs, ((sibling->vec)^(item->vec)))), (new Edge(((e->inside+edge->inside)+rule->prob), ((e->inside+edge->inside)+rule->prob), rule->prob, sibling, item)), A, C, exhaustive));
                }
            END_FOR

        END_FOR

        if ((len(A)>maxA)) {
            maxA = len(A);
        }
    }
    __ss_stderr->write(__modct(const_6, 4, ___box(maxA), ___box(len(A)), ___box(len(C)), ___box(len(filter(NULL, Cx)))));
    __ss_stderr->write(__modct(const_7, 2, ___box(__sum(map(1, __lambda0__, C->values()))), ___box(blocked)));
    if ((!(C)->__contains__(goal))) {
        goal = NULL;
    }
    return (new tuple2<dict<ChartItem *, list<Edge *> *> *, ChartItem *>(2,C,goal));
}

__ss_int process_edge(ChartItem *newitem, Edge *newedge, agenda *A, dict<ChartItem *, list<Edge *> *> *C, __ss_bool exhaustive) {
    __ss_bool __50, __51, __52, __53;

    if (((!(C)->__contains__(newitem)) and (!(A)->__contains__(newitem)))) {
        if ((newedge->score>300.0)) {
            return 1LL;
        }
        A->__setitem__(newitem, newedge);
        C->__setitem__(newitem, (new list<Edge *>()));
    }
    else if (((A)->__contains__(newitem) and (newedge->inside<(A->__getitem__(newitem))->inside))) {
        (C->__getitem__(newitem))->append(A->__getitem__(newitem));
        A->__setitem__(newitem, newedge);
    }
    else if (exhaustive) {
        (C->__getitem__(newitem))->append(newedge);
    }
    return 0LL;
}

__ss_bool concat(Rule *rule, __ss_int lvec, __ss_int rvec) {
    __ss_bool __58, __59, __60, __61, __62, __63, __64, __65, __66, __67, __68, __69, __70, __71;
    __ss_int __54, __55, __56, __57, lpos, m, n, rpos, x;

    lpos = nextset(lvec, 0LL);
    rpos = nextset(rvec, 0LL);

    FAST_FOR(x,0,len(rule->args),1,54,55)
        m = ((rule->lengths)->__getitem__(x)-1LL);

        FAST_FOR(n,0,(m+1LL),1,56,57)
            if (testbit((rule->args)->__getitem__(x), n)) {
                if (((rpos==(-1LL)) or ((lpos!=(-1LL)) and (lpos<=rpos)))) {
                    return False;
                }
                rpos = nextunset(rvec, rpos);
                if (((lpos!=(-1LL)) and (lpos<rpos))) {
                    return False;
                }
                if ((n==m)) {
                    if (testbit(lvec, rpos)) {
                        return False;
                    }
                }
                else if (__NOT(testbit(lvec, rpos))) {
                    return False;
                }
                rpos = nextset(rvec, rpos);
            }
            else {
                if (((lpos==(-1LL)) or ((rpos!=(-1LL)) and (rpos<=lpos)))) {
                    return False;
                }
                lpos = nextunset(lvec, lpos);
                if (((rpos!=(-1LL)) and (rpos<lpos))) {
                    return False;
                }
                if ((n==m)) {
                    if (testbit(rvec, lpos)) {
                        return False;
                    }
                }
                else if (__NOT(testbit(rvec, lpos))) {
                    return False;
                }
                lpos = nextset(lvec, lpos);
            }
        END_FOR

    END_FOR

    if (((lpos!=(-1LL)) or (rpos!=(-1LL)))) {
        return False;
    }
    return True;
}

tuple2<str *, double> *mostprobablederivation(dict<ChartItem *, list<Edge *> *> *chart, ChartItem *start, dict<__ss_int, str *> *tolabel) {
    /**
     produce a string representation of the viterbi parse in bracket
    notation
    */
    Edge *edge;

    edge = ___min(1, 0LL, chart->__getitem__(start));
    return (new tuple2<str *, double>(2,getmpd(chart, start, tolabel),edge->inside));
}

str *getmpd(dict<ChartItem *, list<Edge *> *> *chart, ChartItem *start, dict<__ss_int, str *> *tolabel) {
    __ss_int __72, __73;
    Edge *edge;

    edge = ___min(1, 0LL, chart->__getitem__(start));
    if ((___bool(edge->right) and (edge->right)->label)) {
        return __modct(const_8, 3, tolabel->__getitem__(start->label), getmpd(chart, edge->left, tolabel), getmpd(chart, edge->right, tolabel));
    }
    else {
        return __modct(const_9, 2, tolabel->__getitem__(start->label), (((edge->left)->label)?(getmpd(chart, edge->left, tolabel)):(__str((edge->left)->vec))));
    }
    return 0;
}

str *binrepr(ChartItem *a, list<str *> *sent) {
    
    return (const_10)->join(reversed(((bin(a->vec))->__slice__(1LL, 2LL, 0LL, 0LL))->rjust(len(sent), const_11)));
}

void *pprint_chart(dict<ChartItem *, list<Edge *> *> *chart, list<str *> *sent, dict<__ss_int, str *> *tolabel) {
    tuple2<__ss_int, ChartItem *> *__78;
    Edge *edge;
    ChartItem *a;
    __iter<Edge *> *__84;
    list<Edge *> *__83;
    list<tuple2<__ss_int, ChartItem *> *>::for_in_loop __82;
    list<Edge *>::for_in_loop __86;
    __iter<tuple2<__ss_int, ChartItem *> *> *__80;
    list<tuple2<__ss_int, ChartItem *> *> *__79;
    __ss_int __81, __85, n;

    print2(NULL,0,1, const_12);

    FOR_IN(__78,sorted(new list_comp_1(chart), 0LL, 0LL, 0LL),79,81,82)
        __78 = __78;
        n = __78->__getfirst__();
        a = __78->__getsecond__();
        if (__NOT(___bool(chart->__getitem__(a)))) {
            continue;
        }
        print2(NULL,0,1, __modct(const_13, 2, tolabel->__getitem__(a->label), binrepr(a, sent)));

        FOR_IN(edge,chart->__getitem__(a),83,85,86)
            print2(NULL,1,1, __modct(const_14, 2, ___box(exp((-edge->inside))), ___box(exp((-edge->prob)))));
            if ((edge->left)->label) {
                print2(NULL,1,1, __modct(const_15, 2, tolabel->__getitem__((edge->left)->label), binrepr(edge->left, sent)));
            }
            else {
                print2(NULL,1,2, const_0, repr(sent->__getfast__((edge->left)->vec)));
            }
            if (___bool(edge->right)) {
                print2(NULL,1,1, __modct(const_15, 2, tolabel->__getitem__((edge->right)->label), binrepr(edge->right, sent)));
            }
            print2(NULL,0,0);
        END_FOR

        print2(NULL,0,0);
    END_FOR

    return NULL;
}

__ss_bool __ss_do(str *sent, Grammar *grammar) {
    tuple2<dict<ChartItem *, list<Edge *> *> *, ChartItem *> *__87;
    ChartItem *start;
    double p;
    dict<ChartItem *, list<Edge *> *> *chart;
    str *t;
    tuple2<str *, double> *__88;

    print2(NULL,0,2, const_16, sent);
    __87 = parse(sent->split(), grammar, NULL, (grammar->toid)->__getitem__(const_17), False);
    chart = __87->__getfirst__();
    start = __87->__getsecond__();
    pprint_chart(chart, sent->split(), grammar->tolabel);
    if (___bool(start)) {
        __88 = mostprobablederivation(chart, start, grammar->tolabel);
        t = __88->__getfirst__();
        p = __88->__getsecond__();
        print2(NULL,0,3, ___box(exp((-p))), t, const_18);
    }
    else {
        print2(NULL,0,1, const_19);
    }
    return ___bool((start!=NULL));
}

tuple2<list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *, list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *> *> *read_srcg_grammar(str *rulefile, str *lexiconfile) {
    /**
     Reads a grammar as produced by write_srcg_grammar. 
    */
    list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *> *lexicon;
    list<list<str *> *> *slexicon, *srules;
    list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *rules;

    srules = list_comp_2(rulefile);
    slexicon = list_comp_3(lexiconfile);
    rules = list_comp_5(srules);
    lexicon = list_comp_6(slexicon);
    return (new tuple2<list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *, list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *> *>(2,rules,lexicon));
}

Grammar *splitgrammar(list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *grammar, list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *> *lexicon) {
    /**
     split the grammar into various lookup tables, mapping nonterminal
    labels to numeric identifiers. Also negates log-probabilities to
    accommodate min-heaps.
    Can only represent ordered SRCG rules (monotone LCFRS). 
    */
    tuple2<tuple2<str *, str *> *, str *> *__148;
    tuple2<__array__::array<__ss_int> *, __array__::array<__ss_int> *> *__159;
    Terminal *t;
    list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *__155;
    tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *__154;
    list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *> *__149;
    __ss_int __151, __157;
    list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *>::for_in_loop __152;
    list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *>::for_in_loop __158;
    list<list<Rule *> *> *bylhs, *lbinary, *rbinary, *unary;
    tuple2<str *, str *> *rule, *tag;
    double w;
    tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *__153;
    dict<str *, __ss_int> *toid;
    __array__::array<__ss_int> *args, *arity, *lengths;
    list<tuple2<__ss_int, str *> *> *nonterminals;
    __ss_bool __160, __161;
    str *word;
    Rule *r;
    __iter<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *__156;
    __iter<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *> *__150;
    dict<str *, list<Terminal *> *> *lexical;
    dict<__ss_int, str *> *tolabel;
    tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *__147;
    tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *yf;

    nonterminals = (new list<tuple2<__ss_int, str *> *>(enumerate(((new list<str *>(2,const_3,const_20)))->__add__(sorted(((new set<str *>(new list_comp_7(grammar))))->__sub__((new set<str *>((new list<str *>(2,const_3,const_20))))), 0LL, 0LL, 0LL)))));
    toid = (new dict<str *, __ss_int>(new list_comp_8(nonterminals)));
    tolabel = (new dict<__ss_int, str *>(new list_comp_9(nonterminals)));
    bylhs = list_comp_10(nonterminals);
    unary = list_comp_11(nonterminals);
    lbinary = list_comp_12(nonterminals);
    rbinary = list_comp_13(nonterminals);
    lexical = (new dict<str *, list<Terminal *> *>());
    arity = (new __array__::array<__ss_int>(const_21, ((new list<__ss_int>(1,0LL)))->__mul__(len(nonterminals))));

    FOR_IN(__147,lexicon,149,151,152)
        __147 = __147;
        __148 = __147->__getfirst__();
        tag = __148->__getfirst__();
        word = __148->__getsecond__();
        w = __147->__getsecond__();
        t = (new Terminal(toid->__getitem__(tag->__getitem__(0LL)), toid->__getitem__(tag->__getitem__(1LL)), 0LL, word, __abs(w)));
        ASSERT(___bool(((new tuple2<__ss_int, __ss_int>(2,0LL,1LL)))->__contains__(arity->__getitem__(t->lhs))), 0);
        arity->__setitem__(t->lhs, 1LL);
        (lexical->setdefault(word, (new list<Terminal *>())))->append(t);
    END_FOR


    FOR_IN(__153,grammar,155,157,158)
        __153 = __153;
        __154 = __153->__getfirst__();
        rule = __154->__getfirst__();
        yf = __154->__getsecond__();
        w = __153->__getsecond__();
        __159 = yfarray(yf);
        args = __159->__getfirst__();
        lengths = __159->__getsecond__();
        ASSERT(___bool(__eq(yf, arraytoyf(args, lengths))), 0);
        if (((len(rule)==2LL) and (w==0.0))) {
            w = (w+1e-08);
        }
        r = (new Rule(toid->__getitem__(rule->__getfast__(0LL)), toid->__getitem__(rule->__getfast__(1LL)), (((len(rule)==3LL))?(toid->__getitem__(rule->__getfast__(2LL))):(0LL)), args, lengths, __abs(w)));
        if ((arity->__getitem__(r->lhs)==0LL)) {
            arity->__setitem__(r->lhs, len(args));
        }
        ASSERT(___bool((arity->__getitem__(r->lhs)==len(args))), 0);
        if ((len(rule)==2LL)) {
            (unary->__getfast__(r->rhs1))->append(r);
            (bylhs->__getfast__(r->lhs))->append(r);
        }
        else if ((len(rule)==3LL)) {
            (lbinary->__getfast__(r->rhs1))->append(r);
            (rbinary->__getfast__(r->rhs2))->append(r);
            (bylhs->__getfast__(r->lhs))->append(r);
        }
        else {
            throw ((new ValueError(__modct(const_22, 1, r))));
        }
    END_FOR

    return (new Grammar(unary, lbinary, rbinary, lexical, bylhs, toid, tolabel));
}

tuple2<__array__::array<__ss_int> *, __array__::array<__ss_int> *> *yfarray(tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *yf) {
    /**
     convert a yield function represented as a 2D sequence to an array
    object. 
    */
    __array__::array<__ss_int> *args, *lengths;
    str *lentype, *vectype;
    __ss_int lensize, vecsize;
    list<__ss_int> *initializer;

    vectype = const_23;
    vecsize = 32LL;
    lentype = const_24;
    lensize = 16LL;
    ASSERT(___bool((len(yf)<=lensize)), 0);
    ASSERT(all(new list_comp_14(vecsize, yf)), 0);
    initializer = list_comp_16(yf);
    args = (new __array__::array<__ss_int>(const_23, initializer));
    lengths = (new __array__::array<__ss_int>(const_24, map(1, __lambda2__, yf)));
    return (new tuple2<__array__::array<__ss_int> *, __array__::array<__ss_int> *>(2,args,lengths));
}

tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *arraytoyf(__array__::array<__ss_int> *args, __array__::array<__ss_int> *lengths) {
    
    return (new tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *>(new list_comp_18(lengths, args)));
}

__ss_int nextset(__ss_int a, __ss_int pos) {
    /**
     First set bit, starting from pos 
    */
    __ss_int result;

    result = pos;
    if ((a>>result)) {

        while (((((a>>result))&(1LL))==0LL)) {
            result = (result+1LL);
        }
        return result;
    }
    return (-1LL);
}

__ss_int nextunset(__ss_int a, __ss_int pos) {
    /**
     First unset bit, starting from pos 
    */
    __ss_int result;

    result = pos;

    while ((((a>>result))&(1LL))) {
        result = (result+1LL);
    }
    return result;
}

__ss_int bitcount(__ss_int a) {
    /**
     Number of set bits (1s) 
    */
    __ss_int count;

    count = 0LL;

    while (a) {
        a = ((a)&((a-1LL)));
        count = (count+1LL);
    }
    return count;
}

__ss_int testbit(__ss_int a, __ss_int offset) {
    /**
     Mask a particular bit, return nonzero if set 
    */
    
    return ((a)&((1LL<<offset)));
}

/**
class Grammar
*/

class_ *cl_Grammar;

void *Grammar::__init__(list<list<Rule *> *> *unary, list<list<Rule *> *> *lbinary, list<list<Rule *> *> *rbinary, dict<str *, list<Terminal *> *> *lexical, list<list<Rule *> *> *bylhs, dict<str *, __ss_int> *toid, dict<__ss_int, str *> *tolabel) {
    
    this->unary = unary;
    this->lbinary = lbinary;
    this->rbinary = rbinary;
    this->lexical = lexical;
    this->bylhs = bylhs;
    this->toid = toid;
    this->tolabel = tolabel;
    return NULL;
}

tuple2<str *, str *> *Grammar::__slots__;

/**
class ChartItem
*/

class_ *cl_ChartItem;

long ChartItem::__hash__() {
    __ss_int h;

    h = (((((5381LL<<5LL)+5381LL)*33LL))^(this->label));
    h = (((((h<<5LL)+h)*33LL))^(this->vec));
    return (((h==(-1LL)))?((-2LL)):(h));
}

__ss_bool ChartItem::__eq__(ChartItem *other) {
    __ss_bool __186, __187;

    if ((other==NULL)) {
        return False;
    }
    return __AND(___bool((this->label==other->label)), ___bool((this->vec==other->vec)), 186);
}

void *ChartItem::__init__(__ss_int label, __ss_int vec) {
    
    this->label = label;
    this->vec = vec;
    return NULL;
}

tuple2<str *, str *> *ChartItem::__slots__;

/**
class Edge
*/

class_ *cl_Edge;

__ss_bool Edge::__gt__(Edge *other) {
    
    return ___bool((this->score>other->score));
}

__ss_bool Edge::__lt__(Edge *other) {
    
    return ___bool((this->score<other->score));
}

__ss_bool Edge::__eq__(Edge *other) {
    __ss_bool __188, __189, __190, __191;

    return __AND(___bool((this->inside==other->inside)), __AND(___bool((this->prob==other->prob)), __AND(___bool(__eq(this->left, other->right)), ___bool(__eq(this->right, other->right)), 190), 189), 188);
}

void *Edge::__init__(double score, double inside, double prob, ChartItem *left, ChartItem *right) {
    
    this->score = score;
    this->inside = inside;
    this->prob = prob;
    this->left = left;
    this->right = right;
    return NULL;
}

tuple2<str *, str *> *Edge::__slots__;

/**
class Terminal
*/

class_ *cl_Terminal;

void *Terminal::__init__(__ss_int lhs, __ss_int rhs1, __ss_int rhs2, str *word, double prob) {
    
    this->lhs = lhs;
    this->rhs1 = rhs1;
    this->rhs2 = rhs2;
    this->word = word;
    this->prob = prob;
    return NULL;
}

tuple2<str *, str *> *Terminal::__slots__;

/**
class Rule
*/

class_ *cl_Rule;

void *Rule::__init__(__ss_int lhs, __ss_int rhs1, __ss_int rhs2, __array__::array<__ss_int> *args, __array__::array<__ss_int> *lengths, double prob) {
    
    this->lhs = lhs;
    this->rhs1 = rhs1;
    this->rhs2 = rhs2;
    this->args = args;
    this->lengths = lengths;
    this->prob = prob;
    this->_args = this->args;
    this->_lengths = this->lengths;
    return NULL;
}

tuple2<str *, str *> *Rule::__slots__;

/**
class Entry
*/

class_ *cl_Entry;

__ss_bool Entry::__lt__(Entry *other) {
    __ss_bool __192, __193, __194, __195;

    return __OR(___bool(__lt(this->value, other->value)), __AND(___bool(__eq(this->value, other->value)), ___bool((this->count<other->count)), 193), 192);
}

__ss_bool Entry::__eq__(Entry *other) {
    
    return ___bool((this->count==other->count));
}

void *Entry::__init__(ChartItem *key, Edge *value, __ss_int count) {
    
    this->key = key;
    this->value = value;
    this->count = count;
    return NULL;
}

tuple2<str *, str *> *Entry::__slots__;

/**
class agenda
*/

class_ *cl_agenda;

Edge *agenda::__getitem__(ChartItem *key) {
    
    return ((this->mapping)->__getitem__(key))->value;
}

__ss_bool agenda::__contains__(ChartItem *key) {
    
    return ___bool((this->mapping)->__contains__(key));
}

void *agenda::__setitem__(ChartItem *key, Edge *value) {
    dict<ChartItem *, Entry *> *__196, *__197;
    Entry *entry, *oldentry;

    if ((this->mapping)->__contains__(key)) {
        oldentry = (this->mapping)->__getitem__(key);
        entry = (new Entry(key, value, oldentry->count));
        this->mapping->__setitem__(key, entry);
        heappush(this->heap, entry);
        oldentry->count = INVALID;
    }
    else {
        entry = (new Entry(key, value, this->counter));
        this->counter = (this->counter+1LL);
        this->mapping->__setitem__(key, entry);
        heappush(this->heap, entry);
    }
    return NULL;
}

void *agenda::__init__() {
    
    this->heap = (new list<Entry *>());
    this->mapping = (new dict<ChartItem *, Entry *>());
    this->counter = 1LL;
    return NULL;
}

tuple2<ChartItem *, Edge *> *agenda::popitem() {
    Entry *entry;

    entry = heappop(this->heap);

    while ((entry->count==INVALID)) {
        entry = heappop(this->heap);
    }
    (this->mapping)->__delitem__(entry->key);
    return (new tuple2<ChartItem *, Edge *>(2,entry->key,entry->value));
}

__ss_int agenda::__len__() {
    
    return len(this->mapping);
}

void *batch(str *rulefile, str *lexiconfile, str *sentfile) {
    list<str *> *lines, *sent, *tags;
    tuple2<dict<ChartItem *, list<Edge *> *> *, ChartItem *> *__221;
    ChartItem *start;
    double p;
    dict<ChartItem *, list<Edge *> *> *chart;
    list<list<list<str *> *> *>::for_in_loop __212;
    Grammar *grammar;
    str *root, *t;
    list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *rules;
    list<list<list<str *> *> *> *__209, *sents;
    list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *> *lexicon;
    list<list<str *> *> *wordstags;
    __ss_int __211;
    tuple2<list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *, list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *> *> *__198;
    __iter<list<list<str *> *> *> *__210;
    tuple2<str *, double> *__222;

    __198 = read_srcg_grammar(rulefile, lexiconfile);
    rules = __198->__getfirst__();
    lexicon = __198->__getsecond__();
    root = (rules->__getfast__(0LL)->__getfirst__()->__getfirst__())->__getfast__(0LL);
    grammar = splitgrammar(rules, lexicon);
    lines = ((open(sentfile))->read())->splitlines();
    sents = list_comp_20(lines);

    FOR_IN(wordstags,sents,209,211,212)
        sent = list_comp_21(wordstags);
        tags = list_comp_22(wordstags);
        __ss_stderr->write(__modct(const_25, 1, (const_26)->join(sent)));
        __221 = parse(sent, grammar, tags, (grammar->toid)->__getitem__(root), False);
        chart = __221->__getfirst__();
        start = __221->__getsecond__();
        if (___bool(start)) {
            __222 = mostprobablederivation(chart, start, grammar->tolabel);
            t = __222->__getfirst__();
            p = __222->__getsecond__();
            print2(NULL,0,1, __modct(const_27, 2, ___box(exp((-p))), t));
        }
        else {
            print2(NULL,0,1, const_28);
        }
    END_FOR

    return NULL;
}

void *demo() {
    tuple2<dict<ChartItem *, list<Edge *> *> *, ChartItem *> *__223;
    ChartItem *start;
    dict<ChartItem *, list<Edge *> *> *chart;
    list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *> *rules;
    Grammar *grammar;
    list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *> *lexicon;

    rules = (new list<tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double> *>(4,(new tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double>(2,(new tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *>(2,(new tuple2<str *, str *>(3,const_17,const_29,const_30)),(new tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *>(1,(new tuple2<__ss_int, __ss_int>(3,0LL,1LL,0LL)))))),log(1.0))),(new tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double>(2,(new tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *>(2,(new tuple2<str *, str *>(3,const_29,const_29,const_31)),(new tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *>(2,(new tuple2<__ss_int, __ss_int>(1,0LL)),(new tuple2<__ss_int, __ss_int>(2,0LL,1LL)))))),log(0.5))),(new tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double>(2,(new tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *>(2,(new tuple2<str *, str *>(3,const_29,const_32,const_33)),(new tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *>(2,(new tuple2<__ss_int, __ss_int>(1,0LL)),(new tuple2<__ss_int, __ss_int>(1,1LL)))))),log(0.5))),(new tuple2<tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *> *, double>(2,(new tuple2<tuple2<str *, str *> *, tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *> *>(2,(new tuple2<str *, str *>(2,const_29,const_29)),(new tuple2<tuple2<__ss_int, __ss_int> *, tuple2<__ss_int, __ss_int> *>(2,(new tuple2<__ss_int, __ss_int>(1,0LL)),(new tuple2<__ss_int, __ss_int>(1,0LL)))))),log(0.1)))));
    lexicon = (new list<tuple2<tuple2<tuple2<str *, str *> *, str *> *, double> *>(4,(new tuple2<tuple2<tuple2<str *, str *> *, str *> *, double>(2,(new tuple2<tuple2<str *, str *> *, str *>(2,(new tuple2<str *, str *>(2,const_32,const_3)),const_34)),0.0)),(new tuple2<tuple2<tuple2<str *, str *> *, str *> *, double>(2,(new tuple2<tuple2<str *, str *> *, str *>(2,(new tuple2<str *, str *>(2,const_31,const_3)),const_35)),0.0)),(new tuple2<tuple2<tuple2<str *, str *> *, str *> *, double>(2,(new tuple2<tuple2<str *, str *> *, str *>(2,(new tuple2<str *, str *>(2,const_30,const_3)),const_36)),0.0)),(new tuple2<tuple2<tuple2<str *, str *> *, str *> *, double>(2,(new tuple2<tuple2<str *, str *> *, str *>(2,(new tuple2<str *, str *>(2,const_33,const_3)),const_37)),0.0))));
    grammar = splitgrammar(rules, lexicon);
    __223 = parse((const_38)->split(), grammar, (const_39)->split(), (grammar->toid)->__getitem__(const_17), False);
    chart = __223->__getfirst__();
    start = __223->__getsecond__();
    pprint_chart(chart, (const_38)->split(), grammar->tolabel);
    ASSERT(___bool(__eq(mostprobablederivation(chart, start, grammar->tolabel), (new tuple2<str *, double>(2,const_40,(-log(0.25)))))), 0);
    ASSERT(__ss_do(const_38, grammar), 0);
    ASSERT(__ss_do(const_41, grammar), 0);
    ASSERT(__ss_do(const_42, grammar), 0);
    print2(NULL,0,1, const_43);
    ASSERT(__NOT(__ss_do(const_44, grammar)), 0);
    print2(NULL,0,1, const_45);
    return NULL;
}

void __init() {
    const_0 = __char_cache[9];;
    const_1 = __char_cache[44];;
    const_2 = __char_cache[47];;
    const_3 = new str("Epsilon");
    const_4 = __char_cache[64];;
    const_5 = new str("not covered:");
    const_6 = new str("agenda max %d, now %d, items %d (%d labels), ");
    const_7 = new str("edges %d, blocked %d\n");
    const_8 = new str("(%s %s %s)");
    const_9 = new str("(%s %s)");
    const_10 = new str("");
    const_11 = __char_cache[48];;
    const_12 = new str("chart:");
    const_13 = new str("%s[%s] =>");
    const_14 = new str("%g\t%g");
    const_15 = new str("\t%s[%s]");
    const_16 = new str("sentence");
    const_17 = __char_cache[83];;
    const_18 = __char_cache[10];;
    const_19 = new str("no parse");
    const_20 = new str("ROOT");
    const_21 = __char_cache[66];;
    const_22 = new str("grammar not binarized: %r");
    const_23 = __char_cache[73];;
    const_24 = __char_cache[72];;
    const_25 = new str("parsing: %s\n");
    const_26 = __char_cache[32];;
    const_27 = new str("p=%g\n%s\n\n");
    const_28 = new str("no parse\n");
    const_29 = new str("VP2");
    const_30 = new str("VMFIN");
    const_31 = new str("VAINF");
    const_32 = new str("PROAV");
    const_33 = new str("VVPP");
    const_34 = new str("Darueber");
    const_35 = new str("werden");
    const_36 = new str("muss");
    const_37 = new str("nachgedacht");
    const_38 = new str("Darueber muss nachgedacht werden");
    const_39 = new str("PROAV VMFIN VVPP VAINF");
    const_40 = new str("(S (VP2 (VP2 (PROAV 0) (VVPP 2)) (VAINF 3)) (VMFIN 1))");
    const_41 = new str("Darueber muss nachgedacht werden werden");
    const_42 = new str("Darueber muss nachgedacht werden werden werden");
    const_43 = new str("ungrammatical sentence:");
    const_44 = new str("werden nachgedacht muss Darueber");
    const_45 = new str("(as expected)\n");
    const_46 = new str("unary");
    const_47 = new str("lbinary");
    const_48 = new str("rbinary");
    const_49 = new str("lexical");
    const_50 = new str("bylhs");
    const_51 = new str("toid");
    const_52 = new str("tolabel");
    const_53 = new str("label");
    const_54 = new str("vec");
    const_55 = new str("score");
    const_56 = new str("inside");
    const_57 = new str("prob");
    const_58 = new str("left");
    const_59 = new str("right");
    const_60 = new str("lhs");
    const_61 = new str("rhs1");
    const_62 = new str("rhs2");
    const_63 = new str("word");
    const_64 = new str("args");
    const_65 = new str("lengths");
    const_66 = new str("_args");
    const_67 = new str("key");
    const_68 = new str("value");
    const_69 = new str("count");
    const_70 = new str("__main__");
    const_71 = new str("usage: %s grammar lexicon sentences\n\ngrammar is a tab-separated text file with one rule per line, in this format:\n\nLHS\tRHS1\tRHS2\tYIELD-FUNC\tLOGPROB\ne.g., S\tNP\tVP\t[01,10]\t0.1\n\nLHS, RHS1, and RHS2 are strings specifying the labels of this rule.\nThe yield function is described by a list of bit vectors such as [01,10],\nwhere 0 is a variable that refers to a contribution by RHS1, and 1 refers to\none by RHS2. Adjacent variables are concatenated, comma-separated components\nindicate discontinuities.\nThe final element of a rule is its log probability.\nThe LHS of the first rule will be used as the start symbol.\n\nlexicon is also tab-separated, in this format:\n\nWORD\tEpsilon\tTAG\tLOGPROB\ne.g., nachgedacht\tEpsilon\tVVPP\t0.1\n\nFinally, sentences is a file with one sentence per line, consisting of a space\nseparated list of word/tag pairs, for example:\n\nDarueber/PROAV muss/VMFIN nachgedacht/VVPP werden/VAINF\n\nThe output consists of Viterbi parse trees where terminals have been replaced\nby indices; this makes it possible to express discontinuities in otherwise\ncontext-free trees.");

    __name__ = new str("__main__");

    argv = __sys__::argv;
    __ss_stderr = __sys__::__ss_stderr;
    cl_Grammar = new class_("Grammar");
    Grammar::__slots__ = (new tuple2<str *, str *>(7,const_46,const_47,const_48,const_49,const_50,const_51,const_52));
    cl_ChartItem = new class_("ChartItem");
    ChartItem::__slots__ = (new tuple2<str *, str *>(2,const_53,const_54));
    cl_Edge = new class_("Edge");
    Edge::__slots__ = (new tuple2<str *, str *>(5,const_55,const_56,const_57,const_58,const_59));
    cl_Terminal = new class_("Terminal");
    Terminal::__slots__ = (new tuple2<str *, str *>(5,const_60,const_61,const_62,const_63,const_57));
    cl_Rule = new class_("Rule");
    Rule::__slots__ = (new tuple2<str *, str *>(8,const_60,const_61,const_62,const_57,const_64,const_65,const_66,const_65));
    cl_Entry = new class_("Entry");
    Entry::__slots__ = (new tuple2<str *, str *>(3,const_67,const_68,const_69));
    INVALID = 0LL;
    cl_agenda = new class_("agenda");
    if (__eq(__name__, const_70)) {
        if ((len(argv)==4LL)) {
            batch(argv->__getfast__(1LL), argv->__getfast__(2LL), argv->__getfast__(3LL));
        }
        else {
            demo();
            print2(NULL,0,1, __modct(const_71, 1, argv->__getfast__(0LL)));
        }
    }
}

} // module namespace

int main(int __ss_argc, char **__ss_argv) {
    __shedskin__::__init();
    __sys__::__init(__ss_argc, __ss_argv);
    __math__::__init();
    __array__::__init();
    __itertools__::__init();
    __heapq__::__init();
    __shedskin__::__start(__plcfrs__::__init);
}