module 1 Flashcards
(76 cards)
1
Q
what are the categories of language evaluation criteria?
A
- readability
- writability
- reliability
- cost
2
Q
what are languages developed around?
A
Von Neumann architecture
3
Q
draw and describe the von neumann architecture
A
§ Data and programs stored in memory
§ Memory is separate from CPU
§ Instructions and data are piped from memory to CPU
§ Basis for imperative languages
4
Q
why do we need different languages?
A
New software development methodologies (e.g., object-oriented software development) led to new programming paradigms and by extension, new
programming languages
5
Q
what are the 4 language categories?
A
- imperative: variables, assignment statements, iteration, scripting, visual, and object-oriented languages (Java, C, JavaScript)
- functional: main means of making computations is by applying functions to given parameters
- logic: rule-based (prolog)
- markup/programming hybrid: markup languages extended to support some programming (JSTL)
6
Q
what are the tradeoffs in language design?
A
reliability vs cost of execution (java demands all references to array elements to be checked for proper indexing)
readability vs writability (APL allows complex computations by containing powerful operators)
writability vs reliability (C++ pointers are powerful and flexible but unreliable)
7
Q
3 implementation methods
A
- compilation: programs are translated into machine language (large commercial applications)
- pure interpretation: programs are interpreted by another program known as an interpreter (small programs, efficiency is not concern)
- hybrid implementation systems: compromise between compilers and pure interpreters (small and medium systems)
8
Q
what are the phases of the compilation process?
A
- lexical analysis: converts characters in the source program into lexical units
- syntax analysis: transforms lexical units into parse trees
- semantics analysis: generate intermediate code
- code generation: machine code is generated
9
Q
linking and loading
A
process of collecting system program units and linking them to a user program
10
Q
von neumann bottleneck
A
- connection speed between a computer’s memory and its processor determines the speed of a computer
- program instructions can be executed faster than the speed of the connection
- Memory and the CPU are separated in the Von Neumann architecture, so the CPU must fetch data for every operation it performs
- limiting factor in the speed of computers
11
Q
pure interpretation
A
- no translation
- easier implementation of programs
- slower execution
- often requires more space
12
Q
hybrid implementation systems
A
- high-level language program is translated to an intermediate language and allows easy interpretation
- faster than pure interpretation
13
Q
just in time implementation systems
A
- initially translate programs to an intermediate language
- compile the intermediate language of the subprograms into machine code when they are called
14
Q
what do preprocessors do?
A
processes a program immediately before the program is compiled to expand embedded preprocessor macros (used to specify that code from another file is to be included)
15
Q
syntax
A
form or structure of the expressions, statements, and program units
16
Q
semantics
A
the meaning of the expressions, statements, and program units
17
Q
sentence
A
string of characters over some alphabet
18
Q
language
A
set of sentences
19
Q
lexeme
A
lowest level syntactic unit of a language
20
Q
token
A
category of lexemes
21
Q
recognizer
A
reads input strings over the alphabet of the language and decides whether the input strings belong to the language
22
Q
generator
A
device that generates sentences of a language
23
Q
context-free grammar
A
Language generators, meant to describe the syntax of natural languages
24
Q
backus-naur form
A
BNF is equivalent to context-free grammars
Invented by John Backus to describe the syntax of Algol 58
25
grammar
a finite non-empty set of rules
A start symbol is a special element of the nonterminals of a grammar
Syntactic lists are described using recursion
An abstraction (or nonterminal symbol) can have more than one RHS
26
ambiguous grammar
A grammar is ambiguous if and only if it generates a sentential form that has two or more distinct parse trees
27
attribute grammar
a context free grammar with some additions:
- For each grammar symbol x there is a set A(x) of attribute values
- Each rule has a set of functions that define certain attributes of the nonterminals in the rule
- Each rule has a (possibly empty) set of predicates to check for attribute consistency
28
dynamic semantics
There is no single widely acceptable notation or formalism for describing semantics
29
operational semantics
Describe the meaning of a program by executing its statements on a machine, either simulated or actual
The change in the state of the machine (memory, registers, etc.) defines the meaning of the statement
30
denotational semantics
The meaning of language constructs are defined by only the values of the program's variables
31
expression
expressions are decimal numbers, variables, or binary expressions with one arithmetic operator and two operands, each of which can be an expression
32
axiomatic semantics
Axioms or inference rules are defined for each statement type in the language (to allow transformations of logic expressions into more formal logic expressions)
33
weakest precondition
the least restrictive precondition that will guarantee the postcondition
34
loop invariant
a property of a program loop that is true before each iteration
35
benefits of using BNF
provides a clear and concise syntax description
The parser can be based directly on the BNF
Parsers based on BNF are easy to maintain
36
2 parts of syntax analysis
- lexical analyzer
- syntax analyzer (parser)
37
why are lexical and syntax analysis separated?
- simplicity (separation simplifies the parser)
- efficiency (separation optimizes lexical analyzer)
- portability (parser)
38
what is a lexical analyzer
- a pattern matcher for character strings
- a “front-end” for the parser
- Identifies substrings of the source program that belong together - lexemes
39
lexer responsibilities
•Tokenizing source
•Removing comments
•(Often) dealing with pragmas (i.e., significant comments)
•Saving text of identifiers, numbers, strings
•Saving source locations (file, line, column) for error messages
40
dynamic scoping
bindings depend on the flow of execution during run time
refers to the most recently declared variable
41
static scoping
bindings based on purely textual rules
refers to the highest level declaration of a variable.
42
the longest possible token rule
Nearly universal rule: always take the longest possible token from the input
you return only when the next character can't be used to continue the current token
43
what are the 3 ways scanners are built
§ Ad-hoc (fastest and most compact)
§ Semi-mechanical pure DFA (usually as nested case statements)
§ Table-driven DFA (produced by antlr)
44
lexer rules
Lexer rules specify token definitions and more or less follow the syntax of parser rules except that lexer rules cannot have arguments, return values, or local variables.
45
actions
blocks of text written in the target language and enclosed in curly braces.
The recognizer triggers them according to their locations within the grammar.
46
token attributes
attributes include useful token properties such as the token type and text matched for a token
Actions can access these attributes via :
$label.attribute
47
2 categories of parsers
- top-down:
Produce the parse tree, beginning at the root
Order is that of a leftmost derivation
Traces or builds the parse tree in preorder
- bottom-up:
Produce the parse tree, beginning at the leaves
Order is that of the reverse of a rightmost derivation
48
what are the 2 most common top down parsers
- recursive descent
- LL parser (antlr)
49
what are the 2 most common top down parsers
- recursive descent
- LL parser (antlr)
50
2 most important classes of grammars
LL
- left to right, leftmost derivation
- top-down
- predictive
LR
- left to right, rightmost derivation
- bottom-up
- shift-reduce
51
pairwise disjointedness
The inability to determine the correct RHS on the basis of one token of lookahead
52
binding
A binding is an association between an entity and an attribute, such as between a variable and its type or value, or between an operation and a symbol
53
reserved word
a special word that cannot be used as a user-defined name
54
keyword
word that is special only in certain contexts
55
variable
an abstraction of a memory cell
56
type
determines the range of values of variables and the set of operations that are defined for values of that type; in the case of floating point, type also determines the precision
57
value
the contents of the location with which the variable is associated
58
abstract memory cell
the physical cell or collection of cells associated with a
variable
59
static
objects are given an absolute address that is retained throughout the program’s execution
60
stack
objects are allocated and deallocated in last-in, first-out order, usually related to subroutine calls and returns
61
heap
objects allocated and deallocated at arbitrary times
62
garbage collection
identifies and reclaims unreachable objects
63
explicit deallocation vs implicit deallocation
explicit: simplicity and execution speed provided that the programmer can correctly identify the end of an object’s lifetime
implicit: automatic, eliminates manual allocation errors such as dangling reference and memory leak
64
scope of a variable
range of statements over which it is visible
65
scope of a variable
range of statements over which it is visible
66
local vs nonlocal variables
local: those that are declared in that unit
nonlocal: those that are visible in the unit but
not declared there
67
ambiguous grammar
you have a symbol that appears twice on the right side and once on the left side
68
elaboration
process by which declarations become active when control first enters a scope
69
referencing environment
collection of all names that are visible in the statement
In a static-scoped language, it is the local variables plus all of the visible variables in all of the enclosing scopes
In a dynamic-scoped language, the referencing environment is the local variables plus all visible variables in all active subprograms
70
how to calculate leftmost derivation?
just start with the farthest left element (for example, in id = a, id gets evaluated first), keep going till you have fully evaluated the statement
71
pairwise disjointness test
pick the farthest left character for each statement, if the characters from each statement are the same, they fail the test
72
recursive descent parser trace
next token is: # Next lexeme is a
Enter
Enter
Enter
...
73
3 variations of imperative language group
von neumann, object-oriented, scripting languages
74
2 variations of declarative language group
functional, logic-based
75
difference between lifetime and scope
Scope of a variable determines the area or a region of code where a variable is available to use, lifetime is from when a variable is made visible until it’s destroyed
76
order of programming methodologies utilized
machine efficiency
structured programming
process-oriented
object-oriented
