Детерминированная контекстно-свободная грамматика - Deterministic context-free grammar

В формальная грамматика теория, детерминированные контекстно-свободные грамматики (DCFG) площадь правильное подмножество из контекстно-свободные грамматики. Это подмножество контекстно-свободных грамматик, которые могут быть получены из детерминированные автоматы выталкивания, и они генерируют детерминированные контекстно-свободные языки. DCFG всегда однозначный, и являются важным подклассом однозначных CFG; однако есть недетерминированные однозначные CFG.

DCFG представляют большой практический интерес, так как их можно анализировать за линейное время, и фактически анализатор может быть автоматически сгенерирован из грамматики с помощью генератор парсеров. Таким образом, они широко используются в информатике. Различные ограниченные формы DCFG могут быть проанализированы более простыми, менее ресурсоемкими синтаксическими анализаторами, и поэтому часто используются. Эти классы грамматики называются типом анализатора, который их анализирует, и важными примерами являются LALR, SLR и LL.

История

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

Смотрите также

Рекомендации

  1. ^ Хомский, Ноам (1962). «Контекстно-свободные грамматики и раскрывающееся хранилище». Квартальный отчет, Исследовательская лаборатория электроники Массачусетского технологического института. 65: 187–194.
  2. ^ Иви, Р.Дж. (1963). «Применение магазинных автоматов». 1963 AFIPS Труды осенней совместной компьютерной конференции: 215–227.
  3. ^ Шютценбергер, Марсель Поль (1963). «О контекстно-свободных языках и автоматах». Информация и контроль. 6: 246–264. Дои:10.1016 / с0019-9958 (63) 90306-1.
  4. ^ Саломаа; D Wood; С.Ю., ред. (2001). Полвека теории автоматов. Мировое научное издательство. С. 38–39.
  5. ^ Кнут, Д. Э. (Июль 1965 г.). «О переводе языков слева направо» (PDF). Информация и контроль. 8 (6): 607–639. Дои:10.1016 / S0019-9958 (65) 90426-2. Архивировано из оригинал (PDF) 15 марта 2012 г.. Получено 29 мая 2011.
  6. ^ Франклин Л. Де Ремер (1969). «Практические переводчики языков LR (k)» (PDF). Массачусетский технологический институт, кандидатская диссертация. Архивировано из оригинал (PDF) на 2012-04-05.
  7. ^ X. Чен, Измерение и расширение синтаксического анализа LR (1), Докторская диссертация Гавайского университета, 2009 г.