Qual é a complexidade de tempo de encontrar o primeiro e seguir conjuntos?

Question

Dado o quão importante isso é para analisar, estou surpreso que eu não fosse capaz para encontrar qualquer coisa sobre sua complexidade.Estou interessado em todas as combinações de:

Qual é a complexidade (edita: melhor conhecida) do cálculo de um Gramática?

Links para recursos ou respostas parciais são bem-vindos.

Answer 1

$ \ mathbf {primeiro} _1 $ e $ \ mathbf {Siga} _1 $ como relações sobre os símbolos de uma gramática $ \ mathcal {g} $ pode ser calculado para um determinado não-terminal em $ \ theta (| \ Mathcal {g} |) $ , wnere o tamanho da $ \ mathcal {g} $ é definido de uma forma intuitiva (basicamente, a soma dos comprimentos das produções).

É claro que $ | \ mathcal {g} | $ é um limite inferior, já que nenhum algoritmo pode funcionar sem considerar cada símbolo de cada produção da gramática. Um algoritmo que leva tempo linear para o tamanho da gramática (com uma prova de tempo de complexidade) é fornecido na seção 5.5 de Teoria de análise, vol. 1 (S. Sippu & E. Soisalon-Soininen, 1988) . (Se $ k \ gt 1 $ , um termo polinomial é introduzido por causa do tamanho da $ first_k $ Sets.)

Assim, para calcular toda a relação requer $ o (| \ mathcal {g} | \ Cdot | t |) $ , onde $ t $ é o conjunto de símbolos do terminal em $ \ mathcal {g} $ . A $ | $ | $ fator (que poderia, no pior caso, ser $ o (| \ mathcal {g} |) $ ) é o resultado de ter que executar as operações de conjunto de conjuntos em conjuntos de até $ | $ | $ elementos. Na prática, não há vantagem para tentar calcular a $ primeiro $ e $ siga $ conjuntos para um não terminal individual; Há muita sobreposição nos cálculos individuais.

Estes resultados não foram novos; A bibliografia créditos Donald B. Johnson & Ravi Sethi (1976) Uma caracterização de LL (1) Grammars , mas um paywall impede minha verificação. Os algoritmos também são citados em Hunt, Szymanski & Ullman (1977) Operações em relações esparsas < / em> , que se refere a um documento de 1974 pelos mesmos autores, com aproximadamente o mesmo nome (pago, mas você pode encontrá-lo).

Por meio de uma nota lateral, a estrutura de expressões relacionais desenvolvidas e usadas pela SIPPU & Soisalon-Soininen em todos os dois volumes de Teoria da análise é uma coisa de beleza que para mim era suficiente para justificar meu investimento no livro didático. Mas você pode encontrá-lo em uma boa biblioteca acadêmica.