Elamur Research⌕
☰
home / papers / 1997 / An Abstract Machine for Unification Grammars

An Abstract Machine for Unification Grammars

Paper · 1997 · Shuly Wintner

Summary

This 1997 Technion doctoral thesis by Shuly (Shalom) Wintner, supervised by Nissim Francez, asks how to run unification-based grammars such as HPSG efficiently without giving up formal rigour. It first builds a theory of parsing over typed feature structures (TFS). The theory covers subsumption and its well-foundedness, abstract feature structures, unification, a linear encoding of structures and multi-rooted structures for representing rules. Parsing is then defined as an operational semantics and proved sound, complete and terminating.

On this basis the author designs AMALIA, an abstract machine for linguistic applications. Grammars and type specifications are compiled into machine instructions, as abstract machines do for logic programming. The thesis also describes an implementation. As an application, it develops an HPSG fragment for Hebrew, focusing on noun phrases, the definite article and noun-noun constructs.

The work matters because it links a declarative grammar formalism, a provably correct parsing model and a compiled execution engine.

Key points

  • The theory section gives proofs of soundness, completeness and termination for parsing, plus a correctness argument for the subsumption check.
  • AMALIA's input language specifies a type hierarchy together with grammar rules. Both are compiled: the type hierarchy separately, and rules into machine code.
  • The unification engine contrasts feature structures with first-order terms. It specifies a memory layout for TFSs and a step that flattens them.
  • The listed optimizations and extensions are:
    • lazy evaluation of feature structures,
    • partial descriptions,
    • empty categories,
    • lexical ambiguity,
    • functional attachments.
  • The Hebrew HPSG grammar covers phrase-structure schemata, the internal structure of NPs, the status of the definite article and noun-noun (construct) phrases. The full grammar and the instruction list are given in appendices.

Interesting ideas

  • I1. Treating parsing as an operational semantics makes formal proofs of soundness, completeness and termination possible, rather than testing correctness only on examples.
  • I2. Compiling the type hierarchy ahead of time turns type compatibility checks into cheap lookups instead of searches at run time.
  • I3. Encoding nested feature structures in a flat, linear form makes them simpler to store, copy and unify inside a machine.
  • I4. Lazy evaluation of feature structures defers copying or expansion until a value is actually needed, which saves work on paths that fail.
  • I5. Lexical ambiguity is handled inside the parsing machine itself, rather than being resolved beforehand.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

  • I1 (tree): The parser's transition system could be stated formally, so every parse step has a defined meaning and the explainability claims rest on provable properties.
  • I2 (world): The WordNet/FrameNet/Wikidata ontology could be precompiled into a table of compatible or joined types, so entity-type checks in the text world are fast and deterministic.
  • I3 (frames): Frames and role fillers could be kept as flat indexed records, so frame unification and its trace are compact and easy to inspect.
  • I4 (world): Entity states and holdings could be materialized on demand when a question touches them, rather than fully built for every sentence.
  • I5 (tokens): The tagger could pass several candidate analyses for ambiguous words downstream and let later constraints choose among them, keeping the discarded options visible for explanation.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Technion – Israel Institute of TechnologyHaifa · Israel49 works · 5,306 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputational Theory and Mathematics · 252 works

🧭 Topics 1Research subjects and languages the work is about.Syntax & grammar formalisms · 214 works

Cite

Cite as Shuly Wintner. 1997. An Abstract Machine for Unification Grammars. arXiv:cmp-lg/9709013.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.cmp-lg/9709013 · arXiv cmp-lg/9709013

@misc{wintner1997abstract,
  title = {{An Abstract Machine for Unification Grammars}},
  author = {Shuly Wintner},
  year = {1997},
  doi = {10.48550/arxiv.cmp-lg/9709013},
  eprint = {cmp-lg/9709013},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.cmp-lg/9709013}
}

References

88 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Aho, Alfred V. and Jeffrey D. Ullman. 1972. The Theory of Parsing, Translation and Compiling, volume 1: Parsing. Prentice-Hall, Inc., Englewood Cliffs, N.J. find
  2. Aı̈t-Kaci, Hassan. 1991. Warren’s Abstract Machine: A Tutorial Reconstruction. Logic Programming. The MIT Press, Cambridge, Massachusetts. find
  3. Aı̈t-Kaci, Hassan, Robert Boyer, Patrick Lincoln, and Roger Nasr. 1989. Efficient implementation of lattice operations. ACM Transactions on Programming Languages and Systems, 11(1):115–146, January. ↗
  4. Aı̈t-Kaci, Hassan and Roberto Di Cosmo. 1993. Compiling order-sorted feature term unification. PRL Technical Note 7, Digital Paris Research Laboratory, December. ↗
  5. Aı̈t-Kaci, Hassan and Andreas Podelski. 1993. Towards a meaning of LIFE. Journal of Logic Programming, 16(3-4):195–234, July-August. ↗
  6. Barton, G. Edward, Robert C. Berwick, and Eric Sven Ristad. 1987. Computational Complexity and Natural Language. Computational Models of Cognition and Perception. MIT Press, Cambridge, Mass. find
  7. Beierle, Christoph and Gregor Meyer. 1994. Run-time type computations in the Warren abstract machine. Journal of Logic Programming, 18:123–148. ↗
  8. Bentur, Esther, Aviella Angel, and Danit Segev. 1992. Computerized analysis of Hebrew words. Hebrew Linguistics, 36:33–38, December. (in Hebrew). find
  9. Bird, Steven. 1990. Constraint-Based Phonology. Ph.D. thesis, University of Edinburgh. find
  10. Bird, Steven. 1992. Finite state phonology in HPSG. In Proceedings of COLING-92, pages 74–80. find
  11. Calcagno, Mike, Andreas Kathol, and Carl Pollard. 1993. A bibliography of books, theses and articles in or on HPSG. Unpublished manuscript, August. find
  12. Carpenter, Bob. 1991. Typed feature structures: A generalization of first-order terms. In Vijai Saraswat and Ueda Kazunori, editors, Logic Programming – Proceedings of the 1991 International Symposium, pages 187–201, Cambridge, MA. MIT Press. find
  13. Carpenter, Bob. 1992a. ALE – the attribute logic engine: User’s guide. Technical report, Laboratory for Computational Linguistics, Philosophy Department, Carnegie Mellon University, Pittsburgh, PA 15213, December. find
  14. Carpenter, Bob. 1992b. The Logic of Typed Feature Structures. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press. ↗
  15. Chayen, M. J. and Z. Dror. 1976. Introduction to Hebrew Transformational Grammar. University Publishing Projects Ltd., Jerusalem. (in Hebrew). find
  16. Choueka, Yaacov and Yoni Ne’eman. 1995. ”Nakdan-T”, a text vocalizer for modern Hebrew. In Proceedings of the Fourth Bar-Ilan Symposium on Foundations of Artificial Intelligence, June. find
  17. Cohen, Daniel. 1984. Mechanical Syntactic Analysis of a Hebrew Sentence. Ph.D. thesis, Hebrew University of Jerusalem. (In Hebrew). find
  18. Dörre, Jochen and Michael Dorna. 1993. CUF – a formalism for linguistic knowledge representation. In Jochen Dörre, editor, Computatioal Aspects of Constrained-Based Linguistic Description I, DYANA-2 delivarable R1.2.A, ILLC/Department of Philosophy, University of Amsterdam, Nieuwe Doelenstraat 15, NL-1012 CP Amsterdam, August. find
  19. Emerson, E. Allen. 1983. Alternative semantics for temporal logics. Theoretical Computer Science, 26:121–130. ↗
  20. Erbach, Gregor. 1994. ProFIT: Prolog with features, inheritance and templates. CLAUS Report 42, Computerlinguistik, Universität des Saarlandes, D-66041, Saarbrücken, Germany, July. ↗
  21. Franz, Alex. 1990. A parser for HPSG. Report CMU-LCL-90-3, Laboratory for Computational Linguistics, Department of Philosophy, Carnegie Mellon University, Pittsburgh, PA 15213, July. find
  22. Gazdar, G. E., E. Klein, K. Pullum, and Ivan A. Sag. 1985. Generalized Phrase Structure Grammar. Harvard University Press, Cambridge, Mass. find
  23. Gazdar, Gerald and Chris Mellish. 1989. Natural Language Processing in PROLOG. Addison-Wesley. find
  24. Gerdemann, Dale. 1993. Troll: Type resolution system – fundamental principles and user’s guide. Unpublished manuscript, September. find
  25. Gerdemann, Dale and Erhard W. Hinrichs. 1988. Unicorn: A unification parser for attribute-value grammars. Studies in the Linguistic Sciences, 18(2):41– 86. find
  26. Glinert, Lewis. 1989. The Grammar of Modern Hebrew. Cambridge University Press, Cambridge. find
  27. Götz, Thilo W. 1994. A normal form for types feature structures. Master’s thesis, Eberhard-Karls Universität, Tübingen, March. find
  28. Haas, Andrew. 1989. A parsing algorithm for unification grammar. Computational Linguistics, 15(4):219–232, December. find
  29. Hermenegildo, Manuel V. 1986. An Abstract Machine Based Execution Model for Computer Architecture Design and Efficient Implementation of Logic Programs in Parallel. Ph.D. thesis, Department of Computer Science, The University of Texas at Austin, Austin, Texas 78712-1188, August. ↗
  30. Johnson, Mark. 1988. Attribute-Value Logic and the Theory of Grammar, volume 16 of CSLI Lecture Notes. CSLI, Stanford, California. find
  31. Kaplan, R. and J. Bresnan. 1982. Lexical functional grammar: A formal system for grammatical representation. In J. Bresnan, editor, The Mental Representation of Grammatical Relations. MIT Press, Cambridge, Mass., pages 173–281. find
  32. Kaplan, Ronald M. 1973. A general syntactic processor. In Randall Rustin, editor, Natural Language Processing, number 8 in Courant Computer Science Symposium. Algorithmics Press, P.O. Box 97, New York, N.Y. 10012, pages 194–241. find
  33. Kasper, Robert T. and William B. Rounds. 1986. A logical semantics for feature structures. In Proceedings of the 24th Annual Meeting of the Association for Computational Linguistics, pages 257–265. find
  34. Kay, Martin. 1973. The MIND system. In Randall Rustin, editor, Natural Language Processing, number 8 in Courant Computer Science Symposium. Algorithmics Press, P.O. Box 97, New York, N.Y. 10012, pages 155–188. find
  35. Kay, Martin. 1983. Unification grammar. Technical report, Xerox Palo Alto Research Center, Palo Alto, CA. find
  36. King, Paul. 1989. A Logical Formalism for HPSG. Doctoral dissertation, University of Manchester, Manchester, UK. find
  37. King, Paul. 1992. Unification grammars and descriptive formalisms: Lecture notes for a graduate level course. Unpublished manuscript. find
  38. Kodric̆, Sandi, Fred Popowich, and Carl Vogel. 1992. The HPSG-PL system. CSS-IS TR 92-05, School of Computing Science, Centre for Systems Science, Simon Fraser University, Burnaby, B. C. Canada V5A 1S6, Jun. find
  39. Kolliakou, Dimitra. 1996. Definiteness and the make-up of nominal categories. In Claire Grover and Enric Vallduvı́, editors, Studies in HPSG, volume 12 of Edinburgh Working Papers in Cognitive Science. Centre for Cognitive Science, The University of Edinburgh, chapter 4, pages 121–164. find
  40. Kursawe, Peter. 1987. How to invent a Prolog machine. New Generation Computing, 5:97–114. ↗
  41. Landin, P. J. 1964. The mechanical evaluation of expressions. The Computer Journal, 6(4):308–320. ↗
  42. Lloyd, John Wylie. 1987. Foundations of Logic Programming. Springer series in Symbolic Computation – Artificial Intelligence. Springer, Berlin, second edition. ↗
  43. Manaster-Ramer, Alexis. 1987. Mathematics of Language. John Benjamins Publishing Company, Amsterdam/Philadelphia. find
  44. Moshier, Drew. 1988. Extensions to Unification Grammars for the Description of Programming Languages. Ph.D. thesis, University of Michigan, Ann Arbor. find
  45. Moshier, Drew M. and William C. Rounds. 1987. A logic for partially specified data structures. In 14th Annual ACM Symposium on Principles of Programming Languages, pages 156–167, January. find
  46. Müller, Stefan. 1996. HPSG literature. Available as an electronic document at http://cl-www.dfki.uni-sb.de/HPSG/. ↗
  47. Nerbonne, John. 1992. Feature-based lexicons: An example and a comparison to DATR. Research Report RR-92-04, Deutsches Forschungszentrum für Künstliche Intelligenz GmbH, February. ↗
  48. Nerbonne, John, Klaus Netter, and Carl Pollard, editors. 1994. German in Head-Driven Phrase Structure Grammar. Number 46 in CSLI lecture notes. CSLI, Stanford, Ca. find
  49. Netter, Klaus. 1994. Towards a theory of functional heads. In John Nerbonne, Klaus Netter, and Carl Pollard, editors, German in Head-Driven Phrase Structure Grammar, volume 46 of CSLI Lecture Notes. CSLI, Stanford, CA, chapter 9, pages 297–340. find
  50. Nilsson, Ulf. 1993. Towards a methodology for the design of abstract machines for logic programming languages. Journal of Logic Programming, 16:163–189. ↗
  51. Nirenburg, Sergei and Yosef Ben-Asher. 1984. HUHU – the Hebrew University Hebrew understander. Computer Languages, 9(3/4). ↗
  52. Ornan, Uzzi. 1964. Noun Phrases in Modern Hebrew Literature. Ph.D. thesis, Hebrew University, Jerusalem. (in Hebrew). find
  53. Ornan, Uzzi. 1979. The Simple Sentence. Academon, Jerusalem, Israel. (in Hebrew). find
  54. Ornan, Uzzi. 1986. Phonemic script: A central vehicle for processing natural language – the case of Hebrew. Technical Report 88.181, IBM Research Center, Haifa, Israel. find
  55. Ornan, Uzzi. 1994. Basic concepts in ”romanization” of scripts. Technical Report LCL 94-5, Laboratory for Computational Linguistics, Technion, Haifa, Israel, March. find
  56. Ornan, Uzzi and Michael Katz. 1995. A new program for Hebrew index based on the Phonemic Script. Technical Report LCL 94-7, Laboratory for Computational Linguistics, Technion, Haifa, Israel, July. find
  57. Ousterhout, John K. 1994. Tcl and the Tk Toolkit. Addison-Wesley Professional Computing Series. Addison-Wesley. find
  58. Penn, Gerald. 1993. A comprehensive HPSG grammar in ALE. Technical report, Laboratory for Computational Linguistics, Carnegie Mellon University, Pittsburgh, PA. find
  59. Pereira, Fernando C. N. and David H. D. Warren. 1983. Parsing as deduction. In Proceedings of the 21st Annual Meeting of the Association for Computational Linguistics, pages 137–144, June. find
  60. Pollard, Carl and Ivan A. Sag. 1987. Information Based Syntax and Semantics. Number 13 in CSLI Lecture Notes. CSLI. find
  61. Pollard, Carl and Ivan A. Sag. 1994. Head-Driven Phrase Structure Grammar. University of Chicago Press and CSLI Publications. find
  62. Pollard, Carl J. and M. Drew Moshier. 1990. Unifying partial descriptions of sets. In Philip P. Hanson, editor, Information, Language and Cognition, volume 1 of Vancouver Studies in Cognitive Science. University of British Columbia Press, Vancouver 1990, chapter 10, pages 285–322. find
  63. Popowich, Fred and Carl Vogel. 1991. A logic-based implementation of head-driven phrase structure grammar. In Charles Grant Brown and Gregers Koch, editors, Natural Language Understanding and Logic Programming, III, pages 227–245. Elsevier Science Publishers (North-Holland). find
  64. Prudian, Derek and Carl Pollard. 1985. Parsing head-driven phrase structure grammar. In Proceedings of the 23rd Annual Meeting of the Association for Computational Linguistics, Chicago, IL. University of Chicago. find
  65. Russell, Dale W. 1993. Language Acquisition in a Unification-Based Grammar Processing System Using a Real-World Knowledge Base. Ph.D. thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, July. find
  66. Russinoff, David M. 1992. A verified Prolog compiler for the Warren Abstract Machine. Journal of Logic Programming, 13:367–412. ↗
  67. Sag, Ivan A. and Janet Dean Fodor. 1994. Extraction without traces. In Raul Aranovich, William Byrne, Susanne Preuss, and Martha Senturia, editors, Proceedings of the Thirteenth West Coast Conference on Formal Linguistics, Stanford. CSLI Publications/SLA. find
  68. Samuelsson, Christer. 1995. An efficient algorithm for surface generation. In Proceedings of the International Joint Conference on Artificial Intelligence. ↗
  69. Schumann, Johann M. Ph. 1991. Efficient Theorem Provers based on an Abstract Machine. Ph.D. thesis, Technische Universität München, Institut Für Informatik. find
  70. Shieber, Stuart M. 1985. Using restriction to extend parsing algorithms for complex-feature-based formalisms. In Proceedings of the 23rd Annual Meeting of the ACL, pages 145– 152, July. find
  71. Shieber, Stuart M. 1986. An Introduction to Unification Based Approaches to Grammar. CSLI Lecture Notes. CSLI. find
  72. Shieber, Stuart M. 1992. Constraint-Based Grammar Formalisms. MIT Press, Cambridge, Mass. ↗
  73. Shieber, Stuart M., Yves Schabes, and Fernando C. N. Pereira. 1994. Principles and implementation of deductive parsing. Technical Report TR-11-94, Center for Research in Computing Technology, Division of Applied Sciences, Harvard University, April. ↗
  74. Sikkel, Klaas. 1993. Parsing Schemata. Klaas Sikkel, Enschede. find
  75. Smolka, Gert. 1988. A feature logic with subsorts. LILOG Report 33, IBM Deutschland, May. find
  76. Smolka, Gert and Ralf Treinen. 1994. Records for logic programming. Journal of Logic Programming, 18:229–258. ↗
  77. Swift, Terrance and David Warren. 1993. Compiling OLDT evaluation: Background and overview. Technical Report 92/04, SUNY Stony Brook, March. find
  78. Warren, David H. D. 1983. An abstract Prolog instruction set. Technical Note 309, SRI International, Menlo Park, CA., August. find
  79. Warshall, Stephen. 1962. A theorem on boolean matrices. Journal of the ACM, 9(1):11–12, January. ↗
  80. Wintner, Shuly. 1991. Syntactic analysis of Hebrew sentences. Master’s thesis, Technion, Israel Institute of Technology, Haifa, Israel, July. (In Hebrew, abstract in English). find
  81. Wintner, Shuly. 1992. Syntactic analysis of Hebrew sentences using PATR. In Uzzi Ornan, Gideon Ariely, and Edit Doron, editors, Hebrew Computational Linguistics. Ministry of Science and Technology, chapter 4, pages 105–115. (In Hebrew). find
  82. Wintner, Shuly and Nissim Francez. 1995a. An abstract machine for typed feature structures. In Proceedings of the 5th Workshop on Natural Language Understanding and Logic Programming, pages 205–220, Lisbon, May. find
  83. Wintner, Shuly and Nissim Francez. 1995b. Parsing with typed feature structures. In Proceedings of the Fourth International Workshop on Parsing Technologies, pages 273–287, Prague, September. ↗
  84. Wintner, Shuly, Evgeniy Gabrilovich, and Nissim Francez, 1997. AMALIA – Abstract MAchine for LIinguistic Applications – User’s Guide. Laboratory for Computational Linguistics, Computer Science Deparmtent, Technion, Israel Institute of Technology, 32000 Haifa, Israel, January. find
  85. Wintner, Shuly and Uzzi Ornan. 1991. Syntactic analysis of Hebrew sentences. In Proceedings of the 8th Israeli Symposium on Artificial Intelligence and Computer Vision, pages 201–230. Information Processing Association of Israel, December. find
  86. Wintner, Shuly and Uzzi Ornan. 1996. Syntactic analysis of hebrew sentences. Natural Language Engineering, 1(3):261–288. ↗
  87. Yizhar, Dana. 1993. Computational grammar for Hebrew noun phrases. Master’s thesis, Computer Science Department, Hebrew University, Jerusalem, Israel, June. (In Hebrew). find
  88. Zajac, Rémi. 1992. Inheritance and constraint-based grammar formalisms. Computational Linguistics, 18(2):159–182. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wintner-1997-abstract-machine-unification-grammars/