4 ms·

It doesn't have disadvantages apart from the code to manually manage an explicit stack. The actual space used will be reduced. And yes, it should be possible

It doesn't have disadvantages apart from the code to manually manage an explicit stack. The actual space used will be reduced. And yes, it should be possible to successfully read any well formed sexp that can be created in a text stream and held in memory. That's why quality parsers use an explicit stack as well. Recursion is a useful development tool in some cases, but when iterative algorithms fail because they use it, the implementations are buggy.

kazinator 9y ago
You can hold a S-exp in memory such that you don't have anywhere near enough memory left to scan it with even your condensed explicit stack. > That's why quality parsers use an explicit stack as well. Observation: that rules out the entire description of the ANSI CL reader from being quality, haha.
olliej 9y ago
I rewrote the JSC parser to be mostly iterative many years ago - for a “real” language making an iterative parser that is readable is incredibly challenging. Especially in something like js where an expression could actually contain a statement. The current state is “as iterative as is sanely understandable” and handles all real (and some insane) programs fine. I suspect similar is true for other production hand written parsers. Your alternative is table based parsers which can only reasonably be implemented with generators. The problem is that table based parsers are slower than hand rolled recursive descent parser by a fairl large margin, and general purpose generators (bison, yacc , etc) tend to have difficulty with the quirky syntax of large languages. Note there have been a number of papers over the years that demonstrated 2x perf improvements in yacc/bison by switching from indexed state transitions to computed go to, but even that leaves them slower than hand rolled.
- kazinator 9y ago
  > for a “real” language making an iterative parser that is readable is incredibly challenging. Not to mention if it is defined in terms of a character-classifying read-table which dispatches functions, which can be patched by the user program (as in Common Lisp).

kazinator 9y ago

You can hold a S-exp in memory such that you don't have anywhere near enough memory left to scan it with even your condensed explicit stack. > That's why quality parsers use an explicit stack as well. Observation: that rules out the entire description of the ANSI CL reader from being quality, haha.

olliej 9y ago

I rewrote the JSC parser to be mostly iterative many years ago - for a “real” language making an iterative parser that is readable is incredibly challenging. Especially in something like js where an expression could actually contain a statement. The current state is “as iterative as is sanely understandable” and handles all real (and some insane) programs fine. I suspect similar is true for other production hand written parsers. Your alternative is table based parsers which can only reasonably be implemented with generators. The problem is that table based parsers are slower than hand rolled recursive descent parser by a fairl large margin, and general purpose generators (bison, yacc , etc) tend to have difficulty with the quirky syntax of large languages. Note there have been a number of papers over the years that demonstrated 2x perf improvements in yacc/bison by switching from indexed state transitions to computed go to, but even that leaves them slower than hand rolled.

kazinator 9y ago
> for a “real” language making an iterative parser that is readable is incredibly challenging. Not to mention if it is defined in terms of a character-classifying read-table which dispatches functions, which can be patched by the user program (as in Common Lisp).