Non Recursive Descent Parser-LL(1) Parser

 Nonrecursive Descent Parser-LL(1) Parser in Theory of Automata/Theory of Computation

It is possible to build a nonrecursive descent parser, also called LL (1) parser, by using a stack explicitly, rather than implicitly via recursive calls. The key problem in the design of a predictive parser is that of determining the right products to be applied for a nonterminal. The nonrecursive parser looks up the production to be applied in the parsing table. We shall see how the table can be constructed directly from the grammar. 

A table-driven nonrecursive predictive parser uses an input buffer, a stack, a parsing table, and an output stream. The string to be parsed is read into the input buffer and "$" is appended at the end. "$" is a symbol used as a right-end marker to show the end of the input string. The stack contains a sequence of grammar symbols at any time. Initially "$" is pushed onto the stack, indicating the bottom of the stack. A top-down parser starts working by pushing the start symbol of the grammar onto the stack. The parsing table is a two-dimensional array M [S, a] where "S" is a nonterminal and "a" is a terminal or the input right end marker "$."

The parser works as follows: Suppose "X" is the symbol on the top of the stack and "a" is the current input symbol. The look-ahead symbol is the input pointer's current symbol pointer at any time.. Parser always works by comparing the top of the stack 'X' with the look-ahead symbol "a." These two symbols determine the action to be performed by the parser.