// doc/grammar.dox
  
  
  // Copyright  2018  Johns Hopkins University (author: Daniel Povey)
  
  // See ../../COPYING for clarification regarding multiple authors
  //
  // Licensed under the Apache License, Version 2.0 (the "License");
  // you may not use this file except in compliance with the License.
  // You may obtain a copy of the License at
  
  //  http://www.apache.org/licenses/LICENSE-2.0
  
  // THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  // KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
  // WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
  // MERCHANTABLITY OR NON-INFRINGEMENT.
  // See the Apache 2 License for the specific language governing permissions and
  // limitations under the License.
  
  namespace kaldi {
  
  /**
  
   \page grammar   Support for grammars and graphs with on-the-fly parts.
  
  
   This page explains our support for dynamically created grammars and graphs with
   extra parts that you want be able to compile quickly (like words you want to
   add to the lexicon; contact lists; things like that).  We have used the word
   "grammar" as an easy searchable term for this framework, but this is not the
   only way to implement grammars in Kaldi.  If you have a smallish, fixed grammar
   it would probably be much easier to create an FST (G.fst) directly from the
   grammar (ensuring it is determinizable by means of disambiguation symbols if
   necessary), and using the normal graph creation recipe.  This framework is
   specifically for where you have a compelling need to pre-compile the HCLG.fst
   for various sub-parts and have them dynamically stitched together (typically to
   avoid recompiling large graphs at runtime).
  
   This framework is limited to work only with left-biphone models.  This is
   without loss of performance, because our best models (chain models) already use
   left-biphone context.
  
  
    \section grammar_replace  Relation to OpenFst's 'Replace()' operation
  
    The design of these tools is inspired by OpenFst's  "Replace()"" operation, as implemented
    by its command-line tool fstreplace.  The basic idea is illustrated by its usage message:
  \verbatim
  Recursively replaces FST arcs with other FST(s).
  
    Usage: fstreplace root.fst rootlabel [rule1.fst label1 ...] [out.fst]
  \endverbatim
    Below is a very trivial example of using <code>fstreplace</code>; it just replaces the olabel 5
    in the top-level FST with 6.
  \verbatim
  # (echo 0  1  0  5; echo 1 0) | fstcompile > top.fst
  # (echo 0  1  0  6; echo 1 0) | fstcompile > x.fst
  # fstreplace top.fst 1000 x.fst 5 | fstprint
  0	1	0	0
  1	2	0	6
  2	3	0	0
  3
  \endverbatim
    The framework of these tools is similar, in that at the G.fst level there are
    symbols that will end up getting replaced by other FSTs.  Most of the
    complexity has to do with the need to handle phonetic context-- and this is
    the reason why we can't just use the existing Replace() operation or its
    on-demand equivalent.
  
    A slight difference in interface of our tools versus <code>fstreplace</code> is that in our
    tools, the top-level FST (corresponding to the 1st arg of <code>fstreplace</code>) does not
    have a symbol assigned to it and thus cannot be "replaced into" any
    FST.
  
  
    \section grammar_overview  Overview of the framework
  
   To explain how this works, we'll take the "contact list" scenario, where you want to
   build a large language model with a nonterminal, say <code>\#nonterm:contact_list</code> in it,
   and at recognition time you quickly build some kind of small LM representing
   the contact list (possibly with previously unseen words), and compile that graph.
   Both the "big graph" and the "small graph" are fully compiled down to the HCLG level.
   The GrammarFst code "stitches them together" at decode time.  The way this is
   accomplished is by putting special ilabels in the two HCLGs that the GrammarFst
   code knows how to interpret.  That is: most ilabels in the HCLGs correspond to
   transition-ids, but there are "special ilabels" with values over ten million, that
   the GrammarFst code knows how to interpret, and it uses them to stitch together
   the FSTs, in a way that's related to OpenFst's Replace() operation, but is a little
   more complicated due to the need to get the phonetic context right.  (It only supports
   left-biphone context, to keep the complexity manageable).
  
   The GrammarFst has an interface very similar to OpenFst's "Fst" type--
   sufficiently similar that the decoder can use it as a drop-in replacement for a
   normal FST-- but it does not actually inherit from any OpenFst type; this is to
   simplify the implementation and give us more freedom in designing it.  The
   decoders that use GrammarFst are templated on the FST type, and we use
   GrammarFst as the template argument when we want to decode with them.
  
   The StateId used in the GrammarFst code is a 64-bit StateId, which we interpret
   as a pair of 32-bit integers.  The high-order bits are the "fst instance" and the
   low-order bits are the state in that "fst instance".  In the contact-list example,
   fst-instance zero would be the top-level graph, and there would potentially be
   a new fst-instance, numbered 1, 2, ..., for each time the <code>\#nonterm:contact_list</code> nonterminal
   appears in the big language model.  However, these are only generated on demand
   as those parts of the graph are actually accessed.  The GrammarFst is a
   lightweight object that does very little work at startup.  It is designed to be
   as fast as possible in the "normal case" when we are not crossing FST
   boundaries, and are just traversing inside a single FST.  The GrammarFst code
   needs a fast-to-evaluate "signal" that it needs to do something special for a
   particular FST state.  We let the final-probabilities be that signal: that is,
   each time we initialize an ArcIterator, the GrammarFst code tests
   whether the final-prob has a special value or not.  If it has that special value
   (4096.0), then the GrammarFst code does a little bit of extra work to see whether
   it needs to expand the state, and to look up a previously expanded
   version of the state (or expand it if it wasn't already present).   By "expand"
   the state we mean compute the vector of arcs leaving it.
  
  
   The FST compilation process-- i.e. the process of going from G.fst to HCLG.fst--
   is a little different when we intend to support grammars.  That is, we need to
   extend some of the tools used in compilation to work correctly with certain
   special symbols that we introduce.  The differences are explained below.
  
  
    \subsection  grammar_overview  Where to find example script
  
   The top-level example scripts for this setup are in egs/mini_librispeech/s5;
   see the scripts local/grammar/simple_demo.sh and local/grammar/extend_vocab_demo.sh.
   There are also versions of these scripts that use silence probabilities, in
   local/grammar/simple_demo_silprobs.sh and local/grammar/extend_vocab_demo_silprobs.sh.
   (Actually the workflow is exactly the same in the silprob and no-silprob versions
   of the scripts; we created those different versions for testing purposes, as those
   demo scripts also help us test the correctness of the code).
  
  
    \section grammar_symtabs  Symbol tables and special symbols
  
    When using this framework, we to add certain extra symbols to the words.txt
    and phones.txt symbol tables.  These extra symbols represent certain special
    symbols intrinsic to the framework, plus the user-defined nonterminal symbols.
    In the following example the user-defined special symbols are \#nonterm:foo
    and \#nonterm:bar.
  \verbatim
  tail words.txt
  ZZZ  8431
  #0   8432
  #nonterm_begin  8434
  #nonterm_end  8435
  #nonterm:foo  8437
  #nonterm:bar  8438
  \endverbatim
   The phones.txt contains a couple more symbols:
  \verbatim
  tail phones.txt
  Z_S  243
  #0  244
  #1  245
  #2  246
  #nonterm_bos  247
  #nonterm_begin  248
  #nonterm_end  249
  #nonterm_reenter  250
  #nonterm:foo  251
  #nonterm:bar  252
  \endverbatim
   The user should never need to explicitly add these symbols to the words.txt and
   phones.txt files; they are automatically added by utils/prepare_lang.sh.  All the user
   has to do is to create the file 'nonterminals.txt' in the 'dict dir' (the directory
   containing the dictionary, as validated by validate_dict_dir.pl).
  
   The C++ code never directly interacts with the nonterminal symbols in
   words.txt; that is all done at the script level (e.g. creating L.fst), and the
   C++ code only interacts with the nonterminal symbols in phones.txt.  Therefore
   there are no particularly strong constraints on the symbols in words.txt if you
   are prepared to modify the scripts or create "LG.fst"-type graphs directly.
   There are some constraints on the order of these symbols in phones.txt: in that case,
   the inbuilt symbols (the ones without a colon) must be in the order shown,
   the user-defined nonterminals must directly follow them, and there must be no
   phones numbered higher than the nonterminal-related symbols (although higher-numbered
   disambiguation symbols are allowed).
  
   Some binaries accept an option <code>--nonterm-phones-offset</code>, which tell them
   where to find the nonterminal symbols.  This should always be equal to the
   integer id of the symbol <code>\#nonterm_bos</code> in <code>phones.txt</code>.  In the above example
   it would be <code>--nonterm-phones-offset=247</code>.
  
    \section grammar_special_g  Special symbols in G.fst
  
   If you are using this framework you will be creating several graphs, so there
   may be several copies of G.fst (and the intermediate and fully compiled
   versions thereof).  All of them are allowed to include sub-graphs via
   nonterminals, and this can be done recursively; it is OK if the fully
   compiled graph is infinite, because it is only expanded on demand.
  
   If you want to include a particular nonterminal (say the one for
   <code>\#nonterm:foo</code>), you have to include that symbol <code>\#nonterm:foo</code> on the input
   side of G.fst.  As to what you include on the output side: that's up to you, as
   the framework doesn't care, but bear in mind that symbols without
   pronunciations may cause problems for lattice word alignment.  Note to more
   advanced users: the program lattice-align-words won't work if there are output
   symbols in HCLG.fst that don't have any pronunciation, but the alternative
   solution lattice-align-words-lexicon will still work, as long as you add
   entries for those words with empty pronunciations, in align_lexicon.int; the
   entries will be of the form <code>200007 200007</code>, assuming 200007 is the integer id
   of the word with the empty pronunciation.  The script prepare_lang.sh adds
   these entries for you.
  
   For graphs which are not top-level graphs, all ilabel sequences in
   G.fst should begin with the special symbol <code>\#nonterm_begin</code> and end with
   <code>\#nonterm_end</code>.  This can be accomplished via <code>fstconcat</code> from the command
   line, or by just adding them directly as you create the graph.  These
   symbols will later be involved in selecting the correct phonetic context when we
   enter the compiled HCLG.fst.
  
   For some applications, such as the contact-list scenario where you are adding
   new vocabulary items, it may be easier to skip creating G.fst and just create
   LG.fst manually; this won't be hard to do once you know its expected structure.
   The example script local/grammar/extend_vocab_demo.sh in egs/mini_librispeech/s5/
   may be a good reference for this, even if you don't plan to actually use those
   scripts in production.
  
  
    \section grammar_special_lg  Special symbols in LG.fst
  
   Before we describe what L.fst does with the special symbols,
   we will state what we expect LG.fst to contain after composition.  All the
   special symbols are on the ilabels of LG.fst.
  
   Let us define the set of <em>"left-context phones"</em> as the set of phones that can
   end a word, plus the optional silence, plus the special symbol <code>\#nonterm_bos</code>.
   This is the set of phones that can possibly appear as the left-context when we
   are beginning a word, plus <code>\#nonterm_bos</code> as a stand-in for the beginning-of-sequence
   context where no previous phone was seen.  We will italicize the phrase
   <em>left-context phones</em> when we use it, to emphasize that it has a special meaning.
  
   For non-top-level graphs only:
  
    - All ilabel sequences in the FST must begin with <code>\#nonterm_begin</code> followed by each possible
      <em>left-context phone</em>, i.e. parallel arcs enumerating all possible phonetic
      left-contexts that could precede this nonterminal.
  
      In non-word-position-dependent systems we can just let this set be all phones;
      in word-position-dependent systems it can be all phones except word-internal
      and word-begin phones, i.e.  all phones except those that look like <code>XX_B</code>
      and <code>XX_I</code>.  If the set of possible left contexts is known to be smaller, it may
      be more efficient to make this a smaller set.  In addition to real phones,
      we include <code>\#nonterm_bos</code> in this set, which represents the phonetic
      context we encounter at the start of an utterance.
  
    - All ilabel sequences must end with <code>\#nonterm_end</code>.
  
   Whenever a nonterminal is invoked, whether from a top-level or non-top-level
   graph, the ilabels in LG.fst will be, for example, <code>\#nonterm:foo</code> followed by
   in parallel, all possible <em>left-context phones</em>.  These left-context get added
   by L.fst.
  
    \section grammar_special_l  Special symbols in L.fst
  
   This section explains what sequences involving special symbols in L.fst we need to
   add, in order to compile a LG.fst with the desired properties from G.fst.
   The things we describe below are implemented by
   utils/lang/make_lexicon_fst.py and utils/lang/make_lexicon_fst_silprob.py,
   and is activated when you provide the <code>--left-context-phones</code> and <code>--nonterminals</code>
   options.  This is automatically called from prepare_lang.sh when it sees the
   file nonterminals.txt in the input dictionary directory.
  
   Let the loop-state of L.fst be the state in L.fst with very high out-degree,
   from which all the words leave (and return).
  
  
   The lexicon needs to include, in addition to the normal things:
  
   - A sequence starting at the start state and ending at the loop-state, with
     olabel <code>\#nonterm_begin</code> and ilabels consisting of, <code>\#nonterm_begin</code>
     followed by all possible left-context phones (and <code>\#nonterm_bos</code>) in
     parallel.
   - An arc from the loop-state to a final state, with ilabel and olabel equal to <code>\#nonterm_end</code>.
   - For each user-defined nonterminal (e.g. <code>\#nonterm:foo</code>) and for
     <code>\#nonterm_begin</code>, a loop beginning and ending at the loop-state that starts with
     the user-defined nontermal, e.g. <code>\#nonterm:foo</code>, on the ilabel and
      olabel, and then has all <em>left-context-phones</em> on the ilabel only.
  
   In order to keep LG.fst as stochastic as possible (i.e. as "sum-to-one" as possible
   in probabilistic terms), when we have states from which there leave arcs containing
   all <em>left-context phones</em> we add a cost equal to the log of the number of
   left-context phones.  This will allow us to push the weights later
   on in the graph-building procedure, without causing strange effects that would
   be harmful to decoding speed and accuracy.  When the graphs actually get spliced
   together, all but one of the alternative paths for "all possible left-context
   phone" will be disallowed; and that that point we will cancel out the cost of
   log(number of left-context phones).  This happens in the function
   GrammarFst::CombineArcs().
  
   Note that the above means that each sub-graph corresponding to
   a user-defined nonterminal will allow optional silence after the nonterminal
   but not before it.  This is consistent with the way the nonterminal is invoked
   from the higher-level graph, and generates exactly one optional silence between each pair of
   "real" words, plus one at the beginning and end of the top-level graph.  This equivalence
    is something we test at the end of the example script
    egs/mini_librispeech/s5/local/grammar/simple_demo.sh.
   Users should bear all this in mind if they are going to construct these sub-graphs
   manually at the LG.fst level rather than using the provided scripts.
  
   \subsection grammar_special_l   Interaction with 'silprobs'
  
   In the versions of the lexicons that have word-specific silence probabilities
  (see <a href=http://www.danielpovey.com/files/2015_interspeech_silprob.pdf> this paper</a> for explanation)
   there are actually two versions of the loop state, one for after silence
   and one for after nonsilence .
   When using 'silprobs', each word has a word-specific cost at its beginning and end that
   is associated with the transition to/from nonsilence and silence respectively (where by
   "silence" we specifically mean the optional silence added by the lexicon, not silence phones
   in a more general sense).
  
   Please refer to utils/lang/make_lexicon_fst_silprob.py for the
   details of how we handle nonterminal symbols in combination with these types of
   graphs.  We will just share the top-level idea here, which is this: when we
   enter the HCLG.fst for the nonterminal, and when we return from it, we 'know' the
   identity of immediately preceding phone.  (That is how this framework works; read
   further if you find this surprising).  We use that information to implement
   the 'silprob' idea without having to give the FST additional entry
   points; basically, if the left-context phone was the optional-silence phone, we
   go to the state in L.fst that would have been in after seeing optional silence.
   This will do the right thing in the normal case.  In the specific configuration
   where you were not using word-position-dependent phones (c.f. the  --position-dependent-phones
   option of prepare_lang.sh) and where there are words in your lexicon that end with
   the optional-silence phone (e.g. SIL), this will not quite do the right thing,
   but we don't expect that this difference will be particularly significant in any real-world
   use cases.
  
    \section grammar_special_clg  Special symbols in CLG.fst
  
    First, some background: the symbols on the input of CLG.fst (i.e. the ilabels) have interpretation
    given by a what we call the <code>ilabel_info</code>.  This is explained more in \ref tree_ilabel.  Programs
    that consume CLG.fst always also consume the <code>ilabel_info</code>, which is a <code>vector<vector<int32> ></code>.
    For a particular ilabel, say 1536, <code>ilabel_info[1536] = { 5, 21 }</code> is a vector of integers representing
    a phone-in-context.  E.g. this would represent the phone 21 with a left-context of 5.
    Disambiguation symbols also appear on the input of CLG.fst, and they are represented in the <code>ilabel_info</code>
    a 1-dimensional vector like <code>{ -104 }</code> containing the negative of the disambiguation symbol's
    integer id.
  
    The special symbols we add to the input of CLG.fst to support the grammar-decoding framework
    always correspond to pairs of symbols,
    specifically pairs (</code>\#nontermXXX</code>, <em>left-context phone</em>), where <code>\#nontermXXX</code> is any
    of the symbols <code>\#nonterm_begin</code>, <code>\#nonterm_end</code>, <code>\#nonterm_reenter</code>, or user-defined
    nonterminals like <code>\#nonterm:foo</code>.  The ilabel-info for these special symbols will be
    pairs like <code>{-104, 21}</code> where the first element is the negative of the <code>\#nontermXXX</code> symbol
    and the second is the  <em>left-context phone</em>.  The negation makes it easy to distinguish these
   ilabel_info entries from regular phones-in-context.
  
    The special symbols in CLG.fst will be as follows.
  
    The following special symbols may appear in any CLG graph, top-level or not:
     - When any graph invokes a sub-graph, there will be an arc with an ilabel
       (</code>\#nonterm:foo</code>, <em>left-context-phone</em>) representing the
       user-specified nonterminal and the actual left-context, which will be
       followed by arcs with ilabels of the form (</code>\#nonterm_reenter</code>,
       <em>left-context-phone</em>), for all left-context phones.
  
    For non-top-level CLG graphs only:
     - These graphs will begin with ilabels representing pairs (</code>\#nonterm_begin</code>, <em>left-context-phone</em>),
       representing all potential left-contexts.
     - They will end with ilabels (</code>\#nonterm_end</code>, <em>left-context-phone</em>), representing
       actual left-contexts.
  
  
     \subsection grammar_special_c  Special symbols in C.fst
  
    First, background.  Since this framework only supports left-biphone
    context, the states of C.fst correspond to the left context phone, and the
    ilabels on the transitions correspond to biphones (plus self-loops for
    disambiguation symbols).
  
    Next, what we are trying to accomplish.  C.fst needs to do as follows
   (describing how it needs to change sequences in LG.fst to sequences in CLG.fst):
  
     - It needs to change the sequence <code>\#nonterm_begin</code> p1 (where p1 is a <em>left-context-phone</em>)
       to a single symbol representing the pair (</code>\#nonterm_begin</code>, p1).
     - It needs to change the symbol <code>\#nonterm_end</code> to a single symbol representing
       the pair (</code>\#nonterm_end</code> <em>left-context-phone</em>), where <em>left-context-phone</em>
       represents the current phonetic left-context.
     - For each user-defined nonterminal e.g. <code>\#nonterm:foo</code>, it needs to change
       the sequence <code>\#nonterm:foo</code> p1 (where p1 is a <em>left-context-phone</em>)
       to a sequence of two symbols representing the pairs (</code>\#nonterm:foo</code>, p0) and
       (</code>\#nonterm_renter</code> p1) respectively.  Here, p0 represents the phone that was
       previous to the symbol <code>\#nonterm:foo</code>.
  
   In order to implement the above, we augment the state-space of C.fst by adding
   three new states:
  
      - One which we transition to when the olabel is
       <code>\#nonterm_begin</code>
      - One which we transition to when we see any user-defined
        symbol <code>\#nonterm:foo</code>.
      - One which we transition to when the olabel is <code>\#nonterm_end</code>.
  
   In order to avoid changing the main context-fst code, we implement this in a
   special class fst::InverseLeftBiphoneContextFst which implements these extensions
   and which only supports the left-biphone case.  See that code for more
   details (search for "state space" in grammar-context-fst.h).
  
  
   \section grammar_special_hclg  Special symbols in HCLG.fst
  
    The special symbols in the HCLG.fst graphs will represent the same thing as
    those in CLG.fst graphs, discussed above; but their representation in integer
    form is different.
  
    Firstly, some background.  At the input of CLG.fst the symbols are indexes
    into an <code>ilabel_info</code> table.  At the input of HCLG.fst the symbols, in general,
    represent <code>transition-ids</code>-- and also disambiguation symbols, but those
    are removed after determinization.  The point is that HCLG.fst does not come with
    a table like the <code>ilabel_info</code> that gives us the interpretation of symbols,
    so we need to use an encoding that allows us to combine two integers into one.
  
    We choose a representation of the special symbols in HCLG.fst that avoids
    clashing with the transition-ids and which makes it relatively painless to
    decode the symbols to find what they represent.  The representation  of
    a pair (</code>\#nonterm:XXX</code>, <em>left-context-phone</em>) is,
    in the typical case:
  \verbatim
    hclg_ilabel = 1000000 + 1000 * nonterm_xxx + left_context_phone
  \endverbatim
    where of course <code>nonterm_xxx</code> and <code>left_context_phone</code> are the corresponding
    symbol-ids in <code>phones.txt</code>.  Actually, in place of
   the "1000" above we use the smallest multiple of 1000 that is greater than the value passed to the
   <code>--nonterm-phones-offset</code> option; this allows us to handle large phone sets while also being fairly
   human-readable.
  
  
    \subsection grammar_special_h  Special symbols in H.fst
  
   Since H.fst only needs to change the integer represention of the special
   symbols but otherwise leaves them unchanged, the changes to it are quite trivial.
   H.fst has a high-out-degree state which we will refer to as the loop-state.
   We just need to add a self-loop arc at the loop-state for each of the special
   symbols referred to in the <code>ilabel_info</code>.  The ilabel and olabel
   are different since the integer encodings are different.
  
  
    \section grammar_decoder  The decoder
  
  
   The current approach to decoding with grammars
   is to wrap up the entire thing as an FST so that the same decoding code as
   before can be used.   That is, we just invoke the decoder with a different FST.
   We use 64-bit state-ids, so that we can let the higher-order 32 bits encode the "fst instance"
   and the lower-order bits encode the state within that instance.  The fst instances
   are created on the fly as states are visited.  Instance 0 is always the "top-level" FST,
   and we create new FST instances on the fly as needed, when we encounter arcs with
   "special symbols" on.
  
   The actual decoder code is the same as the regular decoder; we just template it on
   a different FST type: type fst::GrammarFst instead of fst::Fst. Class fst::GrammarFst does not
   inherit from class fst::Fst or support its entire interface (this would have been very
   complex to implement); it only supports the parts of the interface actually needed
   by the decoder.
  
  
    \subsection grammar_decoder_arc_iterator The ArcIterator of GrammarFst
  
    Probably the most critical part of the design is the ArcIterator
   code, since the inner loop of the decoder is a loop over arcs.  In order to avoid
   having to copy the underlying FSTs, for "normal states" (those that don't have arcs
   leaving them which enter or return from other FST instances), the ArcIterator code actually points into the
   arcs of the underlying FSTs, which of course have a differently-typed 'nextstate', with 32 bits
   not 64 bits.  The ArcIterator also stores the higher 32 bits of the state-id, which
   corresponds to the "fst instance" id, and every time you call its Next() function it
   creates a new local copy of the 'current arc' it points to, which differs from the
   underlying arc by having a 64-bit 'nextstate'.  The overhead of copying the arc to a temporary will,
   we hope, be mostly removed by compiler optimation.  (In fact this does seem to be the
   case: the overhead of GrammarFst decoding is about 15\% with -O0 and 5\% with -O2).
  
   Some states in the GrammarFst are 'special' states because they have arcs leaving them that
   cross FST boundaries.   For these 'special' states we have to construct the arcs separately, and
   we store this information in a hash in class GrammarFst.
  
   To keep the decoder code fast and memory-efficient, we need to know quickly,
   every time we visit a state, whether it is a "special" state or a normal state.
   We don't want to do this with a big array indexed by state, because it would
   take up too much memory per GrammarFst object.  Instead we do it by giving a
   special final-prob value to "special states" in the underlying FSTs that
   GrammarFst stitches together.  The ArcIterator code tests whether the
   final-cost has this special value (4096.0) and if it does, it knows that it's a
   "special state" and looks it up in a hash; if not, it just looks up the start
   of the array of arcs for this state in the underlying FST.
  
   In order to avoid having any extra if-statements in the ArcIterator that would
   have to be evaluated while we loop over arcs, we make sure that even "expanded
   states" have vectors of arcs that use the underlying arc type (fst::StdArc)
   with 32-bit state-ids.  The "fst-instance" index of the destination FST is
   stored separately in the ArcIterator, just as it is for normal states.  This,
   of course, requires that we must not have states with arcs leaving them
   that transition to multiple FST instances.  See the next section for how
   we ensure this.
  
  
    \section grammar_prepare Preparing FSTs for use in grammar decoding
  
  
    The GrammarFst code has various requirements on the FSTs that it stitches together,
    some of which were mentioned above.  These requirements are designed to help
    keep the GrammarFst code fast.  The function fst::PrepareForGrammarFst (internally implemented
    by class fst::GrammarFstPreparer) ensures that these preconditions are met.  The user is required
    to call this preparation code prior to instantiating the GrammarFst object, so the preparation is
    considered part of the graph construction;  this keeps the run-time code fast.
    The standard graph-construction script utils/mkgraph.sh calls this automatically (via the binary
    make-grammar-fst) if it detects that you are using this framework.
  
   The tasks of fst::PrepareForGrammarFst include setting a final-cost of 4096.0 for
   FST states that will end up being "special" states, and also making various small
   changes to the HCLG.fst that ensure it has the properties needed by class fst::GrammarFst
   (e.g. ensuring no state will have transitions to multiple FST instances).  These
   changes are mostly accomplished by inserting epsilon arcs; for details, see the
   documentation of class fst::GrammarFstPreparer.
  
    \section grammar_olabels  Output labels in GrammarFsts
  
   In the example scripts we provided, because we only wanted "real words" to
   appear on the output side of HCLG.fst, we ensured that no special symbols of
   the form <code>\#nontermXXX</code> on the output side of G.fst.  However, the
   graph compilation framework does allow you to include those symbols if you
   want.  These might be useful in certain application scenarios, where you want
   to know that a particular span of words was decoded as part of a sub-grammar.
   The only thing you have to be careful of is that the program
   lattice-align-words (and the code underlying it) will not work if you have
   words that have an empty pronunciation.  That can be an issue if you need to find the
   exact time-alignment of words for some reason.  In those cases you should use
   the alternative program lattice-align-words-lexicon (which reads a file
   lexicon.int giving the pronunciation of words in your lexicon), which should
   work even in this case.  The prepare_lang.sh script already puts empty
   pronunciation entries for symbols of the form <code>\#nontermXXX</code>
   in lexicon.int, so lattice-align-words-lexicon method of word alignment
   should "just work" if you made the lang and graph directories using the
   provided scripts.
  
  
  
  
  
  */
  
  
  }