450 exam 2 Flashcards
static semantics vs dynamic semantics
static: syntax
dynamic: meaning
attribute grammar is a ? grammar with additions
context-free
what are the three additions to context-free grammars that make an attribute grammar? (“need to understand but not write all down”)
- each grammar symbol has a set of attributes
- each rule has function(s) that define certain attributes of the nonterminals in the rule
- each rule has predicate(s) to check for attribute consistency
fully attributed parse tree
if all the attribute values in a parse tree have been computed
three approaches to describe dynamic semantics
operational, denotational, axiomatic
dynamic semantics: operational vs denotational vs axiomatic
operational: describe meaning by executing its statements on a machine
denotational: meaning defined by the values of the program’s variables
axiomatic: based on mathematical logic (predicate calculus); axioms (inference rules) defined for each statement type in the language
example of operational semantics
JUnit Testing
@Test
public void testBinarySearch() {
// do stuff
}
example of denotational semantics
grammar rules with a semantic function (? - review this)
example of axiomatic semantics
{x > 5} x = x - 3 {x > 0}
precondition, statement, postcondition
assertions
the logic expressions in axiomatic expressions
precondition
an assertion before a statement that states the relationships and constraints among variables that are true at that point in execution
weakest precondition
the least restrictive precondition that will guarantee the postcondition
postcondition
an assertion following a statement
what is the weakest precondition for x = x- 3 {x > 0} ?
{x > 3}
what is the weakest precondition for a = b + 1 {a > 1} ?
{b > 0}
the syntax analysis portion of a language nearly always consists of two parts
lexical analysis and syntax analysis
lexical analyzer
converts characters in the source program into lexical units (lexemes and tokens)
lexeme
the lowest level syntactic unit (such as =)
token
collection of lexemes (such as ASSIGN_OP)
syntax analyzer (or parser)
analyzes the syntactical structure of the given input and checks if the input is in the correct syntax of the language
two categories of parsers
top-down and bottom-up
top-down parser
produce the parse tree, beginning at the root (downward to the leaves) – order is that of a leftmost derivation
bottom-up parser
produce the parse tree, beginning at the leaves (upward to the root) – order is that of the REVERSE of a rightmost derivation
two most common top-down parsing algorithms (LL algorithms)
recursive-descent parser and LL parser
what does LL stand for in LL algorithms?
Left-to-right, Leftmost
recursive-descent parser
there is a subprogram for each nonterminal in the grammar, which can parse sentences that can be generated by that nonterminal; a coded implementation based on BNF or EBNF
recursive-descent parser coding process
for each terminal symbol in the RHS, compare it with the next input token
if they match, continue; else, there is an error
for each nonterminal symbol in the RHS, call its associated parsing subprogram
LL parser
table- (or stack-) driven implementation
LL parser procedure
in each step, the parser reads the next available symbol from the input stream and the top-most symbol from the stack (application of a grammar rule)
if the input symbol and the stack-top symbol match, the parser discards them both, leaving only the unmatched symbols in the input stream and on the stack
purpose of the pairwise disjointness test
indicates whether the parser can always choose the correct RHS on the basis of the next token of input
pairwise disjointness test
for each nonterminal A in the grammar that has more than one RHS, for each pair of rules A -> ai and A -> aj, it must be true that FIRST(ai) ∩ FIRST(aj) = empty set
pairwise disjointness test on
A -> a | bB | cAb
FIRST(a) = {a}
FIRST(bB) = {b}
FIRST(cAb) = {c}
pass
pairwise disjointness test on
A -> a | aB
FIRST(a) = {a}
FIRST(aB) = {a}
fail
bottom-up parser (LR algorithm)
reads input text from left to right and produces a rightmost derivation in reverse (starts with the input and attempts to rewrite it to the start symbol)
two most common actions for bottom-up parsers
shift and reduce
shift
advances in the input stream by one symbol; that shifted symbol becomes a new node in the parse tree
reduce
applies a grammar rule to some of the recent parse trees, joining them together as one tree with a new root symbol
shift-reduce algorithm
if the input has no syntax errors, the parser continues to shift and reduce until all the input has been consumed and all of the parse trees have been reduced to a single tree representing an entire legal (valid) input
l-value of a variable
address
r-value of a variable
contents
what does x represent in the following statement?
x = 5;
the l-value or address of the variable
what does x represent in the following statement?
y = x + z;
the r-value or content of the variable y
a binding is static if
it first occurs before run time and remains unchanged throughout the program execution
static binding is also called
early binding
dynamic binding is also called
late binding
a binding is dynamic if
it first occurs during execution or can change during the execution of the program
static type binding: explicit declaration definition + example
a statement in a program that lists variable names and specifies that they are a particular data type
example: Java, C++, etc. saying int a = 5;
static type binding: implicit declaration definition
a means of associating variables with types through context (type inference) or default conventions
Example of type inference (static type binding - implicit declaration)
In C#, a variable can be declared with var and an initial value, which sets the type of the variable.
Example of default conventions (static type binding - implicit declaration)
In Perl, any name that begins with $ is a scalar, a name that begins with @ is an array, so $apple and @apple are variables with different types.
for statically typed variables, their types are
fixed for the lifetime of the unit in which they are declared (that is, you cannot change the data type)
dynamic type binding: any variable can be assigned any type value, and a variable’s type (can/cannot) change during execution
can
example of dynamic type binding (language such as Python, Ruby, PHP, etc. use it)
in Python:
a = 17
a = ‘hi’
lifetime of a variable
the time during which it is bound to a particular memory cell (how long it exists in memory)
allocation
getting a memory cell from some pool of available cells
