1

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?

Improve this question
3
  • It seems to me that the typical use of a Synchronous CFG isn't to parse two strings, but to parse one string (from either 'side' of the grammar), and then translate it (into the other side).
    – Michael Dyck
    Commented Dec 13, 2024 at 14:26
  • @MichaelDyck well, not really. because if there is any possible ambiguity, it's not said that one sentence in L1 will always give the same sentence in L2. The algorithm that I am trying to work on, taking in input 2 strings has been cited by David Chiang in his paper on SynCFG (users.umiacs.umd.edu/~resnik/ling645_fa2005/notes/synchcfg.pdf)
    – nic
    Commented Dec 17, 2024 at 15:00
  • I'm speaking of the algorithm at page 6 of the PDF
    – nic
    Commented Dec 17, 2024 at 15:15

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.