Summary

DFAs and NFAs

NFA → DFA Reduction Construct -Closures of subsets of nodes, and use subsets as new node

Minimize DFA Partition DFA into final and non-final states. Split partitions if members in the partition have transitions to different partitions for the same input. Fixed state partitions are new nodes.

Parsing

Given some grammar , define the following

: characters that appear first in string derived from

• For a terminal,

: terminals that appear immediately after

• Terminal symbols have empty FOLLOW set
• does not appear in any FOLLOW set
• the start symbol FOLLOW set should include

: lookahead symbols that are valid for rule

Scope and Binding

• Lexical Scope non-local variables associated with declarations at compile time. Find smallest text block syntactically enclosing the reference and a declaration of the variable. Access Link
• Dynamic Scope non-local variables are associated with declarations at run time. Find the most recent, current active run-time stack frame containing a declaration of the variable. Control Link

FP

car ⇒ first cdr ⇒ rest

[a,b,c] ⇒ '(a (b (c . null)))

Judgement Derivation

Lambda Calculus

• Function application is left associative,
• Function application precedence over abstraction
  • ,
• Multi argument functions

Alpha reduction renaming, Beta reduction substitution

True and false 2 parameter functions return first or second param ,