Implements Chomsky's theory of narrow syntax as described in
Derivation of Phase.
(This page is meant to be a supplement to my CUNY 2012 conference
slides, see parent page here.)
This is the left-to-right incremental parser version of the direct
implementation given in the separate webpage here. The same set of examples
are used on both pages.
It may be useful to step through the derivations with two open
browser windows, one for the incremental parser and one for the direct
implementation. (In the snapshots below, "i" and "f" are used to
indicate incremental and final, respectively.)
(For a concise explanation of the linguistic theory implemented, see
the theory section (here) in the direct
implementation webpage (referenced above) as well as the examples
therein. The theory section below here discusses
parsing implementation issues only.)
Note: Javascript must be enabled for your browser to see
the parses and buttons that permit you to step through the derivations
for the various example sentences.
Example:
No of partial parses considered at each word:
Derivation steps:
Parser Implementation: One grammar, two systems
Chomsky's derivations are simulated using an implementation of
bottom-up Merge (external and internal) plus probe-goal search. The
precise sequence of steps in the derivations are given on the page
referenced earlier (here).
The same grammar used for the Merge implementation is re-purposed for
incremental left-to-right parsing here. The central idea being
explored here is that the parsing and generative procedures should
share as many components as possible.In particular, I'd like to
advance the hypothesis that architectural components needed by the
parser should be available to and be used by the generative procedure
(and vice versa).
First, the same covering grammar is deployed in both implementations
described here. However, instead of bottom-up Merge, the order of
execution is changed so that syntactic objects are gradually
instantiated in top-down fashion.
Architecturally, another major difference is that displacement is
computed in reverse, i.e. from left to right and downwards. (In the
Merge implementation, displacement is always to the left and upwards.)
This necessarily involves the use of organized memory (a buffer) as a
filler seeks its gap (possibly, multiple gaps).
That same buffer is therefore available to and may be repurposed by
the generative component. (See the discussion of the doubling
constituent approach to Binding theory. Paper is available on the
parent page here)
Moreover, probe-goal search is computed top-down incrementally instead
of waiting for syntactic objects to be completely instantiated. This
is not substantially different from the Merge implementation in
principle. However, the order of feature instantiation is
different. This results in minor timing issues when multiple agree
(single probe, multiple goals) is required.
The computation of displacement for parsing is less efficient than
bottom-up Merge. In particular, it may lead to extraneous local
nondeterminism in the computation of phrase structure that does not
exist in the case of (optimal) bottom-up Merge. (This is illustrated
graphically using the chart that accompanies the derivations
above. The length of the vertical bars at each word shows the number
of partial parses being considered as parsing progresses.)
Nevertheless, despite the aforementioned differences with respect to
the order of computation of syntactic objects and degree of optimality
with respect to the computation of displacement, both implementations
compute the exact same structures complete with probe-goal agreement
relations.
System implementation details: A single core definite clause
grammar (DCG) is used to specify the grammar. The grammar is exploited
in two separate ways. Lazy evaluation (via freeze) of recursive
descent parsing is used to simulate left to right processing. Simple
top-down parsing with bottom-up reporting instantiates the Merge
implementation.
to be continued...
Last modified: Sun Mar 11 04:40:37 MST 2012