reparse.cpp

功能比较强的正则表达式分析器

            cout << "% to push parentheses: " << packet.left << ", " <<
                    packet.right << ": " << packet.count << endl;
#endif
        }
        current->mark.tag->left = current->mark.tag->right;
        current->mark.tag->right = pos;
#ifdef __REparse_debug__
        cout << "% visited parentheses: " << pos << endl;
        cout << "% we have: " << current->mark.tag << ": " <<
                current->mark.tag->left << ", " <<
                current->mark.tag->right << endl;
#endif
        return result;
    default:
        return false;
    }
}

void Parser::searchTransfer(int &index, int &pace)
{
    pace = -1;
    if(counterStat == Outside)
    {
        for(; index < transferNum && current->transfers[index].counter.assigned()
                && (pace = match(current->transfers[index])) < 0; index++);
    }
    else
    {
        for(; index < transferNum &&
                (pace = match(current->transfers[index])) < 0; index++);
    }
}

void Parser::leave(int index)
{
    if(getBasicFlag(current) == MarkFlagBothVisited && index == transferNum - 1)
    {
        if(current->mark.tag->left == -1)
        {
#ifdef __REparse_debug__
            cout << "% parentheses incompleted!" << endl;
#endif
            current->mark.tag->left = 0;
            current->mark.tag->right = -1;
        }
#ifdef __REparse_debug__
            cout << "% leaving: " << current->mark.tag->left << ", " <<
                    current->mark.tag->right << endl;
#endif
        setBasicFlag(current, MarkFlagBoth);
    }
    if(counterStat == Inside)
    {
        if (current->transfers[index].counter.assigned())
        {
            current->transfers[index].counter.retrieve().userCount++;
        }
        else
        {
            current->transfers[0].counter.retrieve().userCount = 0;
        }
    }
    else if(counterStat == Outside)
    {
        current->transfers[index].counter.retrieve().userCount++;
    }
}

void Parser::transfer(int index, int pace)
{
    pos += pace;
#ifdef __REparse_debug__
    assert(index >= 0);
#endif
    State *outlet = current->transfers[index].outlet;
    if(current->transfers[index].style == Transfer::Serial &&
            current->transfers[index].charList.getCount() == 0 &&
            !isForbidden(&current->transfers[index]))
    {
        forbiddenList.append(&current->transfers[index]);
    }
    else
    {
        forbiddenList.clear();
    }
    current = outlet;
}

void Parser::saveAttempt(int index, int pace)
{
    track.freeEvents();
    Packet packet;
    packet.state = current;
    packet.pos = pos;
    packet.index = index;
    packet.pace = pace;
    if(isPureCountLoop(current))
    {
        packet.style = Packet::PureCountLoop;
        packet.count = getUserCount(current);
    }
    else
    {
        packet.style = (Packet::Style)counterStat;
    }
    packet.pushInto(track);
}

void Parser::saveExtra(Packet &packet)
{
    packet.state = current;
    setEventFlag(current, true);
    packet.pushInto(track);
}

bool Parser::restore(Packet &packet)
{
    while(1)
    {
        if(track.isEmpty())
        {
            return false;
        }
        packet.popOutof(track);
#ifdef __REparse_debug__
        cout << "% restoring style: " << packet.style << endl;
#endif
        if(packet.style < Packet::NoncountLoop)
        {
            break;
        }
        switch(packet.style)
        {
        case Parser::Packet::NoncountLoop:
            packet.state->mark.tag->left = packet.left;
            packet.state->mark.tag->right = packet.right;
            packet.state->mark.flag = MarkFlagBoth;
#ifdef __REparse_debug__
            cout << "% restoring parentheses: " << packet.left << ", " <<
                    packet.right << endl;
#endif
            break;
        case Parser::Packet::NoncountLoopVisited:
            packet.state->mark.tag->left = packet.left;
            packet.state->mark.tag->right = packet.right;
            packet.state->mark.flag = MarkFlagBothVisited;
#ifdef __REparse_debug__
            cout << "% restoring visited parentheses: " << packet.left << ", "
                    << packet.right << endl;
#endif
            break;
        case Parser::Packet::CountLoop:
            packet.state->mark.tag->left = packet.left;
            packet.state->mark.tag->right = packet.right;
            setUserCount(packet.state, packet.count);
            packet.state->mark.flag = (packet.count == 0)? MarkFlagBoth :
                    MarkFlagBothVisited;
#ifdef __REparse_debug__
            cout << "% restoring parentheses: " << packet.left << ", " <<
                    packet.right << ": " << packet.count << endl;
#endif
            break;
        case Parser::Packet::Single:
            setEventFlag(packet.state, false);
            switch(packet.state->mark.flag)
            {
            case MarkFlagLeft:
                packet.state->mark.tag->left = packet.pos;
                break;
            case MarkFlagRight:
                packet.state->mark.tag->right = packet.pos;
                break;
            }
            break;
        }
    }
#ifdef __REparse_debug__
    cout << "% restoring state: " << packet.state << "..." << endl;
#endif
    current = packet.state;
    pos = packet.pos;
    counterStat = (CounterStat)packet.style;
    if(packet.style == Parser::Packet::PureCountLoop)
    {
        setUserCount(current, packet.count);
    }
    return true;
}

Parser::StateRes Parser::attemptMax()
{
    Packet packet;
    bool extra = enter(packet);
    if(current->transfers[transferNum - 1].counter.assigned())
    {
        return Success;
    }
    int pace = match(current->transfers[transferNum - 1]);
    if(pace < 0)
    {
        if(extra)
        {
            saveExtra(packet);
        }
        return Unmatched;
    }
    if(extra)
    {
        saveExtra(packet);
    }
    setUserCount(current, 0);
    transfer(transferNum - 1, pace);
    return Matched;
}

Parser::StateRes Parser::attemptNormal()
{
    Packet packet;
    bool extra = enter(packet);
    int index1 = 0, index2 = 0, pace1, pace2;
    searchTransfer(index1, pace1);
    if(pace1 < 0)
    {
        if(extra)
        {
            saveExtra(packet);
        }
        else if(isPureCountLoop(current))
        {
            setUserCount(current, 0);
        }
        return Unmatched;
    }
    searchTransfer(index2 = index1 + 1, pace2);
    if(pace2 >= 0)
    {
        saveAttempt(index2, pace2);
#ifdef __REparse_debug__
        cout << "% pushing state: " << current << ", pos: " << pos <<
                ", index: " << index2 << endl;
#endif
    }
    if(extra)
    {
        saveExtra(packet);
    }
    leave(index1);
    transfer(index1, pace1);
    return Matched;
}

Parser::StateRes Parser::attempt()
{
#ifdef __REparse_debug__
    cout << "% attempting state: " << current << ", pos: " << pos
            << endl;
#endif
    if (current == NULL)
    {
        return Success;
    }
    transferNum = current->transfers.getCount();
    switch(counterStat = getCounterStat(current))
    {
    case Noncount: case Inside: case Outside:
        return attemptNormal();
    case Max:
        return attemptMax();
    default:
        return Failure;
    }
}

Parser::StateRes Parser::reattempt()
{
    Packet packet;
    if(restore(packet) == false)
    {
        return Failure;
    }
    forbiddenList.clear();
#ifdef __REparse_debug__
    cout << "% reattempting state: " << current << ", pos: "
            << pos << ", index: " << packet.index << endl;
#endif
    int index1 = packet.index, pace1 = packet.pace, index2 = index1 + 1, pace2;
    bool extra = enter(packet);
    searchTransfer(index2, pace2);
    if(pace2 >= 0)
    {
        saveAttempt(index2, pace2);
#ifdef __REparse_debug__
        cout << "% pushing state: " << current << ", pos: " << pos <<
                ", index: " << index2 << endl;
#endif
    }
    if(extra)
    {
        saveExtra(packet);
    }
    leave(index1);
    transfer(index1, pace1);
    return Matched;
}

bool Parser::process()
{
    Parser::StateRes res = Matched;
    while(1)
    {
        switch(res)
        {
        case Matched:
            res = attempt();
            break;
        case Unmatched:
            res = reattempt();
            break;
        case Success:
            return true;
        case Failure:
            return false;
        }
    }
}

void Parser::cleanNode(TagNode *node)
{
    node->entry.reset();
    int count = node->branches.getCount();
    for(int i = 0; i < count; i++)
    {
        if(node->branches[i])
        {
            cleanNode(node->branches[i]);
        }
    }
}

Parser::Parser()
{
#ifndef __REmachine_as_Reference__
    machine = NULL;
#endif
#ifdef __REparse_debug__
    cout << "% Stack element size: " << sizeof(int) << endl;
#endif
}

Parser::~Parser()
{
#ifdef __REparse_debug__
    cout << "% Max stack depth: " << maxStackDepth << " (" <<
            maxStackDepth * sizeof(int) << " bytes)"<<endl;
#endif
}

#ifdef __REmachine_as_Reference__

Parser::Parser(const char *expression, int len)
{
    __Base::create();
    __retrieve().create(expression, len);
#ifdef __REparse_debug__
    cout << "% Stack element size: " << sizeof(int) << endl;
#endif
}

Parser &Parser::operator =(const Parser &copy)
{
    __Base::operator =(copy);
    return *this;
}

Parser &Parser::operator =(const Machine &m)
{
    __Base::__assign((__Base*)&m);
    return *this;
}

void Parser::createMachine(const char *expression, int len)
{
    __Base::create();
    __retrieve().create(expression, len);
}

void Parser::destroyMachine()
{
    if(assigned())
    {
        __retrieve().destroy();
    }
}

void Parser::release()
{
    __Base::release();
}

#else

void Parser::setMachine(Machine *machine)
{
    this->machine = machine;
}

Machine *Parser::getMachine()
{
    return machine;
}

#endif  // #ifdef __REmachine_as_Reference__

int Parser::parse(char *str, int len)
{
#ifdef __REmachine_as_Reference__
    if(!assigned())
    {
        return -1;
    }
    MachineCore &machine = __retrieve();
#else
    if(machine == NULL)
    {
        return -1;
    }
#endif
    if((current = __machine_member__(start)) == NULL)
    {
        return -1;
    }
    cleanNode(__machine_member__(tagTrie).root);
    this->str = str;
    this->len = len;
#ifdef __REparse_debug__
    stackDepth = maxStackDepth = 0;
#endif
    pos = 0;
    int res = process();
    track.clear();
    return res? __machine_member__(tagTrie).root->entry.right = pos : -1;
}

bool Parser::getShortcut(char *expression, int len, int &left, int &right)
{
#ifdef __REmachine_as_Reference__
    if(!assigned())
    {
        return false;
    }
    MachineCore &machine = __retrieve();
#else
    if(machine == NULL)
    {
        return -1;
    }
#endif
    int pos = 1;
    TagNode *node = __machine_member__(getShortcut)
            (expression, len, pos, __machine_member__(tagTrie).root);
    if(node)
    {
        left = node->entry.left;
        right = node->entry.right;
        return true;
    }
    return false;
}

////////////////////////////////////////////////////////////////////////////////

#ifdef __REparse_debug__

bool MachineCore::isEnd(State *state) const
{
    int count = state->transfers.getCount();
    State::Transfer &transfer = state->transfers[count - 1];
    if (transfer.style == State::Transfer::Serial &&
            transfer.charList.getCount() == 0 && transfer.outlet == NULL)
    {
        return true;
    }
    return false;
}

void MachineCore::viewTransfer(State::Transfer &transfer) const
{
    int count = transfer.charList.getCount();
    cout << "% {outlet: " << transfer.outlet << ", ";
    cout << "style: " << transfer.style << ", ";
    switch(transfer.style)
    {
    case State::Transfer::Serial:
    case State::Transfer::Inclusive:
    case State::Transfer::Exclusive:
        {
            cout << "charlist:";
            for(int i = 0; i < count; i++)
            {
                cout << transfer.charList[i];
            }
            cout << ", ";
            break;
        }
    case State::Transfer::Shortcut:
        cout << "shortcut:" << transfer.tag;
        break;
    }
    State::CounterData cdata;
    if(transfer.counter.retrieve(cdata))
    {
        int count = cdata.countset.getCount();
        cout << "count: ";
        for(int i = 0; i < count; i++)
        {
            cout << cdata.countset[i].low << ", " <<
                    cdata.countset[i].high << ";";
        }
    }
    cout << ">;" << endl;
}

void MachineCore::viewFromState(State *state, ClearList &list) const
{
    if (state == NULL)
    {
        return;
    }
    int count = state->transfers.getCount(), i;
    for(i = list.getCount(); --i >= 0;)
    {
        if(list[i] == state) return;
    }
    list.append(state);
    cout << "% [" << state << "] ";
    if (isEnd(state)) cout << "* ";
    cout << "mark: " << state->mark.tag << ":" << (int)state->mark.flag << endl;
    for(int i = 0; i < count; i++)
    {
        viewTransfer(state->transfers[i]);
    }
    for(i = 0; i < count; i++)
    {
        viewFromState(state->transfers[i].outlet, list);
    }
}

void MachineCore::viewTree(TagNode *node) const
{
    int count = node->branches.getCount();
    cout << "% node: " << node << endl;
    for(int i = 0; i < count; i++)
    {
        if(node->branches[i])
        {
            viewTree(node->branches[i]);
        }
    }
    cout << "% end of node: " << node << endl;
}

void MachineCore::view() const
{
    ClearList list;
    cout << "% states:" << endl;
    viewFromState(start, list);
    cout << "% tree:" << endl;
    if(tagTrie.root) viewTree(tagTrie.root);
}

void Parser::viewMachine() const
{
#ifdef __REmachine_as_Reference__
    if(assigned())
    {
        __retrieve().view();
    }
#else
    if(machine)
    {
        machine->view();
    }
#endif    
}

#endif