CS3361 - Assignment 4

CS 3361 | Fall 2023 | Assignment #4 Name & R#: _________________________________ Assignment #4 Backus-Naur Form Instructions For the questions below, either answer the questions digitally in Word or print out the document to do by hand and scan in a completed copy. What to turn in to BlackBoard A PDF copy of this document, either as a scanned copy when you solve it by hand or a converted copy if you solve it digitally. Double check your work before you submit it, missing pages or answers will be counted as incorrect, and you won’t be allowed to turn them in later for additional credit. Name your submission <FirstName>_<LastName>_<R#>.pdf (example: Eric_Rees_R123456.pdf). Do not turn in your answers in any other format other than .pdf. Assignment For the following BNF grammar rules, answer the questions that follow. <program> ::= <stmts> <stmts> ::= <stmt> | <stmt> ; <stmts> <stmt> ::= <var> = <expr> <var> ::= a | b | c | d <expr> ::= <term> | <expr> <op> <expr> <term> ::= <var> | const <op> ::= + | - | * | / | % 1) (5 pts) Is this grammar ambiguous? (Yes / No) ____________ 2) (10 pts) If this grammar is ambiguous, re-write the rules to remove the ambiguity such that: a. You do not add any new grammar rules b. You only change 1 nonterminal within 1 grammar rule. c. Any previously valid sentence continues to be valid. If the grammar is not ambiguous, re-write the rules as is from above with no changes.

CS 3361 | Fall 2023 | Assignment #4 Name & R#: _________________________________ 3) (15 pts) Using your grammar from Question #2, derive the following sentence. You must show each sentential form / step for the derivation. If the sentence cannot be derived, stop at the last step that you could derive and write “Cannot Continue Derivation”. Sentence: a = const ; b = a ; c = a + const / const ;

CS 3361 | Fall 2023 | Assignment #4 Name & R#: _________________________________ 5) (15 pts) Using your grammar from Question #2, derive the following sentence. You must show each sentential form / step for the derivation. If the sentence cannot be derived, stop at the last step that you could derive and write “Cannot Continue Derivation”. Sentence: a = a * const + c ; b = const – const % a ; d = const ;

CS 3361 | Fall 2023 | Assignment #4 Name & R#: _________________________________ 6) (20 pts) Using your grammar from Question #2, add a new nonterminal <parens> that allows for expressions to be encapsulated within parentheses ‘(‘ and ‘)’. Keep in mind this may require changing existing BNF rules as well as adding the new <parens> rule. Make sure your new grammar conforms to the following rules: a. Parentheses must be balanced, meaning each open parenthesis must have a corresponding close parenthesis. b. The new grammar must be a superset of the original grammar, meaning any sentence generated by the old grammar is still valid in the new one.