Is this production rule left-recursive or not?

Question

My knowledge on formal language and compiler theory is limited. So I am learning by the book The Definitive ANTLR 4 Reference by Terence Parr.

In the book, it says:

Now, with v4, you can match expressions with rules that look like this:

expr : expr '*' expr // match subexpressions joined with '*' operator
     | expr '+' expr // match subexpressions joined with '+' operator
     | INT           // matches simple integer atom
     ;

Self-referential rules like expr are recursive and, in particular, left recursive because at least one of its alternatives immediately refers to itself.

But I think the bold part is incorrect. Accroding to here, the production is left-recursive if the leftmost symbol on the right side is the same as the non terminal on the left side. For example,

    expr → expr + term.

So back to the Terence's book's sample, it is neither left recursive nor right recursive. It's merely recursive.

Am I right? Or did I misunderstand the author?

ADD 1

Thanks for the replies so far. Sorry I didn't make myself clear enough.

My understanding is: being left-recursive means the left-most part of the right-side is the same as the non-terminal on the left side. AND the remaining part of the right-side is ONLY suffix which is NOT the left-side.

In the Parr's book sample, the reamining part of the right-side is not a suffix, it's another same expr, so I don't think it strictly fits the rule of being left-recursive.

Answer 1

Let's compare what the book gives as an example of a left-recursive rule:

expr → expr + term.

with the first part of the compound rule you are examining:

expr : expr '*' expr // match subexpressions joined with '*' operator

Here, the left side is expr; the right side is expr '*' expr, and the left-most symbol on the right side is expr. Since the leftmost symbol on the right side, expr, is the same as the symbol on the left side, also expr, then this part of the rule is left recursive.

The second part of the compound rule would also be left-recursive, for the same reason:

expr : expr '+' expr

This third part of the compound rule is not left recursive, since INT is an atom:

expr : INT           // matches simple integer atom

When you combine these three different expression for expr into one using the | operator, you get the original expression in your question:

expr : expr '*' expr // match subexpressions joined with '*' operator
     | expr '+' expr // match subexpressions joined with '+' operator
     | INT           // matches simple integer atom
     ;

Which, since at least one of its three choices is left-recursive, is itself left-recursive.

Answer 2

"The production is left-recursive if the leftmost symbol on the right side is the same as the non terminal on the left side."

In your example "expr -> expr + term" the leftmost symbol on the right side is "expr" and the non terminal on the left side is "expr" so they're the same. The production is left-recursive. That your alternatives are "expr * expr" and "expr + expr" make no difference; your definition is still left-recursive.

If you imagine you were creating a parser to parse this language, you'd have a function called "parseExpr" that would parse an "expr." According to the definition, the first thing it would have to do in order to evaluate "expr + (anything)" is to parse an "expr." So it should call the function to parse an "expr," which is of course itself. That's basically what left-recursive means.