Recursive descent parser

In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar.[3] Predictive parsing is possible only for the class of LL(k) grammars, which are the context-free grammars for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input.Even when they terminate, parsers that use recursive descent with backtracking may require exponential time.Predictive parsers can be depicted using transition diagrams for each non-terminal symbol where the edges between the initial and the final states are labelled by the symbols (terminals and non-terminals) of the right side of the production rule.Parsing descends in a top-down manner until the final nonterminal has been processed.
computer sciencetop-down parsermutually recursiveprocedurenonterminalsgrammarbacktrackingcontext-free grammarsambiguous grammarsleft recursionlinear timeproductionexponential timeparser generatorNiklaus WirthAlgorithms + Data Structures = ProgramsTerminalsnonterminalJavaCCCoco/RSpirit Parser Frameworkparboiled (Java)Parser combinatorParsing expression grammarRecursive ascent parserTail recursive parserFree On-line Dictionary of ComputingAho, Alfred V.Ullman, JeffreyPascalassembly languageParsing algorithmsTop-downEarleyTail recursiveBottom-upSimpleOperatorShunting-yardLook-aheadCanonicalGeneralizedRecursive ascentShift-reduceCombinatorLeft cornerDefinite clause grammarDeterministic parsingDynamic programmingMemoizationParse treeScannerless parsingHistory of compiler constructionComparison of parser generatorsOperator-precedence grammar