>> [Comp Sci Dept]
>> [R J Botting]
Wed May 26 17:13:31 PDT 2004
8 questions, 25 points each (12 minutes per answer).
- At least 10 sheets of blank paper plus two or three writing sticks.
- The specification of the language Minsky
[ Minsky.html ]
because several questions may refer to this LRM.
- A single 8.5><11 inch sheet of notes -- -- --(cheatsheet)
Answer all 8 questions.
All questions need long answers and/or short essays.
Each is worth 25 points.
Start each question on a new sheet of paper.
Use both sides.
Put last 4 digits of SSN/StId on each sheet.
No access to computers (any machine that can access the Internet or
compile, interpret, check, parse, or analyze any computer language
discussed in this course).
No wireless communication.
I give credit for
working and for incomplete answers. Do not erase your working.
Question Topics Spring 2004
- Show that you recall at least one presentation of a term paper made by
another student in this class.
- Show that you understand BNF, EBNF, Chomski types, ... Parse strings
according to given grammar/BNF. Recall mathematical definition of a
grammar. Show how to apply productions to calculate strings in a language.
Translate EBNF into BNF. Correct a simple ambiguity in BNF.
- Given the formal abstract syntax and semantics of an unusual language show how to determine the meaning of a program/expression/statement in the language.
[ Minsky.html ]
- Define and relate: lexers, parser, interpreters, compilers, quads, syntax
improvement, recursive descent. Given a production write the associated
subprogram/function from a typical recursive descent parser or interpreter
- Describe effect of Von Neumann architecture on imperative languages.
Provide names of typical imperative languages. Show how a given imperative
language fits the paradigm. List differences between two imperative
languages. Describe features of imperative languages: I/O, arithmetic,
GOTOs, control structures, loops, special commands/directives, data
structures, records, pointers, runtime errors, functions and procedures,
activation records and the run time stack, parameter passing. Give a rough
translation of a small FORTRAN program into a language like C++ or Java
with only approximate I/O formatting.
- Explain why OO languages evolved: what needs did they meet? Use
imperative+>OO transition as an example of language evolution. Describe
the features that distinguish OO from imperative, Give examples of OO
features in a language like C++, Java, or C#(your choice). Compare C++ and
Java. Describe 2 or 3 features in Java that serve concurrency. Give an
example of a difficulty with concurrent programming that does not occur in
normal programs. Show how to express a simple data structure (stack,
queue,...) in an OO language. How successful was the shift from imperative
to OO paradigm? Write a short essay on the future of C++(or Java) that
states your opinions and gives reasons for them.
- Name the most Long lasting and famous functional language, and its two main
variants. Describe LISP data in terms of C++/Java. Describe S-expressions
and give examples. Explain a COND function in terms of C++/Java. Given a
small LISP function definition and a call trace the resulting evaluation.
Describe association lists: form of data, typical operations. Describe the
Property list: typical function calls. Know whether you can describe the
semantics of LISP using LISP as a metalanguage. Show how to express a
simple data structure (stack, queue,...) in LISP. Write a short essay on
the future of LISP that sates your opinions and gives reasons for them.
- Describe the propositional calculus,first order (lower) predicate calculus.
Give an example of Modus Ponens, truth table, quantifier, predicate,
proposition, and connectives. Give an example of a Prolog database
containing facts and rules and trace how a typical query accesses these to
give results. Given a Prolog program plus some queries, show what Prolog
responds. Show how to express a simple data structure (stack, queue,...) in
Prolog. Distinguish '=' and 'is' in Prolog -- with examples. Define and
trace a Prolog recursive definition.
Topics/skills not needed in Spring 2004
- Axiomatic semantics.
- Operational Semantics (not in book)
- Improving a given syntax.
- Fixed point theory (not in book).
- Writing good FORTRAN or Pascal.
. . . . . . . . . ( end of section CSci620 Final) <<Contents | Index>>
- BNF::="Backus-Naur Form", for syntax and grammar, developed by Backus and Naur.
- EBNF::="Extended " BNF.
- HTML::= "HyperText Markup Language", used on the WWW.
- HTML_page::syntax= "<HTML>" head body.
- Java::="An " OO " Language from Sun".
- LISP::= "LISt Processing Language".
- LRM::="Language Reference Manual".
- Prolog::="Programming in Logic".
- TBA::="To Be Announced".
- UML::="Unified Modeling Language".
- Universal_Resource_Locator::syntax= protocol ":" location, where
- protocol::= "http" | "ftp" | "mailto" | ... ,
- location::= O( "//" host) O(pathname).
(End of Net)
- WWW::= See http://www.csci.csusb.edu/dick/cs620/,
index to web site for this class.
- XBNF::="eXtreme" BNF, developed by the teacher from EBNF, designed
to ASCII input of syntax, semantics, and other formal specifications.
Formulae and Definitions in Alphabetical Order