(original) (raw)

Page Numbers: Yes X: 306 Y: 0.9" First Page: 11 Margins: Top: 1.1" Bottom: 1.2" Heading: z18344l3000x2e2qk40(0,65535) PROBLEM SET #2 LISP: LANGUAGE AND LITERATURE May 21, 1984 l3000d2469y756x2e2qk40(0,2999)(1,8079)(2,16731)(13,0)\f7 1f1 66f8 44f1 2-XX Fragments from Earlier Draftx2e10jk40(0,3528)(1,4798)(2,6068)(3,7338)(4,8608)(5,9878)(6,11148)(7,12418)(13,65535)\b xxxx2e5jk40 x2e5jk40\f8 44f0 This is as far as I have gotten so far; the remainder is all from the last version.x2e5jk40\b83B x2e5jk40\f8 44f0 xxxx2e5jk40 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 likex2e5jk40\152f3 21f0 (recognize "(a b c)" 'expression *3G*)l4057e5(0,8576)(1,9312)(2,65535)(3,65535)(4,65535)(5,65535)(6,65535)(7,65535)\f3 if *3G* names a grammar of 3-LISP.x2e5jk40(0,3528)(1,4798)(2,6068)(3,7338)(4,8608)(5,9878)(6,11148)(7,12418)\3f3 4f0 20f7 6f0 In the comments introducing the code in appendix E, an example is given.x2e5jk40 2-3-a. Write a grammar *3G* for the fragment of 3-LISP we have used in the previous problems. Your definition should support:x2e5jk40\b6B18f3 4f0 21f7 6f0 (recognize "[a b]") g "accepted"l4057e5(0,10528)(1,11456)(2,65535)(3,65535)(4,65535)(5,65535)(6,65535)(7,65535)\f3 20f4 1f3 (recognize "[a b)") g "rejected"l4057e5\f3 20f4 1f3 (recognize "()") g "rejected"l4057e5\f3 17f4 1f3 (recognize "(lambda (a) [] [] [])") g "accepted"l4057e5\f3 36f4 1f3 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.x2e5jk40(0,3528)(1,4798)(2,6068)(3,7338)(4,8608)(5,9878)(6,11148)(7,12418)\b6B14f3 4f0 58f8 1f0 18f7 6f0 2-3-c. Figure out how the code in appendix E works (this may take a bit of time). Then answer the following questions: x2e5jk40\b6B o Is RECOGNIZE a bottom-up or top-down parser?z18344l4586d4057x2e5jk40(0,4586)(1,7104)(2,10464)(3,10464)(4,6703)(5,7232)(6,7761)(7,8290)(8,8819)(9,9349)(10,9878)(11,10407)(12,10936)(13,12350)(14,17639)\f4 1f0 4f3 9f0 o Describe, in a simple English sentence or two, what the program writer means by a "frontier".z18344l4586d4057x2e5jk40\f4 1f0 o xxxz18344l4586d4057x2e5jk40\f4 1f0 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.x2e5jk40(0,3528)(1,4798)(2,6068)(3,7338)(4,8608)(5,9878)(6,11148)(7,12418)(8,65535)(9,65535)(10,65535)(11,65535)(12,65535)(13,65535)(14,65535)\57i6I59f8 1f0 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.x2e11jk40\i151I 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. x2e5jk40\b6B52f3 5f0 45f3 5f0 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: x2e5jk40\b6B73f8 1f0 17f7 6f0 70f7 6f0 31f7 6f0 ;;; 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] ...l4057e10k40(1270)\f3 This may not work out properly; too hard; leave till next problem.x2e10jk40(0,3528)\i66I 2-4. Augmentsx2e10jk40\b 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:x2e10jk40\145f8 1f0 35f8 1f0 87i4I [lhs transduction rhs1 ... rhsk]l4057e10k40(1270)\f3 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.x2e5jk40(0,3528)\140f7 6f0 x2e5jk40\f8 37f0 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:x2e5jk40\i163I x2e5jk40\f8 37f0 xxxx2e5jk40 xxxx2e5jk40 xxxx2e5jk40 2-5. Extra Creditx2e10jk40\b 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.x2e10jk40\194f7 6f0 112f7 6f0 A simpler task would be to implement an interpretation function. Specifically, for ...x2e10jk40 Finally, the question of parser-generators: procedures that take explicit representations of grammars and produce implicit procedures for recognition, parsing, analysis, translation, etc.x2e5jk40 xxxx2e5jk40 Note: xxx 1x2e9jk40\11f4 1f0 2-1-a. xxxx2e5jk40\b6B xxxz18344l4057x2e5k40(0,4586)(1,5115)(2,5644)(3,6174)(4,6703)(5,7232)(6,7761)(7,8290)(8,8819)(9,9349)(10,9878)(11,10407)(12,10936)(13,12350)(14,17639)\f3 xxxz18344l4057x2e5k40\f3 Footnotes:x2e5jk40(0,3528)(1,4798)(2,6068)(3,7338)(4,8608)(5,9878)(6,11148)(7,12418)(8,65535)(9,65535)(10,65535)(11,65535)(12,65535)(13,65535)(14,65535)\b10B 1. Can't compute chairs; only numbers, linguistic tokens, etc.x2e5jk40 2. Distinguish between semantic and semantical.x2e5jk40 3. Since grammars are mini-theories, this means the distinction is theory-relative, which is exactly right.x2e5jk40 xxxx2e5jk40 xxxx2e5jk40 xxxx2e5jk40 TO BE DONE:x2e5jk40\b11B  Talk early about what "implicit" and "explicit" mean.x2e5jk40  Talk about implicit not necessarily worse than explicit.x2e5jk40  Efficiency?x2e5jk40  Extra credit: parser-generators: grammar -> code for implicit parsers etc.x2e5jk40 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:x2e9jk40\71f7 6f0 14f3 4f0 (load "{turing}<3-lisp.problem-sets>3-lisp-recognizer.3-lisp") (load "{phylum}<3-lisp>course>problem-sets>3-lisp-recognizer.3-lisp") 1z18344l4057x2e5k40(0,4586)(1,5115)(2,5644)(3,6174)(4,6703)(5,7232)(6,7761)(7,8290)(8,8819)(9,9349)(10,9878)(11,10407)(12,10936)(13,12350)(14,17639)\f3 142f4 1f3