Полезно ли использовать алгоритм синтаксического анализа диаграммы CKY для синтаксиса языков программирования (зная, что он в основном используется для синтаксического анализа синтаксиса естественного языка)?CKY для языков программирования Parsing
CKY может анализировать любой контекст свободного языка, но сложность времени невелика по сравнению с альтернативами. CKY требует, чтобы грамматика находилась в нормальной форме Хомского, которая может взорвать размер грамматики и повредить время работы. Это хороший подход к быстрому и грязному парсеру, но вы столкнетесь с проблемами при попытке масштабирования до более крупных входов или сложных грамматик.
Если вы ищете понятный алгоритм синтаксического анализа, который достаточно прост для реализации, взгляните на грамматические выражения грамматики (PEG). Они могут распознавать большое подмножество контекстно-свободных языков, а также некоторые языки с ограниченной чувствительностью к контексту. После того, как у вас есть рабочий анализатор PEG, легко добавить memoization, который дает вам Packrat Parser, который работает в линейном времени. Научные статьи по PEGs, Packrat и this extension, чтобы левые рекурсивные грамматики были вполне понятны.