БНФ-нотация и КС-грамматики

Форма Бэкуса — Наура (сокр. БНФ, Бэкуса — Наура форма) — формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ используется для описания контекстно-свободных формальных грамматик. Существует расширенная форма Бэкуса — Наура, отличающаяся лишь более ёмкими конструкциями.

Используется для описания синтаксиса языков программирования, данных, протоколов (например, в документах RFC) и т. д. (причем как грамматики, так и регулярной лексики, поскольку регулярные грамматики являются подмножеством контекстно-свободных).

Форма Бэкуса–Наура (БНФ) была впервые применена при описании Алгола-60. БНФ совпадает по сути с нотацией КС-грамматик, отличаясь лишь обозначениями.

Контекстно-свободные грамматики.

Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами (объектами, обозначающими какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющими конкретного символьного значения). Смысл термина «контекстно-свободная» заключается в том, что возможность применить продукцию к нетерминалу, в отличие от общего случая неограниченной грамматики Хомского, не зависит от контекста этого нетерминала.

Язык, который может быть задан КС-грамматикой, называется контекстно-свободным языком или КС-языком.

Следует заметить, что по сути КС-грамматика — другая форма БНФ.

КС-грамматики, в свою очередь, делятся на три класса:

s-грамматики;

Q-грамматики;

LL(1)-грамматики.

 

 

Каждому выводу в КС-грамматике, начинающемуся с нетерминального символа, однозначно сопоставляется ориентированный граф, являющийся деревом и называемый деревом вывода. Вершины дерева вывода помечаются символами объединенного алфавита грамматики или пустой цепочкой. Подчеркнем, что дерево вывода сопоставляется не грамматике, а конкретному выводу в данной грамматике, хотя мы увидим, что нескольким различным выводам может быть сопоставлено одно и то же дерево вывода. Прежде чем давать математическое определение дерева вывода, покажем на примере, как по данному выводу в заданной КС-грамматике строится это дерево.

 

S-грамматика

Не все КС-грамматики пригодны для построения нисходящего детерминированного Автомат с Магазинной Памятью(АМП), так как многие из них могут порождать одну и ту же терминальную цепочку различными левыми выводами. Это говорить об их неоднозначности и невозможности использования для детерминированного разбора. Однако, определены и изучены такие классы грамматик, которые поддерживают нисходящий детерминированный разбор. Наиболее простыми из них являются S-грамматики.

КС-грамматика называется S-грамматикой (а также раздельной, или простой) тогда и только тогда, когда выполняются два условия:

Правая часть каждого правила начинается терминалом Ti.

Если два правила имеют совпадающие левые части, то правые части этих правил должны начинаться различными терминальными символами.

 

15) LL(1) – грамматики.

LL(1)-грамматика – это грамматика такого типа, на основании которой можно получить детерминированный синтаксический анализатор, работающий по принципу сверху вниз. Прежде чем более точно определить LL(1)-грамматику, введем понятие s-грамматики.

LL(1)-грамматика является обобщением s-грамматики, и принцип ее обобщения все еще позволяет строить нисходящие детерминированные анализаторы. Две буквы L в LL(1) означают, что строки разбираются слева направо (Left) и используются самые левые выводы (Left), а цифра 1 – что варианты порождающих правил выбираются с помощью одного предварительно просмотренного символа. "Очевидной" грамматикой для большинства языков программирования является не LL(1)-грамматика. Однако обычно очень большое число контекстно-свободных средств языка программирования можно представить с помощью LL(1)-грамматики. Проблема заключается в том, чтобы, имея грамматику, которая не обладает признаком LL(1), найти эквивалентную ей LL(1)-грамматику. Не существует универсального алгоритма преобразования любой КС-грамматики в LL(1) форму (а также определения самой возможности такого преобразования). Однако существует ряд приемов, позволяющих выполнить такое преобразование во многих частных случаях.

LL(1) - грамматики относятся к нисходящим грамматикам (сверху - вниз).

Их правые части могут начинаться с нетерминальных символов, но таких, которые после подстановок терминальных символов обеспечивают однозначность выбора грамматических правил.

В LL(1) - грамматиках разворачиваются самые левые нетерминальные символы сентенциальной формы и анализируется очередной самый левый терминальный входной строки.