450 exam 1 Flashcards
(112 cards)
1
Q
reasons for studying this course
A
- increased ability to express ideas
- improved bg for choosing appropriate languages
- increased ability to learn new languages
- better understanding of significance of implementation
- better use of languages that are already known
- overall advancement of computing
2
Q
four properties of programming languages
A
syntax, names, types, semantics
3
Q
syntax
A
a precise description of a language’s grammatically correct programs
4
Q
names
A
various kinds of entities in a program have names (e.g., variables, functions, parameters, classes, objects, etc.)
5
Q
type
A
a collection of values and a collection of operations on those values
6
Q
semantics
A
the meaning of a program
7
Q
major programming domains
A
scientific, business, systems programming, AI, web software
8
Q
language evaluation criteria (main)
A
simplicity and readability, orthogonality, clarity about binding, reliability, abstraction, support, cost
9
Q
language evaluation criteria (other)
A
writability, portability, generality, well-definedness
10
Q
simplicity and readability
A
small instruction set, simple syntax, ease of learning/programming
11
Q
orthogonality
A
a relatively small set of primitive constructs can be combined in a relatively small number of ways to build the control and data structures; every combination is legal and meaningful
12
Q
a lack of orthogonality leads to
A
exceptions to the rules of the language (and fewer exception rules = conceptual simplicity)
13
Q
binding
A
the association between a variable and a property of that variable (e.g., a variable and its type or value)
14
Q
early binding
A
takes place at compile time
15
Q
late binding
A
takes place at run time
16
Q
reliability
A
program behavior is the same under all conditions
17
Q
with reliability, errors are ? and memory leaks are ?
A
detected and properly trapped; prevented
18
Q
data abstraction
A
programmer-defined classes/types, class libraries
19
Q
procedural abstraction
A
programmer-defined functions, standard function libraries
20
Q
support
A
accessible (public domain) compilers/interpreters/IDEs, good texts and tutorials, wide community of users
21
Q
cost
A
training programmers to use the language, writing/executing programs, maintaining programs (can be 2-4x as much as developing), reliability (poor reliability leads to high costs)
22
Q
writabilty
A
how easily a language can be used to create programs
23
Q
portability
A
the ease with which programs can be moved from one implementation to another
24
Q
generality
A
the applicability to a wide range of applications
25
well-definedness
the completeness and precision of the language’s official definition
26
influence of the von Neumann architecture on the evolution of programming languages
1. data and programs stored in MEMORY
2. instructions and data are PIPED from MEMORY TO CPU
3. basis for IMPERATIVE languages (variables ~ memory cells, assignment statements ~ piping, iteration/repetition is efficient)
27
influence of programming methodologies: 1950s and early 1960s
simple applications; worry about machine efficiency
28
influence of programming methodologies: late 1960s
people efficiency became important; readability, better control structures
29
influence of programming methodologies: late 1970s
data abstraction
30
influence of programming methodologies: middle 1980s
domain and data complexity; object-oriented programming
31
influence of programming methodologies: today
web and networked environment; parallel and distributed computing
32
four main programming paradigms
imperative, object-oriented, functional, and logic (declarative)
33
imperative programming languages
Fortran, Cobol, C, Ada, Perl
34
object-oriented programming languages
Smalltalk, Java, C++, C#, Python
35
functional programming languages
Lisp, Scheme, ML, Haskell
36
logic (declarative) programming languages
Prolog
37
imperative programming
the oldest; follows von Neumann model of computation
38
program and its variables are stored together in memory
imperative programming
39
program = a sequence of commands
imperative programming
40
state = values of all variables when program runs
imperative programming
41
essential building blocks of imperative programming
procedural abstraction, assignments, loops, sequences, conditional statements, etc.
42
object-oriented programming
a collection of objects that interact by passing messages that transform the state
43
sending messages, inheritance, polymorphism
object-oriented programming
44
functional programming
models a computation as a collection of mathematical functions
45
```
input = domain
output = range
```
functional programming
46
characterized by functional composition and recursion
functional programming
47
logic (declarative) programming
declares what outcome the program should accomplish, rather than how it should be accomplished
48
we see programs as sets of constraints on a problem, programs that achieve all possible solutions, and programs that are nondeterministic
logic (declarative) programming
49
implementation methods
compilation, pure interpretation, hybrid implementation systems
50
compilation
translate high-level programs (source language) into machine code (machine language) by a compiler; fast execution
51
compilation use
large commercial applications
52
pure interpretation
programs are interpreted by another program known as an interpreter
53
pure interpretation use
small programs or when efficiency is not an issue
54
hybrid implementation systems
a compromise between compilers and pure interpreters
55
hybrid implementation systems use
small and medium systems when efficiency is not the first concern
56
compilation process
1. lexical analysis (convert characters into lexical units)
2. syntax analysis (lexical units -> parse trees to represent syntactic structure)
3. semantics analysis (generate intermediate code)
4. code generation (of machine code)
57
compilation languages
Fortran, Cobol, C, C++, Ada
58
pure interpretation
easier implementation of programs, slower execution (than compiled programs)
59
run-time errors can easily and immediately be displayed in which implementation method?
pure interpretation
60
pure interpretation made a significant comeback with
some Web scripting languages (e.g., JavaScript, PHP)
61
purely interpreted languages
Scheme, Haskell, Python, APL, SNOBOL, LISP, JavaScript, PHP
62
hybrid implementation languages
Perl, initial implementations of Java (JVM), .NET languages
63
hybrid implementation programs are a compromise between
compilers and pure interpreters
64
hybrid implementation systems
a high-level language program is translated to an intermediate language that allows easy interpretation; faster than pure interpretation
65
example of hybrid implementation system
JIT (Just In Time compilation) used in Java and .NET (bytecode -> interpreter)
66
(chapter two)
(chapter two)
67
syntax (ch 3)
the form (or structure) of the expressions, statements, and program units
68
semantics (ch 3)
the meaning of those expressions, statements, and program units
69
sentence
a string of characters over some alphabet
70
language
a set of sentences
71
lexeme
the lowest level syntactic unit of a language (e.g., *, sum, etc.)
72
token
a category of lexemes (e.g., identifier)
73
languages can be formally defined in two ways
recognizer or generator
74
recognizer
a recognition device reads input strings over the alphabet of the language and decides whether the input strings belong to the language
75
example recognizer
syntax analysis part of a compiler
76
generator
a device that generates sentences of a language
77
language generator
used to construct strings, given a start symbol
78
context-free grammars were developed by ? in the ?
Noam Chomsky; mid-1950s
79
context-free grammars were meant to
describe the syntax of natural languages
80
BNF stands for
Backus-Naur Form
81
BNF was created in
1959
82
BNF was invented by ? and later modified by ?
John Backus (for Algol 58); Peter Naur (for Algol 60)
83
BNF is nearly identical to
Chomsky's context-free grammars
84
BNF was first used to define the syntax of Algol 60, but is now used to define syntax of
most major languages
85
in BNF, abstractions (nonterminals) are used to
represent classes of syntactic structures
86
in BNF, abstractions (nonterminals) act like
syntactic variables
87
in BNF, terminals are
lexemes or tokens
88
a BNF rule has a left-hand side (LHS), which is ?, and a right-hand side (RHS) which is ?
nonterminal; a string of terminals and/or nonterminals
89
BNF nonterminals are often enclosed in
angle brackets
90
BNF grammar
a finite non-empty set of rules
91
BNF rules: an abstraction (or nonterminal symbol) can have
more than one RHS, where | is a metacharacter that separates alternatives
92
syntactic lists are described using
recursion
93
derivation
a repeated application of rules, starting with the start symbol and ending with a sentence (all terminal symbols)
94
every string of symbols in a derivation is a
sentential form
95
a sentence is a sentential form that
only has terminal symbols
96
leftmost derivation
one in which the leftmost nonterminal in each sentential form is the one that is expanded
97
a derivation may be either
leftmost or rightmost
98
parse tree
a hierarchical representation of a derivation
99
each internal node of the parse tree corresponds to
a step in the derivation
100
each child node in a parse tree represents
a right-hand side of a production
101
each leaf node in a parse tree represents
a symbol of the derived string, reading from left to right
102
a grammar is ambiguous if
it generates a sentential form that has two or more distinct parse trees
103
a grammar can be used to define
associativity and precedence among the operators in an expression
104
associativity and precedence are shown by
the structure of the parse tree
105
in a parse tree, operators with highest precedence are
at the bottom
106
in a parse tree, an operator is left-associative if
on the left at each level (recursion happens on the left of the operator and therefore makes the leaf node lower on the left)
107
in a parse tree, an operator is right-associative if
on the right at each level (recursion happens on the right of the operator and therefore makes the leaf node lower on the right)
108
three extensions common to most extended BNF forms
brackets, parentheses with vertical bars, braces
109
optional parts of RHSs are placed
in brackets [ ]
110
alternative parts of RHSs are placed
inside parentheses and separated via vertical bars
111
repetitions (0 or more) are placed
inside braces { }
112
review Fortran and Cobol
to be able to read and give output (based on HW and examples from class)
