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) - грамматиках разворачиваются самые левые нетерминальные символы сентенциальной формы и анализируется очередной самый левый терминальный входной строки.