扩展同步文法

Question

背景：

同步文法类似于两个上下文无关的语法，并行连接。它用于翻译。例如，这里有一个小的同步语法，可用于在自然语言文本和语义表示之间进行翻译：

== {谓词} == *i提供{名词}。您会接受{noun}吗?/ QUERY({noun}) *我不提供任何公司的汽车。/提供(租赁的Car=Without租赁汽车) == {noun} == *{noun}%养老金/养老金{ NIS /Salary={NIS}**公司汽车/租赁Car=With租赁汽车的工资

标题({谓词}，{noun})是语法的非结尾。在每个非终端下面是由这个非终端启用的翻译列表。

从非终端{谓词}开始，我们可以根据上面的语法创建以下7个翻译：

我不提供公司车。=> 租赁的Car=Without租赁汽车(提供)我提供一辆公司的车。=> 租赁的Car=With租赁汽车(提供)您会接受{ NIS }的薪资吗？=> Salary={number}查询 I提供{number} %的养老金。=> 养恤金Fund={number}%提供 I提供{ NIS的薪资。=> Salary={number}报价你会接受一辆公司的汽车吗？=> 租赁的Car=With租赁汽车(查询)你会接受{number} %的养老金吗？=> 养老金Fund={number}%查询

翻译是多到多的(即每个源字符串可以有多个翻译，反之亦然)。因此，特定非终端的每一组翻译都由一个multimap表示(我们使用一个类ValueSetMap<String, String>来表示一个多到多的映射)。一个完整的语法由这样一个多任务映射表示：Map<String, ValueSetMap<String, String>>。它将一个非终端映射到它的多个翻译。

下面是我编写的一些Java代码，用于将语法扩展为一个平面的多个翻译。它适用于上述示例和一些更复杂的示例，但我不知道它是否真的涵盖了所有情况。

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应该是IllegalArgumentException。考虑只返回空的展开集合。它极大地提高了代码的可组合性。考虑使无效状态无法表示。(不过，在这种情况下，我想不出一种琐碎的方法。)
2. 在下面的语句中，如果source和target中的任何一个包含nonterminal，则将递归展开翻译。虽然注释说，如果source包含nonterminal //源包含非终端，则转换将被扩展--如果(source.contains(非终端)\x-target.contains(非终端)){误导性注释通常是错误算法的标志，则递归地展开它。此外，在给出的例子中，我们发现source包含一个nonterminal当且仅当target也包含nonterminal，这可能是语法的一个约束。
3. 此外，source.contains(nonterminal)建议您隐式地假定nonterminals，即以"{“、"}”作为grammarMap开始和结尾的键。而非终端名称不包含"{}"，而且可能有更多的约束。考虑键：noun, pronoun, {pronoun}, {{noun}}。看到迫在眉睫的麻烦了吗？在创建grammar时，应该验证这些键。而一些javadoc等注释如果不够的话也是有帮助的。即使您是这段代码的唯一用户，您也会很快忘记这些隐含的假设。
4. 根据上述建议，考虑使用抽象数据类型而不是无意义的原语类型(java.util.Collection、String等)。这样您的多级循环读取更多类似于for (翻译:平移){grammar.substituteOneLevel(转换)} // in grammar.substituteOneLevel(翻译) for (非终端非终端: translation.getNonterminals()) {表示(展开:grammar.getExpansions(非终端)){grammar.getExpansions(非终端))；}或类似的.除了通过使用来自您领域的语言(名词和动词)来提高您的业务(学术)逻辑的可读性和清晰度之外，您还可以不允许grammar让expansions包含nonterminals，即grammar本身不包含。(你的NullPointerException.)
5. 就效率而言，我的反对意见之一是: for (字符串非终端:非终端){ //依次展开每个非终端，为什么要扩展当前翻译中没有包含的终端？
6. 对于固定数目的步骤，扩展一个非终端似乎不太有用。你的用例是什么？您有一个正在运行的测试用例，它演示了语法的设置以及它的使用方式吗？
7. 即使将非终端扩展到固定数目的步骤是您想要的，您也可能需要一些指示，说明您是否已经用尽所有可能的扩展。(您的扩展中是否没有一个包含非终端)
8. 当然，使用这类语法的可能更有用的查询是：
   • 这个输入的可能翻译是什么？
   • 哪些可能的输入可以转化为这个输出？
   • 这语法是有限的吗？

9. 为什么不使用prolog或lisp变体呢？看看克洛尔。它是一个在JVM上运行的lisp变体。它有一个逻辑库，我相信它比java更有用。