Section 1
Preview this deck
Interpreter
Front
| 5 | 0 | ||
| 4 | 0 | ||
| 3 | 0 | ||
| 2 | 0 | ||
| 1 | 0 |
Active users
1
All-time users
1
Favorites
0
Last updated
1 year ago
Date created
Mar 1, 2020
Cards (69)
Section 1
(50 cards)
Interpreter
executes instructions one by one (analyzing each time) Slower than compiler ex: Scheme, Python, Perl, Bash
Types
A type is a collection of values and a collection of operations on those values. ex: simple types/numbers structured types/strings,lists The type can help determine legal operations, type errors
EBNF
{} for a series of zero or more () for a list, must pick one [] for an optional list; pick one or none
All programming Languages have four properties
Syntax Names Types Semantics
BNF is less powerful than regular expressions
False
Early/Late binding
Early binding takes place at or before compile time Late binding takes place at run time
Parse tree
a hierarchical representation of a derivation
Concrete syntax
rules for writing (expressions, statements and programs) / what statements look like
Semantics
The meaning of a program is called its semantics: What does each statement mean? When a program is running, what happens to the values of the variables? What underlying model governs run time behavior?
Funcitonal
Domain/Range, functional decomposition, recursion. Mains means of computations is applying functions to parameters ex: Lisp, Scheme, ML, F#, Haskell
Production rule (P)
rule that has a left-handed side, which is a nonterminal, and a right-handed side, which is a string of terminals and or nonterminals
Associativity (Exam)
of and operator, left- or right, is determined by the use of left or right recursion, respectively.
Formal language theory is used for semantical structure of programming languages (Chomsky hierarchy)
True
Precedence (Exam)
is determined by the length of the shortest derivation from the start symbol to the operator.
Associativity
of an operator is a property that determines how operators of the same precedence are grouped in the absence of parentheses
Binding
A language element/object is bound to a property at the time that property is defined for it. A binding is the association between an object and a property of that object Ex: a variable and its type -typical bound to type during declaration a variable and its value - bound when variable define/initialized
Imperative
Central features are variables, assignment statements, and iterations. state-value, procedural abstraction ex: C, Perl, Cobol, Fortran, Ada
Ambiguous Grammar
if one of its strings has two or more different parse trees (or two or more different leftmost/rightmost derivations)
token
a category of lexemes
Regular expressions are used because they are more expressive than other common formalisms
False
Associativity of relational operators?
in c (a<b<c) means: if a<b and b<c
Regular grammar
Used in the scanner, produce tokens Used to write formal description of the token patterns (when creating the lexical analyzer - the scanner)
Precedence
The order of operations (or operator precedence) is a collection of rules that define which procedures/operations to perform first in order to evaluate a given expression.
There are programs that can generate the source code for the syntactical analyzer from a description of the grammar
True
Context-free grammar
Verify grammar, parser
Compiler
translates once, produces machine code (faster)
Hybrid Interpreter
Java: process: Source code Lexical Analyzer >>tokens Syntax Analyzer >>parse trees IC generator Interpreter results
Characteristics of successful language
Simplicity and readability Reliability, abstraction, orthongonality, Efficient Implementation
Translation to native code can be done after execution begins
True
Nonterminals (N)
Abstractions used to represent classes of syntactic structures
Interpreter process
Source program Interpreter result
Abstract syntax
internal representation (deep structure); carries only essential information, without concern for syntactic idiosyncrasies like punctuation or parentheses
Norm Chomsky's Grammar
regular grammar (weakest) context-free context-sensitive unrestricted (Strongest)
Backus-Naur Form
stylized context-free grammar. Used to define syntax of most languages
Binding can occur during....
language-definitions Implementation writing compilation execution
Compiled programs
Fortran, cobol, C, C++, Ada, Pascal
There are programs that can generate the source code for the lexical analyzer from a description of the tokens
True
Object-Oriented
data abstraction (Encapsulation, inheritance, polymorphism) Collection of objects that interact by passing messages that transform the state. ex: java, C++, C#, Python, smalltalk
Lexical Syntax
Symbols of the language (all the basics)/the vocabulary of the language names, values, operators etc.
Logic
Rule-based(rules are specified in no particular order) Facts, constraints, and queries, all solution, nondeterministic ex: prolog
lexeme
the lowest level syntactic unit of a language
A program run via an interpreter runs faster than a compiled program
False
Simplicity and orthogonality
Few constructs, a small number of primitives, a small set of rules for combining them
Terminals (T)
Lexemes (tokens)
Names/Entities
Various entities in a program have names: variables, types, functions, parameters, classes, objects... Entities have four basic bindings; scope, visibility, type, lifetime
Programming Paradigms
Imperative Object Oriented Functional Logic
Syntax
The syntax of a programming language is a precise description of all its grammatically correct programs
Dangling else (How is it solved?)
external rule: match w/ closest if (C, Algol60,C++) add delimiter to language such as EndIf (Ada, Visual Basic, Bash, Csh) enforce in grammar (complex BNF) rule- no shortIf (java)
Compiler diagram
Source Code Lexical Analyzer >>tokens (Symbols table) Syntax Analyzer >>Parse tree Type Checker >>IC Code optimizer >>IC Code generator Executable
Levels of Syntax
Lexical syntax Concrete Syntax Abstract Syntax
Section 2
(19 cards)