expanding a synchronous grammar

Question

BACKGROUND: A synchronous grammar is a like two context-free grammars connected in parallel. It is used for translation. For example, here is a small synchronous grammar that can be used for translating between natural language text and semantic representation:

== {verb} ==
* I offer {noun}.                /   OFFER({noun})
* Will you accept {noun}?        /   QUERY({noun})
* I offer no company car.        /   OFFER(Leased Car=Without leased car)

== {noun} ==
* {number} % pension        /   Pension Fund={number}%
* A salary of {number} NIS  /   Salary={number}
* A company car             /   Leased Car=With leased car

The headings ({verb}, {noun}) are the nonterminals of the grammar. under each nonterminal is a list of translations enabled by this nonterminal.

Starting from the nontermnial {verb}, we can create, from the above grammar, the following 7 translations:

I offer no company car. => [OFFER(Leased Car=Without leased car)]
I offer A company car. => [OFFER(Leased Car=With leased car)]
Will you accept A salary of {number} NIS? => [QUERY(Salary={number})]
I offer {number} % pension. => [OFFER(Pension Fund={number}%)]
I offer A salary of {number} NIS. => [OFFER(Salary={number})]
Will you accept A company car? => [QUERY(Leased Car=With leased car)]
Will you accept {number} % pension? => [QUERY(Pension Fund={number}%)]

The translations are many-to-many, i.e., there can be more than one translation to each source string, and vice versa. So, each set of translations for a specific nontermnial is represented by a multimap (we use a class ValueSetMap for representing a many-to-many map). An entire grammar is represented by a map of such multimaps: Map>. It maps a nonterminal to its multimap of translations.

Here is some Java code I wrote, for expanding a grammar into a flat multimap of translations. It works for the above example and some more complicated examples, but I wonder if it really covers all cases. All comments are welcome:

public class GrammarExpander {

    public GrammarExpander(Map<String, ValueSetMap<String,String>> grammarMap) {
        this.grammarMap = grammarMap;
        this.expandedGrammarMap = new HashMap<String,ValueSetMap<String,String>>();
    }

    public ValueSetMap<String, String> expand(String startNonterminal, int maxDepth) {
        if (expandedGrammarMap.containsKey(startNonterminal))
            return expandedGrammarMap.get(startNonterminal);

        Set<String> nonterminals = grammarMap.keySet();
        ValueSetMap<String, String> translationsFromStartNonterminal =
                grammarMap.get(startNonterminal);

        if (translationsFromStartNonterminal==null)
            throw new NullPointerException("No translations from startNonterminal " +
                startNonterminal);

        // don't expand nonterminal anymore - prevent infinite recursion
        if (maxDepth<=0)
            return translationsFromStartNonterminal;

        for (String nonterminal: nonterminals) { // expand each nonterminal in turn
            ValueSetMap<String,String> newTranslations =
                new SimpleValueSetMap<String,String>();
            for (String source: translationsFromStartNonterminal.keySet()) {
                for (String target: translationsFromStartNonterminal.get(source)) {
                    // source contains nonterminal - expand it recursively
                    if (source.contains(nonterminal) || target.contains(nonterminal)) { 
                        ValueSetMap<String, String> expansions = 
                            this.expand(nonterminal, maxDepth-1);
                        for (String expansionSource: expansions.keySet())
                            for (String expansionTarget: expansions.get(expansionSource))
                                newTranslations.put(
                                    source.replace(nonterminal, expansionSource), 
                                    target.replace(nonterminal, expansionTarget));
                    } else {
                        newTranslations.put(source, target);
                    }
                }
            }
            translationsFromStartNonterminal = newTranslations;
        }

        expandedGrammarMap.put(startNonterminal, translationsFromStartNonterminal);
        return translationsFromStartNonterminal;
    }

    /*
     * protected zone
     */

    protected Map<String, ValueSetMap<String, String>> grammarMap;
    protected Map<String, ValueSetMap<String, String>> expandedGrammarMap;
}

Answer 1

1. NullPointerException

   It should be IllegalArgumentException. Consider just returning empty collection of expansion. It greatly improves composeability of your code.

   Think about making invalid states unrepresentable. (though I cannot think a trivial way of doing this, in this case.)

2. In the following statement translation is recursively expanded if either of source and target contains nonterminal. Whereas the comment says that the translation is expanded if source contains nonterminal

   // source contains nonterminal - expand it recursively
   if (source.contains(nonterminal) || target.contains(nonterminal)) { 
   

   Misleading comments are often a sign of a buggy algorithm.

   Moreover in the given examples it is observed that source contains a nonterminal iff target also contains nonterminal

   Maybe this should be a constraint of the grammar.

3. Moreover source.contains(nonterminal) suggest that you implicitly assume nonterminals, that is the keys of grammarMap start and end with "{", "}". and nonterminal names do not contain "{}", and there may be more constraints. Consider keys: noun, pronoun, {pronoun}, {{noun}}. See the looming trouble? The keys should be validated in the creation of the grammar. And some javadoc etc comments will also be helpful if not sufficient. Even if you will be the only user ever of this code, you will forget these implicit assumptions in no time.

4. In according with above advice consider using abstract data types instead of meaningless primitive types (java.util.Collection, String, etc.) such that your multilevel loops read more something like

   for (Translation translation : translations) {
       grammar.substituteOneLevel(translation)
   }
   
   // in grammar.substituteOneLevel(translation)
    for (Nonterminal nonterminal : translation.getNonterminals()) {
        for (Expansion expansion : grammar.getExpansions(nonterminal)) { 
           result.add(translation.substitute(nonterminal, expansion);
        }
    }
   

   or some such..

   Apart from improved readability and clarity of you business(academic) logic by using language (nouns and verbs) of from your domain; you can also disallow a grammar to have expansions that contain nonterminals that the grammar itself does not contain. (your NullPointerException..)

5. Efficiency-wise, one of my objections is the:

   for (String nonterminal: nonterminals) { // expand each nonterminal in turn
   

   why try to expand terminals that is not contained in any of the current translations?

6. Expanding a non-terminal for a fixed number of steps does not seem very useful. What is your use case? Do you have a running test case, that demonstrates the setup of the grammar and the manner it will be used?

7. Even if Expanding a non-terminal for a fixed number of steps is what you want, you probably will also want some indication of whether you have exhausted all possible expansions. (whether none of your expansions contain nonterminals)

8. Of course possibly more useful queries with a these kind of grammars are:

   • What are possible translations of this input?
   • What are possible inputs that translate to this output?
   • Is this grammar finite?

9. Why don't you use a prolog or lisp variant? Have a look at Clojure. It is a lisp variant that runs on JVM. It has a logic library, which I believe can be more useful than java.