Детерминированная контекстно-свободная грамматика
-
Определение и применение DCFG
- DCFG — это подмножество контекстно-свободных грамматик, которые генерируют детерминированные контекстно-свободные языки и могут быть проанализированы детерминированными автоматами pushdown.
- DCFG всегда однозначны и являются важным подклассом однозначных CFG, но существуют также и недетерминированные однозначные CFG.
- DCFG широко используются в информатике благодаря возможности их анализа за линейное время и возможности автоматического создания синтаксических анализаторов.
-
История и развитие DCFG
- В 1960-х годах открытие эквивалентности между контекстно-свободными грамматиками и недетерминированными автоматами с автоматическим запуском привело к их использованию в компиляторах.
- Дональд Кнут разработал синтаксический анализатор LR(k), который требовал много памяти, но был улучшен Фрэнком Деремером с помощью парсеров LALR и Simple LR.
- Современные исследования направлены на уменьшение требований к таблицам в канонических LR-анализаторах.
-
Рекомендации и библиография
- В статье приведены ссылки на различные грамматические классы и синтаксические анализаторы, а также на исследования и диссертации, связанные с DCFG.
Полный текст статьи: