3 ms·

I'm not sure if this is what you meant, but yes the C compiler uses it for the entire expression syntax -- not just arithmetic. Because in C "declaration mimic

by chubot 9y ago

I'm not sure if this is what you meant, but yes the C compiler uses it for the entire expression syntax -- not just arithmetic. Because in C "declaration mimics use", it's used for type expressions too. As for using it for the entire programming language, like for/while/switch, I see the discussion with vidarh below. I haven't seen a parser written like this, so that's interesting. However I consider the "opposite" sort of a mistake? Doug Crockford uses top-down operator precedence to parse ALL of JavaScript, not just the expression language. Review of Pratt/TDOP Parsing Tutorials http://www.oilshell.org/blog/2016/11/02.html http://www.oilshell.org/blog/2016/11/02.html I remember being confused by this, and I think it is still confusing. It seems to me that the statement language and expression language are separate things, and it makes sense to use recursive descent for the statement language and either top-down or bottom-up precedence for expressions. In other words, the architecture of the original C compiler is very clean, and no doubt influenced the language design. (On the other hand, it's probably also responsible for the fact that C has so many levels of precedence, some of which don't make sense!) Also, the difference between "Pratt parsing" and "Precedence climbing" is sort of a code organization issue -- do you handle a[i] and x?a:b in the same place as a*b a+b etc.? I wondered if there is an analogous thing for bottom-up expression parsing. I like having each "form" in one function. Pratt parsing is a nice complement to recursive descent; it's accurate to say that it's a variant of recursive descent with the additional input of numerical priorities.

vidarh 9y ago
> As for using it for the entire programming language, like for/while/switch, I see the discussion with vidarh below. I've done a full Pascal-like language using bottom up precedence parsing in the past. It was my first compiler project about 25 years ago or so, and "invented" precedence parsing with the help of a symbolic expression evaluator in Prolog in a book I picked up that I tried to figure out how to translate to Pascal. It was very disappointing to find out it was a well known algorithm, but it was very interesting to try to expand it to handle a full language, which involved funky things like handling operators with different structure than just simple single-operand prefix/postfix + infix operators. E.g. I implemented a dual-arity prefix operator to handle for/while/if/ternary for example. So "while" took two expressions: the condition and a block. The hard part was not handling the control structures, but getting the priorities right. I'm not sure I'd do that again. My Ruby parser uses recursive descent for the top level productions. But it was fascinating to do, as it did make for a very compact parser. > It seems to me that the statement language and expression language are separate things, I think if you go down that route, then you are implicitly deciding that everything is an expression. In e.g. Ruby that is true, though many constructs just returns nil (e.g "somevar = while condition; end" is valid). But given that many of the "operators" are only allowed at specific levels, it makes less sense to use a precedence parser anyway (e.g. "class" can't occur in a method body for example). For me, those two are the biggest considerations to whether or not I'd consider a precedence parser: Whether or not everything is an expression, and which keywords are only allowed in specific contexts. But even if it's feasible without too many contortions, it may still be very painful.
- chubot 9y ago
  Interesting, thanks for the feedback. It seems like the lesson is analogous to what I learned from Crockford's JavaScript parser. That is, regardless of whether you're doing it top-down or bottom-up, using an operator precedence algorithm for statements is painful. I think the reason is simply that there is a fundamental relationship between the language you are parsing (the data) the algorithm you choose to parse it with (the code). Those 2 things are tightly linked. I think this isn't emphasized enough in introductory texts. They usually only have time to teach one parsing method, and the language being parsed is chosen to fit that. Or maybe you choose one problem like shift-reduce conflicts, but you don't get the comparison / contrast to other methods.

by chubot 9y ago

vidarh 9y ago

> As for using it for the entire programming language, like for/while/switch, I see the discussion with vidarh below. I've done a full Pascal-like language using bottom up precedence parsing in the past. It was my first compiler project about 25 years ago or so, and "invented" precedence parsing with the help of a symbolic expression evaluator in Prolog in a book I picked up that I tried to figure out how to translate to Pascal. It was very disappointing to find out it was a well known algorithm, but it was very interesting to try to expand it to handle a full language, which involved funky things like handling operators with different structure than just simple single-operand prefix/postfix + infix operators. E.g. I implemented a dual-arity prefix operator to handle for/while/if/ternary for example. So "while" took two expressions: the condition and a block. The hard part was not handling the control structures, but getting the priorities right. I'm not sure I'd do that again. My Ruby parser uses recursive descent for the top level productions. But it was fascinating to do, as it did make for a very compact parser. > It seems to me that the statement language and expression language are separate things, I think if you go down that route, then you are implicitly deciding that everything is an expression. In e.g. Ruby that is true, though many constructs just returns nil (e.g "somevar = while condition; end" is valid). But given that many of the "operators" are only allowed at specific levels, it makes less sense to use a precedence parser anyway (e.g. "class" can't occur in a method body for example). For me, those two are the biggest considerations to whether or not I'd consider a precedence parser: Whether or not everything is an expression, and which keywords are only allowed in specific contexts. But even if it's feasible without too many contortions, it may still be very painful.

chubot 9y ago
Interesting, thanks for the feedback. It seems like the lesson is analogous to what I learned from Crockford's JavaScript parser. That is, regardless of whether you're doing it top-down or bottom-up, using an operator precedence algorithm for statements is painful. I think the reason is simply that there is a fundamental relationship between the language you are parsing (the data) the algorithm you choose to parse it with (the code). Those 2 things are tightly linked. I think this isn't emphasized enough in introductory texts. They usually only have time to teach one parsing method, and the language being parsed is chosen to fit that. Or maybe you choose one problem like shift-reduce conflicts, but you don't get the comparison / contrast to other methods.