How do you parse a Synchronous Context Free Grammar?

Question

I am trying to parse a grammar of this type:

g = """
S -> A{1} B{2}, S -> B{2} A{1}
A -> A{1} A{2}, A -> A{2} A{1}
B -> B{1} A{2}, B -> A{2} B{1}
A -> a, A -> e
A -> b, A -> f
B -> b, B -> f
B -> a, B -> e
"""

(The numbers {1}, {2}, etc., represent the links between the non-terminals in the two synchronous grammars.)

I have already written a program that generates strings from this grammar, and it works well. However, I now want to test the produced strings in a parser to ensure that they conform to the grammar.

I know that there are various algorithms for context-free grammar (CFG) parsing, such as the Earley algorithm, CYK, Left-corner, and others. Since I am working with a grammar that is already in Chomsky Normal Form, I can potentially use the CYK algorithm without too many issues (though it will run in O(n^6) instead of O(n^3) as with standard CFGs).

However, I am struggling to figure out how to implement the CYK algorithm to parse two strings from two "linked" grammars.

I believe that:

• I will need two empty tables instead of one.
• It won't be sufficient to parse the two strings separately and simply check if both are accepted by their respective grammars.
• I need to ensure that every cell in one table is linked to a corresponding cell in the other table.

Can anyone help me with this?