11Programming LanguagesTevfik KoşarLecture - IIIJanuary 24th, 20062Roadmap• Creating Language Grammars– Regular Expressions– Context Free Grammars– Parse Trees– Ambiguity23Expressing Digitsdigit -> digit -> 1digit -> 2digit -> 3digit -> 4digit -> 5digit -> 6digit -> 7digit -> 8digit -> 90digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Regular Expression4Expressing Numbersdigit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 two-digit-number -> digit digitnumber -> digit digit** : Kleene star (zero more repetitions of the symbol to its left) natural_number -> non_zero_digit digit*non_zero_digit -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 TerminalsNon-terminalsnatural_number ->35Operators• op -> + | - | * | /• expr -> number op number op number6Context Free Grammars• Adds recursion to regular expressionsexpr -> number op number op numberexpr -> number | expr op expr47Example3 + 4 * 5 derive thisexpr -> number | expr op expr from thisexpr -> expr op expr-> expr op number-> expr * number-> expr op expr * num-> expr op num * num-> expr + num * num-> num + num * num(3) (4)
View Full Document