I was just reading the Wikipedia page for WebAssembly and it says: “WebAssembly is… designed to be faster to parse than JavaScript” , which got me thinking, what makes a certain language or data format faster to parse than others and what parsing algorithms are used?
1 Answer
This topic is very complex. You can google for parser algorithms and you'll get plenty of detailed material.
In general:
- The fewer ambiguities must be resolved, the faster the parsing process.
- The more tokens have to be considered before a decision can be made, the more complex it gets.
For example:
When a JS parser sees the function keyword in this code: function xyz(a, b) {}, the function keyword is ambigous. It first has to process the next token xyz and see that it is an identifier before it can decide that it is a function declaration.
However, if the next token were a ( we are dealing with a function literal: function(a, b) {}. That requires the parser to behave very differently, thus more code in the parser, thus slower execution.
If there were different keywords for these two purposes, there would be no ambiguity:
function_decl xyz(a, b, c) {} and function_lit(a, b, c) {}
However, nobody would want to write in such a language. But WebAssembly is not supposed to be written by hand. That allows the language to be tailored towards machines, rather than humans.
-
1
-
9@Moses: Yes, writing a naive lisp parser is trivial, because the syntax is homoiconic with the structure of an abstract syntax tree and almost no ambiguities exist.– PhoshiMar 10, 2017 at 11:39
-
4Another good example is bytecode, often can be parsed with a looping switch statement and that's it. Mar 10, 2017 at 13:36
-
@whatsisname Indeed, the same applies to regular Assembly and Web Assembly– marstatoMar 10, 2017 at 15:25