0
$\begingroup$

So I have this Recursive Descent Parser which outputs a Syntax Tree for arithmetic expressions.

parse tree

While doing some reading, I learned that LL(1) grammars have a lookahead of 1 - I remembered using a lookahead so I grepped for it. But instead of finding it in my parser, I found it in the lexer.

case "*":
    if self._peek() == "*":
        self._next(2)
        return Token(SyntaxKind.TWO_STAR, self.position - 2, "*")
    self._next(1)
    return Token(SyntaxKind.STAR, self.position - 1, "*")

I use this to differentiate between the power(**) and multiplication operator(*).

So is this the right way to do things? Or should this code be in my parser? And is my grammar still LL(1) if I don't actually lookahead in the parser?

Improve this question
$\endgroup$
6
  • $\begingroup$ I'll bet you anything that you do use lookahead in your parser. You just don't see that you're using it. At various moments during the parse, your parser will examine the next token and then decide what to do. That's a lookahead. In an LL(0) parser, the parser would have to decide what to do before it looks at the next token. Obviously, that's an extreme limitation, and very few languages have LL(0) parsers. (In an LL parser, "decides what to do" means "decide which production to predict". There are other parsing algorithms, so that's not a universal definition in parsing.) $\endgroup$
    – rici
    Commented Dec 4, 2022 at 3:15
  • $\begingroup$ (In fact, since every decision in an LL(0) parser must be made based on no information, there can be nothing which really qualifies as a decision. The only possible language is a singleton set. For this reason, LL(0) is not usually considered a thing. By contrast, an LR(0) parser, although still very weak, can handle some possibly useful languages. The difference is that LR parsers make decisions at the end of a production, not the beginning, so the decision can be informed by what the parser has already seen.) $\endgroup$
    – rici
    Commented Dec 4, 2022 at 3:24
  • $\begingroup$ @rici I see. I think I'm still unsure of the terminology. Does the 1 in LL(1) mean that I can look at 2 tokens at a time(that is, the current token I'm on and the next one) or that I can only look at 1 token(that is, the current token)? If you don't mind looking at the code of the parser, you can find it here. As you can see, I only use the current_token so I imagined I'm not using any lookaheads. $\endgroup$
    – dumbPotato21
    Commented Dec 4, 2022 at 9:35
  • $\begingroup$ No, the 1 in LL(1) means that you can look at 1 token. Calling that token the "current token" doesn't change the fact that it is a token which has not yet been consumed. In LL(k) parsing, you consume a token when you match it with the same token in the prediction stack; that can't happen until you predict the next token, so if you need to look at a token in order to make a prediction, that's using lookahead. $\endgroup$
    – rici
    Commented Dec 5, 2022 at 7:35
  • $\begingroup$ In case they taught you LL(k) parsing with different terminology, the prediction stack is the stack of unterminated right-hand sides. In a recursive descent parser, the stack is implicit --it's part of the parser's code-- but it still exists, at least conceptually. When you decide which code path to follow, you are making a prediction (about what the rest of the input will look like). $\endgroup$
    – rici
    Commented Dec 5, 2022 at 7:38

1 Answer 1

Reset to default
1
$\begingroup$

"The right way to do things" depends on the specifics of the language.

The lexical syntax of most modern programming languages uses what is known as the maximal munch rule, which states that given more than one possibility as to what the next lexeme could be, choose the one that consumes more of the input. This inevitably means that a lexical analyser must backtrack (or look ahead) in general. An example is in in C++, where 0x0 is an integer constant expressed in hexadecimal, but 0x is an integer literal followed by a suffix. To determine the next token, the lexical analyser must look past the x to see what follows it.

This is a design decision by programming language designers to make programming languages easier to implement. It's not the only option.

To answer your last question, any LL(0) grammar is also LL(1) even though it never needs the lookahead symbol. Either way, LL(k)-ness is a property of the grammar, and the grammar doesn't care where the terminal symbols came from.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So aren't the lines between a lexer and parser blurry? I imagined that the parser is the one which looks ahead and decides which path of the grammar to take(say X -> A | B | C) but couldn't you do that within the lexer as well? $\endgroup$
    – dumbPotato21
    Commented Dec 3, 2022 at 13:56
  • $\begingroup$ In the real world, the lines between a lexer and a parser are blurry. But they're often not as blurry in language specifications. $\endgroup$
    – Pseudonym ♦
    Commented Dec 4, 2022 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.