CPSC 411 Lecture 1: CPSC 411 Lecture - 20160112_093116
28 Mar 2016
School
Department
Course
Professor
Document Summary
Page 11: what happens when the parse tree fails (returns a non empty list, you would like to be able to build a parse a tree, when does the grammar permits this sort of translation into code. A grammar is in recursive descent form if in each production the terminal occur before the non terminals. You can always rewrite a grammar into recursive descent form by splitting rules before. We want to know when a recursive descent purser will completely recognize strings of the grammar: Problems: left recursion - infinite series of call: won"t terminate, you have to be ale to decide which rule to fire , null production - default rules when can i use them (subtle problem) To sort this out we are going to develop the theory of context free grammar. Derivations: given a grammar g, a derivation form one sentential form to another form is a sequence. O (possible empty) steps of the for :
