29-10-2010, 03:54 PM
Hi.
Anybody having source code of Top down Parsing in Java please send me on my email i shall be very thank full to you.Its very urgent i need it in 1 or 2days.sibteinali[at]gmail.com
29-10-2010, 03:54 PM
Hi. Anybody having source code of Top down Parsing in Java please send me on my email i shall be very thank full to you.Its very urgent i need it in 1 or 2days.sibteinali[at]gmail.com
12-06-2012, 04:40 PM
Top-Down Parsing
Top-Down Parsing.ppt (Size: 116.5 KB / Downloads: 42) The parse tree is created top to bottom. Top-down parser Recursive-Descent Parsing Backtracking is needed (If a choice of a production rule does not work, we backtrack to try other alternatives.) It is a general parsing technique, but not widely used. Not efficient Predictive Parsing no backtracking efficient needs a special form of grammars (LL(1) grammars). Recursive Predictive Parsing is a special form of Recursive Descent parsing without backtracking. Non-Recursive (Table Driven) Predictive Parser is also known as LL(1) parser. Error Recovery in Predictive Parsing An error may occur in the predictive parsing (LL(1) parsing) if the terminal symbol on the top of stack does not match with the current input symbol. if the top of stack is a non-terminal A, the current input symbol is a, and the parsing table entry M[A,a] is empty. What should the parser do in an error case? The parser should be able to give an error message (as much as possible meaningful error message). It should be recover from that error case, and it should be able to continue the parsing with the rest of the input. Error Recovery Techniques Panic-Mode Error Recovery Skipping the input symbols until a synchronizing token is found. Phrase-Level Error Recovery Each empty entry in the parsing table is filled with a pointer to a specific error routine to take care that error case. Error-Productions If we have a good idea of the common errors that might be encountered, we can augment the grammar with productions that generate erroneous constructs. When an error production is used by the parser, we can generate appropriate error diagnostics. Since it is almost impossible to know all the errors that can be made by the programmers, this method is not practical. Global-Correction Ideally, we we would like a compiler to make as few change as possible in processing incorrect inputs. We have to globally analyze the input to find the error. This is an expensive method, and it is not in practice.
31-10-2012, 04:42 PM
Top-Down Parsing
Top-Down.ppt (Size: 158.5 KB / Downloads: 34) The parse tree is created top to bottom. Top-down parser Recursive-Descent Parsing Backtracking is needed (If a choice of a production rule does not work, we backtrack to try other alternatives.) It is a general parsing technique, but not widely used. Not efficient Predictive Parsing no backtracking efficient needs a special form of grammars (LL(1) grammars). Recursive Predictive Parsing is a special form of Recursive Descent parsing without backtracking. Non-Recursive (Table Driven) Predictive Parser is also known as LL(1) parser. Predictive Parser When we are trying to write the non-terminal stmt, if the current token is if we have to choose first production rule. When we are trying to write the non-terminal stmt, we can uniquely choose the production rule by just looking the current token. We eliminate the left recursion in the grammar, and left factor it. But it may not be suitable for predictive parsing (not LL(1) grammar). Recursive Predictive Parsing If all other productions fail, we should apply an -production. For example, if the current token is not a or b, we may apply the -production. Most correct choice: We should apply an -production for a non-terminal A when the current token is in the follow set of A (which terminals can follow A in the sentential forms). LL(1) Parser input buffer our string to be parsed. We will assume that its end is marked with a special symbol $. output a production rule representing a step of the derivation sequence (left-most derivation) of the string in the input buffer. stack contains the grammar symbols at the bottom of the stack, there is a special end marker symbol $. initially the stack contains only the symbol $ and the starting symbol S. $S initial stack when the stack is emptied (ie. only $ left in the stack), the parsing is completed. parsing table a two-dimensional array M[A,a] each row is a non-terminal symbol each column is a terminal symbol or the special symbol $ each entry holds a production rule. Error Recovery in Predictive Parsing An error may occur in the predictive parsing (LL(1) parsing) if the terminal symbol on the top of stack does not match with the current input symbol. if the top of stack is a non-terminal A, the current input symbol is a, and the parsing table entry M[A,a] is empty. What should the parser do in an error case? The parser should be able to give an error message (as much as possible meaningful error message). It should be recover from that error case, and it should be able to continue the parsing with the rest of the input. Error Recovery Techniques Panic-Mode Error Recovery Skipping the input symbols until a synchronizing token is found. Phrase-Level Error Recovery Each empty entry in the parsing table is filled with a pointer to a specific error routine to take care that error case. Error-Productions If we have a good idea of the common errors that might be encountered, we can augment the grammar with productions that generate erroneous constructs. When an error production is used by the parser, we can generate appropriate error diagnostics. Since it is almost impossible to know all the errors that can be made by the programmers, this method is not practical. Global-Correction Ideally, we we would like a compiler to make as few change as possible in processing incorrect inputs. We have to globally analyze the input to find the error. This is an expensive method, and it is not in practice. |
|