Presentation

Introduction

Abstract categorial grammars (ACGs) were introduced by de Groote (2001)⊕ de Groote, Philippe. 2001. “Towards abstract categorial grammars.” In Association for Computational Linguistics, 39th Annual Meeting and 10th Conference of the European Chapter, 148–55. Toulouse, France, France. doi: 10.3115/1073012.1073045. . They derive from type-theoretic grammars in the tradition of (Lambek 1958; Curry 1961)⊕ Lambek, Joachim. 1958. “The Mathematics of Sentence Structure.” American Mathematical Monthly 65 (3): 154–70. doi: 10.2307/2310058. ⊕ Curry, Haskell Brooks. 1961. “Some Logical Aspects of Grammatical Structure.” In Structure of Language and Its Mathematical Aspects: Proceedings of the Twelfth Symposium in Applied Mathematics, edited by Roman Jakobson, 56–68. American Mathematical Society. http://www.ams.org/books/psapm/012/. , and (Montague 1973)⊕ Montague, Richard. 1973. “The Proper Treatment of Quantification in Ordinary English.” In Approaches to Natural Language: Proceedings of the 1970 Stanford Workshop on Grammar and Semantics, edited by Jaakko Hintikka, Julius Moravcsik, and Patrick Suppes, 221–42. Dordrecht: Springer Netherlands. doi: 10.1007/978-94-010-2506-5_10. . They can be considered as a framework in which several grammatical formalisms may be encoded. The definition of an ACG is based on a small set of mathematical primitives from type-theory, λ-calculus, and linear logic. These primitives combine via simple composition rules, offering ACGs a good flexibility. In particular, ACGs generate languages of linear λ-terms, which generalize both string and tree languages.

But ACGs are not restricted to languages of λ-terms encoding strings or trees. They can express logic-based semantic representation languages. And moving from one kind to another kind of language is realized by composing ACGs.

An ACG actually defines two languages: an abstract one and an object one which are defined on an abstract and an object vocabulary, respectively. The former can generally be seen as the set of admissible parse structures, while the latter can be seen as the set of corresponding surface structures in a broad sense: strings, for instance, but also logical formulas.

The relation between the abstract and the object language is defined by a morphism, called a lexicon, that interprets abstract structures into object ones.

Composition of ACGs happens:

• either when the object vocabulary of an ACG \mathcal{G}_1 also is the abstract vocabulary of some ACG \mathcal{G}_2,
• or when two ACGs \mathcal{G}_1 and \mathcal{G}_2 share the same abstract vocabulary.

For instance, the next figure shows the first composition mode for \mathcal{G}_{\text{derived trees}} and \mathcal{G}_{\text{yield}}, while the second composition mode occurs with \mathcal{G}_{\text{derived trees}} and \mathcal{G}_{\text{sem}}. This architecture is used by Pogodalla (2017)⊕ Pogodalla, Sylvain. 2017. “A syntax-semantics interface for Tree-Adjoining Grammars through Abstract Categorial Grammars.” Journal of Language Modelling 5 (3). Institute of Computer Science, Polish Academy of Sciences, Poland: 527–605. doi: 10.15398/jlm.v5i3.193. to encode Tree-Adjoinging Grammars (Joshi, Levy, and Takahashi 1975; Joshi and Schabes 1997)⊕ Joshi, Aravind K., Leon S. Levy, and Masako Takahashi. 1975. “Tree Adjunct Grammars.” Journal of Computer and System Sciences 10 (1): 136–63. doi: 10.1016/S0022-0000(75)80019-5. ⊕ Joshi, Aravind K., and Yves Schabes. 1997. “Tree-Adjoining Grammars.” In Handbook of Formal Languages, edited by Grzegorz Rozenberg and Arto K. Salomaa. Vol. 3. Springer. doi: 10.1007/978-3-642-59126-6_2. .

Parsing with ACGs

ACG Hierarchy and Expressive Power

Two scales are useful to characterize the expressive power of ACGs.

• The order of an ACG is the maximum order of the type of its constants.
• The complexity of an ACG is the maximum order of the interpretation of its atomic types.

\textit{ACG}_{(n,m)} is the class of ACGs whose order is less than n and whose complexity is less than m.

The class of second-order ACGs is of particular interest because of its polynomial parsing property (Salvati 2005)⊕ Salvati, Sylvain. 2005. “Matching problem and parsing problem for abstract categorial grammars.” Theses, Institut National Polytechnique de Lorraine. https://hal.univ-lorraine.fr/tel-01750002. . When considering strings as the object language, the generated languages coincide with multiple context-free languages (Salvati 2006)⊕ Salvati, Sylvain. 2006. “Encoding second order string ACG with Deterministic Tree Walking Transducers.” In The 11th conference on Formal Grammar, edited by Shuly Wintner, 143–56. FG Online Proceedings. Malaga, Spain: Paola Monachesi; Gerald Penn; Giorgio Satta; Shuly Wintner; CSLI Publications. https://hal.inria.fr/inria-00333886. . When considering trees, the generated languages coincide with the tree languages generated by hyperedge replacement grammars (Kanazawa 2010)⊕ Kanazawa, Makoto. 2010. “Second-Order Abstract Categorial Grammars as Hyperedge Replacement Grammars.” Journal of Logic, Language and Information 19 (2): 137–61. doi: 10.1007/s10849-009-9109-6. . A further refinement on the ACG hierarchy provides a fine-grained correspondence with regular (string or tree) languages, context-free string and linear context-free tree languages, or well-nested multiple context-free languages (string), in particular tree-adjoining languages. The following table sums up some of the formal properties of second-order ACGs (de Groote and Pogodalla 2004; Kanazawa and Salvati 2007)⊕ de Groote, Philippe, and Sylvain Pogodalla. 2004. “On the expressive power of Abstract Categorial Grammars: Representing context-free formalisms.” Journal of Logic, Language and Information 13 (4). Springer Verlag: 421–38. doi: 10.1007/s10849-004-2114-x. ⊕ Kanazawa, Makoto, and Sylvain Salvati. 2007. “Generating control languages with Abstract Categorial Grammars.” In Formal Grammar FG 2007. Ireland: Laura Kallmeyer and Paola Monachesi and Gerald Penn. https://hal.archives-ouvertes.fr/hal-00306222. .

Reversibility

A crucial property of ACGs is that polynomial parsing does not apply only to string or tree generating grammars, but to any second-order ACG, such as the ones that generate first-order or higher-order logical formulas. Consequently, any second-order ACG generating a logical formula can be used to parse a logical formula and provide the admissible parse structure (if any) that generates this logical formula. The ACG framework is inherently reversible (Dymetman 1994)⊕ Dymetman, Marc. 1994. “Inherently Reversible Grammars.” In Reversible Grammars in Natural Language Processing, edited by Tomek Strzalkowski, 33–57. Kluwer Academic Publishers. doi: 10.1007/978-1-4615-2722-0_2. , and parsing and generation with second-order ACGs are performed in polynomial time.

For second-order ACGs, parsing algorithms and optimization techniques are grounded on well established fields such as type-theory and Datalog. Kanazawa (2007)⊕ Kanazawa, Makoto. 2007. “Parsing and Generation as Datalog Queries.” In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics (ACL 2007), 176–83. Prague, Czech Republic: Association for Computational Linguistics. https://aclanthology.org/P07-1023. showed how parsing of second-order ACGs reduces to Datalog querying, offering a general method for getting efficient tabular parsing algorithms (Kanazawa 2017)⊕ Kanazawa, Makoto. 2017. “Parsing and Generation as Datalog Query Evaluation.” IfCoLog Journal of Logics and Their Applications 4 (4): 1103–1211. http://www.collegepublications.co.uk/downloads/ifcolog00013.pdf#page=307. . This parsing method applies whatever the object language: representing strings, trees, and also any kind of (almost linear) \lambda-terms. When the object language consists of logical formulas, the latter can then be parsed as well, and the resulting parse structures can further be interpreted (e.g., as strings) to implement surface realization.

Software

ACGs can be used and tested using the ACG toolkit being developed by the Sémagramme team. The README.md provides a quick start explanation, and the INSTALL.md file explains how to install it (we recommand using opam). A full user documentation is also available.

The ACG toolkit comes with two binaries. The first one, acgc, compiles grammars declaration (as exemplified in the next code block).

signature strings =
    s : type ;
    string = s → s : type;
    infix + = λ⁰ g f x.g(f x) : string → string → string;
    (*  string : type;
       infix + : string → string → string; *)
    epsilon = λ⁰ x.x : string;
    a, b, c : string;
end

signature CFG1 =
    S : type;
    r1 : S → S → S;
    r2 : S;
end

(* L1 is the Dyck language of well-nested brackets *)
lexicon L1 (CFG1): strings =
    S := string;
    r1 := λ⁰ s s'.a+s+b+s';
    r2 := epsilon
end

$acg
ACGtk> "a + b + a + a + b + b : string" | parse lexicon=L1 type=S "a + b + a + a + b + b : string"
Parsing time:               285μs
Parse forest building time: 20.4μs
Term (depth = 4, size = 7): r1 r2 (r1 (r1 r2 r2) r2) : S

ACG Bibliography

Here is a list (sorted by descending publication date) of ACG related publications (by our group or not) we are aware of. Please let us know if you think some relevant publication is missing.

Related work

ACGs were independently introduced but relate to several frameworks:

• Grammatical Framework, developped by Aarne Ranta ((2004)⊕ Ranta, Aarne. 2004. “Grammatical Framework: A Type-Theoretical Grammar Formalism.” Journal of Functional Programming 14 (2): 145–89. doi: 10.1017/S0956796803004738. and subsequent work).
• Lambda Grammars, proposed by Reinhard Muskens (Muskens 2001, 2003)⊕ Muskens, Reinhard. 2001. “Lambda Grammars and the Syntax-Semantics Interface.” In Proceedings of the Thirteenth Amsterdam Colloquium, edited by Robert van Rooy and Martin Stokhof, 150–55. Amsterdam. https://let.uvt.nl/general/people/rmuskens/pubs/amscoll.pdf. ⊕ Muskens, Reinhard. 2003. “Lambdas, Language, and Logic.” In Resource Sensitivity in Binding and Anaphora, edited by Geert-Jan Kruijff and Richard T. Oehrle, 23–54. Studies in Linguistics and Philosophy. Kluwer. doi: 10.1007/978-94-010-0037-6_2. .
• Interpreted Regular Tree Grammars, proposed by Koller and Kuhlmann (2011)⊕ Koller, Alexander, and Marco Kuhlmann. 2011. “A Generalized View on Parsing and Translation.” In Proceedings of the 12th International Conference on Parsing Technologies, 2–13. Dublin, Ireland: Association for Computational Linguistics. https://aclanthology.org/W11-2902. .

Contact

• Philippe de Groote
• Sylvain Pogodalla