| <stmt> ; <stmt_list> <stmt> <var> = <expression> <var> A | B | C <expression> <var> + <var> | <var> - <var> | <var> => begin <var> = <expression> ; <stmt_list> end => begin A = <expression> ; <stmt_list> end => begin A = <var> + <var> ; <stmt_list> end => begin A = B + <var> ; <stmt_list> end => begin A = B + C ; <stmt_list> end => begin A = B + C ; <stmt> end => begin A = B + C ; <var> = <expression> end => begin A = B + C ; B = <expression> end => begin A = B + C ; B = <var> end => begin A = B + C ; B = C end Exercise #1 Given Grammar Leftmost Derivation w/ Target Syntax <sentence> -> <subject> <predicate> <subject> -> <article> <noun> <predicate> -> <verb> <direct-object> -> <article> <noun> <article> -> THE | A <noun> -> MAN | DOG <verb> -> BITES | PETS A DOG PETS A DOG <sentence> -> Answer: => A A A A DOG A DOG A DOG PETS A DOG PETS A DOG Exercise #2 Given Grammar Rightmost Derivation w/ Target Syntax <sentence> -> <subject> <predicate> <subject> -> <article> <noun> <predicate> -> <verb> <direct-object> -> <article> <noun> <article> -> THE | A <noun> -> MAN | DOG <verb> -> BITES | PETS THE MAN BITES A DOG (rightmost!!) Answer: => <subject> <subject> <subject> <subject> <subject> <verb> A <subject> BITES A <article> <noun> BITES A
| <expr> * <expr> | ( <expr> ) | <id> 2nd Ambiguous Grammar Example Grammar Solution(s) for: 3 + 4 * 5 E → E + E E → E * E E → i (left most - right most) Derviation => E => E + E => 3 + E => 3 + E * E => 3 + 4 * E => 3 + 4 * 5 => E => E * E => E + E * E => 3 + E * E => 3 + 4 * E => 3 + 4 * 5 3rd Ambiguous Grammar Example Grammar Solution(s) for: const – const / const <expr> <expr> <op> <expr> | const <op> / | - (left most - right most) if the Grammar is ambiguous there are some notable things to avoid not defining operator precedence further explained below, but you already know this have the SAME abstraction in a rule more than one Anything ambiguous can be re-written
Showing the Proper Parse Tree for ** Grammar A + B * C A ** B + C <expr> <expr> + <term> | <expr> - <term> | <term> <term> <term> * <factor> | <term> / <factor> | <factor> <factor> <exp> ** <factor> | <exp> <exp> ( <expr> ) | <id> <id> A | B | C | … Try A + (B * C) / D just to get used to this new grammar. Did it come out right? Then try A ** B ** C. Which portion was the lowest on the tree? Answersb: FYI Section Who needs to know and understand your language? there are many people needed in the development of a new programming language, but who are they?? Answers: Language recognizers and Generators Language Recognizers (also called Finite State Machines!!) accept a Language like a Machine. The Machines take a string as input. The Machines will accept the input if when run, the Machine stops at an accept state. Otherwise the input is rejected. If a Machine M recognizes all strings in Language L, and accepts input provided by a given string S, M is said to accept S.
Otherwise M is said to reject S. S is in L if and only if M accepts S. JFLAP is a FSM application!! Context Free Grammar (CFGs) are a well-known type of language generator!! Language Generators create the strings (sentences) of a Language. A generator provides a construction description. If a generator is able to construct all stings in a Language L, and every string S that can be constructed by that generator is in L, we can say that the generator is a generator for the language L. If there is no way to construct a string S from the generator, S is not in L. s (PDAs) are a well known form of language recognizers. not really covered here Extended (Updated) BNF (EBNF) like anything else, some updates were made for convenience only increased the readability/writability (for us!!) there are other versions of the updates 3 most common updates optional part in RHS Optional parts are placed in brackets [ ] almost anything with |’s in reality is now replaced if symbol is unique to any of the rules, it may need to stay less rules, or as many lines to write EBNF “Optional” Update (Extension) in C++: <if_stmt> if( <expression> ) <statements> [else <statements> ] <if_stmt> if( <expression> ) <statements> | if( <expression> ) <statements> else <statements>