Como determinar se uma língua é LL (1) LR (0) SLR (1)

StackOverflow https://stackoverflow.com/questions/475949

Pergunta

Existe uma maneira simples para determinar se uma gramática é LL (1), LR (0), SLR (1) ... só de olhar sobre a gramática sem fazer qualquer análise complexa?

Por exemplo:. Para decidir se uma gramática BNF é LL (1) você tem que calcular Primeiras e siga sets - o que pode ser demorado em alguns casos

Alguém tem uma idéia de como fazer isso mais rápido? Qualquer ajuda seria muito apreciada!

Foi útil?

Solução

Primeiro, um pouco de pedantismo. Você não pode determinar se um idioma é LL (1) inspeccionar uma gramática para ele, você só pode fazer declarações sobre o gramática em si. É perfeitamente possível escrever não-LL (1) gramáticas de idiomas para os quais existe um LL (1) gramática.

Com isso fora do caminho:

  • Você poderia escrever um analisador para a gramática e ter uma calculadora primeiro programa e siga conjuntos e outras propriedades para você. Afinal, essa é a grande vantagem de gramáticas BNF, eles são compreensíveis máquina.

  • Verifique a gramática e olhar para violações das restrições de vários tipos de gramática. Por exemplo: LL (1) permite a recursão direito, mas não esquerdo, assim, uma gramática que contém recursão esquerda não é LL (1). (Para outras propriedades gramaticais que você vai ter que gastar algum tempo de qualidade com as definições, porque eu não me lembro de mais nada fora do topo da minha cabeça agora:).

Outras dicas

Em resposta à sua pergunta principal:. Para uma gramática muito simples, pode ser possível determinar se é LL (1) sem construir a primeira e siga conjuntos, p.ex.

A ? A + A | um

não é LL (1), enquanto

A ? uma | b

é.

Mas quando você obtém mais complexa do que isso, você precisa fazer alguma análise.

A ? B | um
B ? A + A

Este não é LL (1), mas pode não ser imediatamente óbvio

As regras de gramática para aritmética obter rapidamente muito complexo:

expr ? termo { '+' termo}
prazo ? fator {fator '*'}
fator ? número | '(' Expr ')'

Essa gramática alças única multiplicação e adição, e já que não está claro de imediato se a gramática é LL (1). Ainda é possível avaliá-lo, olhando através da gramática, mas como a gramática cresce torna-se menos feasable. Se estamos definindo uma gramática para toda uma linguagem de programação, é quase certo que vai levar algum análise complexa.

Dito isto, existem alguns indícios evidentes de que a gramática não é LL (1) - como o A ? A + A acima - e se você pode encontrar qualquer um destes em sua gramática, você vai saber que ele precisa que ser reescrito se você estiver escrevendo um analisador descendente recursivo. Mas não há nenhum atalho para verificar se a gramática é LL (1).

Um aspecto, "é a língua / gramática ambígua", é um conhecido questão indecidível como o Publicar correspondência e problemas vacilantes.

Em linha reta do livro "Compiladores: Princípios, técnicas e ferramentas" por Aho, et. al.

Página 223:

Uma gramática G é LL (1) se e só se sempre que A -> alpha | beta são duas produções distintas de G, as seguintes condições são:

  1. Para nenhum terminal "a" fazer as duas alpha e beta cordas da deriva começando com "a"
  2. No máximo um de alpha e beta pode derivar a cadeia vazia
  3. Se beta pode chegar a transição vazia via zero ou mais transições, então alpha não deriva qualquer string que começa com um terminal em FOLLOW (A). Da mesma forma, se alfa pode atingir a transição vazio através de zero ou mais transições, em seguida, beta não decorre qualquer cadeia começando com um terminal na SIGA (A)

Essencialmente, este é uma questão de verificar a gramática passa a disjunção Teste Pairwise e também não envolve esquerda recursão. Ou de forma mais sucinta uma gramática G que resta-recursivo ou lata ambígua não ser LL (1).

Verifique se a gramática é ambígua ou não. Se for, então a gramática não é LL (1) porque nenhuma gramática ambígua é LL (1).

ya existem atalhos para ll (1) gramática

1) se A-> B1 | B2 | ....... | Bn em seguida, primeiro (B1) intersecção primeiro (B2) intersecção .first (Bn) = conjunto vazio, então é LL (1) gramática

2) se A-> B1 | epsilon então intersecção B1 acompanhamento (A) é conjunto vazio

3) se G é qualquer gramática de tal modo que cada deriva não terminais apenas uma produção, em seguida, a gramática é LL (1) 

p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id
  • Construir o LR (0) DFA, o conjunto seguir para E e a ação SLR / Ir para tabelas.
  • É este um LR (0) gramática? Provar a sua resposta.
  • Usando as tabelas SLR, mostrar os passos (turnos, reduções, aceitar) de uma análise analisador LR:
    id ( id + id )
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top