Co sprawia, że ​​niektóre rzeczy są łatwiejsze do przeanalizowania niż inne?

8

Właśnie czytałem stronę Wikipedii dotyczącą WebAssembly i napisano: „ WebAssembly jest… zaprojektowany tak, aby był szybszy w analizie niż JavaScript ”, co skłoniło mnie do zastanowienia się, co sprawia, że ​​określony język lub format danych jest szybszy do analizy niż inne i jakie są algorytmy parsowania używany?

Mojżesz
źródło

Odpowiedzi:

18

Ten temat jest bardzo złożony. Możesz wyszukiwać w Google algorytmy analizatora składni, a otrzymasz mnóstwo szczegółowych materiałów.

Ogólnie:

  • Im mniej niejasności należy rozwiązać, tym szybszy jest proces analizy.
  • Im więcej tokenów należy wziąć pod uwagę, zanim będzie można podjąć decyzję, tym bardziej będzie ona złożona.

Na przykład:
gdy parser JS widzi functionsłowo kluczowe w tym kodzie function xyz(a, b) {}:, słowo kluczowe funkcji jest niejednoznaczne. Najpierw musi przetworzyć następny token xyzi sprawdzić, czy jest to identyfikator, zanim zdecyduje, że jest to deklaracja funkcji.

Jednakże, jeśli następny żeton były (mamy do czynienia z dosłownym funkcji: function(a, b) {}. Wymaga to, że parser zachowuje się zupełnie inaczej, dlatego więcej kodu w parserze, a tym samym wolniejsze wykonanie.

Gdyby dla tych dwóch celów były różne słowa kluczowe, nie byłoby dwuznaczności:

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

Jednak nikt nie chciałby pisać w takim języku. Ale WebAssembly nie powinien być napisany ręcznie. Pozwala to na dostosowanie języka do maszyn, a nie ludzi.

marstato
źródło
1
Czy to oznaczałoby, że Lisp można bardzo łatwo przeanalizować?
Mojżesz
9
@Moses: Tak, napisanie naiwnego parsera lisp jest banalne, ponieważ składnia jest homoikoniczna ze strukturą abstrakcyjnego drzewa składniowego i prawie nie ma dwuznaczności.
Phoshi,
4
Innym dobrym przykładem jest kod bajtowy, który często można analizować za pomocą instrukcji przełączania pętli i to wszystko.
whatsisname
@whatsisname Rzeczywiście to samo dotyczy zwykłego zgromadzenia i zgromadzenia internetowego
marstato,