4 ms·

One piece of advice I have for people writing a new language. Consider making your language so you can do one-character lookahead, with something like the 'shu

One piece of advice I have for people writing a new language. Consider making your language so you can do one-character lookahead, with something like the 'shunting algorithm' to handle precedence. I work on a system called gap ( www.gap-system.org ), and when parsing we only ever need to look one character ahead to know what we are parsing. This makes the error messages easy, and amazingly good -- we can say "At this character we expected A,B or C, but we found foo". It also makes the language easy to extend, as long as we fight hard against anyone who wants to introduce ambiguity. If your language is ambiguous, and you have to try parsing statements multiple times to find out what they are, then your error handling is always going to be incredibly hard, as you won't know where the problem arose. Of course, if you are parsing a language given to you, you just have to do the best you can.

chrisseaton 10y ago
It's a balancing act between designing syntax that makes sense for the programmer and syntax that makes sense for the parsing technology. I'd feel a bit silly explaining to someone that some twisted or ugly syntax construct was like that because it made writing the parser a bit easier, when the parser only has to be written once but the syntax has to be used in every program written using the language.
- barrkel 10y ago
  Code that's hard to parse is easy to get wrong in surprising ways. Difficulty in parsing almost always means ambiguous parses that need to be resolved with sufficient lookahead or semantic lookup; if the user makes a mistake, it may be in one of the ambiguous cases, which leads to surprise. In particular, error messages are impossible to keep clearly prescriptive in every case, because thy needs to take account of the inherent ambiguity.
tgb 10y ago
I used to use gap! I'd love some examples of explicit choices that were made that allow one-character lookahead.
- CJefferson 10y ago
  I can tell you some things where were rejected. One example of non-one-token lookahead is lambda functions, 'x -> x*2'. This means when you read an identifier, before you check if it valid in this scope you have to check if the next thing is '->'. If it is, this is a new identifer, if it's not, it's a variable reference and better be in scope. Now, let's consider multi-argument lambda functions. One possible notation is: (a,b,c) -> a+b+c. However, (a,b,c) is how GAP denotes permutations, and it was decided that parsing a whole permutation as "maybe this is a permutation, maybe it is the beginning of a lambda expression" would be too annoying, and would mean we couldn't print out some errors until we got to the end, and knew what type of object we had.
tyingq 10y ago
Does anyone have any examples of popular languages that are very easy to parse or ones that have a lot of ambiguity? I assume the lispy type languages fall into the easily parsed bucket, perhaps tcl as well? And Perl may be a good example of a language that has notable ambiguity?
- bandrami 10y ago
  Forth is probably the simplest to parse, and when you write a forth you usually write your parser in assembly. It consists of "start at the first non-whitespace character of the pad and continue until you reach another whitespace character; that's a token" (though "token" has a different meaning in forth; it's a "word"). Lisp seems like it should be nearly as simple: recursively read in a balanced s-expression and attempt to intern the atoms in that s-expression; error out if any of those steps fails. However, Common Lisp's scanner/parser (called the "reader") allows the user to define arbitrary macros; basically the scanner has access to the full compiler if you want it to, so it can get really complicated really quickly.
  - bandrami 10y ago
    And, just to finish that thought, "read macros" aren't some abstract corner case of interest to theoreticians; they are how a whole lot of the language and libraries (e.g. complex numbers, the regex library, etc.) are implemented.
- Drup 10y ago
  Raw lisp is obviously very easy, not sure about the various schemes. OCaml, the whole SML family are easy to parse (just an LR grammar that is easy to copy). I think Rust is the same. IIRC, Java is LL(k), so very easy. C is not LR(1) for annoying reasons (typedef). Same for Go, IIRC. Otherwise, it's okayish. Javascript has this inane "optional semicolon" thing, which probably makes it annoying. C++ is probably the most insane thing to parse. And then, there is bash[1]. http://www.oilshell.org/blog/2016/10/20.html http://www.oilshell.org/blog/2016/10/20.html
  - 10y ago

chrisseaton 10y ago

It's a balancing act between designing syntax that makes sense for the programmer and syntax that makes sense for the parsing technology. I'd feel a bit silly explaining to someone that some twisted or ugly syntax construct was like that because it made writing the parser a bit easier, when the parser only has to be written once but the syntax has to be used in every program written using the language.

barrkel 10y ago
Code that's hard to parse is easy to get wrong in surprising ways. Difficulty in parsing almost always means ambiguous parses that need to be resolved with sufficient lookahead or semantic lookup; if the user makes a mistake, it may be in one of the ambiguous cases, which leads to surprise. In particular, error messages are impossible to keep clearly prescriptive in every case, because thy needs to take account of the inherent ambiguity.

tgb 10y ago

I used to use gap! I'd love some examples of explicit choices that were made that allow one-character lookahead.

CJefferson 10y ago
I can tell you some things where were rejected. One example of non-one-token lookahead is lambda functions, 'x -> x*2'. This means when you read an identifier, before you check if it valid in this scope you have to check if the next thing is '->'. If it is, this is a new identifer, if it's not, it's a variable reference and better be in scope. Now, let's consider multi-argument lambda functions. One possible notation is: (a,b,c) -> a+b+c. However, (a,b,c) is how GAP denotes permutations, and it was decided that parsing a whole permutation as "maybe this is a permutation, maybe it is the beginning of a lambda expression" would be too annoying, and would mean we couldn't print out some errors until we got to the end, and knew what type of object we had.

tyingq 10y ago

Does anyone have any examples of popular languages that are very easy to parse or ones that have a lot of ambiguity? I assume the lispy type languages fall into the easily parsed bucket, perhaps tcl as well? And Perl may be a good example of a language that has notable ambiguity?

bandrami 10y ago
Forth is probably the simplest to parse, and when you write a forth you usually write your parser in assembly. It consists of "start at the first non-whitespace character of the pad and continue until you reach another whitespace character; that's a token" (though "token" has a different meaning in forth; it's a "word"). Lisp seems like it should be nearly as simple: recursively read in a balanced s-expression and attempt to intern the atoms in that s-expression; error out if any of those steps fails. However, Common Lisp's scanner/parser (called the "reader") allows the user to define arbitrary macros; basically the scanner has access to the full compiler if you want it to, so it can get really complicated really quickly.
- bandrami 10y ago
  And, just to finish that thought, "read macros" aren't some abstract corner case of interest to theoreticians; they are how a whole lot of the language and libraries (e.g. complex numbers, the regex library, etc.) are implemented.
Drup 10y ago
Raw lisp is obviously very easy, not sure about the various schemes. OCaml, the whole SML family are easy to parse (just an LR grammar that is easy to copy). I think Rust is the same. IIRC, Java is LL(k), so very easy. C is not LR(1) for annoying reasons (typedef). Same for Go, IIRC. Otherwise, it's okayish. Javascript has this inane "optional semicolon" thing, which probably makes it annoying. C++ is probably the most insane thing to parse. And then, there is bash[1]. http://www.oilshell.org/blog/2016/10/20.html http://www.oilshell.org/blog/2016/10/20.html
- 10y ago