O'Reilly logo

Building Parsers with Java™ by Steven John Metsker

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

6.3. Eliminating Left Recursion

Grammar G2 in the preceding section describes the Minimath language, but it translates to code that will not work. Once again, the grammar is

// Grammar G2 

e = e '–' Num | Num; // suffers from left recursion!

The problem with G2 is that e depends directly on e. When e tries to parse text, it starts by trying its first alternative. Thus, trying e means trying e, which means trying e…. This loops indefinitely.

It does not help to reverse the alternation, writing

// Grammar G2b 

e = Num | e '–' Num; // suffers too!

Here, when e tries its second alternative, it will try to match e, which has two alternatives. When e matches its second alternative, it will try to match e again. This cycling continues until the Java ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required