Timeline for Should I lookahead in the lexer or parser?
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 5, 2022 at 8:01 | comment | added | dumbPotato21 | @rici That makes sense - thanks so much! | |
| Dec 5, 2022 at 7:38 | comment | added | rici | 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). | |
| Dec 5, 2022 at 7:35 | comment | added | rici | 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. | |
| Dec 4, 2022 at 10:20 | vote | accept | dumbPotato21 | ||
| Dec 4, 2022 at 9:35 | comment | added | dumbPotato21 | @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. | |
| Dec 4, 2022 at 3:24 | comment | added | rici | (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.) | |
| Dec 4, 2022 at 3:15 | comment | added | rici | 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.) | |
| Dec 3, 2022 at 13:46 | answer | added | Pseudonym♦ | timeline score: 1 | |
| Dec 3, 2022 at 13:26 | history | asked | dumbPotato21 | CC BY-SA 4.0 |