Written solutions to problems 4.1.1, 4.1.4, and two of the following problems: 4.1.7, 4.1.10, 4.2.1, and example 4.1.9 are due at the beginning of class Thursday March 18th. For example 4.1.9, show that the example in the textbook is incorrect, and that the machine does not perform a right shift as indicated. Then fix the machine. Implement the dynamic programming algorithm for parsing grammars in Chomsky Normal form. You may use the example Chomsky Grammars provided in the previous lab. Treat the first non-terminal you see as the start symbol. I recommend not storing the table N[i,j] directly, but as a dictionary. Python won't let you hash on a list object, but it will let you hash on a tuple (indicated with parentheses instead of brackets), thus d[(i,j)]=[A] is OK while d[[i,j]]=[A] is not. Create some input strings that should be valid/invalid and check that your algorithm is correct. For the ETF+*id grammar, you can use x as a terminal instead of id so you don't have to put spaces in your input strings

Home Page

Last updated: Tuesday, September 22, 2020 at 09:07:44 AM