SMT Parser

This work is supported in part by NSF Grant CISE-MSI: DP: IIS: Hybrid-Architecture Symbolic Parser with Neural Lexicon awarded to PI Prof. Hilton Alers-Valentin at the University of Puerto Rico Mayaguez.
The author of this computational implementation, Sandiway Fong, is a co-PI on the project, which makes use of this software.

The author is also grateful to Prof. Jason Ginsburg of Kyoto University, a long-time collaborator on computational modeling, see our joint work on the previous-generation Minimalist Machine here (on this website) and here (at Kyoto University). This new work owes a significant debt to that deep collaboration.

And to Prof. Masayuki Oishi at Tohoku Gakuin University, a co-author (on related work, hopefully to appear soon), for many critical yet gentle suggestions.

Finally, the author is deeply indebted to Prof. Noam Chomsky for much vital discussion of lingustic theory (that directly underpins this project).
Also to Prof. Daniel Seely of Michigan State University for organizing many group meetings on linguistic theory, meetings that provided invaluable background, and who spearheaded the effort for Merge and the Strong Minimalist Thesis (2023) (link).

There is a narrative due to Noam Chomsky that Nature unlocked recursive Merge with Language Organ-Specific Conditions (LSC) such as Theta Theory when modern humans, viz. homo sapiens, arrived on the scene a few hundred thousand years ago. Recursive Merge permitted modern humans to construct complex thought expressions not possible before, and the result was the subsequent explosion of symbolic and intellectual activity seen in the archaeological record and today. In terms of the evolutionary timescale, this was a very recent event, leaving no time to evolve more complex mechanisms other than the simplest possible form of Merge. All surviving humans since then share this same language/thought capability. Once evolved, simplest Merge applied to language is now part of our genetic endowment.

Language can (optionally) be externalized via different modalities, e.g. speech and sign. Although there has been no time to evolve other mechanisms or for Nature to tinker with (and potentially complexify) Merge, it is a fact that modern humans can effectively parse and interpret externalized language. How does that happen if essentially there is only Merge available? In other words, isn't it a mystery that we can parse externalized language at all?

Chomsky's Strong Minimalist Thesis implies that the simplest mechanism sufficient to encode structural dependencies, the so-called Basic Property of language, is utilized by the language organ. This is binary set merge, when recursively applied forms hierarchically structured expressions. Moreover, the SMT implies Nature makes optimal use of this new-found mechanism given the computational limits of biology. The operation of the language organ is not just maximally simple (for evolutionary plausibility), but must also be computationally efficient (as the brain is largely chemical-based).

This project explores Merge computation through formalization and computer simulation of the combinatorics of the theory. We show how a parser can operate using just Merge and the LSC Theta Theory to manage the computational complexity of Workspace from which parses are derived. The goal of the SMT Parser project is to suggest that this scenario is not only plausible, but can be made efficient enough without positing (evolutionarily implausible) additional parsing mechanisms. If so, unlocking Merge is all that was needed.

• Parses shown here are derived using the SMT Parser, and can be viewed by clicking on the button .
  A pop-up window should appear at the top-right of this webpage when you do that. To close the pop-up, hit the X.
  (Your browser must have Javascript enabled to draw the tree representation of the sets.)
• To see how they're obtained, click to see the Merge step-by-step derivations.
• Two sets of derivations are usually provided, a smaller one using heads from a hand-constructed LEX, the other using WordNet's morphy to access WordNet's large lexicon (from nltk in Python).
• The number of Initial Workspaces (WS) shown in each case depends on lexical lookup. e.g.in WordNet, dances is a verb (pres TNS, ? 3sg) and a noun (NUM pl), and narrow is an adjective and a verb (pres TNS, ? non-3sg, or nonfinite).
• See Read a set expression? for details of heads and their features.

• Black curly braces {...} are used to represent a set.
• Green curly braces {... } are used to represent sets created by FormSet
• Greyed out words are not pronounced (FormCopy has applied).
• Subscripting is used on heads to show head selection properties and other features.
  Some examples (from below):
  • arrive_? means the verbal root arrives takes a ?-relevant WS item as its complement.
  • v_arrive means the categorized v selects a phrase headed by arrive.
  • v_dance:?:pres means the categorized v selects a phrase headed by dance and a ?-relevant WS item as the 2nd Merge. It also has TNS feature pres (for present).
  • mechanic_the means the ?-relevant nominal mechanic has the determiner the as a feature, which will spellout at the left edge.
  • INFL_v:3sg means that inflection head INFL selects a phrase headed by v. In this case, it also hosts ?-features 3sg (3rd person singular). In later versions of the output produced by the parser, verbal ?-features will show up at spellout shifted to v instead.
  • C_Qleft(who) means the interrogative complementizer head C_Q will spell the wh-word who at its left edge.
  • C_relword(who) means the relative clause head C_rel spells out as the relative pronoun who.
  • C: declarative complementizer C has no features. We assume all variants of C select for a phrase headed by INFL.
  • v_{like:?:pres:box(who)} means the verbal categorizer v selects for a phrase headed by the verbal root like. v also selects a ?-relevant WS item for 2nd Merge. It has TNS pres. Finally, box contains the wh-?-relevant item who found in its c-command domain.

• Verb and noun inflectional decomposition also largely rely on WordNet morphy. See Princeton University's documentation morphy(7WN).
• Greyed out heads are not spelled out. They are captured by FormCopy, which operates on the structure after the final WS (single syntactic object).
• Heads have selectional properties, e.g. a verb root_? means root selects for a ?-relevant complement. The verbalizer v_root:? selects for root as complement and a ?-relevant specifier (2nd Merge).
• Following Chomsky GK, TNS (past/pres) is on v. ?-features may appear on INFL, but play no part in Merge, they are spelled out at EXT. In the current implementation, in the INFL-v-root sequence of heads, ?-features hop over to first v (given FormSet v membership). v has both ? and TNS. So v-Root is the classic morpho-sequence ? TNS Root at linearization. And then spelled, e.g. 3sg pres arrive spells as arrives, pst see as saw.
• See also the Help section at the top of each derivation.

Still in the debugging phase. Videos and written instructions to come. Software is free.

• Requires SWI-Prolog, a free download here. Make sure you're on at least version 9.2. How to tell? See here
• Requires some basic familiarity with typing shell and SWI-Prolog commands into a Terminal window.
  For example, type swipl to start SWI-Prolog.
  Once inside Prolog, ?- parse(Words,SO). to run the parser, where Words is a comma-separated list [...] of words and SO is the name of the variable for the syntactic object to be constructed.
  Then Prolog's semicolon (;) to find alternative parses. Or hit return to finish. See video.
  Note: commands prefixed by the prompt ?- are meant to be typed directly into SWI-Prolog (you don't type the prompt characters though).
  Completion (using TAB) is available in SWI-Prolog. All other commands are typed to the shell.
  You don't need to know Python, i.e. there is no need to type anything to Python (except for the nltk WordNet install, see below).
  Remember all commands require you to hit enter to submit.
  (Sorry, a direct GUI interface is planned, but hasn't been built yet.)
• Uses the Janus library (reference), no need to download - bundled with SWI-Prolog from version 9.2, to run an embedded Python interpreter when code is loaded.
  Which Python installation is embedded? Here's how to find out, link
• Uses nltk WordNet (reference) for the non-handbuilt English lexicon. WordNet is free.
  Also uses morphy ( reference) for English stemming and spellout duties (even if you choose not to use the WordNet lexicon).
• nltk (Natural Langugage Toolkit) is free. Install nltk (link) and nltk_data (link) in the _embedded_ Python linked via the Janus library.
  Note: you may grumble that you already have nltk installed for Python. However, your Python install may not be the same Python that Janus is linked to! So you probably need to install nltk (again) for this particular Python.
  This versioning stupidity is not my fault.
  Installation instructions here.
• After confirming the above steps have been completed, download my code here.
• Note: you can add missing words to the handbuilt LEX either by editing lex.pl (permanent) or by command addWord(Word,Category) at the Terminal (temporary). See example video.
• Requires a browser with Javascript enabled (if you want to see the syntax trees) via the ?- report. command.
• Runs on macOS, Linux and Windows. Currently, not recommended directly on Windows, use WSL2 (a free install) inside Windows. (This is due to source code UTF-8 issues that I have to look at when I have time). Ubuntu Linux issues and fixes documented here

• LEX: How to add words and run parses. PDF (Updated: Sep 3rd 2024)