Производительность предиката семантического лексера

Question

У меня есть lexer, создающий маркеры MACRO для динамического списка макросов, переданных в lexer. Я использовал семантический предикат в самом верхнем правиле лексического анализатора для реализации этой функции:

MACRO: { macros != null && tryMacro() }? .; 

Где tryMacro() просто проверяет, если какая-либо макрос строка соответствует входной последовательности.

Эффективность такого подхода было очень плохо, и после некоторых исследований я попытался изменить правила лексического анализатора к следующему:

MACRO: . { macros != null && tryMacro() }?; 

Это существенно улучшило производительность, но я не понимаю, почему. :) С тех пор как. соответствует любому символу, правило семантического предиката должно вызываться точно столько же раз, сколько и раньше, не так ли? Может ли кто-нибудь объяснить это поведение?

Answer 1

Я отлаживал это немного дальше, и оказалось, что переупорядочение правила изменило поведение макросов, вызывающих лексер, чтобы их не принимали во время разбора. Причина предполагаемого увеличения производительности заключалась в том, что семантический предикат оценивался только пару раз, прежде чем лексер отменил правило при выполнении своих прогнозов. Таким образом, изменение правила было фактически недействительным, а не улучшением производительности.

Наконец-то я решил проблему с производительностью, переместив обработку макросов в парсер.

Answer 2

Причина довольно проста: если вы положите предикат в начале, лексер будет оценивать его, чтобы решить, должно ли применяться правило MACRO. Если вы положите его в конец, он выполнит проверку только тогда, когда у него есть потенциальное совпадение для правила MACRO.

Поскольку MACRO является очень родовым, я полагаю, вы положили его в конце правил, и в связи с priority rules он, несомненно, получите попытался последний. Он может соответствовать только одиночным символам, поэтому более точные правила будут приоритетными.

Если правило MACRO заменено более приоритетным правилом, оно не будет рассматриваться, и ваш предикат не будет вызван.