9

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?

19

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
    Would this mean that Lisp is very easily parsed? – Moses Mar 10 '17 at 11:10
  • 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. – Phoshi Mar 10 '17 at 11:39
  • 4
    Another good example is bytecode, often can be parsed with a looping switch statement and that's it. – whatsisname Mar 10 '17 at 13:36
  • @whatsisname Indeed, the same applies to regular Assembly and Web Assembly – marstato Mar 10 '17 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.