CISS 445 - Programming Languages - Test #1

• Readability
• Writeability
• Reliability

• programmer training
• writing cost
• compiling
• executing
• development environment cost
• maintenance
• program failure cost

A relatively small set of primative constructs can be combined in a relatively small number of ways to build the control and data structures of the language. Furthermore, every possible combination of primatives is legal and meaningful.

Having more than one way to accomplish a particular operation.

Having two or more distinct names that can be used to access the same memory cell.

• Imperative Programming Languages are the "Classic" languages. Each statement executed one at a time in an order determined by the programmer. Includes object oriented (C++ Java..), visual languages (.NET), scripting languages (PERL, JavaScript, Ruby..)
• Non-Procedureal Programming Language are the Data oriented program design methodology emphasizes data design, focusing on the use of abstract data types to solve problems.

• compiler
• interpreter
• hybrid

• Initially translate program to intermediate language.
• During execution, compile each intermediate method code into machine code the first time it is called.
• Saves generating machine code for parts of the source program that are never called.

The first compiled high-level language -- tremendously increased use of computers in 1950s-1960s and still dominates scientific programming.

Designed for Artificial Intelligence (AI) applications -- pioneered functional languages (all computation accomplished by applying functions to arguments).

Introduced the "run-time stack" to handle stack-dynamic variables, and this affected subsequent computer architecture (machine language) to support a system stack.

Was the most used programming language ever, leading the electronic mechanization of accounting starting in the 1960s.

A teaching language at Dartmouth -- first language to consider user time more important than computer (CPU) time.

Tried to handle both scientific and business applications, so it had very many features.

Pioneered dynamic typed variables (a variable acquires a data type and is allocated memory when it is assigned a value).

Used "orthogonality" as it's primary design criteria. Affected future languages even though ALGOL 68 was never widely used.

Most popular teaching language of the 1970s-1990s, taught students to use "structured programming" concepts (Fortran & Basic didn't teach structured programming).

First high-level language used to write an operating system kernel (UNIX).

Still the premiere non-procedural language, based on formal logic.

Pioneered data abstraction (packages), generic subprograms, and concurrent execution.

The first fully object oriented language, having all 3 OO concepts: data abstration, inheritance, dynamic method binding.

Added Object Oriented programming to C while maintaining C's performance and backward compatibility with C.

Object Oriented derived from C++, but removed many unsafe features, making it simple enough for small computers (cell phones, routers, tablets).

• Designed for web-programming (creating the behavior of web-sites).
• These web languages provide features that make it easier to program smaller web programs, at the expense of execution speed and error detection.

• The form of a programming language's expressions, statements, and program units.
• In a "natural language", like English, it's the form of nouns, verbs, subject, object, etc., required to make grammatically correct sentences.
• English has a continually evolving complex set of "grammar rules" (you learned them in grade school English class) for specifying syntactically correct sentences.
• A "formal language", such a programming language, by comparison, is syntactically simple, specified by a fixed simple set of grammar rules.

The meaning of the expressions, statements, and program units of the programming language's syntax.

• A string of characters taken from some alphabet.
• A sentential form that has only terminal symbols.

• The lowest-level syntactic units, including numeric literals, operators, special words, etc.
• A word or punctuation mark in English or '*', IF, FOR,... in C++.

• A category of related lexemes.
• For example: a noun or verb or other part of speech in English.
• An identifier or operator or constant (literal) in C++.

• A device that reads input strings and decides whether the input strings are "legal" in the language.
• Diagramming English sentences in grade school.
• Syntax analysis part of a compiler.

A device that can generate all the syntactically correct sentences of a language.

Every string of symbols in a derivation is a sentential form.

The words in a sentence.

• The parts of speech and other grammatical parts of a sentence (noun, adjective, subject, verb, object,...).
• Are enclosed in <angle brackets>.

Generates a sentential form that has two or more distinct parse trees.

Generates a sentential form that has only one unique parse tree.

• Is only indirectly related to the meaning of programs during execution; rather, it has to do with the legal forms of programs (syntax rather than semantics).
• Typically state a languages type constraints.
• So named because the analysis required to check these specifications can be done at compile time.

• Attributes for each symbol
• Functions (a.k.a semantic rules) for each syntax rule
• Boolean predicates for each rule

• To enforce a language's data-type rules in expressions and assignments.
• To enforce a language's context-sensitive rules such as requiring variables to be declared before they are used.

• Lexical analysis -- recognizes the "lexemes" in a character string source program and returns the associated "tokens", one after another.
• Syntax analysis (parser) -- Uses the grammar rules to create the derivation or parse tree from the tokens or lexemes returned by the lexical analyzer.

• Both types of parsers use one token look-ahead in order to make the correct choice of which grammar rule to apply.
• The RECURSIVE-DESCENT top-down parsing algorithm uses a function to handle each nonterminal.
• LL parser is a top-down parser that scans the input string Left-to-right and constructs a Leftmost derivation.
• Direct or indirect left recursion in grammar rules makes the grammar unusable by a LL parser.

• Disjoint in this context means that:
• For each "non-terminal", <A>, in the grammar that has more than one RHS, the first "terminal" symbol that can be generated for each of the RHSs must be unique to that RHS.

• The following example PASSES:
• <A> -> aB | bAb | Bb
• <B> -> cB | d

• Therefore <A> -> aB, the first "terminal" is {a}
• Therefore <A> -> bAb, the first "terminal" is {b}
• Therefore <A> -> Bb, the first "terminal" symbol that can be generated is {c, d} because:
• <B> -> cB, the first "terminal" is {c}, and
• <B> -> d, the first "terminal" is {d}, thus
• the set {c, d} for the third RHS of <A>.
• Because each RHS of <A> is unique to each other RHS, the grammar is therefore "disjoint" and PASSES the test.

The following example FAILS:

• <A> -> aB | BAb
• <B> -> aB | b

• Therefore <A> -> aB, the first "terminal" is {a}
• Therefore <A> -> BAb, the first "terminal" symbol that can be generated is {a, b} because:
• <B> -> aB, the first "terminal" is {a}, and
• <B> -> b, the first "terminal" is {b}, thus
• the set {a, b} for the second RHS of <A>.
• Because both sets of each RHS include {a}, the grammar is "not disjoint" and FAILs the test.

A bottom-up parser that scans input string Left-to-right and constructs a Rightmost derivation.

At any step in a bottom-up parse, the HANDLE is the correct sub-sequence of symbols in this step's sentential form that corresponds to the RHS of some grammar rule to apply (backwards), producing the correct next sentential form in the parse.

• Maintain a "stack" of (state,symbol) pairs (initially push state 0).
• Select an entry in the ACTION table based on the top state in the stack and the next input symbol.
• The ACTION table entry tells the parser to either SHIFT (push another pair onto the stack), or REDUCE (apply a grammar rule and advance to the next input token).
• When REDUCing, the GOTO table entry tells the parser what state to push onto the stack.
• The tables are automatically generated from Knuth's algorithm.

• Name
• Address
• Value
• Type
• Lifetime
• Scope

The time at which an attribute is associated with a variable (or other program entity).

Associating a data-type with a variable.

• EXPLICIT type declaration: A program statement is used for declaring the types of variables. An advantage is that the Programmer is in control of the declaration. A disadvantage is that if the Programmer does not declare the variable type explicitly then the compiler will implicitly declare the type, possibly incorrectly.
• IMPLICIT type declaration: Type specified through default conventions rather than declaration statement. A minor advantage is that it is easily writable. A disadvantage is that they can be detrimental to reliability because they prevent the compilation process from detecting some typographical and programmer errors.

• Used in JavaScript, Python, Ruby, PHP, C#(limited).
• Advantages: flexibility (generic program units, what C++ calls Templates).
• Disadvantages: High run-time cost (dynamic type-checking and interpretation), and type-error detection by compiler is difficult.

• Memory allocated before run-time and remains throughout execution.
• Most efficient, but disallows recursive functions.

• Memory allocared/freed on system stack during run-time.
• Allows recursion & conserves storage, but less efficient than static.
• Functions can't be "history sensitive".

• Programmer statements (new/delete) allocate/free memory from the "heap".
• Flexable storage management, but not as efficient as stack dynamic.
• Error prone.

• Allocate/free memory caused by assignment statements.
• Very flexible, but highest run-time costs.

Local Variable: Those declared in a program unit.

Non-Local Variable: Variables visible in a program unit but not declared there.

Global Variable: Certain nonlocal variables that are potentially available to all subprograms, even between separate compilations.

• Static Scope:
• - Based on program text.
• - To connect a name reference to a variable, you or the compiler must find the declaration.
• - Search declarations first locally, then in increasingly larger enclosing scopes, until a declaration is found for the given name.

• Dynamic Scope:
• - Scope based on calling sequence of subprograms, not their textual layout.
• - To determine which variable is referenced, search back through the chain of subprogram calls rather than searching through static blocks.

• Blocks allow a section of code to have its own local variables whose scope is minimized.
• This allows new Static Scopes to be defined in the midst of executable code.

• Usually too much access is possible.
• Scope changes as program structure evolves.

• Convenient for programmers.
• Static type checking impossible.
• Poor readability.

• Lifetime is the duration of the variable in memory.
• Scope is the boundary of variables visiblity.

The collection of all names visible to that statement.