Предоставляют ли Lex и Yacc оптимизированный код или требуется, чтобы мы писали собственный код вручную для повышения производительности?
Предоставляют ли lex и yacc оптимизированный код?
comment
Я думаю, что основная проблема сгенерированных парсеров заключается в том, чтобы указать точное местоположение и причину синтаксических ошибок, а не в производительности. Табличный подход, используемый инструментами генерации синтаксических анализаторов на основе LALR(1), довольно оптимален с точки зрения скорости.
- person Joey schedule 06.05.2010
Ответы (2)
Код, который вы пишете, существенно влияет на скорость, особенно на стороне лексера. Некоторые версии Flex поставляются с полдюжиной (или около того) различных счетчиков слов, большинство из которых написано с помощью Flex, а некоторые написаны вручную — код дает довольно хорошее представление о том, как оптимизировать скорость сканирования (и довольно разумное сравнение что вы можете ожидать от рукописных и машинных лексеров).
Со стороны синтаксического анализатора вы, как правило, немного более ограничены — вы не можете внести столько изменений, не влияя на семантику. Здесь многое зависит от используемого вами генератора синтаксических анализаторов — например, некоторые алгоритмы для грамматик с меньшими ограничениями постоянно производят относительно медленные синтаксические анализаторы, в то время как другие алгоритмы замедляются только для конструкций с меньшими ограничениями и работают относительно быстро, пока входные данные не использует более сложные конструкции.
person
Jerry Coffin
schedule
06.05.2010
Yacc производит табличный синтаксический анализатор, который никогда не может быть таким же быстрым, как хорошо написанный вручную синтаксический анализатор. Я не знаю, относится ли то же самое к Лексу.
person
Marcelo Cantos
schedule
06.05.2010
[ требуется ссылка ]. Как бы вы разработали синтаксический анализатор с гораздо более высокой производительностью по сравнению с табличным подходом? Насколько мне известно, является довольно быстрым методом синтаксического анализа.
- person Joey; 06.05.2010
Вот аннотация к статье о создании жестких -кодированные парсеры. Они заявляют об ускорении от 2 до 6 раз по сравнению с yacc.
- person Marcelo Cantos; 06.05.2010
Аннотация гласит: Мы разработали генератор синтаксических анализаторов, совместимый с yacc, который создает синтаксические анализаторы в 2,0–6,0 раз быстрее, чем сгенерированные yacc или bison. Наш инструмент mule создает непосредственно исполняемые, жестко закодированные синтаксические анализаторы в ANSI; yacc создает интерпретируемые парсеры, управляемые таблицами. ЖЕСТКОЕ кодирование не является РУЧНЫМ кодированием.
- person Kaz; 23.04.2012
т.е. Yacc в основном имеет управляемую таблицей конечную машину DFA для распознавания дескрипторов сокращения. Неудивительно, что вместо этого это можно превратить в код. Но выдает ли этот Мул парсеры, сравнимые с парсерами, которые кто-то написал бы от руки? Будет ли кто-нибудь использовать ту же технику для написания кода, аналогичного тому, что делает этот инструмент? В любом случае, он все равно устанавливает существование.
- person Kaz; 23.04.2012
@Kaz: Парсеры с жестким кодом и парсеры с ручным кодом, вероятно, будут похожи. Тот факт, что они создаются с помощью разных процессов, не имеет значения, тем более, что ключевым моментом является то, что yacc не оптимален, а не закодирован вручную (или жестко закодирован).
- person Marcelo Cantos; 23.04.2012
Да; работа предполагает, что стратегия реализации таблицы для LARL (1) может быть побеждена. т.е. обычные реализации инструмента на самом деле не обеспечивают наилучшего возможного кода.
- person Kaz; 23.04.2012
