Regular Expressions are used in grep, sed, awk, perl, vi, shells, lex, yacc
– Each may use slightly different convention
State Machines
Parser Classification
LR: Bottom Up Parser
-L: scan left to right
-R: traces rightmost derivation of input string
LL: Top Down Parser
-L: Scan left to right
-L: traces leftmost derivation of input string
Typical notation
– LL(0), LL(1), LR(1), LR(k)
– number(k) refers to maximum look ahead
Recursive Descent Parsing
Non-terminal variable
convert
correct select rule for expansion matchToken
consumes token or Error
EBNF to BNF::= '*' | EBNF ::= {'*' } BNF ::= ::= '*' | ε
