Что делает некоторые вещи проще для анализа, чем другие?

8

Я только что прочитал страницу Википедии для WebAssembly и там написано: « WebAssembly… предназначен для более быстрого анализа, чем JavaScript », и это заставило меня задуматься о том, что делает определенный язык или формат данных более быстрым для анализа, чем другие, и каковы алгоритмы синтаксического анализа используемый?

Моисей
источник

Ответы:

18

Эта тема очень сложная. Вы можете поискать алгоритмы синтаксического анализа в Google и получить много подробных материалов.

В основном:

  • Чем меньше неясностей необходимо устранить, тем быстрее процесс синтаксического анализа.
  • Чем больше токенов нужно рассмотреть, прежде чем принимать решение, тем сложнее оно становится.

Например:
когда анализатор JS видит functionключевое слово в этом коде: function xyz(a, b) {}ключевое слово function является неоднозначным. Сначала он должен обработать следующий токен xyzи увидеть, что это идентификатор, прежде чем он сможет решить, что это объявление функции.

Тем не менее, если следующая лексема были (мы имеем дело с функцией литерала: function(a, b) {}. Это требует, чтобы синтаксический анализатор вел себя очень по-разному, поэтому в синтаксическом анализаторе было больше кода, что замедляло его выполнение.

Если бы были разные ключевые слова для этих двух целей, не было бы никакой двусмысленности:

function_decl xyz(a, b, c) {} а также function_lit(a, b, c) {}

Однако никто не хотел бы писать на таком языке. Но WebAssembly не должен быть написан от руки. Это позволяет адаптировать язык к машинам, а не к людям.

marstato
источник
1
Означает ли это, что Лисп очень легко анализируется?
Моисей
9
@Moses: Да, написание синтаксического анализатора наивного lisp тривиально, потому что синтаксис гомоичен со структурой абстрактного синтаксического дерева и почти не существует двусмысленности.
Phoshi
4
Другим хорошим примером является байт-код, который часто можно проанализировать с помощью оператора переключения цикла, и все.
whatsisname
@whatsisname Действительно, то же самое относится к регулярной сборке и веб-сборке
marstato