PPL Flashcards

Generator for Regular Class

Regular expression

Recognizer for Regular Class

Finite automata

Generator for Context-Free Class

Context free grammar

Recognizer for Context-Free Class

Push down automata

Generator for Context-Sensitive Class

Context-sensitive grammar

Recognizer for Context-Sensitive Class

Linear bounded automata

Generator for Recursively Enumerable Class

Generating Turing machine

Recognizer for Recursively Enumerable Class

Recognizing Turing machine

Reserved characters for regular expressions

+ | ? * [] () /

ab

Sequence: a followed by b

a + b, a | b

Either a OR b

a?

0 or 1 copies of a

a*

0 to unlimited copies of a

a+

1 to unlimited copies of a

\+, \?, etc.

Direct use of reserved characters

(abc)

Grouping

[AB][ab]

Classes

[0-3]

Lazy class listing: means one of 0, 1, 2, 3

\d = [0-9], \w = [A-Za-z0-9]

Named combinations; Use slash

<while> → while (<log-expr>){<stmt>};

<id-list> → <id>|<id>, <id-list>;

<var> → M|N|P|Q

Backus-Naur Form (BNF)

Ambiguity

Multiple derivations of an expression exist.

(m+n) + p = m + (n + p)

Associativty

<if_stmt> → if (<log>) <stmt> [ else <stmt>]

Extended BNF

Relations

Mapping between sets

Functions

Special class of relations;

Each input has at most one output

Partial Function

Not every input results in an output

Injective Function

1-1 functions

Surjective functions

Onto functions

Bijective Functions

Functions that are both injective and surjective

Implicitly Typed Function

fn x => x * x * x

val

Can hold a function as its value

fun

Named function

real

Number with decimal point

int

Number without decimal point

Operators that imply int

=, <, >, >=, <=

SML Operators

+, -, *, div, mod, ~, abs

Real(x)

Cast to real

string

“_____” - chars in double quotes

implode

Take a list of chars and turn them into a string

explode

take a string and turn it into a list of its characters

char

A single character

ord

Returns the ASCII value of a passed character

succ

Returns the successor to the current char

pred

Returns the predecessor to the current char

toLower

Turn a char to its lowercase form

toUpper

Turn a char to its uppercase form

isLower, isUpper, isDigit, isAlpha, isAscii

Check state and return true or false

(* —— *)

SML comment syntax

()

Tuple

Terminal Representation for Tuple

type*type*…*type

Record

Tuples with field-named sets of values

{a=3, b=2.0, c=”dog”}

[]

Empty list

::

List constructor

All elements of a list must be _______

Same type

:: type

‘a * ’a list → ‘a list

length L

Returns length of list

hd L

Returns first value of a list

tl L

Returns last value in a list

rev L

Returns reversed list

_

Wiidcard

Referential Transparency

Can interchange a computation and a value without impacting the overall program

Lexeme

It represents a single word or a base form of a word; Can be nouns, verbs, adjectives, adverbs

Type Specs

What types do the inputs have; what types do the outputs have

Semantic

Actual properties of the values

Mutual Recursion

Two functions that call each other recursively

Strongly Typed Language

Types computable at compile time

Enumeration

Type with a fixed list of values

[||]

Empty Array