CISS 445 - Programming Languages - Test #1

Card Set Information

CISS 445 - Programming Languages - Test #1
2012-06-13 11:40:36

Study Guide for Test #1 Covering Chapters 1 thru 5
Show Answers:

  1. What are the 3 criteria used to evaluate a programming language?
    • Readability
    • Writeability
    • Reliability
  2. What contributes to the total cost of using a particular programming language?
    • programmer training
    • writing cost
    • compiling
    • executing
    • development environment cost
    • maintenance
    • program failure cost
  3. What is orthogonality?
    A relatively small set of primative constructs can be combined in a relatively small number of ways to build the control and data structures of the language. Furthermore, every possible combination of primatives is legal and meaningful.
  4. What is feature multiplicity?
    Having more than one way to accomplish a particular operation.
  5. What is aliasing?
    Having two or more distinct names that can be used to access the same memory cell.
  6. What is the difference between an imperative and a non-procedureal programming language?
    • Imperative Programming Languages are the "Classic" languages. Each statement executed one at a time in an order determined by the programmer. Includes object oriented (C++ Java..), visual languages (.NET), scripting languages (PERL, JavaScript, Ruby..)
    • Non-Procedureal Programming Language are the Data oriented program design methodology emphasizes data design, focusing on the use of abstract data types to solve problems.
  7. What are the 3 main ways to implement a programming language?
    • compiler
    • interpreter
    • hybrid
  8. What is the "just-in-time" process of implementing a language, and what benefit might it provide?
    • Initially translate program to intermediate language.
    • During execution, compile each intermediate method code into machine code the first time it is called.
    • Saves generating machine code for parts of the source program that are never called.
    The first compiled high-level language -- tremendously increased use of computers in 1950s-1960s and still dominates scientific programming.
  10. LISP
    Designed for Artificial Intelligence (AI) applications -- pioneered functional languages (all computation accomplished by applying functions to arguments).
  11. ALGOL 60
    Introduced the "run-time stack" to handle stack-dynamic variables, and this affected subsequent computer architecture (machine language) to support a system stack.
  12. COBOL
    Was the most used programming language ever, leading the electronic mechanization of accounting starting in the 1960s.
  13. BASIC
    A teaching language at Dartmouth -- first language to consider user time more important than computer (CPU) time.
  14. PL/I (IBM)
    Tried to handle both scientific and business applications, so it had very many features.
  15. APL & SNOBOL
    Pioneered dynamic typed variables (a variable acquires a data type and is allocated memory when it is assigned a value).
  16. ALGOL 68
    Used "orthogonality" as it's primary design criteria. Affected future languages even though ALGOL 68 was never widely used.
  17. PASCAL
    Most popular teaching language of the 1970s-1990s, taught students to use "structured programming" concepts (Fortran & Basic didn't teach structured programming).
  18. C
    First high-level language used to write an operating system kernel (UNIX).
  19. PROLOG
    Still the premiere non-procedural language, based on formal logic.
  20. ADA
    Pioneered data abstraction (packages), generic subprograms, and concurrent execution.
  21. Smalltalk
    The first fully object oriented language, having all 3 OO concepts: data abstration, inheritance, dynamic method binding.
  22. C++
    Added Object Oriented programming to C while maintaining C's performance and backward compatibility with C.
  23. Java
    Object Oriented derived from C++, but removed many unsafe features, making it simple enough for small computers (cell phones, routers, tablets).
  24. Web Scripting Languages: PERL, JavaScript, PHP, Python, Ruby
    • Designed for web-programming (creating the behavior of web-sites).
    • These web languages provide features that make it easier to program smaller web programs, at the expense of execution speed and error detection.
  25. Syntax
    • The form of a programming language's expressions, statements, and program units.
    • In a "natural language", like English, it's the form of nouns, verbs, subject, object, etc., required to make grammatically correct sentences.
    • English has a continually evolving complex set of "grammar rules" (you learned them in grade school English class) for specifying syntactically correct sentences.
    • A "formal language", such a programming language, by comparison, is syntactically simple, specified by a fixed simple set of grammar rules.
  26. Semantics
    The meaning of the expressions, statements, and program units of the programming language's syntax.
  27. Sentence
    • A string of characters taken from some alphabet.
    • A sentential form that has only terminal symbols.
  28. Lexeme
    • The lowest-level syntactic units, including numeric literals, operators, special words, etc.
    • A word or punctuation mark in English or '*', IF, FOR,... in C++.
  29. Token
    • A category of related lexemes.
    • For example: a noun or verb or other part of speech in English.
    • An identifier or operator or constant (literal) in C++.
  30. Recognizer
    • A device that reads input strings and decides whether the input strings are "legal" in the language.
    • Diagramming English sentences in grade school.
    • Syntax analysis part of a compiler.
  31. Generator
    A device that can generate all the syntactically correct sentences of a language.
  32. Sentential Form
    Every string of symbols in a derivation is a sentential form.
  33. Terminal Symbol
    The words in a sentence.
  34. Non-Terminal Symbol
    • The parts of speech and other grammatical parts of a sentence (noun, adjective, subject, verb, object,...).
    • Are enclosed in <angle brackets>.
  35. Ambiguous Grammar
    Generates a sentential form that has two or more distinct parse trees.
  36. Unambiguous Grammar
    Generates a sentential form that has only one unique parse tree.
  37. Static Semantics
    • Is only indirectly related to the meaning of programs during execution; rather, it has to do with the legal forms of programs (syntax rather than semantics).
    • Typically state a languages type constraints.
    • So named because the analysis required to check these specifications can be done at compile time.
  38. What are 3 things added to a grammar to create an attribute grammar?
    • Attributes for each symbol
    • Functions (a.k.a semantic rules) for each syntax rule
    • Boolean predicates for each rule
  39. What are the main two uses of attribute grammars?
    • To enforce a language's data-type rules in expressions and assignments.
    • To enforce a language's context-sensitive rules such as requiring variables to be declared before they are used.
  40. What are the two steps of analyzing syntax of a program?
    • Lexical analysis -- recognizes the "lexemes" in a character string source program and returns the associated "tokens", one after another.
    • Syntax analysis (parser) -- Uses the grammar rules to create the derivation or parse tree from the tokens or lexemes returned by the lexical analyzer.
  41. How does a TOP DOWN and BOTTOM UP parser work?
    • Both types of parsers use one token look-ahead in order to make the correct choice of which grammar rule to apply.
    • The RECURSIVE-DESCENT top-down parsing algorithm uses a function to handle each nonterminal.
    • LL parser is a top-down parser that scans the input string Left-to-right and constructs a Leftmost derivation.
    • Direct or indirect left recursion in grammar rules makes the grammar unusable by a LL parser.
  42. Pairwise Disjointedness Test
    • Disjoint in this context means that:
    • For each "non-terminal", <A>, in the grammar that has more than one RHS, the first "terminal" symbol that can be generated for each of the RHSs must be unique to that RHS.

    • The following example PASSES:
    • <A> -> aB | bAb | Bb
    • <B> -> cB | d

    • Therefore <A> -> aB, the first "terminal" is {a}
    • Therefore <A> -> bAb, the first "terminal" is {b}
    • Therefore <A> -> Bb, the first "terminal" symbol that can be generated is {c, d} because:
    • <B> -> cB, the first "terminal" is {c}, and
    • <B> -> d, the first "terminal" is {d}, thus
    • the set {c, d} for the third RHS of <A>.
    • Because each RHS of <A> is unique to each other RHS, the grammar is therefore "disjoint" and PASSES the test.

    The following example FAILS:

    • <A> -> aB | BAb
    • <B> -> aB | b

    • Therefore <A> -> aB, the first "terminal" is {a}
    • Therefore <A> -> BAb, the first "terminal" symbol that can be generated is {a, b} because:
    • <B> -> aB, the first "terminal" is {a}, and
    • <B> -> b, the first "terminal" is {b}, thus
    • the set {a, b} for the second RHS of <A>.
    • Because both sets of each RHS include {a}, the grammar is "not disjoint" and FAILs the test.
  43. LR Parser
    A bottom-up parser that scans input string Left-to-right and constructs a Rightmost derivation.
  44. What is a HANDLE?
    At any step in a bottom-up parse, the HANDLE is the correct sub-sequence of symbols in this step's sentential form that corresponds to the RHS of some grammar rule to apply (backwards), producing the correct next sentential form in the parse.
  45. How does the "shift-reduce" bottom-up parsing algorithm work for a given grammar and the ACTION and GOTO tables?
    • Maintain a "stack" of (state,symbol) pairs (initially push state 0).
    • Select an entry in the ACTION table based on the top state in the stack and the next input symbol.
    • The ACTION table entry tells the parser to either SHIFT (push another pair onto the stack), or REDUCE (apply a grammar rule and advance to the next input token).
    • When REDUCing, the GOTO table entry tells the parser what state to push onto the stack.
    • The tables are automatically generated from Knuth's algorithm.
  46. What are the 6 attributes of a variable?
    • Name
    • Address
    • Value
    • Type
    • Lifetime
    • Scope
  47. What is BINDING TIME?
    The time at which an attribute is associated with a variable (or other program entity).
  48. What is type binding?
    Associating a data-type with a variable.
  49. What is the difference between EXPLICIT and IMPLICIT type declaration, and an advantage and disadvantage of each?
    • EXPLICIT type declaration: A program statement is used for declaring the types of variables. An advantage is that the Programmer is in control of the declaration. A disadvantage is that if the Programmer does not declare the variable type explicitly then the compiler will implicitly declare the type, possibly incorrectly.
    • IMPLICIT type declaration: Type specified through default conventions rather than declaration statement. A minor advantage is that it is easily writable. A disadvantage is that they can be detrimental to reliability because they prevent the compilation process from detecting some typographical and programmer errors.
  50. What is "dynamic type binding" and an advantage and disadvantage of it?
    • Used in JavaScript, Python, Ruby, PHP, C#(limited).
    • Advantages: flexibility (generic program units, what C++ calls Templates).
    • Disadvantages: High run-time cost (dynamic type-checking and interpretation), and type-error detection by compiler is difficult.
  51. Static Memory Binding
    • Memory allocated before run-time and remains throughout execution.
    • Most efficient, but disallows recursive functions.
  52. Stack Dynamic Memory Binding
    • Memory allocared/freed on system stack during run-time.
    • Allows recursion & conserves storage, but less efficient than static.
    • Functions can't be "history sensitive".
  53. Explicit Heap-Dynamic Memory Binding
    • Programmer statements (new/delete) allocate/free memory from the "heap".
    • Flexable storage management, but not as efficient as stack dynamic.
    • Error prone.
  54. Implicit Heap-Dynamic Memory Binding
    • Allocate/free memory caused by assignment statements.
    • Very flexible, but highest run-time costs.
  55. What is the difference between Local, Non-Local, and Global variables?
    Local Variable: Those declared in a program unit.

    Non-Local Variable: Variables visible in a program unit but not declared there.

    Global Variable: Certain nonlocal variables that are potentially available to all subprograms, even between separate compilations.
  56. What is the difference beween Static Scope and Dynamic Scope?
    • Static Scope:
    • - Based on program text.
    • - To connect a name reference to a variable, you or the compiler must find the declaration.
    • - Search declarations first locally, then in increasingly larger enclosing scopes, until a declaration is found for the given name.

    • Dynamic Scope:
    • - Scope based on calling sequence of subprograms, not their textual layout.
    • - To determine which variable is referenced, search back through the chain of subprogram calls rather than searching through static blocks.
  57. How is a BLOCK related to Static Scopes?
    • Blocks allow a section of code to have its own local variables whose scope is minimized.
    • This allows new Static Scopes to be defined in the midst of executable code.
  58. What are two disadvantages of Static Scope?
    • Usually too much access is possible.
    • Scope changes as program structure evolves.
  59. What is an advantage and disadvantage of Dynamic Scope?
    • Convenient for programmers.
    • Static type checking impossible.
    • Poor readability.
  60. How is the lifetime of a variable different than it's scope?
    • Lifetime is the duration of the variable in memory.
    • Scope is the boundary of variables visiblity.
  61. What is the REFERENCING ENVIRONMENT of a statement?
    The collection of all names visible to that statement.