Como identificar se uma gramática é LL(1), LR(0) ou SLR(1)?
como você identifica se uma gramática é LL (1), LR(0), ou SLR(1)?
alguém pode explicar isto usando este exemplo, ou qualquer outro exemplo?
X → Yz / a
y → BZ / ε
z → ε
5 answers
Para verificar se uma gramática é LL(1), uma opção é construir a tabela de análise LL(1) e verificar se existem conflitos. Estes conflitos podem ser
- Primeiro/Primeiro conflitos, onde duas produções diferentes teriam de ser previstas para um par não terminal/terminal.
- Primeiro / seguir conflitos, onde duas produções diferentes são previstas, uma representando que alguma produção deve ser tomada e se expande para um número não-zero de símbolos, e uma representando que um a produção deve ser usada indicando que algum não-terminal deve ser finalmente expandido para a cadeia vazia.
- seguir / Seguir conflitos, onde duas produções indicando que um não-terminal deve, em última análise, ser expandido para o conflito de cadeia vazia um com o outro.
FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon}
Também temos que os seguintes conjuntos são
FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}
De isto, podemos construir a seguinte tabela de análise LL(1):
a b z $
X a Yz Yz
Y bZ eps
Z eps
Uma vez que podemos construir esta tabela de análise sem conflitos, a gramática é LL(1).
Para verificar se uma gramática é LR (0) ou SLR(1), começamos por construir todos os conjuntos configurados LR(0) para a gramática. Neste caso, assumindo que X é o seu símbolo inicial, obtemos o seguinte:
(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.
A partir disto, podemos ver que a gramática não é LR(0) porque existem conflitos de mudança/redução nos Estados (1) e (6). Especificamente, porque temos os itens de redução Z → . and Y → ., nós não podemos dizer se devemos reduzir a string vazia para estes símbolos ou mudar algum outro símbolo. Mais geralmente, nenhuma gramática com produções ε É LR (0).
No entanto, esta gramática pode ser SLR (1). Para ver isso, aumentamos cada redução com o conjunto lookahead para os não-terminais em particular. Isto devolve este conjunto de conjuntos configurados 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]
Se não tiver os primeiros / primeiros conflitos e os primeiros / subsequentes conflitos, a sua gramática é LL(1).
Um exemplo de um primeiro / primeiro conflito:
S -> Xb | Yc
X -> a
Y -> a
Ao ver apenas o primeiro símbolo de entrada a, você não pode saber se deve aplicar a produção S - > Xb ou S - > Yc, porque a está no primeiro conjunto de X e Y.
Um exemplo de um primeiro / seguinte conflito:
S -> AB
A -> fe | epsilon
B -> fg
Observe que se você não tem nenhuma epsilon-productions você não pode ter um conflito primeiro / seguinte.
Resposta simples:diz-se que uma gramática é um LL(1),se a tabela de análise LL(1) associada tem no máximo uma produção em cada entrada de tabela.
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. |
--------------------------------------------
Como [S,b] contém duas produções, existe uma confusão quanto à regra para choose.So it is not LL(1).
Algumas verificações simples para ver se uma gramática é LL(1) ou não. verificar 1 : a gramática não deve ser deixada recursiva. Exemplo: e --> E+T. não é LL (1) porque é deixado recursivo. Verificar 2 : A A gramática deve ser deixada em consideração.
A factoring à esquerda é necessária quando duas ou mais opções de regras de gramática partilham uma cadeia de prefixos comum. Exemplo: S-- > a +int / a .
Confira 3 : a gramática não deve ser ambígua.
These are some simple checks.
A gramática LL(1) é uma gramática sem contexto que pode ser processada por analisadores LL(1).
In LL(1)
- o primeiro L representa a entrada de digitalização da esquerda para a direita. Segundo l stands Para A maior parte das derivações. 1 significa usar um símbolo de entrada em cada passo.
Para verificar a gramática é LL (1) você pode desenhar uma tabela de análise preditiva. E se você encontrar quaisquer entradas múltiplas na tabela, então você pode dizer que a gramática não é LL(1).
Eles também são curtos para verificar. se a gramática for LL(1) ou não . Técnica De Atalho
Com estes dois passos podemos verificar se ele LL(1) ou não. Ambos têm de ficar satisfeitos.
1.Se tivermos a produção: a - >a1 / a2 / a3|a4/.....|um. Então, primeiro(a(i)) interseção primeiro(a(j)) deve ser phi (conjunto vazio)[a (i)-um subscrito I.]
2.Para cada Não terminal "A", se a primeira(a) contiver epsilon Então primeiro(A) intersecção segue(a) deve ser phi (conjunto vazio).