Как определить, является ли грамматика LL (1), LR (0) или SLR (1)?

Ответ 1

Чтобы проверить, является ли грамматика LL (1), одним из вариантов является создание таблицы разбора LL (1) и проверка любых конфликтов. Эти конфликты могут быть

• FIRST/FIRST конфликты, где должны быть предсказаны две разные постановки для пары с нетерминальной/конечной.
• FIRST/FOLLOW, где прогнозируются две разные постановки, одна из которых означает, что необходимо произвести некоторую продукцию и расширить ее до ненулевого числа символов, а один из них означает, что следует использовать производство, указывающее на то, что некоторые нетерминалы должны быть в конечном счете расширены в пустую строку.
• конфликты FOLLOW/FOLLOW, в которых два продукта, указывающие на то, что нетерминал должен в конечном счете быть расширен до пустых строк, конфликтуют друг с другом.

Попробуйте это на вашей грамматике, построив FIRST и FOLLOW для каждого из нетерминалов. Здесь мы получаем, что

FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon} 

Мы также имеем, что наборы FOLLOW являются

FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}

Из этого можно построить следующую таблицу разбора LL (1):

    a    b    z   $
X   a    Yz   Yz  
Y        bZ   eps
Z             eps

Поскольку мы можем построить эту таблицу синтаксического анализа без конфликтов, грамматика LL (1).

Чтобы проверить, является ли грамматика LR (0) или SLR (1), мы начинаем с создания всех конфигурационных наборов LR (0) для грамматики. В этом случае, считая, что X является вашим стартовым символом, мы получаем следующее:

(1)
X' -> .X
X -> .Yz
X -> .a
Y -> .
Y -> .bZ

(2)
X' -> X.

(3)
X -> Y.z

(4)
X -> Yz.

(5)
X -> a.

(6)
Y -> b.Z
Z -> .

(7)
Y -> bZ.

Отсюда видно, что грамматика не является LR (0), поскольку в состояниях (1) и (6) возникают конфликты сдвига/уменьшения. В частности, потому что у нас есть элементы сокращения Z →, и Y →., мы не можем определить, следует ли уменьшить пустую строку до этих символов или сдвинуть какой-то другой символ. В более общем смысле, никакая грамматика с & epsilon -productions не является LR (0).

Однако эта грамматика может быть SLR (1). Чтобы убедиться в этом, мы увеличиваем каждое сокращение с помощью набора координат для конкретных нетерминалов. Это возвращает этот набор конфигурационных наборов SLR (1):

(1)
X' -> .X
X -> .Yz [$]
X -> .a  [$]
Y -> .   [z]
Y -> .bZ [z]

(2)
X' -> X.

(3)
X -> Y.z [$]

(4)
X -> Yz. [$]

(5)
X -> a.  [$]

(6)
Y -> b.Z [z]
Z -> .   [z]

(7)
Y -> bZ. [z]

Теперь у нас больше нет конфликтов смены. Конфликт в состоянии (1) был устранен, потому что мы уменьшаем только тогда, когда lookahead равен z, что не конфликтует ни с одним из других элементов. Точно так же конфликт в (6) ушел по той же причине.

Надеюсь, это поможет!

Ответ 2

Если у вас нет конфликтов FIRST/FIRST и конфликтов FIRST/FOLLOW, ваша грамматика LL (1).

Пример конфликта FIRST/FIRST:

S -> Xb | Yc
X -> a 
Y -> a 

Увидев только первый входной символ a, вы не можете знать, следует ли применять производство S → Xb или S → Yc, потому что a находится в ПЕРВОЙ наборе как X, так и Y.

Пример конфликта FIRST/FOLLOW:

S -> AB 
A -> fe | epsilon 
B -> fg 

Видя только первый входной символ f, вы не можете решить, следует ли применять производство A → fe или → epsilon, так как f находится как в ПЕРВОМ наборе A, так и в наборе FOLLOW A (A может быть анализируется как epsilon и B как f).

Обратите внимание: если у вас нет эпсилон-производств, у вас не может возникнуть конфликт FIRST/FOLLOW.

Ответ 3

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

Take the simple grammar A -->Aa|b.[A is non-terminal & a,b are terminals]
   then find the First and follow sets A.
    First{A}={b}.
    Follow{A}={$,a}.

    Parsing table for Our grammar.Terminals as columns and Nonterminal S as a row element.

        a            b                   $
    --------------------------------------------
 S  |               A-->a                      |
    |               A-->Aa.                    |
    -------------------------------------------- 

Поскольку [S, b] содержит два Productions, возникает путаница относительно того, какое правило выбрать. Таким образом, это не LL (1).

Некоторые простые проверки, чтобы увидеть, является ли грамматика LL (1) или нет. Проверить 1. Грамматика не должна оставаться рекурсивной.          Пример: E → E + T. не является LL (1), потому что он левый рекурсивный. Проверить 2. Грамматика должна быть левая.

Левый факторинг требуется, если два или более варианта правил грамматики имеют общую префиксную строку.              Пример: S → A + int | A.

Проверить 3. Грамматика не должна быть двусмысленной.

These are some simple checks.

Ответ 4

LL (1) грамматика - это контекстная свободная однозначная грамматика, которая может быть проанализирована парсерами LL (1).

В LL (1)

• Первый L обозначает ввод сканирования слева направо. Второй стенд L для левой выработки. 1 означает использование одного входного символа на каждом шаг.

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

Их также сокращен, чтобы проверить, является ли грамматика LL (1) или нет. Техника ярлыков