Qu'est-ce qui rend certaines choses plus faciles à analyser que d'autres?

8

Je lisais juste la page Wikipédia de WebAssembly et elle dit: « WebAssembly est… conçu pour être plus rapide à analyser que JavaScript », ce qui m'a fait réfléchir, ce qui rend un certain langage ou format de données plus rapide à analyser que d'autres et quels algorithmes d'analyse sont utilisé?

data-structures parsing syntax Moïse
la source

Réponses:

18

Ce sujet est très complexe. Vous pouvez rechercher des algorithmes d'analyse syntaxique sur Google et vous obtiendrez de nombreuses informations détaillées.

En général:

  • Moins il faut résoudre d'ambiguïtés, plus le processus d'analyse est rapide.
  • Plus il faut prendre en compte de jetons avant qu'une décision puisse être prise, plus elle devient complexe.

Par exemple:
Lorsqu'un analyseur JS voit le functionmot - clé dans ce code function xyz(a, b) {}:, le mot-clé de fonction est ambigu. Il doit d'abord traiter le jeton suivant xyzet voir qu'il s'agit d'un identifiant avant de pouvoir décider qu'il s'agit d'une déclaration de fonction.

Cependant, si le jeton suivant était un (nous avons affaire à un littéral de fonction: function(a, b) {}. Cela nécessite que l'analyseur se comporte très différemment, donc plus de code dans l'analyseur, donc une exécution plus lente.

S'il y avait des mots clés différents pour ces deux objectifs, il n'y aurait aucune ambiguïté:

function_decl xyz(a, b, c) {} et function_lit(a, b, c) {}

Cependant, personne ne voudrait écrire dans une telle langue. Mais WebAssembly n'est pas censé être écrit à la main. Cela permet d'adapter le langage aux machines plutôt qu'aux humains.

marstato
la source
1
Cela signifierait-il que Lisp est très facilement analysé?
Moses
9
@Moses: Oui, écrire un analyseur nisp naïf est trivial, car la syntaxe est homoiconique avec la structure d'un arbre de syntaxe abstraite et il n'y a presque aucune ambiguïté.
Phoshi
4
Un autre bon exemple est le bytecode, souvent peut être analysé avec une instruction switch en boucle et c'est tout.
whatsisname
@whatsisname En effet, la même chose s'applique à l'assemblage régulier et à l'assemblage Web
marstato