Synchronous context-free grammars (SynCFG or SCFG; not to be confused with stochastic CFGs) are a type of

formal grammar In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the language's syntax. A grammar does not describe ...

designed for use in

transfer-based machine translation Transfer-based machine translation is a type of machine translation (MT). It is currently one of the most widely used methods of machine translation. In contrast to the simpler direct model of MT, transfer MT breaks translation into three steps: ...

. Rules in these grammars apply to two languages at the same time, capturing grammatical structures that are each other's translations. The theory of SynCFGs borrows from syntax-directed transduction and syntax-based machine translation, modeling the reordering of clauses that occurs when translating a sentence by correspondences between phrase-structure rules in the source and target languages. Performance of SCFG-based MT systems has been found comparable with, or even better than, state-of-the-art phrase-based machine translation systems. Several algorithms exist to perform translation using SynCFGs.

Formalism

Rules in a SynCFG are superficially similar to CFG rules, except that they specify the structure of two phrases at the same time; one in the source language (the language being translated) and one in the target language. Numeric indices indicate correspondences between non-terminals in both constituent trees. Chiang gives the Chinese/English example: : (yu you , have with ) This rule indicates that an phrase can be formed in Chinese with the structure "yu you ", where and are variables standing in for subphrases; and that the corresponding structure in English is "have with " where and {{math, ''X''₂ are independently translated to English.

Software

cdec
MT decoding package that supports SynCFGs
Joshua
a machine translation decoding system written in Java

References

Formal languages Machine translation Natural language parsing Statistical natural language processing