I read basically the whole of the TeXbook (the spiral-bound book documenting the TeX language and implementation) many years ago, and found it fun and quirky, and very educational regarding how typesetting is done, and how typesetting practices can be transported into a computer implementation.
It was, for example, where I learned what an "em" is, the difference between a hyphen and an em-dash, what a kern is, what italic correction is, what leading is, and on and on.
But I found the language description not very clear. There are passages in the TeXbook that refer to different stages in processing as the stomach, mouth, gullet, etc. I later read an offhand comment that Knuth did not use a conventional lexer/parser setup in implementing TeX, and that decision made TeX more ad hoc from a language point of view. This, in turn, may have made the macro expansion setup more complex, with its expandable vs. not expandable tokens, restricted modes, etc.
I wonder if others who have more experience with language design had the same reaction?
I think that there aren't many fans of TeX's design. (Well, I rather like it, but probably because I am not a language designer.) Seibel (http://lambda-the-ultimate.org/node/3613#comment-51120) quotes Knuth as saying (in "Coders at Work"—but the relevant page is not on Google books):
Mostly I don't consider that I have great talent for language design.
Some writers of real compilers (vs. school projects) even today would avoid lex and yacc. Stroustrup, for example, wrote that in hindsight he shouldn't have used yacc for his cfront, apparently it brought him more pain than benefit.
Yacc and lex (and even more modern versions of the parser generators) have good "educational" value, but are far from being the silver bullets in practice.
To add my example: For my first and simple compiler used in the commercial application I used yacc. The start looked simple, then I hated it. It looked to me that I invested more energy in managing to do something "the yacc way" than to actually do something. For my more recent one, much more complex, I avoided yacc using a variant of recursive descent and never came to the point to miss anything, quite the opposite.
The one production compiler I worked on used YACC because we thought it was a good idea, but this was probably correct in that the PhD that did the parser part was a student of Hopcroft. She actually published a paper about error correction based on the work there.
Any compiler I write these days would do what you are saying--recursive descent. There is a nice technique called "chart" that helps with this.
Thanks. Do you mean this: http://en.wikipedia.org/wiki/Chart_parser It seems it's something to be more used for the natural language parsing, less for the programming languages?
That turns out to not be a very good writeup. The published work is http://dl.acm.org/citation.cfm?id=801348 and Dick Vile did a lot of work on it years after that, using it to describe an in-house production language.
TeX is weird. Really weird, if one expects it to work like a modern programming language.
The crux of it is that it's a macro-expansion language, which means that you pretty much need to do the kind of stream-processing approach TeX uses, since you don't know the expansion of a macro up-front, which in turn can very well change the meaning of tokens downstream of that again. For an (admittedly extreme) example of this, consider TikZ; it's basically an entire new programming language, implemented purely by TeX macros.
I sometimes compare it to programming in Common Lisp, but you all you have available are the primitives (except lambda, I supppose) and defmacro.
Thanks, I think that's pretty much the issue. Because of the flexibility of the language (not just macros, but individual characters can change meaning using the \catcode mechanism), you can't have a fixed lexer. This makes the situation unlike the standard language setups I'm used to.
The more I work with languages, parsing, etc. the more I think that the lexer/parser setup is a bad idea. Many non-trivial languages are actually harder to implement clearly in the traditional lexer/parser setup due to required coupling between the lexer and parser.
Really? Why would they be coupled? I mean, maybe a little bit. For instance, maybe the parser could tell the lexer what kind of token it expects to see next, so that the lexer doesn't parse an int as a float by mistake, but that doesn't sound that bad to me. (I should point out that my experience here is a single class in college.)
The traditional theories about parsing and their implementations in tools like yacc, lex, antlr, etc. are not that important in practice. I also used them in some university courses, but after I encountered parsing problems in practice it seemed easier to just implement a recursive descent parser in the host language.
First, you have to learn the DSL's of these tools (which are non-trivial in detail). Second you have to integrate them into your toolchain. Third - and that is my biggest complaint - you have to connect the Parser combinator's AST to your domain AST. The last thing is pretty amusing as I consider it the main purpose of a parser.
In practice (hopefully after evaluating the need for a custom data format as it might be possible to hijack existing languages and standards) I either use a combinator-parser (if FP available) or an ad-hoc recursive descent parser. Maybe I consider a lexer but the representation of tokens is also a non-trivial decision.
Most languages will have some sort of way of letting you extend them; inasmuch as this will require a new way of lexing, this will add some coupling.
One example: shell aliases. The shell syntax in POSIX is defined in the standard lexer/parser divide (which is already a bit of a pain, as a significant of the parsing logic is needed to correctly tokenize command expansions). When you encounter an alias expansion (which since it has to happen in the command position, doesn't happen until parse time) you expand the alias, and then need to re-lex the results.
In practice, many mature compilers and interpreters use a recursive-descent parser rather than any of the LL/LR/LALR things I learned in school.
Common Lisp actually defines its syntax in terms of a recursive-descent algorithm, and that's a language that largely came out of academia.
It was, for example, where I learned what an "em" is, the difference between a hyphen and an em-dash, what a kern is, what italic correction is, what leading is, and on and on.
But I found the language description not very clear. There are passages in the TeXbook that refer to different stages in processing as the stomach, mouth, gullet, etc. I later read an offhand comment that Knuth did not use a conventional lexer/parser setup in implementing TeX, and that decision made TeX more ad hoc from a language point of view. This, in turn, may have made the macro expansion setup more complex, with its expandable vs. not expandable tokens, restricted modes, etc.
I wonder if others who have more experience with language design had the same reaction?