Page Numbers: Yes X: 306 Y: 0.9" First Page: 11
Margins: Top: 1.1" Bottom: 1.2"
Heading:

PROBLEM SET #2 LISP: LANGUAGE AND LITERATURE May 21, 1984
————————————————————————————————————————————

2-XX Fragments from Earlier Draft

xxx

————————————————————————————————————————————

This is as far as I have gotten so far; the remainder is all from the last version.

————————————————————————————————————————————

xxx

In appendix E, a recognition procedure is defined that takes a grammar as an explicit argument. I.e., whereas for the code in appendix C you would say (recognize "(a b c)"), we will now require something like

(recognize "(a b c)" ’expression *3G*)

if *3G* names a grammar of 3-LISP.

In the comments introducing the code in appendix E, an example is given.

2-3-a. Write a grammar *3G* for the fragment of 3-LISP we have used in the previous problems. Your definition should support:

(recognize "[a b]")g"accepted"

(recognize "[a b)")g"rejected"

(recognize "()")g"rejected"

(recognize "(lambda (a) [] [] [])")g"accepted"

2-3-b. Extend your *3G* grammar to support dots, up and down arrows, and handles — i.e., extend the 3-LISP fragment as you did in problem 2-1-a.

2-3-c. Figure out how the code in appendix E works (this may take a bit of time). Then answer the following questions:

oIs RECOGNIZE a bottom-up or top-down parser?

oDescribe, in a simple English sentence or two, what the program writer means by a "frontier".

oxxx

Appendix F contains a similar transducer, in this case a parser. It takes its grammars explicitly, and gives back parses — representations of information about the grammatical structure of the expressions it is given as arguments.

Question: Should writing the code in Appendix F be given as a problem? It is probably not impossibly difficult, but then it won’t be trivial, either.

2-3-d. Write a simple ambiguous grammar for appendix F’s PARSE, and illustrate on some simple examples how PARSE returns all possible parses, not just a single one.

2-3-e. Write a modification to the code in appendix F to support a translator — specifically, a 3-LISP internalizer that translates expressions in our standard fragment of 3-LISP notation to the corresponding 3-LISP internal structures. I..e, you should write an internalizer that takes grammars explicitly. The translations should be specified by extensions to the grammar rules. I.e., you would define a grammar something like the following:

;;; General form for extended grammar rule:
;;;
;;; [lhs [rhs1 rhs2 ... rhsk] template]
;;;
;;; where the right hand sides (rhs’s) are as before. The template should be a form,
;;; into which the ...
;;;
;;; For example, the rule for rails would be:
;;;
;;; [’rail ["[" rail-args] ...

This may not work out properly; too hard; leave till next problem.

2-4. Augments

It is clear, given all of these various procedure definitions, that it would be powerful to abstract over all the various sorts of transductions — parsing, recognition, translation — and define a general purpose transduction procedure that in some sense would take the task as an explicit argument, as well as the grammar. In appendix G such a general purpose transducer is presented. It takes grammar rules of the form:

[lhs transduction rhs1 ... rhsk]

where the transduction is a function to be applied to the transductions of the remainig constituents to be found, or (in the base case) any 3-LISP entity.

—————————————————————————————————————

This is as far as I have gotten so far. It is clear, from appendix H, what remains (not much): explicit augments for parsing, recognition, internalixation. Then:

—————————————————————————————————————

xxx

xxx

xxx

2-5. Extra Credit

The machinery presented in problem 2.4 is even more powerful than the examples there might suggets. In particular, it would be possible, by writing sufficiently powerful augments, to translate 3-LISP expressions not just into their internalizations, but into normal-form results. I.e., one could implement the 3-LISP processor using this machinery. It should be relatively straightforward to see how this would go except for the question of environments. However, by using sufficiently fancy augments, one can pass environments up and down the tree of the expression. However we will not do that here.

A simpler task would be to implement an interpretation function. Specifically, for ...

Finally, the question of parser-generators: procedures that take explicit representations of grammars and produce implicit procedures for recognition, parsing, analysis, translation, etc.

xxx

Note: xxx 1

2-1-a. xxx

xxx

xxx

Footnotes:

1. Can’t compute chairs; only numbers, linguistic tokens, etc.

2.Distinguish between semantic and semantical.

3.Since grammars are mini-theories, this means the distinction is theory-relative, which is exactly right.

xxx

xxx

xxx

TO BE DONE:

—Talk early about what "implicit" and "explicit" mean.

—Talk about implicit not necessarily worse than explicit.

—Efficiency?

—Extra credit: parser-generators: grammar -> code for implicit parsers etc.

Note: The code shown in each of the appendices can be loaded into your 3-LISP by using the LOAD procedure; the file names are given at the head of each appendix. Thus to load in the code given in appendix C you would type the first of the following expressions if you are at CSLI/Stanford; the second if you are at CSLI/Xerox:

(load "{turing}<3-lisp.problem-sets>3-lisp-recognizer.3-lisp")
(load "{phylum}<3-lisp>course>problem-sets>3-lisp-recognizer.3-lisp") 1