4 ms·

1. You're arguing against a strawman (maybe one that lives in some basements) if you think anybody's parsing expressions by writing down a CFG and translating t

1. You're arguing against a strawman (maybe one that lives in some basements) if you think anybody's parsing expressions by writing down a CFG and translating that into a strawman "recursive descent" parser. A hand-rolled parser will not traipse down 13 levels to parse an atom. Also, you don't have to "compose two different algorithms" per se, there's no impedance mismatch. 2. I've found refactoring hand-rolled parsers to be just fine, I believe the things I needed to do would not be so convenient with parsing tools, though it depends on what direction I'd have gone down at a certain point in time. 3. The problem there is that of proper language design. You need to combine your sub-languages in a way such that there isn't parsing problems. Your language needs to be parsed by humans, too, after all. 4. This is actually a solved problem, it's just the solution isn't evenly distributed. I think that parsing code is much more low-risk than other C code I've written, but there are people who do things a lot more bozotically... 5a. Does the parser has special obligations beyond recording comments and source locations here? 4a^H^H5b. Yeah, now, the question is, how did they solve that problem?

mcguire 10y ago
"You're arguing against a strawman (maybe one that lives in some basements) if you think anybody's parsing expressions by writing down a CFG and translating that into a strawman "recursive descent" parser. A hand-rolled parser will not traipse down 13 levels to parse an atom." So, how do you handle expression precedence? (I haven't hand written a parser since I made peace and developed a working relationship with bison.)
- SamReidHughes 10y ago
  Step 1. Begin writing a parser. Step 2. Notice that writing functions parsing "expressions," "expressions without equals signs," "expressions without equals signs or plus/minus signs," ... is very repetitive. Step 3. Being a competent programmer, find a way to solve that problem. (Instead of N functions, make one function that takes a parameter specifying the precedence level. Edit: Durr, I'm a moron, this doesn't really describe how to solve the problem of making N recursive calls. But still, you just figure it out, see my other post for how I actually tend to do it. Edit: Or judofyr's post describes it too.)
- jblow 10y ago
  Precedence is actually not hard. The way I do it is: (1) Parse everything as though it were left-to-right. (2) After each node is parsed, look at its immediate descendants and rearrange links as necessary. (Nodes in parentheses are flagged so you don't rearrange them.) I can tell that the person above who is listing off a bunch of reasons not to use "recursive descent" hasn't written a compiler by hand ever (or not well). Most of the things he is talking about are easier to do by hand than in some complicated and relatively inflexible system. Note that 'prediction' is mostly a red herring since you can look as many tokens ahead as you want before calling the appropriate function to handle the input. You would need to have a pathologically ambiguous language in order to make that part hard, and if your language is that ambiguous, it is going to confuse programmers! In general, parsing is easy (if you know how to program well in the first place) and is only made more difficult/inflexible/user-unfriendly by using parsing tools. That doesn't mean that academic theories about parsing are bad -- it's good that we understand deeply things about grammars -- but that does not mean you should use those systems to generate your source code. (I do think it's a good idea to use a system like that to spot ambiguities in your grammar and decide how to handle hem, because otherwise it's easy to be ignorant... But I would not use them to generate code!)
  - chubot 10y ago
    Precedence isn't hard -- but it's often not done with recursive descent. In other words, it's not just "typing out the code". I think you're misreading my reply. A hand-written recursive descent works a lot of the time, and is almost certainly the right "default". But my point is that it doesn't work all the time. If it works for you, great! That doesn't mean all parsing is easy. Try adding an autoformatter like gofmt or IDE completion for Jai, and see how your parser changes (or if you have to write an entirely new parser). In particular, I'm NOT advocating that all parsers should written with parsing tools. I think you must have read that somewhere else. In fact, I used EXACTLY the same strategy as you mention on my recent shell parser. I machine-checked the grammar with ANTLR, and wrote some test cases for it. Then I transcribed that grammar to recursive descent by hand, along with several other ad hoc strategies that you need to parse an ad hoc language like shell. (ANTLR is a great front end, but not necessarily a good back end. The generated Java code is probably OK, but the C++ code it generates is preposterous. Yacc is not that much better, i.e. with globals all over the place.) "Just type out the code" is a horrible strategy because you will end up not knowing what language you've designed. If your post advocated "prototype your grammar with a tool, and then manually transcribe the grammar to code", then I'd be inclined to agree. But that's not what you said. It seems like you are more interested in telling everyone what a great programmer you are, and how things are so easy for you, rather than spreading any interesting knowledge about parsing.
- judofyr 10y ago
  A Pratt-style parser makes expression precedence easy in a recursive descent parser: "use strict"; var tokens = [2, '+', 5, '+', 9, '+', 4]; var PREC = {'+': 1, '-': 1, '*': 2, '/': 2}; function expr(prec) { var value = tokens.shift(); while (true) { var nextToken = tokens[0]; var nextPrec = PREC[nextToken]; if (!nextPrec) break; // not an operator if (nextPrec <= prec) break; tokens.shift(); var rest = expr(nextPrec); value = [nextToken, value, rest]; } return value; } console.log(expr(0)); I find this technique useful because I can implement it in any language without being dependent on a parser generator.
chubot 10y ago
Your comments betray a lot of ignorance, so I will just point out the glaring inaccuracies in #1. Here are two different expression parsers that are likely installed on machines you use, and they absolutely make a function call for each level of precedence (eval1, eval2, ..., exp1, exp2, ...) http://code.metager.de/source/xref/gnu/coreutils/src/expr.c http://code.metager.de/source/xref/gnu/coreutils/src/expr.c https://opensource.apple.com/source/bash/bash-76.1/bash/expr.c https://opensource.apple.com/source/bash/bash-76.1/bash/expr... My point is not that this is BAD -- it probably doesn't matter on modern machines. I'm just saying there are choices to make. Parsing requires some knowledge and choices -- that's all. You don't just "type out the code". #3 is not a refutation, because all the languages I mentioned are extraordinarily common. The answer to "parsing real languages is hard" is not "don't parse real languages". I can also tell by #4 that you don't have any background in security. It's not about YOUR code per se. It's about code that is deployed and that we all rely on.
- SamReidHughes 10y ago
  1. Did I not say there might be some living strawmen out there? 3. Did I say we shouldn't parse real languages? No, I said the problem was that it's not straightforward to combine two languages into a new one. The problem's not at the level of parsers. 4. Did I not say it wasn't evenly distributed?

mcguire 10y ago

"You're arguing against a strawman (maybe one that lives in some basements) if you think anybody's parsing expressions by writing down a CFG and translating that into a strawman "recursive descent" parser. A hand-rolled parser will not traipse down 13 levels to parse an atom." So, how do you handle expression precedence? (I haven't hand written a parser since I made peace and developed a working relationship with bison.)

SamReidHughes 10y ago
Step 1. Begin writing a parser. Step 2. Notice that writing functions parsing "expressions," "expressions without equals signs," "expressions without equals signs or plus/minus signs," ... is very repetitive. Step 3. Being a competent programmer, find a way to solve that problem. (Instead of N functions, make one function that takes a parameter specifying the precedence level. Edit: Durr, I'm a moron, this doesn't really describe how to solve the problem of making N recursive calls. But still, you just figure it out, see my other post for how I actually tend to do it. Edit: Or judofyr's post describes it too.)
jblow 10y ago
Precedence is actually not hard. The way I do it is: (1) Parse everything as though it were left-to-right. (2) After each node is parsed, look at its immediate descendants and rearrange links as necessary. (Nodes in parentheses are flagged so you don't rearrange them.) I can tell that the person above who is listing off a bunch of reasons not to use "recursive descent" hasn't written a compiler by hand ever (or not well). Most of the things he is talking about are easier to do by hand than in some complicated and relatively inflexible system. Note that 'prediction' is mostly a red herring since you can look as many tokens ahead as you want before calling the appropriate function to handle the input. You would need to have a pathologically ambiguous language in order to make that part hard, and if your language is that ambiguous, it is going to confuse programmers! In general, parsing is easy (if you know how to program well in the first place) and is only made more difficult/inflexible/user-unfriendly by using parsing tools. That doesn't mean that academic theories about parsing are bad -- it's good that we understand deeply things about grammars -- but that does not mean you should use those systems to generate your source code. (I do think it's a good idea to use a system like that to spot ambiguities in your grammar and decide how to handle hem, because otherwise it's easy to be ignorant... But I would not use them to generate code!)
- chubot 10y ago
  Precedence isn't hard -- but it's often not done with recursive descent. In other words, it's not just "typing out the code". I think you're misreading my reply. A hand-written recursive descent works a lot of the time, and is almost certainly the right "default". But my point is that it doesn't work all the time. If it works for you, great! That doesn't mean all parsing is easy. Try adding an autoformatter like gofmt or IDE completion for Jai, and see how your parser changes (or if you have to write an entirely new parser). In particular, I'm NOT advocating that all parsers should written with parsing tools. I think you must have read that somewhere else. In fact, I used EXACTLY the same strategy as you mention on my recent shell parser. I machine-checked the grammar with ANTLR, and wrote some test cases for it. Then I transcribed that grammar to recursive descent by hand, along with several other ad hoc strategies that you need to parse an ad hoc language like shell. (ANTLR is a great front end, but not necessarily a good back end. The generated Java code is probably OK, but the C++ code it generates is preposterous. Yacc is not that much better, i.e. with globals all over the place.) "Just type out the code" is a horrible strategy because you will end up not knowing what language you've designed. If your post advocated "prototype your grammar with a tool, and then manually transcribe the grammar to code", then I'd be inclined to agree. But that's not what you said. It seems like you are more interested in telling everyone what a great programmer you are, and how things are so easy for you, rather than spreading any interesting knowledge about parsing.
judofyr 10y ago
A Pratt-style parser makes expression precedence easy in a recursive descent parser: "use strict"; var tokens = [2, '+', 5, '+', 9, '+', 4]; var PREC = {'+': 1, '-': 1, '*': 2, '/': 2}; function expr(prec) { var value = tokens.shift(); while (true) { var nextToken = tokens[0]; var nextPrec = PREC[nextToken]; if (!nextPrec) break; // not an operator if (nextPrec <= prec) break; tokens.shift(); var rest = expr(nextPrec); value = [nextToken, value, rest]; } return value; } console.log(expr(0)); I find this technique useful because I can implement it in any language without being dependent on a parser generator.

chubot 10y ago

Your comments betray a lot of ignorance, so I will just point out the glaring inaccuracies in #1. Here are two different expression parsers that are likely installed on machines you use, and they absolutely make a function call for each level of precedence (eval1, eval2, ..., exp1, exp2, ...) http://code.metager.de/source/xref/gnu/coreutils/src/expr.c http://code.metager.de/source/xref/gnu/coreutils/src/expr.c https://opensource.apple.com/source/bash/bash-76.1/bash/expr.c https://opensource.apple.com/source/bash/bash-76.1/bash/expr... My point is not that this is BAD -- it probably doesn't matter on modern machines. I'm just saying there are choices to make. Parsing requires some knowledge and choices -- that's all. You don't just "type out the code". #3 is not a refutation, because all the languages I mentioned are extraordinarily common. The answer to "parsing real languages is hard" is not "don't parse real languages". I can also tell by #4 that you don't have any background in security. It's not about YOUR code per se. It's about code that is deployed and that we all rely on.

SamReidHughes 10y ago
1. Did I not say there might be some living strawmen out there? 3. Did I say we shouldn't parse real languages? No, I said the problem was that it's not straightforward to combine two languages into a new one. The problem's not at the level of parsers. 4. Did I not say it wasn't evenly distributed?