Content deleted Content added
Rust's raw string literals are an example of a context-sensitive language that can be parsed left to right by a (tail-)recursive descent parser that is allowed to carry an integer in the stack frames, so the restriction to LL(1) assumes that recursive descent stack frames have a finite number of states Tag: Reverted |
Added a paragraph about how handwritten recursive descent is commonly combined with a symbol table to resolve ambiguities Tag: Reverted |
||
Line 7:
Recursive descent with backtracking is a technique that determines which [[Production rule (formal languages)|production]] to use by trying each production in turn. Recursive descent with backtracking is not limited to LL(''k'') grammars, but is not guaranteed to terminate unless the grammar is LL(''k''). Even when they terminate, parsers that use recursive descent with backtracking may require [[exponential time]].
Handwritten predictive recursive descent parsers may also be used to parse some popular deterministic [[Context-sensitive_language|context-sensitive]] programming languages by making use of a [[symbol table]] during the parsing process. Symbol tables resolve common ambiguities in mainstream programming languages where different grammar rules should apply depending on whether an identifier represents a type or a value. Using a parsing strategy intended for context-free languages to parse some such languages such as [[C++]] may require using a nondeterministic parser and choosing which parse tree to use during semantic analysis.
Although predictive parsers are widely used, and are frequently chosen if writing a parser by hand, programmers often prefer to use a table-based parser produced by a [[parser generator]],{{Citation needed|date=February 2018}} either for an LL(''k'') language or using an alternative parser, such as [[LALR parser|LALR]] or [[LR parser|LR]]. This is particularly the case if a grammar is not in [[LL parser|LL(''k'')]] form, as transforming the grammar to LL to make it suitable for predictive parsing is involved. Predictive parsers can also be automatically generated, using tools like [[ANTLR]].
| |||