Как вы определяете, является ли грамматика LL (1), LR (0) или SLR (1)?Как определить, является ли грамматика LL (1), LR (0) или SLR (1)?
Может ли кто-нибудь объяснить это с помощью этого примера или любого другого примера?
X → Yz | a
Y → bZ | & Эпсилон;
Z → & epsilon;
Чтобы проверить, является ли грамматика LL (1), одним из вариантов является создание таблицы разбора LL (1) и проверка любых конфликтов. Этими конфликтами могут быть:
Давайте попробуем это на вашей грамматике, построив установки FIRST и FOLLOW для каждого из нетерминалов. Здесь мы получаем, что
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 →., мы не можем определить, следует ли уменьшить пустую строку до этих символов или сдвинуть какой-то другой символ. В более общем смысле, никакая грамматика с & epsilon -productions не является LR (0).
Однако эта грамматика может быть зеркальной (1). Чтобы убедиться в этом, мы увеличиваем каждое сокращение с помощью набора координат для конкретных нетерминалов. Это возвращает этот набор зеркальных (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) ушел по той же причине.
Надеюсь, это поможет!
Если у вас нет конфликтов FIRST/FIRST и конфликтов FIRST/FOLLOW, ваша грамматика LL (1).
Пример ПЕРВОГО/Первый конфликт:
S -> Xb | Yc
X -> a
Y -> a
Увидев только первый входной символ а, вы не можете знать, применять ли производство S -> XB или S -> Ус, так как это в первом наборе Х и Y.
пример пЕРВОГО/ПОСЛЕДУЮЩИЕ конфликта:
S -> AB
A -> fe | epsilon
B -> fg
увидев только первый входной символ F, вы не можете решить, следует ли применять микрофильтр A -> fe или A -> epsilon, так как f находится как в ПЕРВОМ наборе A, так и в FOLLOW множестве A (A можно проанализировать как epsilon и B как f).
Обратите внимание, что если у вас нет эпсилон-производств, у вас не может быть конфликт FIRST/FOLLOW.
Простой ответ: грамматика называется 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, Ь] содержит два Productions Существует путаница относительно того, какое правило, чтобы choose.So его не LL (1).
Некоторые простые проверки, чтобы проверить, является ли грамматика LL (1) или нет. Проверить 1: Грамматика не должна быть рекурсивной. Пример: E -> E + T. не является LL (1), потому что он левый рекурсивный. Проверить 2: Грамматика должна быть левая.
Левый факторинг требуется, если два или более варианта правил грамматики имеют общую префиксную строку. Пример: S ->A + int | A.
Check 3: Грамматика не должен быть неоднозначным.
These are some simple checks.
Ваш ответ может быть улучшен путем включения пример применения этого правила и потенциального источника для резервного копирования ваших требований. –
Спасибо за комментарий. Я добавил пример и другую полезную информацию. –
LL (1) грамматика контекстно-свободная грамматика однозначная, который может быть проанализирован с помощью LL (1) парсеров.
В LL (1)
Для проверки грамматики LL (1) вы можете провести прогнозную таблицу синтаксического анализа. И если вы найдете несколько записей в таблице, вы можете сказать, что грамматика не LL (1).
Их также короткий разрез, чтобы проверить, является ли грамматика LL (1) или нет. Shortcut Technique
Не существует ли ПЕРВЫЙ/ПЕРВЫЙ конфликт между X и Y в вашем обсуждении грамматики LL (1)? Оба они содержат b. –
@ JohnRoberts-FIRST/FIRST конфликт возникает, когда два произведения для одного и того же нетерминала имеют перекрывающиеся FIRST множества. Несмотря на то, что X и Y содержат b в своих FIRST-наборах, в грамматике не существует нетерминала с двумя постановками, одна из которых начинается с X, а одна из них начинается с Y. Имеет ли это смысл? – templatetypedef
Итак, вы говорите, что, поскольку две постановки связаны с разными нетерминалами, конфликта нет? –