В формальной теории грамматики детерминированные контекстно-свободные грамматики ( DCFG ) являются собственным подмножеством контекстно -свободных грамматик . Они являются подмножеством контекстно-свободных грамматик, которые могут быть получены из детерминированных магазинных автоматов , и они генерируют детерминированные контекстно-свободные языки . DCFG всегда однозначны и являются важным подклассом однозначных CFG; однако существуют недетерминированные однозначные CFG.
DCFG представляют большой практический интерес, поскольку их можно разобрать за линейное время , и фактически парсер может быть автоматически сгенерирован из грамматики генератором парсеров . Таким образом, они широко используются в компьютерной науке. Различные ограниченные формы DCFG могут быть разобраны более простыми, менее ресурсоемкими парсерами, и поэтому часто используются. Эти классы грамматики называются по типу парсера, который их разбирает, и важными примерами являются LALR , SLR и LL .
В 1960-х годах теоретические исследования в области компьютерных наук по регулярным выражениям и конечным автоматам привели к открытию того, что контекстно-свободные грамматики эквивалентны недетерминированным магазинным автоматам . [1] [2] [3] Считалось, что эти грамматики охватывают синтаксис языков программирования. В то время разрабатывались первые языки программирования высокого уровня (см. История языков программирования ), и написание компиляторов было сложным. Но использование контекстно-свободных грамматик для автоматизации части синтаксического анализа компилятора упростило задачу. Детерминированные контекстно-свободные грамматики были особенно полезны, поскольку их можно было последовательно разобрать детерминированным магазинным автоматом , что было требованием из-за ограничений памяти компьютера. [4] В 1965 году Дональд Кнут изобрел анализатор LR(k) и доказал, что существует грамматика LR(k) для каждого детерминированного контекстно-свободного языка. [5] Этот анализатор по-прежнему требовал много памяти. В 1969 году Фрэнк ДеРемер изобрел парсеры LALR и Simple LR , оба основанные на парсере LR и имеющие значительно сниженные требования к памяти за счет меньшей мощности распознавания языка. Парсер LALR был более сильной альтернативой. [6] Эти два парсера с тех пор широко использовались в компиляторах многих языков программирования. Недавние исследования выявили методы, с помощью которых канонические парсеры LR могут быть реализованы с существенно сниженными требованиями к таблицам по сравнению с алгоритмом построения таблиц Кнута. [7]