Revision 64

Date:
2011/06/07 19:59:45
Author:
gdshaw@RISCID.ORG
Revision Log:
Added function fragtable::restrict, with changes to handling of unary rules to reduct number of recorded tags.
Files:

Legend:

 
Added
 
Removed
 
Modified
  • trunk/parser/fragtable.cc

     
    52 52
    53 53 void fragtable::apply(const grammar& rules)
    54 54 {
    55 for (size_t i=0;i!=_capacity;++i)
    56 {
    57 tags(i,1)|=rules.find(tags(i,1));
    58 }
    59
    60 55 // Loop 1: begin constructing fragments of length 2,
    61 56 // end with one that fills the whole buffer.
    62 57 for (size_t i=2;i!=_capacity+1;++i)
     
    69 64 // end with a RHS of length 1.
    70 65 for (size_t k=1;k!=i;++k)
    71 66 {
    72 tags(j,i)|=rules.find(tags(j,k),tags(j+k,i-k));
    73 tags(j,i)|=rules.find(tags(j,i));
    67 tagset lhs=rules.find(tags(j,k));
    68 tagset rhs=rules.find(tags(j+k,i-k));
    69 tags(j,i)|=rules.find(lhs,rhs);
    74 70 }
    75 71 }
    76 72 }
    77 73 }
    78 74
    75 void fragtable::restrict(const grammar& rules)
    76 {
    77 // Loop 1: begin examining fragments of length _capacity-1,
    78 // end with fragments of length 1.
    79 for (size_t i=_capacity-1;i!=0;--i)
    80 {
    81 // Loop 2: begin examining the fragment at the
    82 // far left of the buffer, end at the far right.
    83 for (size_t j=0;j!=_capacity-i+1;++j)
    84 {
    85 // Loop 3: iterate over the existing tags for this fragment.
    86 tagset new_tags;
    87 tagset old_tags=tags(j,i);
    88
    89 for (tagset::const_iterator t=old_tags.begin(),t_end=old_tags.end();t!=t_end;++t)
    90 {
    91 tagset test_tags;
    92 test_tags|=*t;
    93 test_tags|=rules.find(test_tags);
    94
    95 // Loop 4a: try fragment as the right-hand side of a rule.
    96 // (k is the start of the left-hand fragment.)
    97 for (size_t k=0;k!=j;++k)
    98 {
    99 tagset lhs=rules.find(tags(k,j-k));
    100 tagset produced_tags=rules.find(lhs,test_tags);
    101 produced_tags|=rules.find(produced_tags);
    102 if (!(produced_tags&tags(k,j+i-k)).empty())
    103 {
    104 new_tags|=*t;
    105 break;
    106 }
    107 }
    108
    109 // Loop 4b: try fragment as the left-hand side of a rule.
    110 // (k is one past the end of the right-hand fragment.)
    111 for (size_t k=j+i+1;k!=_capacity+1;++k)
    112 {
    113 tagset rhs=rules.find(tags(j+i,k-j-i));
    114 tagset produced_tags=rules.find(test_tags,rhs);
    115 produced_tags|=rules.find(produced_tags);
    116 if (!(produced_tags&tags(j,k-j)).empty())
    117 {
    118 new_tags|=*t;
    119 break;
    120 }
    121 }
    122 }
    123 tags(j,i)=new_tags;
    124 }
    125 }
    126 }
    127
    79 128 void fragtable::write(std::ostream& out) const
    80 129 {
    81 130 for (size_t i=0;i!=_capacity;++i)
  • trunk/parser/fragtable.h

     
    97 97 */
    98 98 void apply(const grammar& rules);
    99 99
    100 /** Restrict tags to those which form part of a full solution.
    101 * @param rules the grammar to be used
    102 */
    103 void restrict(const grammar& rules);
    104
    100 105 /** Write table to stream.
    101 106 * @param out the stream
    102 107 */