326 exam 1

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+ 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