326 exam 1 and Final

How do we evaluate programming languages?

Readability, writability, and reliability

What are the evaluation criteria

1) simplicity/orthogonality

2) control structures

3) data types

4) syntax design

5) abstraction support

6) expressive

7) Type checking

8) exception handling

9) aliasing

What are the 3 implementation methods

1) compilation/translation

2) interpretation

3) hybrid (both)

What’s the difference between a compiler and interpreter

Compiler: translates source program and generates an executable

Interpreter: reads a line of code, translates it, and executes the translation

What are the common types of programming paradigms

imperative and declarative

how do we precisely describe what a program is in a language

we use grammars to describe the syntax of different languages

list all the terms used to describe syntax and briefly describe them

1) Lexeme: lowest level syntactic unit of a language: *, class, sum, …

2) Token: A category of lexemes: identifies, keywords, …

3) Sentence: A stream of characters over an alphabet

What are the 2 distinct ways to define a language

recognizer (scanner) and a generator (parser)

What is a metalanguage

a language used to describe another language

Explain how BNF can be used

to create rules for any languages

why are derivations important

It shows the steps/sequence of rules that must be applied to generate a sentence of a given language

what’s a parse tree

a tree that represents a syntactically valid program/string

given a parse tree and a grammar, can we always produce a correct derivation without any mistakes

yes, but ONLY if the grammar is unambiguous

when is a grammar ambiguous

2+ DIFFERENT parse trees for the same string

How do we preserve left associativity

1) Determine the precedence of all operators

2) Write the grammar in a cascading manner

Can we prove when a grammar is ambiguous

No, but we can demonstrate it

How do we precisely describe what a program is in a language

We use grammars to desceibe the sytax of deifferent languages

What are the 2 distinct goals of parsing

1) Determine if the program/string is syntactically correct

2) Produce/generate a unique parse tree

What are the 2 types of parsing algorithms that we will study

1) top down

2) bottom up

Top Down parsing

parse tree is created from root (start) to leaves (terminals) during a Left Most derivation

Bottom Up Parsing

parse tree is created from leaf nodes (terminals) to root (start symbol during a Right Most derivation

What is a recursive descent parsing, and how is it implemented

1) A kind of top down parsing

2) One function per non terminal with one case per different RHS (for the same LHS)

Provide an example of an expression that can be parsed using a recursive descent parser

A → aA | ε

w = aaa…a

If we let G be a grammar, then what can a parser do?

It can describe whether w (input) is the language generated by a grammar

What are the rules for computing the first sets

1) If X produces a terminal a, then FIRST(X) = {a}

2) If X produces ε, then FIRST(X) = {ε}

3) If X produces a mix of terminals and non-terminals, then FIRST(X) = FIRST(Y1) U FIRST(Y2) U … excluding {ε}

What makes a grammar LL(1)

1) No left recursive rules

2) Must pass pairwise disjoint test

What is “name resolution” used for?

mapping an identifier to the actual declaration or definition the identifier corresponds to

what can be named

classes

parameters

fields

functions

local variables

global variables

packages

name spaces

files

what do we mean by “this is the scope of variable x”?

where x exists in memory

where x can be read/modified

where x is visible to the compiler

what’s the difference between static and dynamic scope

static: scope of a variable is determined at compile time by looking upwards int the code (symbol table)

dynamic: scope of a variable is determined at runtime based on the call stack

what is an activation record? How are they represented

1) a data structure used by a program during function calls

return address (caller)

arguments

local vars

registers

static/dynamic links

what is a primitive or atomic type?

simplest type provided by a language: int, float, etc

what is a constructed type?

types that are built by combining primitives and or other constructed types: arrays, structs, classes, etc.

why can’t floating point values be accurately represented in memory

because of how binary numbers represent real numbers

explain why a boolean type is not an actual type in C/C++

there isnt a special boolean register

bool is just a macro definition

what’s the difference between structs and unions

struct: stores multiple variables together, each with its own scope

union: stores only one of many vars at a time to save memory

name 4 different types of binding times and explain them

Language design time: any legal construct in the language - if(a>b){}

Language Implementation: representation of literals/values - int num = 3;

Compile time: binding happens during compilation - static double PI = 3.14

Runtime: binding happens during execution - int * ptr = new int;

at what time does the binding of a value to a variable “x” occur?

Global: during compilation

Local: during execution

what is static binding or early binding?

association of a name to a symbol (entity) at compile time

static double PI = 3.14

what is dynamic binding or late binding

association of a name to a symbol (entity) at run time

int * ptr = new int;

what does strongly typed mean? Is C++ strongly typed?

All type related errors are caught at compile time. C++ is NOT strongly typed: pointers, inheritance, and polymorphism