CODEWITHSUNDEEP
parsingrecursionll-grammarcompiler-construction
Vaibhav Patle
Vaibhav Patle

Reputation: 49

How can LL(1) grammars be recursive if an LL(1) parser is non-recursive?

An LL(1) parser is a non-recursive predctive parser. Given that, why can LL(1) grammars is be recursive? These seem inconsistent with one another.

Upvotes: 1

Views: 1119

Answers (1)

templatetypedef
templatetypedef

Reputation: 373082

I think your confusion stems from the fact that there are several different types of recursion here.

First, there's the fact that any CFG that can generate infinitely many strings - which would be basically any CFG you'd actually want to use in practice - has to involve some amount of recursion. If there isn't any recursion, you only get finitely many strings. So in that sense, there's CFG recursion, where there are production rules that lead to the original nonterminal getting produced a second (or third, fourth, etc.) time.

Next, there's the way that the parser is implemented. Some parsers are implemented using recursive descent or recursive backtracking. That's a design decision that's separate from whether the original grammar is recursive. Let's call that parser recursion.

Generally speaking, most LL(1) parsers are implemented to not use parser recursion and to instead do a bunch of table-based lookups to determine how to drive the parsing. However, many LL(1) grammars have CFG recursion in them, but that's separate.

As an example, consider this (very simple) LL(1) grammar:

A → b | cA

Notice that there's CFG recursion here, since the production A → cA is recursive.

After augmenting the grammar, we get this grammar:

S → A$

A → b | cA

Here's the LL(1) parsing table for the above grammar:

     | b  | c  | $
-----+----+----+---
  S  | A$ | A$ | acc
  A  | b  | cA | -

We can use this parsing table to implement a (non-iterative) LL(1) parser by just keeping track of the partial match so far and consulting this table any time we need to predict which production to use.

Upvotes: 2

Related Questions