Class RBBITableBuilder

java.lang.Object
com.ibm.icu.text.RBBITableBuilder
class RBBITableBuilder extends Object
This class is part of the RBBI rule compiler. It builds the state transition table used by the RBBI runtime from the expression syntax tree generated by the rule scanner.

This class is part of the RBBI implementation only. There is no user-visible public API here.

  • Field Details

    • fRB

      private RBBIRuleBuilder fRB

    • fRootIx

      private int fRootIx
      The array index into RBBIRuleBuilder.fTreeRoots for the parse tree to operate on.

    • fDStates

      private List<RBBITableBuilder.RBBIStateDescriptor> fDStates
      D states (Aho's terminology). Index is state number.

    • fSafeTable

      private List<short[]> fSafeTable
      Synthesized safe table, a List of row arrays.

    • MAX_STATE_FOR_8BITS_TABLE

      private static final int MAX_STATE_FOR_8BITS_TABLE
      See Also:

    • fLookAheadRuleMap

      int[] fLookAheadRuleMap
      Map from rule number (fVal in look ahead nodes) to sequential lookahead index.

    • fLASlotsInUse

      int fLASlotsInUse
      Counter used when assigning lookahead rule numbers. Contains the last look-ahead number already in use. The first look-ahead number is 2; Number 1 (ACCEPTING_UNCONDITIONAL) is reserved for non-lookahead accepting states. See the declarations of RBBIStateTableRowT.

  • Constructor Details

  • Method Details

    • buildForwardTable

      void buildForwardTable()

    • calcNullable

      void calcNullable(RBBINode n)

    • calcFirstPos

      void calcFirstPos(RBBINode n)

    • calcLastPos

      void calcLastPos(RBBINode n)

    • calcFollowPos

      void calcFollowPos(RBBINode n)

    • addRuleRootNodes

      void addRuleRootNodes(List<RBBINode> dest, RBBINode node)

    • calcChainedFollowPos

      void calcChainedFollowPos(RBBINode tree, RBBINode endMarkNode)

    • buildStateTable

      void buildStateTable()

    • mapLookAheadRules

      void mapLookAheadRules()
      mapLookAheadRules

    • flagAcceptingStates

      void flagAcceptingStates()

    • flagLookAheadStates

      void flagLookAheadStates()

    • flagTaggedStates

      void flagTaggedStates()

    • mergeRuleStatusVals

      void mergeRuleStatusVals()

    • minimizeStates

      void minimizeStates()

    • printPosSets

      void printPosSets(RBBINode n)

    • findDuplCharClassFrom

      boolean findDuplCharClassFrom(RBBIRuleBuilder.IntPair categories)
      Find duplicate (redundant) character classes. Begin looking with categories.first. Duplicates, if found are returned in the categories parameter. This is an iterator-like function, used to identify character classes (state table columns) that can be eliminated.
      Parameters:
      categories - in/out parameter, specifies where to start looking for duplicates, and returns the first pair of duplicates found, if any.
      Returns:
      true if duplicate char classes were found, false otherwise.

    • removeColumn

      void removeColumn(int column)
      Remove a column from the state table. Used when two character categories have been found equivalent, and merged together, to eliminate the unneeded table column.

    • findDuplicateSafeState

      boolean findDuplicateSafeState(RBBIRuleBuilder.IntPair states)
      Find the next duplicate state in the safe reverse table. An iterator function.
      Parameters:
      states - in/out parameter, specifies where to start looking for duplicates, and returns the first pair of duplicates found, if any.
      Returns:
      true if duplicate states were found, false otherwise.

    • removeSafeState

      void removeSafeState(RBBIRuleBuilder.IntPair duplStates)
      Remove a duplicate state from the safe table.
      Parameters:
      duplStates - The duplicate pair of states. The first is kept, the second is removed. All references to the second in the state table are retargeted to the first.

    • removeDuplicateStates

      int removeDuplicateStates()
      Check for, and remove duplicate states (table rows).
      Returns:
      the number of states removed.

    • minimizeLookaheads

      void minimizeLookaheads()
      Minimizes the number of slots used by the lookaheads.

      When the state machine is first generated, every lookahead rule occupies a different slot, for instance, given 

        x / z;  # Lookahead 1 below.
  y / z;  # Lookahead 2 below.
  [xyz]*;
      the following state machine is produced, 
                x
        x โฎ  z
        โ†’ ๐‘ โ‚ โ†’ ๐‘Žโ‚
  START  xโ‡…y
    โ†ปz  โ†’ ๐‘ โ‚‚ โ†’ ๐‘Žโ‚‚
        y โ†ป  z
          y
      where ๐‘ แตข sets the current position for lookahead i (assigning pแตข=p_current), and ๐‘Žแตข accepts lookahead i if set, i.e., on state ๐‘Žแตข,the break iterator returns pแตข if set. Because they accept different lookaheads, states ๐‘Žโ‚ and ๐‘Žโ‚‚ are distinct in the initial partition constructed by minimizeStates(), and cannot be merged, and the state machine cannot be simplified.

      However, there is no need for lookaheads 1 and 2 to occupy different slots, i.e., there is no need for the state machine to separately store the positions set by ๐‘ โ‚ and ๐‘ โ‚‚ (for pโ‚ and pโ‚‚ to be distinct variables). Indeed, if state ๐‘ โ‚ is encountered, state ๐‘Žโ‚‚ cannot be reached without going through state ๐‘ โ‚‚, and vice versa, so if pโ‚ and pโ‚‚ are backed by the same variable p, the value set by p=pโ‚=p_current on ๐‘ โ‚ will have been overriden by p=pโ‚‚=p_current on ๐‘ โ‚‚, so that the pโ‚-pโ‚‚ merger has no effect.

      If the lookaheads are merged, states ๐‘Žโ‚ and ๐‘Žโ‚‚ are no longer initially distinct in minimizeStates() (they both accept the only lookahead), and indeed the whole state machine simplifies to 

              [xy]     z
  START   โ†’  ๐‘   โ†’  ๐‘Ž
    โ†ปz       โ†ป
            [xy]
      Lookaheads i and j can be merged if:
      1. From any state that sets lookahead i, no state that accepts lookahead j can be reached without going through a state that sets lookahead j; and
      2. From any state that sets lookahead j, no state that accepts lookahead i can be reached without going through a state that sets lookahead i.
      This reachability relation defines a directed graph of lookaheads, and an optimal merging of lookaheads is then a colouring of that graph. (In the example above, the graph of lookaheads has no edges, and is thus 1-colourable; more interesting examples can be found in the test
      invalid reference 
      com.ibm.icu.dev.test.rbbi.RBBITest#TestLookaheadPolychromy
      .)

      This function first computes the adjacency matrix of lookahead reachability, and then colours the graph of lookaheads and reassigns lookahead slots accordingly.

    • getTableSize

      int getTableSize()
      Calculate the size in bytes of the serialized form of this state transition table, which is identical to the ICU4C runtime form. Refer to common/rbbidata.h from ICU4C for the declarations of the structures being matched by this calculation.

    • exportTable

      RBBIDataWrapper.RBBIStateTable exportTable()
      Create a RBBIDataWrapper.RBBIStateTable for a newly compiled table. RBBIDataWrapper.RBBIStateTable is similar to struct RBBIStateTable in ICU4C, in common/rbbidata.h

    • buildSafeReverseTable

      void buildSafeReverseTable()
      Synthesize a safe state table from the main state table.

    • getSafeTableSize

      int getSafeTableSize()
      Calculate the size of the runtime form of this safe state table.

    • exportSafeTable

      RBBIDataWrapper.RBBIStateTable exportSafeTable()
      Create a RBBIDataWrapper.RBBIStateTable for the safe reverse table. RBBIDataWrapper.RBBIStateTable is similar to struct RBBIStateTable in ICU4C, in common/rbbidata.h

    • printSet

      void printSet(Collection<RBBINode> s)

    • printStates

      void printStates()

    • printReverseTable

      void printReverseTable()
      Debug Function. Dump the fully constructed safe reverse table.

    • printRuleStatusTable

      void printRuleStatusTable()

    • reachableByTransitions

      private boolean reachableByTransitions(int source, Predicate<Integer> isSink, Predicate<Integer> excludedState)
      Returns true if a state for which `isSink` returns true is reachable from state `source` by following transitions without going through any state for which `excludedState` returns true. Note that โ€œgoing throughโ€ is distinct from โ€œreachingโ€, and means entering and then leaving: A state can be both a sink and excluded, and can still be reachable.