xfq159 xfq159 - 7 months ago 27
Javascript Question

What is a random-logic lexical scanner and what is tree-walking code generator?

I'm studying SpiderMonkey internals. Its documentation says:

The compiler consists of: a random-logic rather than table-driven
lexical scanner, a recursive-descent parser that produces an AST, and
a tree-walking code generator.

I don't know what a random-logic lexical scanner is and what a tree-walking code generator is. I searched "random-logic lexical scanner" and "tree-walking code generator" but didn't get anything that looked promising. Can I get a pointer to these concepts?


I suppose what they mean by "random-logic lexical scanner" is that the lexical scanner was built by hand (or by many hands) rather than using a regular-expression-based table-driven lexical-scanner generator such as (f)lex. Presumably, the word is used as per the hacker lexicon, possibly acceptation 4 (incoherent, inelegant, disorganized) ["The program has a random set of misfeatures." "That's a random name for that function."] I'll refrain from further editorial comment.

Tree-walking is a pretty standard tool in code-generation, although few compilers are "pure" in the sense of being built from automatically-generated tree walkers and most serious compilers walk the tree more than once. While simple languages like Lua can be compiled directly during the parse, for most languages it is necessary to first build an abstract syntax tree (AST) and then do one or more walks over the tree. (Note: "abstract" in that phrase qualifies the word "syntax", not the word "tree". The AST is very concrete. English can be annoyingly ambiguous at times.)

Look at the LLVM documentation for many examples of tree walks, for example. Also, ANTLR will do automatic tree generation and there have been a number of attempts to automate or systematize code-generation with ANTLR; one example (which I haven't read so cannot either endorse or criticise) is AJ Admiraal's master's thesis "Automated ANTLR Tree walker Generation" which I mention only because it was the first of a large number of hits from a Google search for "tree-walking code-generation".