Здравствуйте, WolfHound, Вы писали:

WH>http://thesz.livejournal.com/1486500.html
WH>

WH>Я тут бьюсь с ANTLR4, который отдельные файлы с VHDL кодом разбирает ужасающе долго (со скоростью в 8К байт в секунду и даже меньше). Это, натурально, беда.

WH>В общем далеко ему ещё до промышленного качества. А то что его используют так это от того что остальное ещё хуже.

Почитал его статью Adaptive LL(*) Parsing: The Power of Dynamic Analysis. Там на 11-13 страницах есть отчет о производительности и сравнение с другими языками.

Отчет очень интересный, так как там показаны результаты и других технологий. В том числе там ест результаты GLR/GLL. Причем один из GLR-ов показал относительно не плохой результат (правда все равно в 4 раза медленнее АНТЛР-а), но дико слил на одном большом файле. Из чего авторы делают вывод о непредсказуемости производительности GLR/GLL-ов.

И действительно там на 12-й странице написано про тормоза на некоторых грамматиках.

Grammar     KB/sec
XML         45,993
Java        24,972
JSON        17,696
DOT         16,152
Lua          5,698
C            4,238
Verilog2001  1,994
Erlang       751

Списывают это на то, что грамматика написана не подходящим для них образом.

Some of these grammars yield reasonable but much slower parse times compared to Java and XML but demonstrate that
programmers can convert a language specification to ANTLR’s meta-syntax and get a working grammar without major modiGrammar

fications. (In our experience, grammar specifications are rarely tuned to a particular tool or parsing strategy and are often ambiguous.)
Later, programmers can use ANTLR’s profiling and diagnostics to improve performance, as with any programming
task. For example, the C11 specification grammar is LL not SLL because of rule declarationSpecifiers, which we altered
to be SLL in our C grammar (getting a 7x speed boost).

То есть для достижения высокой скорости парсинга грамматику нужно приводить к загадочному SLL-классу (Strong LL):

Parsers that ignore the parser call stack for prediction are called Strong LL (SLL) parsers. The recursive-descent parsers
programmers build by hand are in the SLL class. By convention, the literature refers to SLL as LL but we distinguish the
terms since “real” LL is needed to handle all grammars. The above grammar is LL(2) but not SLL(k) for any k, though
duplicating A for each call site renders the grammar SLL(2).

Creating a different lookahead DFA for each possible parser call stack is not feasible since the number of stack permutations
is exponential in the stack depth. Instead, we take advantage of the fact that most decisions are not stack-sensitive and build
lookahead DFA ignoring the parser call stack. If SLL ATN simulation finds a prediction conflict (Section 5.3), it cannot be
sure if the lookahead phrase is ambiguous or stack-sensitive.
In this case, adaptivePredict must re-examine the lookahead using the parser stack γ0. This hybrid or optimized LL mode
improves performance by caching stack-insensitive prediction results in lookahead DFA when possible while retaining full
stack-sensitive prediction power. Optimized LL mode applies on a per-decision basis, but two-stage parsing, described next,
can often avoid LL simulation completely. (We henceforth use SLL to indicate stack-insensitive parsing and LL to indicate
stack-sensitive.)

Это конечно косяк. Но, тем не менее, SLL-грамматик скорость у них очень даже высокая.

А вот GLR-ам эта статья ставит однозначный приговор.

Что касается нас, то нам бы тоже надо сначала провести подобные испытания, а потом уже выпендриваться. Конечно, использование мемоизации должно давать более линейную зависимость от качества (класса) грамматики. Но не исключены, что и у нас есть слабые места. По крайней мере одно из них ты сам нашел в грамматике самой же Нитры. Уж не помню победил ты его или нет.

WH>Когда с парсером возились там вообще беда была. Любое изменение алгоритма восстановления и генерация ошибок ломалась.

Это — да. Собственно одна из причин по которой я сделал сбор ошибок на посетителе и была постоянные изменения алгоритмов и кишков. А обходчики ты уже сам чинил, так что с тех пор я ни разу этот код не переписывал.