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

Question

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

может ли кто-нибудь объяснить это, используя этот пример или любой другой пример?

X → Yz / a

Y → bZ / ε

Z → ε

1101 5

parsing grammar ll

5 ответов:

Comments

Ничего не найдено.

templatetypedef · Accepted Answer · 2011-12-14 00:03:50

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

первый / первый конфликты, где два разных производства должны быть предсказаны для нетерминальной / терминальной пары.

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

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

давайте попробуем это на вашей грамматике, построив первый и последующие наборы для каждого из нетерминалов. Вот, мы получаем, что
FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon} 
у нас также есть следующие наборы являются
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 → ., мы не можем сказать, уменьшить ли пустую строку до этих символов или сдвинуть какой-то другой символ. В более общем случае никакая грамматика с ε-производствами не является LR (0).

однако эта грамматика может быть SLR (1). Чтобы увидеть это, мы увеличиваем каждое сокращение с помощью набора lookahead для конкретных нетерминалов. Это возвращает этот набор 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) исчез по той же причине.

надеюсь, что это помогает!

Kent Munthe Caspersen · Accepted Answer · 2013-12-02 19:18:19

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

пример первого / первого конфликта:
S -> Xb | Yc
X -> a 
Y -> a 
видя только первый входной символ a, вы не можете знать, Следует ли применять производство S - > Xb или S - > Yc, потому что a находится в первом наборе как X, так и Y.

пример первого / последующего конфликта:
S -> AB 
A -> fe | epsilon 
B -> fg 
видя только первый входной символ f, вы не можете решить, следует ли примените производство A -> fe или A - > epsilon, потому что f находится как в первом наборе A, так и в следующем наборе A (A может быть проанализирован как epsilon и B как f).

обратите внимание, что если у вас нет epsilon-productions, у вас не может быть конфликта FIRST/FOLLOW.

Anil Kumar · Accepted Answer · 2015-08-05 15:29:06

простой ответ: грамматика называется LL(1),Если связанная таблица синтаксического анализа LL (1) имеет atmost одно производство в каждой записи таблицы.
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] содержит два производства, существует путаница в отношении того, какое правило choose.So это не LL (1).

некоторые простые проверки, чтобы увидеть, является ли грамматика LL (1) или нет. проверяем 1: грамматика не должна быть левой рекурсии. Пример: E --> E+T. не LL(1), потому что он остается способный к повторному использованию. Регистрация 2: грамматика должна быть оставлена без учета.

левый факторинг требуется, когда два или более вариантов правил грамматики имеют общую строку префикса. Пример: С-->A + int/A.

проверка 3:грамматика не должна быть двусмысленной.
These are some simple checks.

Badal · Accepted Answer · 2016-05-01 15:39:18

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

в LL (1)

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

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

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

user2050807 · Accepted Answer · 2018-06-24 08:39:51

с помощью этих двух шагов мы можем проверить, если он LL (1) или нет. Оба они должны быть удовлетворены.

1.Если у нас есть производство: A - >a1|a2|a3|a4/.....|-. Тогда первое(a(i)) пересечение первого(a(j)) должно быть phi (пустое множество)[a (i)-индекс i.]

2.Для каждого нетерминального 'A', если первый(A) содержит Эпсилон Затем сначала(a) пересечение следует(A) должно быть phi (пустой набор).