CODEWITHSUNDEEP
parsingrecursioncompiler-constructioncompilationrecursive-descent
Kaylee
Kaylee

Reputation: 145

Recursive descent parser first and follow

to implement a recursive descent parser is the first and follow sets required? and if so can you still build the recursive descent given non uniqueness in the first and follows? I'm having a hard time distinguishing between recursive descent and ll(1) parsing.

Thanks.

Upvotes: 0

Views: 602

Answers (1)

CoronA
CoronA

Reputation: 8095

Recursive descent parsers do not have to be deterministic, i.e. one can construct recursive descent parsers that cannot decide which derivation to choose after a finite constant lookahead.

LL(k) parsers construct a parse tree incrementally, each new character will extend the parse tree.

Nondetermistic recursive descent parsers can build a parse tree, which is discarded completely on the occurrence of a certain character.

Examples for recursive descent which is not necessarily LL(k):

  • Parsing in PROLOG (backtracking)
  • Packrat Parsing (backtracking with memoization)

Upvotes: 1

Related Questions