CSE 110 : Introduction to Computer Science
- Radix Sort : An O(n) sort that works without comparison.
- Radix Sort : Distribute into bins based on the 1's place, then 10's, 100's, etc.
- Regular Expression: A kind of query.
- De jure Standard : IEEE POSIX (SRE, BRE or ERE)
- De facto Standard : PCRE
- Regular Language: A language constructed as the set of all responces of a
particular Regular Expression.
- Regular Grammar: A grammar that describes a Regular Language.
Backus-Naur Form (BNF)
- BNF: A notation for describing a grammar.
- C ← B means B can replace C/li>
- A 3 line BNF:
Parse Trees for Regular Grammars
- In a Regular Grammar Parse Tree, a node's children are those that can replace it.
- A ← B means B can replace A (think B points to its parent A)