4 ms·

I agree with the sentiment of the article, but the last code example doesn't help the argument. I think the following are far easier to read/understand than th

I agree with the sentiment of the article, but the last code example doesn't help the argument. I think the following are far easier to read/understand than the goto example that was provided. Token tok; while ( (tok = gettoken())!=END ) { if (shift(tok)) continue; if (reduce(tok) && shift(tok)) continue; return ERROR; } return ACCEPT; -- if continue is unavailable/taboo -- Token tok; while ( (tok = gettoken())!=END ) { if ( !shift(tok) && !(reduce(tok) && shift(tok)) ) return ERROR; } return ACCEPT;

abecedarius 17y ago
I may just be sleep-deprived, but I got Token tok; while ((tok = gettoken()) != END) while (!shift(tok)) if (!reduce(tok)) return ERROR; return ACCEPT;
- nkurz 17y ago
  Looks right to me. But does this strike you as clearer than the original? I like that the original makes it very clear that we only return ACCEPT if we reach END; that after a successful shift we continue reading; that after a successful reduce we shift again; and that we only return ERROR if a reduce fails. I think yours works the same, but for me at least it takes longer to parse. If I were actually debugging yours, I might even resort to looking at the compiled code with objdump and writing the labels in by hand. Presuming it's correct, I bet this would result in something that looked a lot like the original!
  - abecedarius 17y ago
    Clarity's in the eye of the beholder, yes. I had to scratch my head over the original to deduce that, ah, for each token before END, there are 0 or more attempts to reduce, until we can shift (exactly once). To me, that's a clearer description of what we're trying to do: more declarative. It directly reflects a grammar: (!END reduce* shift)* END. If we can "parse" that grammar, we get ACCEPT, else ERROR. But it's true that different expressions make different things clear. Structured programming helps most when it gets you to mirror the data's structure in the code.
Adlai 17y ago
I don't think that code reproduces the behavior of the original when the functions shift(tok) and reduce(tok) might return different values for successive calls. However, I don't know much about parsers and it could be that in the context of a parser, shift and reduce are proper functions in this sense.
- bullseye 17y ago
  No, you are right. In an effort to keep it O(n), I introduced a potential bug. Abecedarius's solution is more correct.
nkurz 17y ago
This code does not work like the original. Consider the case of a reduce does not shift: gettoken == not END, shift == false, reduce == true, shift == false. In the original code, the next operation is (correctly) another reduce. In your example, you stop reducing too soon and read the next token. Furthermore, I find that the labels in the original make the logic easier to follow.

abecedarius 17y ago

I may just be sleep-deprived, but I got Token tok; while ((tok = gettoken()) != END) while (!shift(tok)) if (!reduce(tok)) return ERROR; return ACCEPT;

nkurz 17y ago
Looks right to me. But does this strike you as clearer than the original? I like that the original makes it very clear that we only return ACCEPT if we reach END; that after a successful shift we continue reading; that after a successful reduce we shift again; and that we only return ERROR if a reduce fails. I think yours works the same, but for me at least it takes longer to parse. If I were actually debugging yours, I might even resort to looking at the compiled code with objdump and writing the labels in by hand. Presuming it's correct, I bet this would result in something that looked a lot like the original!
- abecedarius 17y ago
  Clarity's in the eye of the beholder, yes. I had to scratch my head over the original to deduce that, ah, for each token before END, there are 0 or more attempts to reduce, until we can shift (exactly once). To me, that's a clearer description of what we're trying to do: more declarative. It directly reflects a grammar: (!END reduce* shift)* END. If we can "parse" that grammar, we get ACCEPT, else ERROR. But it's true that different expressions make different things clear. Structured programming helps most when it gets you to mirror the data's structure in the code.

Adlai 17y ago

I don't think that code reproduces the behavior of the original when the functions shift(tok) and reduce(tok) might return different values for successive calls. However, I don't know much about parsers and it could be that in the context of a parser, shift and reduce are proper functions in this sense.

bullseye 17y ago
No, you are right. In an effort to keep it O(n), I introduced a potential bug. Abecedarius's solution is more correct.

nkurz 17y ago

This code does not work like the original. Consider the case of a reduce does not shift: gettoken == not END, shift == false, reduce == true, shift == false. In the original code, the next operation is (correctly) another reduce. In your example, you stop reducing too soon and read the next token. Furthermore, I find that the labels in the original make the logic easier to follow.