void RBBISetBuilder::printSets() {
    int                   i;

    RBBIDebugPrintf("\n\nUnicode Sets List\n------------------\n");
    for (i=0; ; i++) {
        RBBINode        *usetNode;
        RBBINode        *setRef;
        RBBINode        *varRef;
        UnicodeString    setName;

        usetNode = (RBBINode *)fRB->fUSetNodes->elementAt(i);
        if (usetNode == NULL) {
            break;
        }

        RBBIDebugPrintf("%3d    ", i);
        setName = UNICODE_STRING("anonymous", 9);
        setRef = usetNode->fParent;
        if (setRef != NULL) {
            varRef = setRef->fParent;
            if (varRef != NULL  &&  varRef->fType == RBBINode::varRef) {
                setName = varRef->fText;
            }
        }
        RBBI_DEBUG_printUnicodeString(setName);
        RBBIDebugPrintf("   ");
        RBBI_DEBUG_printUnicodeString(usetNode->fText);
        RBBIDebugPrintf("\n");
        if (usetNode->fLeftChild != NULL) {
            usetNode->fLeftChild->printTree(TRUE);
        }
    }
    RBBIDebugPrintf("\n");
}

void RBBINode::printNode() {
    static const char * const nodeTypeNames[] = {
                "setRef",
                "uset",
                "varRef",
                "leafChar",
                "lookAhead",
                "tag",
                "endMark",
                "opStart",
                "opCat",
                "opOr",
                "opStar",
                "opPlus",
                "opQuestion",
                "opBreak",
                "opReverse",
                "opLParen"
    };

    if (this==NULL) {
        RBBIDebugPrintf("%10p", (void *)this);
    } else {
        RBBIDebugPrintf("%10p  %12s  %10p  %10p  %10p      %4d     %6d   %d ",
            (void *)this, nodeTypeNames[fType], (void *)fParent, (void *)fLeftChild, (void *)fRightChild,
            fSerialNum, fFirstPos, fVal);
        if (fType == varRef) {
            RBBI_DEBUG_printUnicodeString(fText);
        }
    }
    RBBIDebugPrintf("\n");
}

void RBBISetBuilder::printRanges()
{
	RangeDescriptor    *   rlRange;
	int                    i;

	RBBIDebugPrintf("\n\n Nonoverlapping Ranges ...\n");
	for (rlRange = fRangeList; rlRange != 0; rlRange = rlRange->fNext)
	{
		RBBIDebugPrintf("%2i  %4x-%4x  ", rlRange->fNum, rlRange->fStartChar, rlRange->fEndChar);

		for (i = 0; i < rlRange->fIncludesSets->size(); i++)
		{
			RBBINode    *   usetNode    = (RBBINode *)rlRange->fIncludesSets->elementAt(i);
			UnicodeString   setName = UNICODE_STRING("anon", 4);
			RBBINode    *   setRef = usetNode->fParent;
			if (setRef != NULL)
			{
				RBBINode * varRef = setRef->fParent;
				if (varRef != NULL  &&  varRef->fType == RBBINode::varRef)
				{
					setName = varRef->fText;
				}
			}
			RBBI_DEBUG_printUnicodeString(setName); RBBIDebugPrintf("  ");
		}
		RBBIDebugPrintf("\n");
	}
}

void RBBISymbolTable::rbbiSymtablePrint() const {
    RBBIDebugPrintf("Variable Definitions\n"
           "Name               Node Val     String Val\n"
           "----------------------------------------------------------------------\n");

    int32_t pos = -1;
    const UHashElement  *e   = NULL;
    for (;;) {
        e = uhash_nextElement(fHashTable,  &pos);
        if (e == NULL ) {
            break;
        }
        RBBISymbolTableEntry  *s   = (RBBISymbolTableEntry *)e->value.pointer;

        RBBI_DEBUG_printUnicodeString(s->key, 15);
        RBBIDebugPrintf("   %8p   ", (void *)s->val);
        RBBI_DEBUG_printUnicodeString(s->val->fLeftChild->fText);
        RBBIDebugPrintf("\n");
    }

    RBBIDebugPrintf("\nParsed Variable Definitions\n");
    pos = -1;
    for (;;) {
        e = uhash_nextElement(fHashTable,  &pos);
        if (e == NULL ) {
            break;
        }
        RBBISymbolTableEntry  *s   = (RBBISymbolTableEntry *)e->value.pointer;
        RBBI_DEBUG_printUnicodeString(s->key);
        s->val->fLeftChild->printTree(TRUE);
        RBBIDebugPrintf("\n");
    }
}

void RBBITableBuilder::printSet(UVector *s) {
    int32_t  i;
    for (i=0; i<s->size(); i++) {
        const RBBINode *v = static_cast<const RBBINode *>(s->elementAt(i));
        RBBIDebugPrintf("%5d", v==NULL? -1 : v->fSerialNum);
    }
    RBBIDebugPrintf("\n");
}

void RBBITableBuilder::printSet(UVector *s) {
    int32_t  i;
    for (i=0; i<s->size(); i++) {
        void *v = s->elementAt(i);
        RBBIDebugPrintf("%10p", v);
    }
    RBBIDebugPrintf("\n");
}

U_CFUNC void RBBI_DEBUG_printUnicodeString(const UnicodeString &s, int minWidth)
{
    int i;
    for (i=0; i<s.length(); i++) {
        RBBIDebugPrintf("%c", s.charAt(i));
        // putc(s.charAt(i), stdout);
    }
    for (i=s.length(); i<minWidth; i++) {
        RBBIDebugPrintf(" ");
    }
}

void RBBISymbolTable::rbbiSymtablePrint() const {
    RBBIDebugPrintf("Variable Definitions Symbol Table\n"
           "Name                  Node         serial  String Val\n"
           "-------------------------------------------------------------------\n");

    int32_t pos = UHASH_FIRST;
    const UHashElement  *e   = NULL;
    for (;;) {
        e = uhash_nextElement(fHashTable,  &pos);
        if (e == NULL ) {
            break;
        }
        RBBISymbolTableEntry  *s   = (RBBISymbolTableEntry *)e->value.pointer;

        RBBIDebugPrintf("%-19s   %8p %7d ", CStr(s->key)(), (void *)s->val, s->val->fSerialNum);
        RBBIDebugPrintf(" %s\n", CStr(s->val->fLeftChild->fText)());
    }

    RBBIDebugPrintf("\nParsed Variable Definitions\n");
    pos = -1;
    for (;;) {
        e = uhash_nextElement(fHashTable,  &pos);
        if (e == NULL ) {
            break;
        }
        RBBISymbolTableEntry  *s   = (RBBISymbolTableEntry *)e->value.pointer;
        RBBIDebugPrintf("%s\n", CStr(s->key)());
        RBBINode::printTree(s->val, TRUE);
        RBBINode::printTree(s->val->fLeftChild, FALSE);
        RBBIDebugPrintf("\n");
    }
}

//---------------------------------------------------------------------------------
//
//  pushNewNode   create a new RBBINode of the specified type and push it
//                onto the stack of nodes.
//
//---------------------------------------------------------------------------------
RBBINode  *RBBIRuleScanner::pushNewNode(RBBINode::NodeType  t) {
    fNodeStackPtr++;
    if (fNodeStackPtr >= kStackSize) {
        error(U_BRK_INTERNAL_ERROR);
        RBBIDebugPrintf("RBBIRuleScanner::pushNewNode - stack overflow.\n");
        *fRB->fStatus = U_BRK_INTERNAL_ERROR;
        return NULL;
    }
    fNodeStack[fNodeStackPtr] = new RBBINode(t);
    if (fNodeStack[fNodeStackPtr] == NULL) {
        *fRB->fStatus = U_MEMORY_ALLOCATION_ERROR;
    }
    return fNodeStack[fNodeStackPtr];
}

void  RBBIDataWrapper::printData() {
    RBBIDebugPrintf("RBBI Data at %p\n", (void *)fHeader);
    RBBIDebugPrintf("   Version = %d\n", fHeader->fVersion);
    RBBIDebugPrintf("   total length of data  = %d\n", fHeader->fLength);
    RBBIDebugPrintf("   number of character categories = %d\n\n", fHeader->fCatCount);

    printTable("Forward State Transition Table", fForwardTable);
    printTable("Reverse State Transition Table", fReverseTable);
    printTable("Safe Forward State Transition Table", fSafeFwdTable);
    printTable("Safe Reverse State Transition Table", fSafeRevTable);

    RBBIDebugPrintf("\nOrignal Rules source:\n");
    for (int32_t c=0; fRuleSource[c] != 0; c++) {
        RBBIDebugPrintf("%c", fRuleSource[c]);
    }
    RBBIDebugPrintf("\n\n");
}

//----------------------------------------------------------------------------------------
//
//  fixOpStack   The parse stack holds partially assembled chunks of the parse tree.
//               An entry on the stack may be as small as a single setRef node,
//               or as large as the parse tree
//               for an entire expression (this will be the one item left on the stack
//               when the parsing of an RBBI rule completes.
//
//               This function is called when a binary operator is encountered.
//               It looks back up the stack for operators that are not yet associated
//               with a right operand, and if the precedence of the stacked operator >=
//               the precedence of the current operator, binds the operand left,
//               to the previously encountered operator.
//
//----------------------------------------------------------------------------------------
void RBBIRuleScanner::fixOpStack(RBBINode::OpPrecedence p) {
    RBBINode *n;
    // printNodeStack("entering fixOpStack()");
    for (;;) {
        n = fNodeStack[fNodeStackPtr-1];   // an operator node
        if (n->fPrecedence == 0) {
            RBBIDebugPrintf("RBBIRuleScanner::fixOpStack, bad operator node\n");
            error(U_BRK_INTERNAL_ERROR);
            return;
        }

        if (n->fPrecedence < p || n->fPrecedence <= RBBINode::precLParen) {
            // The most recent operand goes with the current operator,
            //   not with the previously stacked one.
            break;
        }
            // Stack operator is a binary op  ( '|' or concatenation)
            //   TOS operand becomes right child of this operator.
            //   Resulting subexpression becomes the TOS operand.
            n->fRightChild = fNodeStack[fNodeStackPtr];
            fNodeStack[fNodeStackPtr]->fParent = n;
            fNodeStackPtr--;
        // printNodeStack("looping in fixOpStack()   ");
    }

    if (p <= RBBINode::precLParen) {
        // Scan is at a right paren or end of expression.
        //  The scanned item must match the stack, or else there was an error.
        //  Discard the left paren (or start expr) node from the stack,
            //  leaving the completed (sub)expression as TOS.
            if (n->fPrecedence != p) {
                // Right paren encountered matched start of expression node, or
                // end of expression matched with a left paren node.
                error(U_BRK_MISMATCHED_PAREN);
            }
            fNodeStack[fNodeStackPtr-1] = fNodeStack[fNodeStackPtr];
            fNodeStackPtr--;
            // Delete the now-discarded LParen or Start node.
            delete n;
    }
    // printNodeStack("leaving fixOpStack()");
}

void  RBBIDataWrapper::printData() {
#ifdef RBBI_DEBUG
    RBBIDebugPrintf("RBBI Data at %p\n", (void *)fHeader);
    RBBIDebugPrintf("   Version = {%d %d %d %d}\n", fHeader->fFormatVersion[0], fHeader->fFormatVersion[1],
                                                    fHeader->fFormatVersion[2], fHeader->fFormatVersion[3]);
    RBBIDebugPrintf("   total length of data  = %d\n", fHeader->fLength);
    RBBIDebugPrintf("   number of character categories = %d\n\n", fHeader->fCatCount);

    printTable("Forward State Transition Table", fForwardTable);
    printTable("Reverse State Transition Table", fReverseTable);

    RBBIDebugPrintf("\nOrignal Rules source:\n");
    for (int32_t c=0; fRuleSource[c] != 0; c++) {
        RBBIDebugPrintf("%c", fRuleSource[c]);
    }
    RBBIDebugPrintf("\n\n");
#endif
}

//.........这里部分代码省略.........
            }
            // Run the loop one last time with the fake end-of-input character category.
            mode = RBBI_END;
            category = 1;
        }

        //
        // Get the char category.  An incoming category of 1 or 2 means that
        //      we are preset for doing the beginning or end of input, and
        //      that we shouldn't get a category from an actual text input character.
        //
        if (mode == RBBI_RUN) {
            // look up the current character's character category, which tells us
            // which column in the state table to look at.
            // Note:  the 16 in UTRIE_GET16 refers to the size of the data being returned,
            //        not the size of the character going in, which is a UChar32.
            //
            UTRIE_GET16(&fTrie, c, category);

            // Check the dictionary bit in the character's category.
            //    Counter is only used by dictionary based iterators (subclasses).
            //    Chars that need to be handled by a dictionary have a flag bit set
            //    in their category values.
            //
            if ((category & 0x4000) != 0)  {
                fDictionaryCharCount++;
                //  And off the dictionary flag bit.
                category &= ~0x4000;
            }
        }

        #ifdef RBBI_DEBUG
            if (fTrace) {
                RBBIDebugPrintf("             %4d   ", (int32_t)utext_getNativeIndex(fText));
                if (0x20<=c && c<0x7f) {
                    RBBIDebugPrintf("\"%c\"  ", c);
                } else {
                    RBBIDebugPrintf("%5x  ", c);
                }
                RBBIDebugPrintf("%3d  %3d\n", state, category);
            }
        #endif

        // State Transition - move machine to its next state
        //
        state = row->fNextState[category];
        row = (RBBIStateTableRow *)
            (statetable->fTableData + (statetable->fRowLen * state));

        if (row->fAccepting == -1) {
            // Match found, common case.
            result = (int32_t)UTEXT_GETNATIVEINDEX(fText);
        }

        if (row->fLookAhead != 0) {
            if (lookaheadStatus != 0
                && row->fAccepting == lookaheadStatus) {
                // Lookahead match is completed.  
                result               = lookaheadResult;
                lookaheadStatus      = 0;
                // TODO:  make a standalone hard break in a rule work.
                if (lookAheadHardBreak) {
                    UTEXT_SETNATIVEINDEX(fText, result);
                    return result;
                }
                // Look-ahead completed, but other rules may match further.  Continue on

//-----------------------------------------------------------------------------
//
//  print   -  debugging function to dump the runtime data tables.
//
//-----------------------------------------------------------------------------
void  RBBIDataWrapper::printData() {
#ifdef RBBI_DEBUG
    uint32_t c, s;

    RBBIDebugPrintf("RBBI Data at %p\n", (void *)fHeader);
    RBBIDebugPrintf("   Version = %d\n", fHeader->fVersion);
    RBBIDebugPrintf("   total length of data  = %d\n", fHeader->fLength);
    RBBIDebugPrintf("   number of character categories = %d\n\n", fHeader->fCatCount);

    RBBIDebugPrintf("   Forward State Transition Table\n");
    RBBIDebugPrintf("State |  Acc  LA   Tag");
    for (c=0; c<fHeader->fCatCount; c++) {RBBIDebugPrintf("%3d ", c);}
    RBBIDebugPrintf("\n------|---------------"); for (c=0;c<fHeader->fCatCount; c++) {RBBIDebugPrintf("----");}
    RBBIDebugPrintf("\n");

    for (s=0; s<fForwardTable->fNumStates; s++) {
        RBBIStateTableRow *row = (RBBIStateTableRow *)
                                  (fForwardTable->fTableData + (fForwardTable->fRowLen * s));
        RBBIDebugPrintf("%4d  |  %3d %3d %3d ", s, row->fAccepting, row->fLookAhead, row->fTag);
        for (c=0; c<fHeader->fCatCount; c++)  {
            RBBIDebugPrintf("%3d ", row->fNextState[c]);
        }
        RBBIDebugPrintf("\n");
    }

    RBBIDebugPrintf("\nOrignal Rules source:\n");
    c = 0;
    for (;;) {
        if (fRuleSource[c] == 0)
            break;
        RBBIDebugPrintf("%c", fRuleSource[c]);
        c++;
    }
    RBBIDebugPrintf("\n\n");
#endif
}

//-----------------------------------------------------------------------------
//
//   RBBITableBuilder::build  -  This is the main function for building the DFA state transtion
//                               table from the RBBI rules parse tree.
//
//-----------------------------------------------------------------------------
void  RBBITableBuilder::build() {

    if (U_FAILURE(*fStatus)) {
        return;
    }

    // If there were no rules, just return.  This situation can easily arise
    //   for the reverse rules.
    if (fTree==NULL) {
        return;
    }

    //
    // Walk through the tree, replacing any references to $variables with a copy of the
    //   parse tree for the substition expression.
    //
    fTree = fTree->flattenVariables();
    if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "ftree")) {
        RBBIDebugPrintf("Parse tree after flattening variable references.\n");
        fTree->printTree(TRUE);
    }

    //
    // Add a unique right-end marker to the expression.
    //   Appears as a cat-node, left child being the original tree,
    //   right child being the end marker.
    //
    RBBINode *cn = new RBBINode(RBBINode::opCat);
    cn->fLeftChild = fTree;
    fTree->fParent = cn;
    cn->fRightChild = new RBBINode(RBBINode::endMark);
    cn->fRightChild->fParent = cn;
    fTree = cn;

    //
    //  Replace all references to UnicodeSets with the tree for the equivalent
    //      expression.
    //
    fTree->flattenSets();
    if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "stree")) {
        RBBIDebugPrintf("Parse tree after flattening Unicode Set references.\n");
        fTree->printTree(TRUE);
    }


    //
    // calculate the functions nullable, firstpos, lastpos and followpos on
    // nodes in the parse tree.
    //    See the alogrithm description in Aho.
    //    Understanding how this works by looking at the code alone will be
    //       nearly impossible.
    //
    calcNullable(fTree);
    calcFirstPos(fTree);
    calcLastPos(fTree);
    calcFollowPos(fTree);
    if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "pos")) {
        RBBIDebugPrintf("\n\n");
        printPosSets(fTree);
    }

    //
    //  For "chained" rules, modify the followPos sets
    //
    if (fRB->fChainRules) {
        calcChainedFollowPos(fTree);
    }

    //
    // Build the DFA state transition tables.
    //
    buildStateTable();
    flagAcceptingStates();
    flagLookAheadStates();
    flagTaggedStates();

    //
    // Update the global table of rule status {tag} values
    // The rule builder has a global vector of status values that are common
    //    for all tables.  Merge the ones from this table into the global set.
    //
    mergeRuleStatusVals();

    if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "states")) {printStates();};
}

void  RBBIDataWrapper::printTable(const char * heading, const RBBIStateTable * table)
{
	uint32_t   c;
	uint32_t   s;

	RBBIDebugPrintf("   %s\n", heading);

	RBBIDebugPrintf("State |  Acc  LA TagIx");
	for (c = 0; c < fHeader->fCatCount; c++) {RBBIDebugPrintf("%3d ", c);}
	RBBIDebugPrintf("\n------|---------------");
	for (c = 0; c < fHeader->fCatCount; c++)
	{
		RBBIDebugPrintf("----");
	}
	RBBIDebugPrintf("\n");

	if (table == NULL)
	{
		RBBIDebugPrintf("         N U L L   T A B L E\n\n");
		return;
	}
	for (s = 0; s < table->fNumStates; s++)
	{
		RBBIStateTableRow * row = (RBBIStateTableRow *)
		                          (table->fTableData + (table->fRowLen * s));
		RBBIDebugPrintf("%4d  |  %3d %3d %3d ", s, row->fAccepting, row->fLookAhead, row->fTagIdx);
		for (c = 0; c < fHeader->fCatCount; c++)
		{
			RBBIDebugPrintf("%3d ", row->fNextState[c]);
		}
		RBBIDebugPrintf("\n");
	}
	RBBIDebugPrintf("\n");
}