In this seminar, I'm trying to teach my student some computational semantics using van Eijck and Unger's book.
Solution to part 1. The following is a bottom-up version:
transS
in Section 9.8 (Adding Semantics) by eliminating calls to bInLF
, as we did with lfSent
from Section 6.2 (Predicate Logic as Representation Language).
The various parsers in this chapter are all deterministic simulations of a particular kind of non-deterministic pushdown automaton associated with context-free grammars. There are three well-known types of non-deterministic pushdown automata for CFGs that are used as bases of parsing: top-down, bottom-up, and left-corner (see here for more information). The one that's used here is the top-down variety, and the corresponding parsing method is also called "recursive descent". It is particularly natural in the context of functional programming. (Note that the term "stack-based" is often used to describe parsing based on NPDA.)
"Top-down" and "bottom-up" on LF do not completely correspond to "top-down" and "bottom-up" on syntactic trees of English. The direction of flow of information sometimes gets reversed in English trees. With the bottom-up approach, the DET needs to receive information both from the RCN and the VP, so the information from the VP has to first get passed to the NP, and then from the NP to the DET.
The mapping \[ \alpha \mapsto \overline{\alpha}, \] which replaces each occurrence of \(e\) and \(t\) by \(s \rightarrow e\) and \(s \rightarrow t\), and the associated intensionalization and extensionalization operators (\({}^{\cap}\) and \({}^{\cup}\)) is not familiar to linguists. In linguistics, a common practice nowadays is to use the fewest instances of \( s \) as are necessary for adequate semantic analysis, rather than systematically replacing each occurrence of an atomic type by its intensional counterpart.
The book uses a combination of a string and an integer as a representation of a variable in first-order logic. An alternative is to use a Haskell variable. In this approach, a quantified formula consists of the constructor for the quantifier and a function from terms to formulas. In other words, we treat \[ \forall x\: \varphi \] as a shorthand for \[ \forall (\lambda x.\varphi), \] where the \(\lambda\)-abstract is a real function, not an expression. The local variable in the function definition plays the role of the bound variable.
lf2
is wrong.
Eta reduction: \( (\lambda v \mapsto (E\: v)) \stackrel{\eta}{\longrightarrow} E \)
Condition: \( v \) is not free in \( E \).
module Ptest where import P recognizeDyck :: String -> Bool recognizeDyck = \xs -> null xs || or [ recognizeDyck ys | ["a",ys,"b"] <- splitN 3 xs ] || or [ recognizeDyck ys && recognizeDyck zs | (ys,zs) <- split2 xs ]we get non-termination for "abab".
*Ptest> recognizeDyck "ab" True *Ptest> recognizeDyck "abab" ^C ^CInterrupted. *Ptest>
Last modified: 2017-04-06 19:07:47 JST