Brainscape's Knowledge GenomeTM

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


See full index

CSCI 3210: Theory > Test 1 > Flashcards

Test 1 Flashcards

1
Q

Why Study Theory of Programming Languages?

A
  1. Increased Capacity to express ideas
  2. Improved background for choosing languages that are appropriate
  3. Increased ability to learn about new languages
  4. Better understanding of implementation
  5. Better use of languages that are known
  6. Overall advancement of computing
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the three Language Evaluation Criteria ?

A

Readability, Writability, Reliability

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

Readability

A
  • How easy it is for others to read and follow development and work on it.
    1. Simplicity:
    • # of language features to provide
    • Minimal Feature Multiplicity
    • Minimal Operator Loading/overloading (provides flexibility, if
      used appropriately makes it easier to understand)
  1. Orthogonality:
    • Every possible combination is meaningful combinations
    • Exceptions: In c++ cant make function return array &
      arrays are passed to functions by reference not value
    • The more orthogonal the design of a language, the fewer exceptions the
      language rules require.
    • Too much orthogonality can lead to unnecessary complexity.
  2. Data Types:
    • The presence of adequate facilities for defining data types and data structures
  3. Syntax Design:
    • Effects readability -> special words & compound statements
    • semantics depend on syntax **. ( statements’ appearance should indicate their purpose)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Writability

A
  • Same as readability
  1. Abstraction:
    • Procedure Abstraction (functions or simple procedures)
    • Data Abstraction (Classes & Objects)
  2. Expressivity:
    • How powerful & convenient to specify a computation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Reliability

A
  • Features the program provides to make it more reliable
  • All factors of Readability & Reliability
  1. Type Checking:
    • happens at compile time or runtime
  2. Exception Handling:
    • program deals with exceptions
  3. Aliasing:
    • two or more distinct names used to access same memory cell
    • VERY DANGEROUS
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Cost

A

Three most important contributors to language costs:

 1. Program Development
2. Maintenance
3. Reliability
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Other Criteria used for Evaluation Programming Languages

A
  1. Portability:
    • ease with which programs can be moved from one implementation to another
  2. Generality:
    • applicability to a wide range of applications
  3. well-definedness:
    • Completeness & precision of lang. definition
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How are design criteria weighted differently from different perspectives?

A
  • Language implementors:
    ->difficulty of
    implementing the constructs and features of the language
  • Language Users:
    • > writability first and readability later

-Language designers:
-> emphasize elegance and the ability
to attract widespread use.

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

What are the three Language design trade-offs?

A
  1. Reliability vs. Cost of Execution
  2. Readability vs. Writability
  3. Writability (flexibility) vs. Reliability
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Reliability vs. Cost of Execution

A

Java demands all references to array elements be checked for proper
indexing, which leads to increased execution costs

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

Readability vs. Writability

A

APL provides many powerful operators (and a large number of new
symbols), allowing complex computations to be written in a compact program but
at the cost of poor readability

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

Writability vs. Reliability

A

C++ pointers are powerful and very flexible but are unreliable

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

What are the two Language Categories?

A

Declarative and Imperative Languages

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

Declarative Languages

A

Focus on WHAT the computer is to do

-Higher level
-In tune with the programmer’s point of
view

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

Imperative Languages

A

Focus on HOW the computer should do it

-Predominate

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

What are three types of Declarative Languages?

A

Functional:
- employ a computational model based
on the recursive definition of functions.
- FL, ML, Haskell

Dataflow:
- model computation as the flow of information (tokens)

Logic or Constraint-Based languages

 - prolog
 - find values that satisfy certain specified relationships
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are the three types of imperative languages?

A

Von Neumann:

 - statements (assignments in particular) that influence subsequent computation
 - most familiar and successful

Scripting:

 - Subset of von neumann
 - distinguished by their emphasis on ”gluing together” components that were originally developed as independent programs

Object-oriented:

 - closely related ^ 
 - Have more structured and distributed model of memory and computation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are the three general methods that programming languages can be implemented by?

A
  1. Compilation:
    • Programs are translated into ML
    • Use: large commercial applications
  2. Pure Interpretation:
    • Programs interpreted by another program known as an interpreter
    • Use: Small programs / efficiency is not an issue
  3. Hybrid Implementation Systems:
    • A compromise between compilers and pure interpreters
    • Use: Small & medium systems when efficiency is not a first concern
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Compilation

A
  • Translate high-level language to ML
  • Slow translation, fast execution
  • Phases:
    1. Lexical Analysis:
      • characters to lexical units
    2. Syntax Analysis:
      • lexical units to parse trees (syntactic
        structure)
    3. Semantics Analysis:
      • generate intermediate code
    4. Code Generation:
      • machine code generated
  • Load Module:
    • user and system code together
  • Linking and Loading:
    • Collect program units & link them to
      user program
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

von Neumann bottleneck

A

the primary limiting factor in computer speed

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

Pure Interpretation

A
  • No translation
  • Easier implementation (runtime errors immediately displayed)
  • Slower execution
  • Needs more space
  • Rare for traditional high-level languages
  • JavaScript, PHP
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Hybrid Implementation Systems

A
  • High level language –> intermediate language –> easy interpretation
  • Faster than pure interpretation

-Perl programs –> partially compiled to
detect errors before interpretation

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

Just-in-time implementation Systems

A
  • Translate programs to an intermediate language
  • Intermediate lang –> machine code
  • Machine code kept for subsequent calls
  • Java Programs, .NET languages

(Delayed Compilers)

24
Q

Token

A
  • Represents a lexical unit
  • a pair of a token name and attribute value
  • Defined Tokens:
    1. String Literal
    2. Identifiers
    3. Comment
    4. Punctuation
    5. Integers, numbers
    6. Key words
    7. Plus, Minus
25
Q

Lexeme

A
  • Sequence of characters in a program that matches the pattern for a token.
  • Lowest level syntactic unit
26
Q

Regular Expressions

A

Specifies a Token Pattern

RE is always defined over a set of symbols called alphabet (Σ)

Each symbol in alphabet is a RE

epsilon (ϵ) –> empty string (not in alphabet)

27
Q

What are the operators to construct more complicated RE?

A
  1. Choice | (lowest precedence)
  2. Concatentation –> ab == “ab”
  3. Repetitions (highest precedence) –> (a|b)* == ( (a|b) )*
28
Q

What are some RE extentions?

A 
r+ = rr* 
r*
r? = (ϵ|r)
r{n} = r{2} = rr
{a,b,c] = a | b | c
[0-9] = (0 | 1 | 2 | 3 | ... 9)
[abj - oZ] = ab[j-o]Z
[ˆabc] means any character except a, b, or c

^r matches a r, but only at the beginning of a line.

r$ matches a r, but only at the end of a line.

29
Q

Algebraic laws for regular expressions

A

..

30
Q

Context Free Grammars

A
  • Specifies language syntax
  • Define a class of languages called context-free
    languages
  • Noam Chomsky in the mid-1950s
31
Q

What is BNF?

A

Backus-Naur Form (1959)

  • CFG = BNF
32
Q

What are BNF Fundamentals?

A 
Nonterminals:
     - act like syntactic 
     variables
     - represent classes of 
     syntactic structures

Terminals:
- Lexemes or tokens

33
Q

A Rule or Production

A

LHS - > RHS

LHS: always a nonterminal
RHS: terminals and/or non

34
Q

Grammar

A

a finite non-empty set of rules

Has a nonterminal as the start symbol

35
Q

Derivation

A

-A derivation is a repeated application of rules, starting with the start symbol
and ending with a sentence (all terminal symbols)

  • Any string derived from the start symbol is a sentential
    form.

-

36
Q

A Language

A

The set of sentential forms containing only terminal symbols.

37
Q

Parse Tree

A

A labeled tree representation of a derivation that filters out the order in which productions are applied to replace nonterminals.

Gives structural representation of a program

  • Interior nodes: non terminals
  • Leaf node: terminals
38
Q

Ambiguity

A

if grammar generates two or more distinct parse trees

  • Problem: compilers often base the semantics of those
    structures on their syntactic form.
39
Q

How to solve ambiguity?

A
  • Rewrite CFG
  • Introduce rules to specify which tree is preferred
    (PRECEDENCE)
40
Q

EBNF

A

Three extentions:

 - Option
 - Alternation
 - Repetition

metasymbols added ( notational tools, not terminal symbols)

41
Q

EBNF: Option

A

[ ]

42
Q

EBNF: Alternation

A

( * | \ | % )

43
Q

EBNF: Repetition

A

{, }

44
Q

Static Semantics

A

CFGs cant describe all syntax of prog. lang.
( type compatible, declaring vars before usage, wrong arguments in funct. call, redefinition of ident. )

Defines restrictions on the
structure of valid texts that are hard or impossible to
express

45
Q

Attribute Grammar

A

Device used that describes structure of prog lang.

Have additions to CFGs

Primary Value:

 - Static semantic specification
 - Compiler design (SS checking)
46
Q

Dynamic Semantics

A
  • Behavior of program
  • Result & output expected

3 Common Methods:

  • Operational
  • Denotational
  • Axiomatic
47
Q

Operational Semantics

A
  • executing program’s statements on a machine ( stimulated or actual)
  • change of machine state –> defines statement meaning
  • To use:
    High-Level Lang –> virtual machine needed
  • Better Alternative: complete computer simulation
    • Build translator ( source code –> machine code)
    • build simulator
    • Good if used informally
48
Q

What are the uses of Operational Semantics?

A
  • Language manuals and textbooks

- Teaching programming languages

49
Q

What are the two different levels or uses of Operational Semantics?

A
  • Natural Operational Semantics: At the highest level, the interest is in the final result of the execution of a complete program
  • Structural operational semantics: At lowest level, through a complete sequence of state changes when program is executed, the precise meaning is determined
50
Q

Denotational Semantics

A

Formal method for describing meaning of program

Most abstract semantics description method

Mapping each language construct to a math function

Defined based on state of program

State of Program –> values of all variables existing in program

51
Q

What is the evaluation of Denotational Semantics?

A

Can be used to prove correctness of program

Provides a rigorous way to think about programs

Can be an aid to language design

Has been used in compiler generation systems

Because of its complexity, it is of little use to language
users

52
Q

Axiomatic Semantics

A

Based on formal logic

Axioms or inference rules are defined for each
statement type in the language

The logic expressions are called assertions

Original purpose: formal program verification

If program satisfies precondition, it should always satisfy post-condition after execution

If input meets precondition, will always meet post-condition

TO USE:
- Must have a set of inference rules

53
Q

What is the evaluation of Axiomatic Semantics?

A

Developing axioms or inference rules for all of the
statements in a language is difficult

It is a good tool for correctness proofs, and an excellent framework for reasoning about programs, but it is not as useful for language users and compiler writers

54
Q

What is an Inference Rule?

A

A method of inferring the truth of one assertion on the basis of the values of other assertions.

55
Q

What is an Axiom?

A

A logical statement that is assumed to be
true.

Therefore, an axiom is an inference rule without
an antecedent.

CSCI 3210: Theory (1 decks)

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