Каковы разумные верхние границы для числа состояний, символов и правил грамматик LR (1)?
Я делаю парсер LR (1) и сталкиваюсь с узкими местами производительности в разных местах.
Я хотел бы попытаться оптимизировать структуры данных для синтаксического анализатора, но для этого мне необходимо приблизительное представление о том, сколько состояний, правил и символов терминалов целесообразно для (возможно, сложных) компьютерных языков, таких как C ++.
Я предполагаю, что типичная грамматика для сложного языка будет иметь:
- ≤ 100 терминальных символов
- ≤ 50 символов на производство
- ≤ 2000 правил
- ≤ 10000 штатов
но я действительно не знаю, насколько они правы.
Обратите внимание, что я предполагаю, что каждое правило имеет вид нетерминал → условное обозначение условное обозначение условное обозначение…, так что одно составное «правило», которое выглядит как foo: (bar | baz)+ на самом деле может состоять, скажем, из 5 правил, а не только из одного правила.
Они разумны? Если нет, где я найду эти цифры?
Решение
Система DMS, которую я ежедневно разрабатывал, обрабатывает производственную грамматику переднего плана IBM Enterprise COBOL примерно за 7 секунд на изможденном ноутбуке (измеряется только сейчас на этом ноутбуке).
Грамматика имеет около 500 терминалов и 2500 производств, в среднем около 2,5 токенов
за производство. Наша продукция точно такая, как вы ее описали (нет EBNF, просто не покупаем достаточно, чтобы иметь значение, и да, мы большие поклонники DSL. Иногда гигавы, которые ставят DSL, не стоят того). Генератор парсера выдает 3800 состояний. (Эти значения измерены только сейчас тоже).
DMS имеет полную грамматику C ++ 11 с множеством дополнительных вещей для обработки диалектов GCC и MS, а также OpenMP. Грамматика имеет 457 терминалов, около 3000 произведений, около 2,3 токенов на среднее производство. Генератор парсера выдает 5800 состояний. Генерация занимает больше времени: 11 секунд на i7. Что может вас удивить, так это то, что
несколько десятков секунд, чтобы сгенерировать лексер (на самом деле несколько лексеров); в C ++ 11 странных лексических странностей гораздо больше, чем вы ожидаете.
Генератор является генератором GLR нашей собственной реализации.
Мы не сделали много, чтобы оптимизировать время генерации. Это может быть ускорено в 10 или более раз; мы не проводим сложную оптимизацию обнаружения циклов, как это предлагается в большинстве статей о генерации LR-парсера. Следствием этого является то, что генерация таблиц занимает больше времени, но ничего не теряется в функциональности. У нас никогда не было достаточной мотивации для такой оптимизации, потому что есть много других вещей, связанных с языковым интерфейсом, кроме беспокойства о времени генерации таблицы анализатора.
Я сомневаюсь, что структуры данных имеют большое значение, если они разработаны разумно. Мы не сильно беспокоимся о размерах правил, наборах предметов или состояниях; мы просто используем динамические массивы, и они заботятся о себе. Мы упаковываем объекты в плотные битовые векторы.
В качестве дополнительных справочных данных вы, вероятно, найдете этот документ полезным: Тьяго Алвес и Джуст Виссер, Метрикация грамматик SDF. Технический отчет, DI-Research.PURe-05.05.01, Departamento de Informática, Universidade do Minho, май 2005 г.
Генератор парсера — это не то место, где вам трудно работать с грамматикой. Это получение правил грамматики право для конкретных реализаций.
Другие решения
Других решений пока нет …