Skip to content

Instantly share code, notes, and snippets.

@stesh
Created March 14, 2011 22:48
Show Gist options
  • Save stesh/870033 to your computer and use it in GitHub Desktop.
Save stesh/870033 to your computer and use it in GitHub Desktop.
/**
* As described in 'updates' in the nodes
*/
void CHART::do_cell(int i, int k) {
Rule r;
Category A, B, C;
int A_included, B_included;
// constituents of length a...k
for (int a = 1; a < k; ++a) {
// Each rule of the grammar
for (unsigned int j = 0; j < g.rules.size(); j++) {
if (g.rules[j].dtrs.size() == 2) {
// C --> A B
// head/mother/whatever
C = g.rules[j].mother;
// Daughters (assuming CNF, so has to be binary)
A = g.rules[j].dtrs[0];
B = g.rules[j].dtrs[1];
// Loop through all the constituents recorded in the current
// cell to determine whether or not the first daughter of the
// current rule is included in it.
for (unsigned int c = 0; c < edges[i][a].size(); c++) {
A_included = are_equal(A, edges[i][a][c]);
// As soon as A is found, we can stop searching
if (A_included) {
break;
}
}
// No point in looking for B unless A is already there
if (A_included) {
for (unsigned int c = 0; c < edges[i+k][k-a].size(); c++) {
B_included = are_equal(B, edges[i+k][k-a][c]);
// As soon as B is found, we can stop
if (B_included) {
break;
}
}
}
}
// Both have to be in the correct positions in order to recognize the
// mother of the current rule.
if (A_included and B_included) {
edges[i][k].push_back(C);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment