| Inductive Definitions Languages, Grammars, Parsing |
| Motivation: Parsing |
| Grammars, and Induction |
| Inductive Definitions |
| Inductive Definitions |
| Inductive Definitions |
| Example of ID: Binary Trees |
| Examples of Binary Trees |
| Example of ID: Natural Numbers w |
| Notes |
| Interpretations of Successor (Õ) |
| Decimal Numerals |
| Decimal Numbering Rule |
| 1-adic Numerals |
| 2-adic Numerals |
| Roman Numerals |
| Numerals vs. Numbers |
| Strings over an alphabet S |
| Strings over an alphabet S |
| Languages |
| More Languages |
| Languages |
| Non-Trivial Language Defined Inductively |
| Grammars: A Shorthand |
| Grammar Definition |
| Using the Grammar Rules |
| Generalizing Grammar Rules |
| Example: Grammar for Additive Arithmetic Expressions |
| Example Derivations |
| Shorthands on top of Shorthands |
| Derivation Tree Visualization |
| Syntax Tree (!= Derivation
Tree) Shows Implied ÒInterpretation" of String |
| Right Grouping (used so
far) vs. Left Grouping Productions |
| Does Grouping Matter? |
| Floating Point is Not Associative |
| Precedence Issue (multiple operator symbols) |
| Multiple Auxiliaries |
| Precedence Issue |
| Example: Grammar for Additive & Multiplicative Arithmetic Expressions |
| Syntactic Categories |
| Example Derivations |
| Example Syntactic Categories |
| Exercise: Include ^ (power) |
| How to handle Ô(Õ Ô)Õ |
| Two Main Language Problems |
| Na•ve Solution to the Recognition Problem |
| Parsing |
| Recursive Descent Parsing |
| Recursive Descent |
| Parse Methods |
| Example |
| Example: Success |
| Example: Failure |
| A rex version of parsing |
| A rex version of parsing (1) |
| Test cases |
| A rex version of parsing (2) |
| Operators + and * with * having higher precedence |
| rex parsing for +, * (A) |
| rex parsing for +, * (M) |
| Parsing Methods in Java |
| Parsing Methods in Java |
| Additive Grammar |
| Runnable Examples |
| V() method |
| makeString(char c) |
| isVar() |
| Recursive A() method |
| Replacing some
Recursion with Iteration |
| ÒInverse McCarthy
TransformationÓ for Grammars with left-grouping |
| A() method, iterative version |
| The Additive/Multiplicative Grammar |
| Remembering Precedence Rules |
| Syntax Tree Applet |
| Example: SimpleCalc |
| Slide 76 |
| Grammar for Unicalc |
| Result of Parsing Unicalc |