На практике дело даже не объеме памяти, а в тех накладных расходах на сохранение результатов в таблицу и извлечение оттуда. Поэтому многие исследователи потом старались сделать Packrat не таким "всеядным".

Кстати, без lexer-хака обошлись в компиляторе CompCert. Есть 2 основных способа (об этом и в учебниках пишут) бороться с подобными контекстными неоднозначностями. Lexer-hack это первый способ, а в CompCert — второй.

Кстати, а в каких более-менее известных языках применяют PEG кроме Python?

А зачем вообще лексеру знать такие детали? Его задача, насколько я понимаю, из A*B выдать нечто вроде Identifier("A"), Star, Identifier("B") и все, а дальше уже синтаксический парсер разбирается, что значит Star - умножение или разыменовывание - в зависимости от того, где это выражение встречается

Затем что бывает неоднозначность в токенах, самый классический пример с шаблонами в плюсах

Это где A<B<C>> и лексер считает, что там оператор сдвига?

ага

Опять же, решение вроде очевидное - не иметь одной составной лексемы >>, а иметь две отдельные лексемы >

Можно же токены сделать попроще, чтобы те не несли смысловой нагрузки

В сишарпе например есть и оператор >>, и точно такой же синтаксис генериков, но проблему решили без убогого хака с пробелом между треугольными скобками

Здесь есть простой пример почему для сишечки костыль в лексер необходим: https://en.wikipedia.org/wiki/Lexer_hack

Если в кратце, то невозможно определить является ли конструкция
(A) * B

умножением A * B
или
приведением типа (A) (*B)

Еще раз мое сообщение, в котором я отвечал на эту же самую ссылку, перечитайте пожалуйста )

TL;DR: зачем это определять лексеру?

О, да, извиняюсь )

Я бы предположил что они не хотели переусложнять грамматику. По ссылке (https://web.archive.org/web/20070622120718/http://www.cs.utah.edu/research/projects/mso/goofie/grammar5.txt) из той странички wiki есть объяснение от (не очень понял кто этот "независимый консультант", но похоже разработчик компилятора):

       IDENTIFIER '(' '*' IDENTIFIER ')' '[' INTEGERconstant ']' ';'

or

       TYPEDEFname '(' '*' IDENTIFIER ')' '[' INTEGERconstant ']' ';'

The two case are very easy for a context free grammar to  distinguish,
and  the  ambiguity  vanishes.  Note that the fact that such a hack is
used (out of necessity) demonstrates that C  is  not  a  context  free
language,  but  the hack allows us to continue to use an LR(1) parser,
and a context free grammar.

все с ног на голову перевернули %)

интересно, действительно ли такой подход работает быстрее, чем подход с LR(k) или бэктрекинг, или же это просто пережиток времен, когда 640 кб должно было хватить всем )

В современной практике такие языки
большого значения не имеют

я думаю, что кс - это компромисс между легкостью разбора и удобством синтаксиса языка

Возвращаясь к вопросу о ключевых проектных решениях в LuaJiT. Вот здесь Mike Pall сам их перечисляет: http://lua-users.org/lists/lua-l/2009-11/msg00089.html