Por que é o seguinte gramática não é LL(1)

Question

Considere a seguinte gramática:

S → bAb
  | bBa
A → aS
  | CB
B → b
  | Bc
C → c
  | cC

Eu tenho que fornecer as razões por que esta gramática não é LL(1).Até agora tudo o que posso pensar é que a gramática não é deixado consignado dado a produções:

S → bAb
  | bBa

Mas eu também estou querendo saber se a gramática é recursiva à esquerda, devido ao produções:

B → b
  | Bc

Opções fornecidas são:

• Essa gramática tem recursão à esquerda.(Inseguro)
• Essa gramática tem direito a recursividade.(Não faria gramática não é LL(1))
• Esta gramática é ambígua.(Inseguro)
• Esta gramática não é fatorada a esquerda.(Correto)
• Esta gramática pode produzir um número infinito de cadeias distintas.(Isto não deve afetar uma gramática certo?)

Tanto quanto eu posso dizer, a gramática não é ambígua, eu tentei 3 entradas diferentes e todos resultaram em uma única árvore de análise.Assim é esta gramática não é LL(1) apenas por causa da falta de esquerda factoring?ou, também, porque a gramática é recursiva à esquerda?

Answer 1

LL(1) gramáticas deve ser inequívoca, não tem deixado de recursividade, e sem conflitos.

A gramática que você fornecer é inequívoco em termos de sintaxe árvore, no entanto, há conflitos quando a análise (que o impede de ser um LL(1) gramática).Os conflitos residem no primeiro conjunto de S e C.Isto é, FIRST(S) = { b }, mas a sua ambígua em que a regra de produção a aplicar: S -> bAb ou S -> bBa.Este pode ser eliminado através de factoring, o b como tal:

S  -> b S'
S' -> A b | B a

Da mesma forma para C:

C  -> c C'
C' -> c C' | eps

A gramática também deixou a recursividade na regra B -> Bc;esta é a definição de recursão à esquerda.Esta pode ser removida como tal:

B   -> b B'
B'  -> c B' | B''
B'' -> c

Verifique o seguinte para obter mais informações:

• LL analisador: https://en.wikipedia.org/wiki/LL_parser
• Esquerda recursão: https://en.wikipedia.org/wiki/Left_recursion
• CFG verificador (incluindo LL(1)): http://smlweb.cpsc.ucalgary.ca/