Studied by 0 people
Looks like no one added any tags here yet for you.
_____ is a first machine-independent language and first language whose syntax was formally defined (BNF)
Algol
______ is the evaluation criteria for the ease with which programs can be read and understood
Readability
______ is for the evaluation criteria for the ease with which a language can be used to create programs
Writability
______ is for the evaluation criteria for the conformance to specifications (i.e., performs to its specifications)
Reliability
______ is for the evaluation criteria for the ultimate financial consideration
Cost
If each feature of a language can be used in conjunction with all other features, this is about
Orthogonality
_____ governs the rule of programming language and grammar.
Syntax
_____ governs the execution or meaning of each feature in a language.
Semantics
One of the Functional languages is _______
Lisp
One of the logic languages is ______
Prolog
Today's most programming languages are _______, to be contrasted with declarative languages.
Imperative
A program, which converts a program in some language into an executable program, is called by _______ or translator.
Compiler
what two common data structures were included in Plankalkül?
Arrays, records, and nested records
what was the primary application area of computers at the time Fortran was designed?
Scientific
what was the most significant feature added to Fortran I to get Fortran II?
Independent compilation for user defined subprograms
which version of Fortran was the first to have character handling?
Fortran 77
in what way are scheme and common lisp opposites to each other?
Common LISP allows for static scoping and dynamic scoping Scheme only uses static scoping. Scheme is relatively small while Common LISP is large and complex.
on what programming language was Cobol based?
FLOW-MATIC
P/I was designed to replace what two languages?
FORTRAN /COBOL
what language introduce the case statement?
Fortran 90
what design criterion was used extensively in ALGOL 68?
Orthogonality
what are two kinds of statements that populate a prolog database?
Facts, Rules
what populates the Small talk world?
Objects, from integer constants to large complex software system
what Ada construct provides support for abstract data type?
Packages provide the means for encapsulation data objects, specification for data types, and procedures
what do Ada and Cobol languages have in common?
DOD
What dialect of lisp is used for introductory programming courses at some universities?
Scheme
A(n) _____ is a string of characters over some alphabet.
Sentence
A(n) ____ is a set of sentences
Language
A(n) _____ is the lowest level syntactic unit of a language (e.g., +, *, 123, ...).
Lexeme
A(n) _____ is a category of lexemes (e.g., identifier)
Token
Context-Free Grammars is developed by ____ in the mid-1950s.
Noam Chomsky
In BNF, a rule has a left-hand side (LHS), which is/are _____
nonterminal
A(n) ____ is a sentential form that has only terminal symbols
Sentence
Leftmost derivation is used in ____ parsing.
LL
The following grammar is ambiguous.
Which one of the following grammar is equivalent to this grammar but not ambiguous?
Which one of the following statements is NOT correct? For an attribute grammar, ___
An attribute can be inherited but not synthesized.
The "disassemble" Lisp function provides an ____ semantics of a program.
operational
Consider the following analysis of a program, as discussed in the class.
{...} a = b + 1 {a > 1}
Looking at post-condition of { a > 1} after execution of (a=b+1). Its weakest precondition is ___.
{b > 0}
Compute the weakest precondition for each of the following assignment statement and postcondition: a = 2 * (b - 1) - 1 {a > 0}
b > 3 / 2
] Compute the weakest precondition for each of the following assignment statement and postcondition: b = (c + 10) / 3 {b > 6}
c > 8
Compute the weakest precondition for each of the following assignment statement and postcondition: a = a + 2 * b - 1 {a > 1}
b > 1 - a / 2
Compute the weakest precondition for each of the following assignment statement and postcondition: x = 2 * y + x - 1 {x > 11}
2 * y + x > 12
A grammar is ____ if and only if it generates a sentential form that has two or more distinct parse trees
ambiguous
The meaning of language constructs are defined by only the values of the program's variables. That is, the state of a program is the values of all its current variables.
denotational semantics
____ describes the meaning of a program by executing its statements on a machine, either simulated or actual.
operational semantics
_____ is a logic expression in Axiomatic Semantics
assertion
_____ is an assertion before a statement stating the relationships and constraints among variables that are true at that point in execution
precondition
_____ is an assertion following a statement which states the relationships and constraints among variables that are true after that point in execution
postcondition
_____ is lexeme or token, and shows only in right-hand side of a grammar rule.
terminal
_____ is the least restrictive precondition that will guarantee the postcondition.
weakest precondition
_____ is the meaning of the expressions, statements, and program units.
semantics
_____ semantics is based on formal logic (predicate calculus)
axiomatic
_____ semantics is the semantics based on recursive function theory
denotational
_____, which is also called (or in) BNF, is the most common approach for describing syntax.
context-free grammar
Consider the formal definition of context free grammars by Noam Chomsky where a grammar <Σ, N, P, S> consists of four parts where the first component is a finite set Σ of ________, the alphabet of the language, which are assembled to make up the sentences in the language.
Terminal symbols
Consider the formal definition of context free grammars by Noam Chomsky where a grammar <Σ, N, P, S> consists of four parts where the second component is a finite set N of ________, each of which represents some collection of subphrases of the sentences.
Nonterminal symbols
Consider the formal definition of context free grammars by Noam Chomsky where a grammar <Σ, N, P, S> consists of four parts where the third component is a finite set P of _______ that describe how each nonterminal is defined in terms of terminal symbols and nonterminals.
Production rules
Consider the formal definition of context free grammars by Noam Chomsky where a grammar <Σ, N, P, S> consists of four parts. The choice of _______ determines the phrases of the language to which we ascribe meaning.
Nonterminals
Consider the formal definition of context free grammars by Noam Chomsky where a grammar <Σ, N, P, S> consists of four parts where the fourth component is a distinguished nonterminal S, the _____, that specifies the principal category being defined—for example, sentence or program.
Starting symbol
Consider the following the notation for a grammar rule:
The symbol ("
The following expr grammar is ____.
ambiguous
The following grammar is an example of _____.
[1].actual_type ← lookup (A)
[2].actual_type ← lookup (B)
[1].actual_type =? [2].actual_type
attribute grammar
Define a left recursive grammar rule
LHS appears in its RHS
Descibe the operation of a genral language language generator
generates sentences of a language
Descibe the operation of a genral language language recognizer
reads input strings over the alphabet of the language and decides whether the input strings belong to the language
what are three extensions to most EBNF?
1• Optional parts are placed in brackets [ ]
2• Deals with multiple choice options. The options are placed in parentheses and separated by OR operator
3• Repetitions (0 or more) are placed inside braces { }
What is a prediate transformer function?
to state the static semantic rules of the language; associated with grammar rule
what is the precondition of a given statement in axiomatic semantic?
An assertion before a statement (a precondition) states the relationships and constraints among variables that are true at that point in execution
what is the postcondition of a given statement in aximatic semantic?
An assertion following a statement is a postcondition describes a new condition of those variables after execution of statement
what is statis semantic?
Static sematics is only indirectly related to the meaning of the program; rather, it has to deal with the legal forms of programs. Static semantic is so named because the nalyisis can be done during compile time.
what is dynamic semantic?
Meaning of expression, statements and program units
Given the following Grammar, answer the following questions.
expr : term ( ( PLUS | MINUS ) term )* ;
term : factor ( ( MULT | DIV ) factor )* ;
factor : INT ;
PLUS : '+' ;
MINUS : '-' ;
MULT : '*' ;
DIV : '/' ;
INT : '0'..'9'+ ;
What are the terminal symbols?
+, -, *, /, [0,..,9]+
Given the following Grammar, answer the following questions.
expr : term ( ( PLUS | MINUS ) term )* ;
term : factor ( ( MULT | DIV ) factor )* ;
factor : INT ;
PLUS : '+' ;
MINUS : '-' ;
MULT : '*' ;
DIV : '/' ;
INT : '0'..'9'+ ;
What are the nonterminal symbols?
expr, term, factor, PLUS, MINUS, MULT, DIV, INT
Given the following Grammar, answer the following questions.
expr : term ( ( PLUS | MINUS ) term )* ;
term : factor ( ( MULT | DIV ) factor )* ;
factor : INT ;
PLUS : '+' ;
MINUS : '-' ;
MULT : '*' ;
DIV : '/' ;
INT : '0'..'9'+ ;
is the grammar recursive? Why?
No, because LHS doesn't appear at RHS
Which one of the following statements is CORRECT?
For bottom-up parsing, the parsing problem is finding the correct RHS in a(n) ____ form to reduce to get the previous ____ form in the derivation
right-sentential
Which one of the following choices is CORRECT?
b is the ___ of the right sentential form g=abw if and only if S =>*rm a A w =>rm a b w.
handle
Which one of the following choices is CORRECT?
b is a(n) ___ of the right sentential form g if and only if S =>* g = a1 A a2 =>+ a1 b a2
phrase
Which one of the following choices is CORRECT?
b is a simple phrase of the right sentential form g if and only if S =>* g = a1 A a2 => a1 b a2
simple phrase
input onto the parse stack or reduces the handle that is on top of the stack.
LR
Every parser for a context-free programming language is a ____, because this is a recognizer for a context-free language.
push-down automaton
For CFG, parsers that work for all unambiguous grammars have complexity ____ in general.
O(n^3)
LR parsers use two parsing tables: action and ____.
goto
Most compiler uses an efficient parser to implement syntax analyzers for programming language, working on subclasses of unambiguous grammars, and having complexity ___.
O(n)
Some grammars that fail the pairwise-disjointness test often can be modified to pass it, using ____.
left-factoring
Syntax analyzers are either ____, meaning they construct leftmost derivations and a parse tree in top-down order, or ____, in which case they construct the reverse of a rightmost derivation and a parse tree in bottom-up order.
top-down, bottom-up
The ____ part in LR parser specifies what the parser should do, given the state symbol on top of the parse stack and the next token of input.
action
The ____ table in LR parser is used to determine which state symbol should be placed on the parse stack after a reduction has been done.
goto
The original LR algorithm was designed by ____ in 1960's.
Knuth
The top symbol on the LR parse stack is always a ____ symbol that represents all of the information in the parse stack that is relevant to the parsing process.
state
Two distinct grammar characteristics prevent the construction of a recursive-descent parser based on the grammar. One is _____.
left recursion
Two goals of syntax analyzers are: (1) to detect syntax errors in a given program and (2) to produce a/an _____.
parse tree
_____ is a pattern matcher that isolates the small-scale parts (of a program) which are called lexemes.
lexical analyzer
_____ is normally based on a formal syntax description of the language being implemented.
syntax analysis
_____ parser is an LL parser that is implemented by writing code directly from the grammar of the source language. EBNF is ideal as the basis for this type of parsers and much easier and simpler to implement.
recursive-descent
_____, which is also called (or in) BNF, is the most common approach for describing syntax.
context-free grammar
LR parsers use two parsing tables: action and ____.
goto
Some grammars that fail the pairwise disjointness test often can be modified to pass it, using ____.
left-factoring
The ____ part in LR parser specifies what the parser should do, given the state symbol on top of the parse stack and the next token of input.
action
The top symbol on the LR parse stack is always a ____ symbol that represents all of the information in the parse stack that is relevant to the parsing process.
state
What is a state transition diagram?
Directed graph; nodes are labeled state name; arcs are labeled input characters cause transition among states
