Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

comp lang > module 1 > Flashcards

module 1 Flashcards

1
Q

what are the categories of language evaluation criteria?

A
  • readability
  • writability
  • reliability
  • cost
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

what are languages developed around?

A

Von Neumann architecture

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

linking and loading

A

process of collecting system program units and linking them to a user program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

pure interpretation

A
  • no translation
  • easier implementation of programs
  • slower execution
  • often requires more space
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

hybrid implementation systems

A
  • high-level language program is translated to an intermediate language and allows easy interpretation
  • faster than pure interpretation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

syntax

A

form or structure of the expressions, statements, and program units

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

semantics

A

the meaning of the expressions, statements, and program units

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

sentence

A

string of characters over some alphabet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

language

A

set of sentences

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

lexeme

A

lowest level syntactic unit of a language

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

token

A

category of lexemes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

recognizer

A

reads input strings over the alphabet of the language and decides whether the input strings belong to the language

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

generator

A

device that generates sentences of a language

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

context-free grammar

A

Language generators, meant to describe the syntax of natural languages

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

backus-naur form

A

BNF is equivalent to context-free grammars
Invented by John Backus to describe the syntax of Algol 58

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

grammar

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

ambiguous grammar

A

A grammar is ambiguous if and only if it generates a sentential form that has two or more distinct parse trees

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

attribute grammar

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

dynamic semantics

A

There is no single widely acceptable notation or formalism for describing semantics

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

operational semantics

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

denotational semantics

A

The meaning of language constructs are defined by only the values of the program’s variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

expression

A

expressions are decimal numbers, variables, or binary expressions with one arithmetic operator and two operands, each of which can be an expression

32
Q

axiomatic semantics

A

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
Q

weakest precondition

A

the least restrictive precondition that will guarantee the postcondition

34
Q

loop invariant

A

a property of a program loop that is true before each iteration

35
Q

benefits of using BNF

A

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
Q

2 parts of syntax analysis

A
  • lexical analyzer
  • syntax analyzer (parser)
37
Q

why are lexical and syntax analysis separated?

A
  • simplicity (separation simplifies the parser)
  • efficiency (separation optimizes lexical analyzer)
  • portability (parser)
38
Q

what is a lexical analyzer

A
  • a pattern matcher for character strings
  • a “front-end” for the parser
  • Identifies substrings of the source program that belong together - lexemes
39
Q

lexer responsibilities

A

•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
Q

dynamic scoping

A

bindings depend on the flow of execution during run time
refers to the most recently declared variable

41
Q

static scoping

A

bindings based on purely textual rules
refers to the highest level declaration of a variable.

42
Q

the longest possible token rule

A

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
Q

what are the 3 ways scanners are built

A

§ Ad-hoc (fastest and most compact)
§ Semi-mechanical pure DFA (usually as nested case statements)
§ Table-driven DFA (produced by antlr)

44
Q

lexer rules

A

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
Q

actions

A

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
Q

token attributes

A

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
Q

2 categories of parsers

A
  • 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
Q

what are the 2 most common top down parsers

A
  • recursive descent
  • LL parser (antlr)
49
Q

what are the 2 most common top down parsers

A
  • recursive descent
  • LL parser (antlr)
50
Q

2 most important classes of grammars

A

LL
- left to right, leftmost derivation
- top-down
- predictive
LR
- left to right, rightmost derivation
- bottom-up
- shift-reduce

51
Q

pairwise disjointedness

A

The inability to determine the correct RHS on the basis of one token of lookahead

52
Q

binding

A

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
Q

reserved word

A

a special word that cannot be used as a user-defined name

54
Q

keyword

A

word that is special only in certain contexts

55
Q

variable

A

an abstraction of a memory cell

56
Q

type

A

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
Q

value

A

the contents of the location with which the variable is associated

58
Q

abstract memory cell

A

the physical cell or collection of cells associated with a
variable

59
Q

static

A

objects are given an absolute address that is retained throughout the program’s execution

60
Q

stack

A

objects are allocated and deallocated in last-in, first-out order, usually related to subroutine calls and returns

61
Q

heap

A

objects allocated and deallocated at arbitrary times

62
Q

garbage collection

A

identifies and reclaims unreachable objects

63
Q

explicit deallocation vs implicit deallocation

A

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
Q

scope of a variable

A

range of statements over which it is visible

65
Q

scope of a variable

A

range of statements over which it is visible

66
Q

local vs nonlocal variables

A

local: those that are declared in that unit
nonlocal: those that are visible in the unit but
not declared there

67
Q

ambiguous grammar

A

you have a symbol that appears twice on the right side and once on the left side

68
Q

elaboration

A

process by which declarations become active when control first enters a scope

69
Q

referencing environment

A

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
Q

how to calculate leftmost derivation?

A

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
Q

pairwise disjointness test

A

pick the farthest left character for each statement, if the characters from each statement are the same, they fail the test

72
Q

recursive descent parser trace

A

next token is: # Next lexeme is a
Enter
Enter
Enter
…

73
Q

3 variations of imperative language group

A

von neumann, object-oriented, scripting languages

74
Q

2 variations of declarative language group

A

functional, logic-based

75
Q

difference between lifetime and scope

A

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
Q

order of programming methodologies utilized

A

machine efficiency
structured programming
process-oriented
object-oriented

comp lang (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions