7 ms·

Text parsing for programming languages is NOT a difficult problem. It is very easy actually, much easier than most academics would have you believe. What they

by jblow 10y ago

Text parsing for programming languages is NOT a difficult problem. It is very easy actually, much easier than most academics would have you believe. What they are doing is trying to write theories and build conceptual systems about how to do things. That is their job. But when it comes to practical matters, the best route to take, as someone who wants to build a working compiler that gives good error messages and where the parser does not hamstring the rest of it, is to ignore almost all that stuff and just type the obvious code.

treeform 10y ago
In jai, did you write the parser yourself or used a parser generator like yacc? In my toy languages I find writing my own parser more fun and not hard. I find it harder to make yacc do things such as indentation significance.
- nulltype 10y ago
  I'm pretty sure he mentioned he wrote his own parser. https://twitter.com/jonathan_blow/status/734817293331357697 https://twitter.com/jonathan_blow/status/734817293331357697
  - jblow 10y ago
    Yes, it is hand-written. The parser is MUCH easier to build than the interesting/new parts of the compiler are. Lexing is the absolute easiest thing, then parsing is 2nd place.
zeroxfe 10y ago
> Text parsing for programming languages is NOT a difficult problem. That depends entirely on 1) what grammar you're parsing, 2) what memory pressure you're in, 3) how fast you want to do it, and 4) how comprehensive you want the error handling. It's actually quite difficult to parse C++ on a low-memory embedded device without resorting to clever techniques.
- wofo 10y ago
  > It's actually quite difficult to parse C++ This is a specific problem of C++ though, given the fact that its grammar is extremely complex.
  - comex 10y ago
    I'm pretty curious what kind of project gave zeroxfe experience with parsing C++ on low-memory embedded devices.
- chubot 10y ago
  It also depends on what functionality you want your parser to support. In theory, parsing just means "accept or reject". In practice, you need to do something like build a tree, and there are many different possible tree representations depending on what you want to do. Clang aims to support very general transformation of C++ with their parser and AST. I was shocked to learn that Clang's AST has 60K lines of header files! That's not including the code, and it's not templates! That's class definitions!!! (wc -l include/clang/AST/*.h)
  - sklogic 10y ago
    This is not because of a parsing complexity, it is only because C++ is an awful language for writing ASTs and parsers. Without all the boilerplate, an AST can be much smaller.
- sklogic 10y ago
  Why would you parse C++ on a low memory device anyway? What are you going to do with it? Anything that follows the parsing would require far more memory.
- kazinator 10y ago
  Ideally, you don't even target a low-memory embedded device with C++, let alone process C++ on it. Anyway, C++ is just a strawman that seems to have been contrived deliberately in order to wreck most of the rational arguments defending "programming languages are easy to parse". Parsing as programming language is exactly as difficult as the hole we dig ourselves into. Programming language parsing isn't some information processing problem that exists in the world, or in another domain, that computer science is tasked with to solve; it's a problem that computer scientists and software people inflict on themselves. By making languages hard to parse by machine, we are also making them hard to use by humans. Humans need to parse the language also, and not have a magic oracle for doing so. (Indentation only goes so far, and can tell a lie). Still, there aren't actually difficult problems in parsing C++. It's more of a "death by a thousand blows". There is just the sheer size of it alone. The C++ parser source file in GCC is larger than some programming language implementations: their parsers, interpreters/compilers and all intrinsic routines combined. It's hard to comprehend the C++ grammar so that you can identify where the ambiguities lie, and form a strategy to deal with them, so as not to be surprised later.
chubot 10y ago
What algorithm are you using with the "obvious code"? Recursive descent? That definitely works well in many cases, but not all. Here are some things that I think are difficult about parsing: 1. The algorithm to use depends heavily on the language, and it takes some experience to know which algorithm to use for which language. Some languages are hard to write predictive recursive descent parsers for -- they can require a lot of backtracking, which is exponential in general. C would be a good example -- it is more efficiently parsed with a bottom-up algorithm than top down (recursive descent), because of the lookahead issue. In contrast, languages like Python or Go are designed to be LL(1) -- you just have to look at a single token -- "def" or "func" -- to know what kind of thing you need to parse next. Recursive descent was also considered too slow for expression parsing, where you have left recursion. If you have 13 levels of precedence, then you require 13 nested function calls to parse an atom. So you have basically 3 choices of: Pratt parsing, Shunting Yard algorithm, or Precedence Climbing (I've implemented #1 and #3 and like #3 the most). So you have to change the algorithm for the sublanguage of expressions, i.e. compose two different algorithms. (I think these days nobody cares about 13 levels of function calls, unless you are parsing gigabytes of C++ code. Of course, this happens literally all the time, because of header file explosion ...) 2. If you know exactly what language you are going to parse, writing a hand-written parser is straightforward (although laborious). If you don't know the language, then refactoring parsers can be quite difficult. You need good test cases not to break corner cases. A Lua paper talked about how until Lua 4.0 they used yacc while they were designing the language, and then when the language became more fixed in Lua 5.0, they switched to a hand-written parser. This seems to be very common. I think gcc also switched from yacc to a hand-written parser. 3. It's not straightforward to combine two parsers for two sublanguages and get a parser for the combined language (or get errors if the languages can't be composed). Many real languages are really several different sublanguages combined. C++ has a normal mathematical expression language, and a template expression language (there was that notorious >> vs foo<bar<T>> ambiguity in C++). Unix sh is about 5 different sublanguages mashed together (not counting external utilities). Parsing HTML requires parsing JS and CSS. http://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt.html http://tratt.net/laurie/blog/entries/parsing_the_solved_prob... 4. Writing secure parsers. This is an issue for languages like JavaScript, where the input is untrusted. If you write a parser in C, I pretty much guarantee I will find a crash or buffer overflow in it (through fuzzing or otherwise). Basically ALL parsers in production have crash bugs uncovered after YEARS of widespread use, e.g. Python, Clang, etc. See http://lcamtuf.blogspot.com/2015/04/finding-bugs-in-sqlite-easy-way.html http://lcamtuf.blogspot.com/2015/04/finding-bugs-in-sqlite-e... . Note how mature sqlite is and how extensively it is tested -- you can still shake obscure bugs out quite easily. 5. Writing reusable parsers. 5a. Try writing a parser that allows you to reformat your source code, with whitespace and comments preserved. Most languages have multiple parsers these days -- i.e. the Java parser in your compiler is not the same parser that's used by the IDE. 5b. Try writing a parser with the hooks necessary to supports code completion and auto-correct. There was a good video by Anders Hejlsberg here that mentioned that these type of parsers have to parse MORE THAN the language, so that they can continue to provide the required functionality when the code in the IDE is malformed. FWIW I recall that Steve Wozniak also disclaimed any background in parsing algorithms, and that he said he invented his own table driven parsing algorithm for BASIC. That is totally plausible, but I also think he would have a hard time writing certain parsers for certain languages, supporting advanced functionality, without some study. EDIT: #6: The line between the lexer and parser is not clear -- it depends on the language being parsed, and sometimes even on the implementation language. In theory, you have a pipeline from the lexer to the parser. In practice, the lexer and the parser often need to communicate, resulting in circularity. This communication can be hard to reason about and debug. Moreoever, you can often solve parsing problems (i.e. resolve ambiguity) in either the lexer or the parser. (I think Go's and JavaScript's semicolon insertion are done in the lexer) If you pick the wrong choice, then you can have bugs or a lot of extra complexity. It takes experience and thought to get these things right. (Side note: depending on the language, there can be more stages than just lexing and parsing. Unix shell has at least 3 stages.)
tacos 10y ago
> Text parsing for programming languages is NOT a difficult problem Counterpoint: Ohloh tried to build a simple line counter. After 7 years even with community support they never really got it right. https://github.com/blackducksoftware/ohcount/tree/master/src/parsers https://github.com/blackducksoftware/ohcount/tree/master/src...
- jblow 10y ago
  I don't know what Ohloh is but it looks like it's some kind of web software, in which case I am totally unsurprised. Are you confident that the same programmers could have successfully built a line-counter if they built it using parser tools?
  - scribu 10y ago
    Saying "it's not a difficult problem" and then turning around and implying "... but only if you're not one of those lousy web programmers" sure sounds like moving the goalpost.
    - jblow 10y ago
      Well, I think a lot of web programmers do not really know how to program. If someone is going to be offended that a potential employer asks them to reverse a linked list in an interview -- something that seems a bit trendy in the web world lately and several such articles have made the HN front page -- then look, that person does not really know how to program, so of course they think it's hard to do basic stuff. Such a person's opinion on how hard things are is not that relevant to how hard they are given a reasonable background education. Probably this sounds snobby to some people, but look, programming well is a never-ending pursuit, you can spend your whole life getting better, but it won't help anyone advance if we all pretend that everyone is good already.
  - tacos 10y ago
    The directory I linked shows Ragel lexers. It was a command line tool that fed a web app. All it had to do was count lines of code, blank lines, and comment lines for a variety of languages. It took years and they never got it right. Partly because every technical decision was based on neato-tool-of-the-month in the early Ruby/Zed Shaw era. But mostly because it's hard.
wfunction 10y ago
> Text parsing for programming languages is NOT a difficult problem And of course that's why the world is littered with a million 100%-functional C++ parsers, right?
- PeCaN 10y ago
  Given that parsing C++ may be Turing complete¹ I'm not exactly sure that's the best example to use. The world _is_ littered with a million JavaScript and Python parsers. ¹ http://stackoverflow.com/questions/14589346/is-c-context-free-or-context-sensitive/14589567#14589567 http://stackoverflow.com/questions/14589346/is-c-context-fre...
- thwd 10y ago
  C++ is a bad example because its' grammar is not actually context free. Writing a recursive descent parser is actually quite intuitive. It's the solution that you'd eventually arrive at if given the problem of parsing some specific context free language. GLR, GLL and PwD are solutions to parsing non-cfg (i.e. grammars that have more than one parse-tree) in optimal time.
- jackmott 10y ago
  It kind of is yeah. A new language is posted on reddit every day.

by jblow 10y ago

treeform 10y ago

In jai, did you write the parser yourself or used a parser generator like yacc? In my toy languages I find writing my own parser more fun and not hard. I find it harder to make yacc do things such as indentation significance.

nulltype 10y ago
I'm pretty sure he mentioned he wrote his own parser. https://twitter.com/jonathan_blow/status/734817293331357697 https://twitter.com/jonathan_blow/status/734817293331357697
- jblow 10y ago
  Yes, it is hand-written. The parser is MUCH easier to build than the interesting/new parts of the compiler are. Lexing is the absolute easiest thing, then parsing is 2nd place.

zeroxfe 10y ago

> Text parsing for programming languages is NOT a difficult problem. That depends entirely on 1) what grammar you're parsing, 2) what memory pressure you're in, 3) how fast you want to do it, and 4) how comprehensive you want the error handling. It's actually quite difficult to parse C++ on a low-memory embedded device without resorting to clever techniques.

wofo 10y ago
> It's actually quite difficult to parse C++ This is a specific problem of C++ though, given the fact that its grammar is extremely complex.
- comex 10y ago
  I'm pretty curious what kind of project gave zeroxfe experience with parsing C++ on low-memory embedded devices.
chubot 10y ago
It also depends on what functionality you want your parser to support. In theory, parsing just means "accept or reject". In practice, you need to do something like build a tree, and there are many different possible tree representations depending on what you want to do. Clang aims to support very general transformation of C++ with their parser and AST. I was shocked to learn that Clang's AST has 60K lines of header files! That's not including the code, and it's not templates! That's class definitions!!! (wc -l include/clang/AST/*.h)
- sklogic 10y ago
  This is not because of a parsing complexity, it is only because C++ is an awful language for writing ASTs and parsers. Without all the boilerplate, an AST can be much smaller.
sklogic 10y ago
Why would you parse C++ on a low memory device anyway? What are you going to do with it? Anything that follows the parsing would require far more memory.
kazinator 10y ago
Ideally, you don't even target a low-memory embedded device with C++, let alone process C++ on it. Anyway, C++ is just a strawman that seems to have been contrived deliberately in order to wreck most of the rational arguments defending "programming languages are easy to parse". Parsing as programming language is exactly as difficult as the hole we dig ourselves into. Programming language parsing isn't some information processing problem that exists in the world, or in another domain, that computer science is tasked with to solve; it's a problem that computer scientists and software people inflict on themselves. By making languages hard to parse by machine, we are also making them hard to use by humans. Humans need to parse the language also, and not have a magic oracle for doing so. (Indentation only goes so far, and can tell a lie). Still, there aren't actually difficult problems in parsing C++. It's more of a "death by a thousand blows". There is just the sheer size of it alone. The C++ parser source file in GCC is larger than some programming language implementations: their parsers, interpreters/compilers and all intrinsic routines combined. It's hard to comprehend the C++ grammar so that you can identify where the ambiguities lie, and form a strategy to deal with them, so as not to be surprised later.

chubot 10y ago

What algorithm are you using with the "obvious code"? Recursive descent? That definitely works well in many cases, but not all. Here are some things that I think are difficult about parsing: 1. The algorithm to use depends heavily on the language, and it takes some experience to know which algorithm to use for which language. Some languages are hard to write predictive recursive descent parsers for -- they can require a lot of backtracking, which is exponential in general. C would be a good example -- it is more efficiently parsed with a bottom-up algorithm than top down (recursive descent), because of the lookahead issue. In contrast, languages like Python or Go are designed to be LL(1) -- you just have to look at a single token -- "def" or "func" -- to know what kind of thing you need to parse next. Recursive descent was also considered too slow for expression parsing, where you have left recursion. If you have 13 levels of precedence, then you require 13 nested function calls to parse an atom. So you have basically 3 choices of: Pratt parsing, Shunting Yard algorithm, or Precedence Climbing (I've implemented #1 and #3 and like #3 the most). So you have to change the algorithm for the sublanguage of expressions, i.e. compose two different algorithms. (I think these days nobody cares about 13 levels of function calls, unless you are parsing gigabytes of C++ code. Of course, this happens literally all the time, because of header file explosion ...) 2. If you know exactly what language you are going to parse, writing a hand-written parser is straightforward (although laborious). If you don't know the language, then refactoring parsers can be quite difficult. You need good test cases not to break corner cases. A Lua paper talked about how until Lua 4.0 they used yacc while they were designing the language, and then when the language became more fixed in Lua 5.0, they switched to a hand-written parser. This seems to be very common. I think gcc also switched from yacc to a hand-written parser. 3. It's not straightforward to combine two parsers for two sublanguages and get a parser for the combined language (or get errors if the languages can't be composed). Many real languages are really several different sublanguages combined. C++ has a normal mathematical expression language, and a template expression language (there was that notorious >> vs foo<bar<T>> ambiguity in C++). Unix sh is about 5 different sublanguages mashed together (not counting external utilities). Parsing HTML requires parsing JS and CSS. http://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt.html http://tratt.net/laurie/blog/entries/parsing_the_solved_prob... 4. Writing secure parsers. This is an issue for languages like JavaScript, where the input is untrusted. If you write a parser in C, I pretty much guarantee I will find a crash or buffer overflow in it (through fuzzing or otherwise). Basically ALL parsers in production have crash bugs uncovered after YEARS of widespread use, e.g. Python, Clang, etc. See http://lcamtuf.blogspot.com/2015/04/finding-bugs-in-sqlite-easy-way.html http://lcamtuf.blogspot.com/2015/04/finding-bugs-in-sqlite-e... . Note how mature sqlite is and how extensively it is tested -- you can still shake obscure bugs out quite easily. 5. Writing reusable parsers. 5a. Try writing a parser that allows you to reformat your source code, with whitespace and comments preserved. Most languages have multiple parsers these days -- i.e. the Java parser in your compiler is not the same parser that's used by the IDE. 5b. Try writing a parser with the hooks necessary to supports code completion and auto-correct. There was a good video by Anders Hejlsberg here that mentioned that these type of parsers have to parse MORE THAN the language, so that they can continue to provide the required functionality when the code in the IDE is malformed. FWIW I recall that Steve Wozniak also disclaimed any background in parsing algorithms, and that he said he invented his own table driven parsing algorithm for BASIC. That is totally plausible, but I also think he would have a hard time writing certain parsers for certain languages, supporting advanced functionality, without some study. EDIT: #6: The line between the lexer and parser is not clear -- it depends on the language being parsed, and sometimes even on the implementation language. In theory, you have a pipeline from the lexer to the parser. In practice, the lexer and the parser often need to communicate, resulting in circularity. This communication can be hard to reason about and debug. Moreoever, you can often solve parsing problems (i.e. resolve ambiguity) in either the lexer or the parser. (I think Go's and JavaScript's semicolon insertion are done in the lexer) If you pick the wrong choice, then you can have bugs or a lot of extra complexity. It takes experience and thought to get these things right. (Side note: depending on the language, there can be more stages than just lexing and parsing. Unix shell has at least 3 stages.)

tacos 10y ago

> Text parsing for programming languages is NOT a difficult problem Counterpoint: Ohloh tried to build a simple line counter. After 7 years even with community support they never really got it right. https://github.com/blackducksoftware/ohcount/tree/master/src/parsers https://github.com/blackducksoftware/ohcount/tree/master/src...

jblow 10y ago
I don't know what Ohloh is but it looks like it's some kind of web software, in which case I am totally unsurprised. Are you confident that the same programmers could have successfully built a line-counter if they built it using parser tools?
- scribu 10y ago
  Saying "it's not a difficult problem" and then turning around and implying "... but only if you're not one of those lousy web programmers" sure sounds like moving the goalpost.
  - jblow 10y ago
    Well, I think a lot of web programmers do not really know how to program. If someone is going to be offended that a potential employer asks them to reverse a linked list in an interview -- something that seems a bit trendy in the web world lately and several such articles have made the HN front page -- then look, that person does not really know how to program, so of course they think it's hard to do basic stuff. Such a person's opinion on how hard things are is not that relevant to how hard they are given a reasonable background education. Probably this sounds snobby to some people, but look, programming well is a never-ending pursuit, you can spend your whole life getting better, but it won't help anyone advance if we all pretend that everyone is good already.
- tacos 10y ago
  The directory I linked shows Ragel lexers. It was a command line tool that fed a web app. All it had to do was count lines of code, blank lines, and comment lines for a variety of languages. It took years and they never got it right. Partly because every technical decision was based on neato-tool-of-the-month in the early Ruby/Zed Shaw era. But mostly because it's hard.

wfunction 10y ago

> Text parsing for programming languages is NOT a difficult problem And of course that's why the world is littered with a million 100%-functional C++ parsers, right?

PeCaN 10y ago
Given that parsing C++ may be Turing complete¹ I'm not exactly sure that's the best example to use. The world _is_ littered with a million JavaScript and Python parsers. ¹ http://stackoverflow.com/questions/14589346/is-c-context-free-or-context-sensitive/14589567#14589567 http://stackoverflow.com/questions/14589346/is-c-context-fre...
thwd 10y ago
C++ is a bad example because its' grammar is not actually context free. Writing a recursive descent parser is actually quite intuitive. It's the solution that you'd eventually arrive at if given the problem of parsing some specific context free language. GLR, GLL and PwD are solutions to parsing non-cfg (i.e. grammars that have more than one parse-tree) in optimal time.
jackmott 10y ago
It kind of is yeah. A new language is posted on reddit every day.