Compiler Construction: The Art of Niklaus Wirth (2000) [pdf]
pdfs.semanticscholar.org
pdfs.semanticscholar.org
Unfortunately this is something that no compiler I know of does, as evidenced by their -O0 being far worse than even what a naive Asm programmer (human) could do, and it's one of the things that irks me about compilers. Dataflow-directed, "work backwards" techniques might be the solution to this, but once again I don't know of any compilers that do it.
On the other hand, his points about using recursive-descent parsing seem to agree with the majority of widely-used compilers. However, this is factually incorrect:
I even think that the availability of powerful bottom-up parser generators such as Yacc are responsible for the cryptic syntax of C.
Dennis Ritchie's first C compiler used recursive descent. Yacc itself was written in C, so it could not have come before. You can see the sources yourself here: https://news.ycombinator.com/item?id=5748672
http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c...
Search for statement() and forstmt().
(This site has a more modern, easier-to-read version of the Github files, which at least has #defines rather than hard-coded ints!!!)
But a large part of it is also Dijikstra's shunting yard algorithm:
http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c...
Read an expression and return a pointer to its tree. It's the classical bottom-up, priority-driven scheme. The initflg prevents the parse from going past "," or ":" because those delimitesrs are special in initializer (and some other) expressions.
tree()
If you're willing to sacrifice a bit more generality you can parse a lot more. E.g. my (very much in-progress and incomplete) Ruby compiler uses precedence parsing with tweaks to parse most of the Ruby grammar, including blocks (do/end, {/}), array indices and initializers (foo[1], vs [1,2,3]) and more.
It's been hell to adjust the priorities, and it's not correct yet, but I also think it can be cleaned up quite a bit more. The biggest pain point, actually, is tidying up the generated tree to remove superfluous nodes and flaten various bits, and that's where I'll need to do the most work to simplify.
There are of course ugly parts of this with Ruby that ruined my originally quite nice and clean generic shunting yard code. E.g. if "foo" is a local variable "foo [1]" should parse as "foo.[](1)" (that is '[]' is a method name), while if "foo" is not a local variable, it is implicitly a method call, and "foo [1]" should parse as "foo([1])" with "self" as implicit receiver. I've for now resolved that by having a few "artificial" terminals to handle this and a few other ambiguities that are picked based on context and resolved later, but I'm really not happy about it. Worst case is I "surrender" and convert it to a recursive descent like the higher levels of the grammar, but I want to see what I can do with the current one first.
Currently the full parser, which still lacks some parts of Ruby is about 1600 lines of Ruby (including the lexical tokenizer and some generic parser/scanner utility classes), which I'm distinctly displeased about - it's much smaller than MRI, but not as much smaller as I think should be possible, especially since it's still missing pieces; granted there's a lot of comments, but I think parsing Ruby in Ruby should be doable in <1000 lines of Ruby code using recursive descent + precedence parsing despite Ruby's many idiosyncracies. Less if you exclude the code for a decent generic parser library. I think that says a lot of the simplicity of applying both recursive descent and precedence parsing..
Sure, you can also deal with terminal overloading using adjacency if you want. However, the parser gets more complex and it becomes less worth it. In the parsers I build, I match braces in a separate earlier phase anyways (you don’t need a parser to do that, and it makes the parser much more robust if you do).
However, the main drawback of a precedence parser is that you don’t get any parse errors out of it, and you have to manually go back and check that your trees are actually well formed. So I’ve went back to pure recursive descent.
It really doesn't change much. Here's a simple one that can handle simple function call syntax: https://gist.github.com/vidarh/a109c3788044736568bd71e79e842...
Apart from the operator definitions, to handle parentheses it contains two checks for the ":lp" operator type I used for left parentheses / any other tokens like brackets that'd behave the same, and one line to force :rp (right/closing parenthesis) to trigger a reduce. 40-something of those lines are the actual shunting yard/precedence parsing.
The variant I use for my Ruby parser does have some extra (ugly) hacks needed to deal with Ruby ambiguities, and "fun" stuff like variable arity operators (e.g. to handle method calls or things like "return") but the above is pretty much what you need to deal with saner grammars in a fairly generic way.
> you don’t need a parser to do that, and it makes the parser much more robust if you do
That very much depends on the language. In Ruby for example, the meaning of both parenthesis and curly/square brackets is context-sensitive. E.g. {} is a Hash literal. "foo {}" is a method call with a block. Or one of my "favorites": foo(5,1) is valid and has two arguments. foo(5,:bar => :baz) is valid. foo(:bar => :baz,5) is a syntax error ( "=>" is expected rather than ")" as the first "=>" turned it and all following elements of the argument list into an implicit Hash literal (so the last two ones are equivalent to foo(5, {:bar => :baz) and foo({:bar => :baz, 5}) respectively). There are more caveats, but I don't remember all of them off the top of my head. Some of them you could probably handle quite easily while pre-parsing, but you'd need to apply at least some grammar rules as many constructs acts very differently depending on whether or not an operator is used as prefix or infix for example. E.g. "% foo " is the literal quoted string "foo" (space acts as the quote character) while (foo % bar) is foo modulo bar, so you can't even safely tokenize Ruby without some thought to the preceding token at a minimum.
> However, the main drawback of a precedence parser is that you don’t get any parse errors out of it, and you have to manually go back and check that your trees are actually well formed.
Sure you do. If the value stack contains fewer arguments than the current operator requires after any reduce step that the priorities require, you have an error, and the cause is generally straightforward enough to place.
Constructing precise errors from that can be a bit painful, but it usually points at the "correct" spot if you record the locations of tokens, and the priorities lets you process the priorities of the operators and easily enough determine what would be valid.
I'm not sure how you'd use it to end up with invalid trees. In the contexts I've used it, the tokenizer combined with the precedence table is enough to ensure that the trees are syntactically well formed. If you want to apply semantic checks, you can just as easily call out to do those tests with a precedence parser as with a recursive descent one.
The only place where a pre match step doesn’t work is when you have tokens that are overloaded to sometimes be braces or not; I.e. < and > in most languages after C++ that has generics. Actually, you need non deterministic parsing in most cases with these, which is a pain and I wish new languages wouldn’t keep copying this mistake (typescript).
It looks like you are checking correctness in your precedence parser, which is fine, but it’s not possible to do that for many languages.
I don't see what you mean when you say it makes it more robust. They're no different than other operators and punctuation.
With respect to balancing, I'm actually not sure, There are sufficient corner cases to try to exploit that it's not obvious to me if you can or can't construct cases that'd be hard to get right. Writing a Ruby parser keeps teaching me corners of the grammar that I've never touched in 13 years of using the grammar... Many of them are dark corners I've never seen in the wild, and hope I never do.
With respect to "<>", you certainly can do %<foo> in Ruby, but that's easy enough to handle in the tokenizer, assuming you add a token lookbehind so I don't think it changes things (needed to know if "%" is the modulo operator or starting a quoted string). Meanwhile "%>foo>" means the same ("<[{(" after "%" starts a quoted string that ends with the "closing" sybol, but most other non-alphabetic symbols starts a quoted string that ends with the same symbol - unfortunately this includes whitespace)
I'm starting to think you may be right they'll be ok to handle separately, though I still don't see a reason to do it.
> It looks like you are checking correctness in your precedence parser, which is fine, but it’s not possible to do that for many languages.
Depends what you mean by "checking for correctness". In the simplest form, such as the example I posted, it is applying one very basic check: Does the number of available values on the value stack match what is required by the operator currently being processed?
The only thing you need to be able to do in order to do that is to be able to split the tokens into operators and other symbols (which are all values/operands as far as the precedence parser is concerned), and match the operators against a list of operator types and priorities. If you can do that, you can construct a well formed tree as per the rules specified by the precedence parser configuration. If you can't, you probably shouldn't parse it with that parser, but should instead either augment the parser to support what you need, or use something else.
It sounds to me as if you're checking the trees afterwards because you've shoehorned a grammar that's beyond the capabilities of the specific precedence parser into using it anyway but deliver trees that matches what you've actually specified but not what you want, and that this is what you don't consider well formed. That's fair enough, and I've done post-processing myself too, but generally I've come to think it's better to push capabilities to build the tree the way you want it in the first place to the parser. In any case I don't really consider that "fixing" malformed trees: The parser will only accept trees that are syntactically valid according to the classification of the tokens and the precedence rules.
Error recovery mainly. An unpaired brace can simply be flagged and then ignored during parsing. Maybe not so interesting for a batch parser, but it works really well in an IDE where transient errors like this are common. The other thing is that you know exactly where your brace constructions end, so you don't need to parse beyond them. Likewise, if you have parsed all that you can inside the brace area and still haven't reached the end, you can just flag the remaining tokens as unexpected junk and move on to the end of the brace, recovering very gracefully. Finally, to if you type ( inside (....) to get (...(...), you can use the fact that the outer parens to were previously matched to flag that the inner paren just typed is the one unmatched, not the outer ones.
For live programming contexts where you are constantly parsing and type checking, this is useful.
> Depends what you mean by "checking for correctness". In the simplest form, such as the example I posted, it is applying one very basic check: Does the number of available values on the value stack match what is required by the operator currently being processed?
That is basically a check, I'm not really versed in Ruby's grammar, in many languages the grammars are quite complicated and BNF-style enforcements is very necessary...you also need to consider construction of your AST for type checking and execution (which you might not need for your case).
> The parser will only accept trees that are syntactically valid according to the classification of the tokens and the precedence rules.
Given just precedence rules, it should be clear that syntactic validity isn't really a thing.
I don't see what that'd generally buy vs. simply trying the parse until it fails, though.
> The other thing is that you know exactly where your brace constructions end, so you don't need to parse beyond them.
That's automatically handled simply by adding the closing braces to the operator table, and terminating when the right type is reached, or when a symbol is hit that is not valid within the context. E.g. the example parser I linked to will automatically terminate that way if you invoke it the right way.
> Likewise, if you have parsed all that you can inside the brace area and still haven't reached the end, you can just flag the remaining tokens as unexpected junk and move on to the end of the brace, recovering very gracefully.
That's a line or two to catch the exceptions the example code throws and the read tokens until the specified closing brace/bracket type.
> Finally, to if you type ( inside (....) to get (...(...), you can use the fact that the outer parens to were previously matched to flag that the inner paren just typed is the one unmatched, not the outer ones.
That sounds specific to an IDE, and not really something I've looked at, and does sound like it might be useful. The other ones don't really convince me, but I guess for an interactive parser this one could be. Of course it's trivial to combine that with a precedence parser too, and still handle it in the parser.
> That is basically a check, I'm not really versed in Ruby's grammar, in many languages the grammars are quite complicated and BNF-style enforcements is very necessary...you also need to consider construction of your AST for type checking and execution (which you might not need for your case).
It's a check that is inherent to the precedence parser. The entire point of the parser is "shunt" tokens onto an operand and operator stack effective sort them into reverse polish notation. You can't do that without knowing if the operator is prefix, postfix or infix and what arity the operator has (though most preced check if the token stream matches the rules in the operator table, and if so output expressions. ence parsers will just assume an arity of 1 for prefix/postfix and 2 for infix, that's easy to overcome).
The operator table is a specification of the grammar according to those rules. If you get a malformed tree, either the parser in question doesn't support your grammar, or your grammar specification in the form of the operator table is malformed.
> BNF-style enforcements is very necessary..
There are certainly subsets that are awkward or requires you to augment a precedence parser. E.g. as I described elsewhere, in a past experiment where I did parse a whole Pascal-like language this way, I had to add a bunch of extra operator types, but really it just boils down to specifying minimum and maximum arity to the left and right of the operator, and you can handle very complex structures, but certainly not all.
You probably could extend a precedence parser to handle most languages in their entirety with a relatively small set of rules, but we agree it's probably not worth it. My point is not to try to parse every construct with a precedence parser, but that I've yet to see a grammar that doesn't have the typical highly recursive expression subset of the grammar that a precedence parser is a great fit for, but also that even surrounding that, a precedence parser is often easy enough to extend to a fairly large additional subset of the grammar.
E.g. my Ruby parser handles 26 productions outside the precedence parser and 50 operators (some "synthetic" to handle special parser rules) in the precedence parser.. It'd be easy enough to handle most of the 26 in the precedence parser too, and in fact I've moved more things into the precedence parser than the other way, but some constructs like "class", "if/else/elsif/else/end", "case/when" etc. will probably never get added to it.
> you also need to consider construction of your AST for type checking and execution (which you might not need for your case).
The precedence parser itself does not need to put any limits on the AST construction. In fact, the example I posted explicitly decouple tree construction from the parsing, so you can pass it a builder class that can apply whatever additional constraints you want on the construction of the trees. I don't think the tree construction there would end up typically being any more complex than in a typical recursive descent parser.
Brace completion that isn’t stupid for one.
Everything I’ve done is for IDEs, I don’t really believe in batch parsers anymore.
As for using it for the entire programming language, like for/while/switch, I see the discussion with vidarh below.
I haven't seen a parser written like this, so that's interesting.
However I consider the "opposite" sort of a mistake? Doug Crockford uses top-down operator precedence to parse ALL of JavaScript, not just the expression language.
Review of Pratt/TDOP Parsing Tutorials http://www.oilshell.org/blog/2016/11/02.html
I remember being confused by this, and I think it is still confusing. It seems to me that the statement language and expression language are separate things, and it makes sense to use recursive descent for the statement language and either top-down or bottom-up precedence for expressions. In other words, the architecture of the original C compiler is very clean, and no doubt influenced the language design. (On the other hand, it's probably also responsible for the fact that C has so many levels of precedence, some of which don't make sense!)
Also, the difference between "Pratt parsing" and "Precedence climbing" is sort of a code organization issue -- do you handle a[i] and x?a:b in the same place as a*b a+b etc.? I wondered if there is an analogous thing for bottom-up expression parsing. I like having each "form" in one function.
Pratt parsing is a nice complement to recursive descent; it's accurate to say that it's a variant of recursive descent with the additional input of numerical priorities.
I've done a full Pascal-like language using bottom up precedence parsing in the past. It was my first compiler project about 25 years ago or so, and "invented" precedence parsing with the help of a symbolic expression evaluator in Prolog in a book I picked up that I tried to figure out how to translate to Pascal.
It was very disappointing to find out it was a well known algorithm, but it was very interesting to try to expand it to handle a full language, which involved funky things like handling operators with different structure than just simple single-operand prefix/postfix + infix operators. E.g. I implemented a dual-arity prefix operator to handle for/while/if/ternary for example. So "while" took two expressions: the condition and a block.
The hard part was not handling the control structures, but getting the priorities right.
I'm not sure I'd do that again. My Ruby parser uses recursive descent for the top level productions.
But it was fascinating to do, as it did make for a very compact parser.
> It seems to me that the statement language and expression language are separate things,
I think if you go down that route, then you are implicitly deciding that everything is an expression. In e.g. Ruby that is true, though many constructs just returns nil (e.g "somevar = while condition; end" is valid). But given that many of the "operators" are only allowed at specific levels, it makes less sense to use a precedence parser anyway (e.g. "class" can't occur in a method body for example).
For me, those two are the biggest considerations to whether or not I'd consider a precedence parser: Whether or not everything is an expression, and which keywords are only allowed in specific contexts.
But even if it's feasible without too many contortions, it may still be very painful.
That is, regardless of whether you're doing it top-down or bottom-up, using an operator precedence algorithm for statements is painful.
I think the reason is simply that there is a fundamental relationship between the language you are parsing (the data) the algorithm you choose to parse it with (the code). Those 2 things are tightly linked.
I think this isn't emphasized enough in introductory texts. They usually only have time to teach one parsing method, and the language being parsed is chosen to fit that. Or maybe you choose one problem like shift-reduce conflicts, but you don't get the comparison / contrast to other methods.
Turbo Pascal (and Delphi), originally influenced by Wirth's books did exactly that. It was an incredibly fast compiler that generated surprizingly decent binaries.
I'm sure it helped that Pascal had a IMNHO saner calling convention (more like the current amd64 convention) - so would utilise register for passing arguments rather than always using the stack.
I'm not saying you can't, I'm just saying that "as fast machine code as early 90s era c compilers" might not translate to as fast as today's c++ compilers machine code.
> Unfortunately this is something that no compiler I know of does,
You're probably right compared to modern compilers. What you need to compare to are the compilers of the era, which were truly abysmal.
It's not that the Wirth compilers generated fantastic code (e.g. at least one of Wirths students explored adding much more aggressive optimization to his Oberon compiler), but they generated code that was a great deal better than a lot of non-Wirth style compilers at the time.
Some compilers of the time even depended on peephole optimizer passes because the code they generated was so bad that even simple 2-3 instruction peephole passes were enough to drastically improve the code. There was little reason for this. E.g. most of the time it was a matter of as basic stuff as passing on information about the registers to use rather than the dumb/naive approach of generating everything using scratch registers that you move things to/from.
I remember back in my asm days that I once had the C source for a GUI component I wanted to use, but the code the C compiler I had available generated was so awful that in exasperation I compiled it, disassembled it, and proceeded to manually clean it up. I deleted about half the instructions of about several thousand lines of compiler output, with very minimal fixups.
The first Java client jit compiler, was developed by Robert Griesemer (former PhD student of Wirth). The design of the compiler is described in the paper "A compiler for the java hotspot virtual machine", published in the same book: "The School of Niklaus Wirth: The Art of Simplicity".
> Dataflow-directed, "work backwards" techniques might be the solution
Destination driven code generation is a known technique. It doesn't generate good enough results to have gotten much attention (better than what you get from -O0, though).
Single pass compilers have their advantages.
[0] https://www.amazon.com/School-Niklaus-Wirth-Art-Simplicity/d...
Unfortunately in languages like C++ these inefficiencies often originate from inline function expansion rather than the programmer and thus are absolutely necessary.
> Strive for short compilation times
I wish designers of Swift heard this... Swift's build times can be horrifically slow for no good reason, it seems. I think slow build times have become a new norm pretty much like e.g. graphics display boot up times, i.e. someone at some point convinced the users that it's the way it should be and as a new norm no vendor strives to improve it.
People tend to defend slow boot up times with arguments that boil down to the aphorism:
Better the code be correct than fast.
Unfortunately most modern software out there is neither, which is where the whole argument falls apart.
Hanspeter Mössenböck: Compiler Construction - The Art of Niklaus Wirth. Chapter in: Böszörmeny et al.(eds): The School of Niklaus Wirth, dpunkt.verlag 2000, pp.55-68
An extensive list of Mössenböck's publications can be found here[2]
[1] http://ssw.jku.at/Research/Papers/Moe00b.html
[2] http://ssw.jku.at/Research/Papers/ (while this from the page looks like it's for his institute, it looks like all of them have him as at least co-author, and they include papers from his past institutions including his time at ETHZ with Wirth; e.g. a favourite of mine of his earlier paper is this collaboration with Marc M. Brandis on generating SSA forms for structured languages in a single pass [3] from '94 - as a confessed Niklaus Wirth fanboy I read most of the papers that came out of his research group in the early 90's..)
[3] http://ssw.jku.at/Research/Papers/Moe94.html
EDIT: I of course had to check, and Amazon (at least in the UK) has the book this is from (The School of Niklaus Wirth: The Art of Simplicity ), though it's expensive... I just had to share this hilarious find from one of the reviews:
"For me, this book is one to keep forever. I enjoyed every page (apart from the section written by Dijkstra since it was handwritten..)."
EDIT2: And having been seduced into buying this book, I can confirm Dijkstra's contribution (On the transitive closure of a well founded relation; dedicated to Niklaus Wirth) is in fact included in his handwritten form. I wish I had handwriting like that (but not enough to put in the effort).
I used to have that book somewhere. All of it was nicely typeset, except for Dijkstra's chapter, which was facsimile copies of (nicely) handwritten text.