Problema (tl; dr)

Dada uma gramática livre de contexto, , encontre um conjunto de strings que conduzam a toda produção que ela possui pelo menos uma vez.$G$$G$

Como e com que rapidez isso pode ser feito?

fundo

Estou trabalhando em um compilador cujo analisador é implementado com uma ferramenta semelhante ao Yacc + Antlr. Escrevi a maior parte do código do analisador e gostaria de gerar algum código da linguagem do objeto que invoque todas as produções da gramática pelo menos uma vez, para que eu possa alimentá-lo e garantir que nada esteja errado. .

No interesse de um bom teste, o que eu realmente gostaria é de um pequeno arquivo de teste que tenha uma produção específica "em teste" - portanto, para cada regra de produção, desejo gerar uma sequência mínima que leve o analisador do estado inicial, através da produção sendo testada, para um conjunto de terminais.

Soluções possíveis

Imagino que exista uma solução elegante usando a teoria dos grafos, mas não tenho muita certeza do que seja. Gostaria apenas de usar o algoritmo de Dijkstra para encontrar caminhos mais curtos através de uma estrutura apropriada, mas acho que uma string é analisada por uma gramática livre de contexto em uma estrutura de árvore em vez de um caminho, por isso não sei como fazer esse trabalho .

Eu acho que pode haver uma maneira inteligente de colocá-lo como um problema de fluxo de rede. Algo assim: pegue um gráfico que tenha um vértice para cada símbolo (terminal e não-terminal) e um vértice para cada produção. Se um não-terminal tiver uma produção, adicione uma borda direcionada do não-terminal à produção. Se uma produção produzir um símbolo, adicione uma aresta direcionada da produção ao símbolo. Adicione uma fonte com alguma capacidade e anexe-a ao vértice correspondente ao símbolo de início. Adicione uma pia com capacidade infinita e conecte-a a cada terminal.$c$

Se um não-terminal tiver um arco com capacidade , adicione um arco do não-terminal a cada uma de suas produções com capacidade$k$$k$. Se uma produção tiver um arco com capacidade$k$ e tem um arco externo para $n$ não terminais, adicione um arco com capacidade $\frac k n$ da produção para cada não-terminal.

Em seguida, execute algum algoritmo de fluxo máximo na rede e deixe as produções "pingarem" do símbolo de início até os terminais. Você deve terminar com um fluxo$c$saindo da sua fonte e você pode retornar todos os terminais atingidos com um fluxo diferente de zero como sua sequência de resultados. Então você acaba com algo como$O(n^3)$ complexidade de tempo para cada execução, onde $n$ é a soma do número de terminais e não terminais na sua gramática - nada mal.

No entanto, ainda não tenho muita certeza de como esse gráfico se parece: acho que ele precisa ser infinito e não tenho certeza se é possível encontrar o fluxo máximo de uma rede de fluxo infinito. Além disso, não tenho certeza de como "remover" uma produção da consideração, para garantir uma nova para cada execução de teste.

Pesquisei no Google e não consegui encontrar nada. Existe uma boa solução para esse problema?

Em poucas palavras

Sem conhecer bastante a literatura, elaborei uma solução que será apresentada na próxima seção, juntamente com uma prova da parte mais difícil. Depois que soubesse o que era necessário, eu poderia procurar na literatura as idéias certas. Aqui está uma rápida apresentação do algoritmo, com base na literatura, que é essencialmente a mesma que desenvolvi.

A primeira coisa a fazer é encontrar uma cadeia de terminais de tamanho mínimo $\sigma(U)$ para todos os não terminais $U$da gramática. Isso pode ser feito usando a extensão de Knuth para conc-ou gráficos (também conhecidos como gramáticas CF) e-ou gráficos do algoritmo de caminho mais curto de Dijkstra . O exemplo B do artigo de Knuth faz quase o necessário.

Na verdade, Knuth calcula apenas o comprimento dessas cadeias de terminais, mas é bastante fácil modificar seu algoritmo para realmente calcular uma dessas cadeias de terminais $\sigma(U)$ para cada não terminal $U$(como faço na minha própria versão abaixo). Nós também definimos$\sigma(a)=a$ para cada terminal $a$e estendemos $\sigma$ como sempre em um homomorfismo de cordas.

Então consideramos um gráfico direcionado onde não terminais são os nós e existe um arco $(U,V)$ se houver uma regra $U\rightarrow \alpha V\beta$. Se várias dessas regras puderem produzir o mesmo arco$(U,V)$, mantemos um tal que o comprimento $|\sigma(\alpha\beta)|$é mínimo. O arco é rotulado com essa regra e esse comprimento mínimo $|\sigma(\alpha\beta)|$ torna-se o peso do arco.

Finalmente, usando o algoritmo de caminho mais curto de Dijkstra, calculamos o caminho mais curto a partir do terminal não terminal inicial $S$para cada não terminal da gramática. Dado o caminho mais curto para um terminal não terminal$U$, os rótulos de regra nos arcos podem ser usados ​​para obter uma derivação $S\overset{*}{\Longrightarrow}\alpha U \beta$. Então, para todas as regras do formulário$U\rightarrow\gamma$ na gramática, associamos a cadeia terminal tamanho-mínimo $\sigma(\alpha\gamma\beta)$ que pode ser derivado usando essa regra.

Para alcançar baixa complexidade , o algoritmo de Dijkstra e a extensão de Knuth são implementados com heaps , filas de prioridade AKA. Isso dá ao algoritmo de Dijkstra uma complexidade de$O(n\log n +t)$, e para o algoritmo de Knuth uma complexidade $O(m \log n +t)$, onde existem $m$ regras gramaticais e $n$ não terminais e $t$é o comprimento total de todas as regras. O todo é dominado pela complexidade do algoritmo de Knuth desde$m\geq n$.

O que segue é o meu próprio trabalho, antes de produzir a resposta curta acima.

Derivando a solução do algoritmo de eliminação de símbolos inúteis.

Existem vários aspectos nesse algoritmo. Para uma melhor intuição, escolhi apresentá-lo em três versões sucessivas que introduzem progressivamente mais recursos. A primeira versão não responde à pergunta, mas é um algoritmo padrão para eliminação de símbolos inúteis que sugere uma solução. A segunda versão responde à pergunta sem a restrição de minimalidade. A terceira versão fornece uma resposta para a pergunta, satisfazendo a restrição de minimalidade. Essa terceira solução é aprimorada usando uma adaptação para e-ou gráficos do algoritmo de caminho mais curto de Dijkstra .

O resultado final é um algoritmo muito simples, que evita reconsiderar os cálculos já realizados. Mas é menos intuitivo e requer uma prova.

Essa resposta tenta apenas responder à pergunta conforme precisada pelo comentário do OP: " para cada regra de produção, quero gerar uma sequência mínima que leve o analisador do estado inicial, através da produção sendo testada, a um conjunto de terminais. "Portanto, apenas tento obter um conjunto de cadeias de caracteres para que, para cada regra, haja uma cadeia no conjunto que seja uma das cadeias de tamanho mínimo da linguagem que tenha uma derivação usando a regra.

No entanto, deve-se observar que o fato de uma string "invocar" uma regra, ou seja, ter uma derivação usando essa regra, não significa necessariamente que a regra será considerada por um analisador que trabalha com gramáticas ambíguas e resolve arbitrariamente as ambiguidades. Lidar com essa situação provavelmente exigiria um conhecimento mais preciso do analisador e pode ser uma pergunta mais complexa.

O algoritmo básico

Para resolver esta questão, pode-se começar com o algoritmo clássico para remoção de símbolos inúteis em gramáticas sem contexto. Está na seção 4.4, pp 88-89, de Hopcroft & Ullman, edição de 1979. Mas a apresentação aqui pode ser um pouco diferente.

O algoritmo visa justamente provar a existência de tal cobertura, conforme solicitado pelo OP, e consiste em duas partes:

• lema 4.1 de H&U, página 88: remoção de todos os não terminais improdutivos . Isso é feito tentando encontrar para cada terminal uma cadeia de terminais na qual ele possa derivar. Uma maneira simples de explicar isso é a seguinte: Você cria um conjunto$Prod$símbolos produtivos, que você inicializa com todos os terminais. Em seguida, para cada regra, ainda não processada, com todos os seus símbolos do lado direito (RHS)$Prod$, você adiciona o lado não terminal LHS (lado esquerdo) ao conjunto $Prod$e você remove todas as regras com o mesmo LHS não terminal do conjunto de regras a serem processadas. Você itera o processo até que não haja nenhuma regra com todos os seus símbolos RHS em$Prod$. Os restantes não terminais, não em$Prod$ no final deste processo, são improdutivos: não podem ser derivados em uma cadeia de terminais e, portanto, podem ser removidos da gramática.

• lema 4.2 de H&U, página 89: remoção de todos os símbolos inacessíveis . Isso é feito pela acessibilidade clássica do nó em gráficos direcionados, considerando os não terminais como nós e tendo um arco$(U,V)$ se houver uma regra $U\rightarrow \alpha$ de tal modo que $V$ ocorre em $\alpha$. Você cria um conjunto$Reach$ de símbolos alcançáveis ​​que são inicializados apenas com o símbolo inicial $S$. Então, para cada símbolo não terminal$U$ no $Reach$ ou mais tarde adicionado a ele e para todas as regras $U\rightarrow \alpha$, você adiciona a $Reach$ todos os símbolos em $\alpha$. Quando todos os não terminais na$Reach$ foram processados, todos os símbolos (terminais ou não terminais) que não estão incluídos no $Reach$não pode aparecer em uma sequência derivada do símbolo inicial e, portanto, é inútil. Assim, eles podem ser removidos da gramática.

Esses dois algoritmos básicos são úteis para simplificar os resultados brutos de algumas técnicas de construção gramatical, como as usadas para a interseção de uma linguagem livre de contexto e de um conjunto regular. Em particular, este é útil na limpeza dos resultados de analisadores gerais CF .

A remoção inútil de símbolos não terminais é necessária no contexto da solução da pergunta, pois as regras que os utilizam não podem ser "invocadas" (isto é, usadas em sua derivação) por qualquer string do idioma.

Construindo um conjunto de cadeias que invocam todas as regras

(Ainda não estamos procurando por seqüências mínimas.)

Agora, respondendo especificamente à pergunta, é preciso remover de fato todos os símbolos inúteis, sejam símbolos inacessíveis ou símbolos não-terminais improdutivos, e também regras inúteis com termos não-terminais inúteis como o LHS. Eles não têm chance de serem invocados de maneira útil ao analisar uma cadeia de terminais (embora alguns possam desperdiçar o tempo de processamento de um analisador quando não forem removidos; quais podem perder tempo depende da tecnologia do analisador).

Agora consideramos, para cada regra (útil), a produção de uma cadeia de terminais que a invoca, ou seja, que pode ser gerada usando essa regra. Isso é essencialmente o que é feito por esses dois algoritmos acima, embora eles não mantenham as informações, pois estão satisfeitos em provar a existência dessas seqüências para garantir que os não terminais sejam alcançáveis ​​e produtivos.

Modificamos o primeiro algoritmo (lema 4.1), mantendo com cada terminal não terminal $U$ no conjunto $Prod$ uma cadeia de terminais $\sigma(U)$ deriva de: $U\overset{*}{\Longrightarrow}\sigma(U)$. Para cada terminal, definimos o$\sigma$como o mapeamento de identidade. Quando$U$ é adicionado ao conjunto $Prod$ porque uma regra $U\rightarrow\gamma$ tem todos os seus símbolos RHS em $Prod$, então definimos $\sigma(U)=\sigma(\gamma)$estendendo $\sigma$ como um homomorfismo em cordas, e removemos todos $U$-rules, ou seja, todas as regras com $U$ como LHS.

Modificamos o segundo algoritmo (lema 4.2) mantendo cada símbolo não terminal $U$ Adicionado a $Reach$ o caminho usado para alcançá-lo a partir do símbolo inicial $S$, que fornece as regras sucessivas para obter uma derivação $S\overset{*}{\Longrightarrow}\alpha U \beta$.

Então, para cada regra $U\rightarrow\gamma$na gramática, produzimos uma cadeia de terminais que "chama" esta regra da seguinte maneira. Tomamos do resultado do segundo algoritmo a derivação $S\overset{*}{\Longrightarrow}\alpha U \beta$. Em seguida, aplicamos a regra para obter a string$\alpha \gamma \beta$. Uma cadeia de terminais "invocando" a regra$U\rightarrow\gamma$ é $\sigma(\alpha \gamma \beta)$

Construindo um conjunto de seqüências mínimas que "invocam" todas as regras

Ignoramos a questão de eliminar símbolos inúteis, que podem ser um subproduto desses algoritmos modificados.

Construir um conjunto de seqüências mínimas depende primeiro da obtenção de uma sequência derivada mínima para cada não terminal. Isso é feito modificando ainda mais o primeiro algoritmo (lema 4.1). Primeiro, removemos do conjunto de regras a serem processadas todas as regras recursivas (ou seja, com um símbolo LHS ocorrendo na string RHS). É óbvio que nenhuma dessas regras pode derivar para uma cadeia terminal mais curta que as regras não recursivas com o mesmo LHS. E deve haver pelo menos uma regra não recursiva se o LHS não for um não-terminal inútil (porque não produtivo).

Então procedemos como antes para construir o conjunto $Prod$ de símbolos produtivos, associados a cada sinbol $U$ uma cadeia de terminais, que notamos $\sigma(U)$. A corda$\sigma(U)$ é produzido como antes pela aplicação da regra $U\rightarrow\gamma$, substituindo cada não terminal $V$ ocorrendo em $\gamma$ com $\sigma(V)$. Até o momento, era necessário aplicar isso a apenas uma regra com um dado não terminal$U$ como seu LHS, o primeiro que teria todos os seus não terminais RHS em $Prod$e, em seguida, ignore os outros, porque qualquer string derivada faria. Mas agora estamos procurando uma string derivada mínima. Portanto, para um não terminal$U$, isso deve ser feito para todas as regras com $U$como LHS. Mas mantemos apenas uma cadeia de terminais$\sigma(U)$, substituindo o atual pelo recém-encontrado, sempre que o novo for menor.

Além disso, sempre que a string $\sigma(U)$ é substituído por um menor, todas as regras com ocorrência de $U$no RHS que já havia sido processado, é necessário recolocar o conjunto de regras a serem processadas, pois as alterações permitem derivar seu RHS em uma sequência mais curta. Portanto, isso exigirá mais iterações, mas acabará sendo finalizado, pois nenhuma dessas strings fica muito menor do que a string vazia.

No final deste primeiro algoritmo, a string $\sigma(U)$ é uma das menores seqüências que podem ser derivadas de $U$. Pode haver outros.

Agora também temos que modificar o segundo algoritmo para obter, para cada não terminal $U$, (uma das) a cadeia mais curta que contém U como o único não terminal. Para fazer isso, mantemos o mesmo gráfico direcionado com não terminais que os nós e com um arco$(U,V)$ se houver uma regra $U\rightarrow \alpha V \beta$. Mas agora colocamos pesos nos arcos, para calcular o comprimento mínimo do contexto do terminal que deve ser associado aos não terminais alcançáveis. O peso associado ao arco$(U,V)$ acima é o comprimento $|\sigma(\alpha\beta)|$, onde o mapeamento $\sigma$é estendido aos terminais como a identidade e depois estendido novamente como um homomorfismo de cadeia. É o comprimento de (uma das) seqüências terminais mais curtas que podem ser derivadas da sequência $\alpha\beta$. Observe que$V$é removido neste cálculo. No entanto, quando existem várias ocorrências de$V$no RHS, apenas um deve ser removido. Pode haver vários possíveis$(U,V)$ arcos, com pesos diferentes, se houver várias regras com $U$ como LHS e $V$no RHS. Nesse caso, apenas (um de) o arco mais leve é ​​mantido.

Neste gráfico, não procuramos mais apenas a acessibilidade de nós de $S$, mas para o caminho ponderado mais curto que atinge todos os nós do símbolo inicial $S$. Isso pode ser feito com o algoritmo de Dijkstra .

Dado o caminho mais curto para um terminal não terminal $U$, lemos como antes como uma sequência de regras, da qual obtemos uma derivação $S\overset{*}{\Longrightarrow}\alpha U \beta$. Então, para todas as regras do formulário$U\rightarrow\gamma$ na gramática, produzimos uma cadeia terminal mínima que "chama" essa regra como $\sigma(\alpha\gamma\beta)$

Observação : a mesma seqüência mínima provavelmente pode ser usada para várias regras. Mas o fato de uma das seqüências usar uma regra$\rho$ na sua derivação não significa necessariamente que é uma sequência mínima para essa regra $\rho$, como pode ter sido encontrado para outra regra, enquanto um mais curto pode ser encontrado para $\rho$. Pode ser possível aumentar a probabilidade de que a mesma sequência mínima seja encontrada para várias regras usando alguma política de prioridade sempre que houver flexibilidade. Mas vale a pena o problema?

Um algoritmo mais rápido para o mínimo de string de terminal derivado de um não-terminal

Construindo a função $\sigma$ de tal modo que $\sigma(U)$ é uma cadeia terminal mínima derivada de $U$é feito acima com uma técnica bastante ingênua que requer uma reconsideração iterativa do trabalho já realizado quando uma nova sequência derivada menor é encontrada para alguns não terminais. Isso é um desperdício, mesmo que o processo termine claramente.

Propomos aqui um algoritmo mais eficiente, que é, em essência, uma adaptação ao gráfico gramatical de CF de uma extensão do algoritmo de caminho mais curto de Dijkstra para e-ou gráficos, com uma definição adequada do conceito de caminho para um e-ou gráfico . Essa variante do algoritmo provavelmente existe na literatura (supondo que esteja correta), mas não consegui encontrá-lo nos recursos que posso acessar. Por isso, estou descrevendo-o em mais detalhes, juntamente com uma prova.

Como anteriormente, removemos primeiro do conjunto de regras a serem processadas todas as regras recursivas (ou seja, regras com um símbolo LHS ocorrendo na cadeia RHS). É óbvio que nenhuma dessas regras recursivas pode derivar para uma cadeia terminal mais curta que as regras não recursivas com o mesmo LHS. E, para um LHS$U$ deve haver pelo menos um não recursivo $U$- regra se o símbolo $U$não é um não terminal inútil (porque não produtivo). Isso não é estritamente necessário, mas reduz o número de regras a serem consideradas posteriormente.

Então procedemos como antes para construir o conjunto $Prod$ de símbolos produtivos, associados a cada sinbol $X$ uma cadeia de terminais, que notamos $\sigma(X)$, que é uma cadeia de terminais de tamanho mínimo derivável de $X$ (no algoritmo anterior, isso era verdade somente após o término). O conjunto $Prod$ é inicializado com todos os símbolos do terminal e para cada símbolo do terminal $a$, definimos $\sigma(a)=a$.

Então consideramos todas as regras $U\rightarrow\gamma$ de modo que todos os símbolos RHS estejam em $Prod$e escolhemos um desses que $\sigma(\gamma)$é tamanho mínimo. Então nós adicionamos$U$ para $Prod$com $\sigma(U)=\sigma(\gamma)$e remova tudo $U$-regras. Repetimos até que todos os terminais produtivos tenham sido inseridos$Prod$. Qualquer não terminal$U$, uma vez inserido $Prod$, nunca precisa ser considerado novamente para mudar $\sigma(U)$ para uma corda menor.

Prova :

Os algoritmos anteriores eram mais ou menos intuitivamente óbvios. Este é um pouco mais complicado, devido ao caráter e-ou do gráfico, e uma prova parece mais necessária. Tudo o que precisamos é realmente o seguinte lema, que estabelece a correção do algoritmo quando aplicado à última iteração.

Lema : após cada iteração do algoritmo,$\sigma(X)$ é uma cadeia de terminais de tamanho mínimo derivável de $X$, para todos $X$ no $Prod$.

O passo base é óbvio, pois isso é verdadeiro por definição para todos os terminais no $Prod$ quando é inicializado.

Então, supondo que seja verdade depois que alguns não terminais foram adicionados ao $Prod$, deixei $U\rightarrow\gamma$ ser a regra escolhida para adicionar um novo não terminal ao $Prod$. Sabemos que esta regra é escolhida porque $\gamma\in{Prod}^*$ e $\sigma(\gamma)$ é tamanho mínimo em todo RHS de todas as regras com um RHS em ${Prod}^*$. Então$U$ é adicionado a $Prod$, e temos apenas que provar que $\sigma(\gamma)$ é uma cadeia de terminais de tamanho mínimo derivável de $U$.

Obviamente, esse é o caso de todas as derivações que começam com a regra $U\rightarrow\gamma$, já que por hipótese de indução, aplicação de mapeamento $\sigma$ é tal que todos os não terminais na $\sigma$são substituídos por cadeias terminais de tamanho mínimo derivadas delas. Portanto, nenhuma outra derivação pode produzir uma cadeia terminal mais curta.

Assim, consideramos apenas derivações começando com outra $U$-regra $U\rightarrow\beta$, de tal modo que $\beta\overset{*}{\Longrightarrow}w\in\Sigma^*$, Onde $\Sigma$ é o conjunto de símbolos do terminal.

E se $\beta\in{Prod}^*$, uma sequência mínima na qual ela pode derivar é $\sigma(\beta)$. Mas, desde que escolhemos a regra$U\rightarrow\gamma$, deve ser isso $|\sigma(\beta)|\geq|\sigma(\gamma)|$. Então a regra $U\rightarrow\beta$ não deriva em uma substring terminal menor.

O último caso a considerar é quando $\beta\notin{Prod}^*$, e então consideramos uma derivação $\beta\overset{*}{\Longrightarrow}w\in\Sigma^*$. Se essa derivação envolver apenas não-terminais,$Prod$, então $\beta\in{Prod}^*$, que é um caso que já vimos. Portanto, consideramos apenas derivações que possuem etapas usando uma regra com seu LHS que não esteja em$Prod$. Deixei$V\rightarrow\alpha$ tal regra, tal que $\alpha\in{Prod}^*$. Deve haver pelo menos uma dessas regras, uma vez que elas são parcialmente ordenadas por ordem de derivação, e $w\in{Prod}^*$.

Assim nós temos $U\Longrightarrow\beta\overset{*}{\Longrightarrow}\mu V\nu$. Nós sabemos isso$\mu$ e $\nu$ derivam em uma sequência de tamanho pelo menos 0 e, como não $V$regra com um RHS em ${Prod}^*$ foi escolhido, eles derivam em cordas terminais de comprimento pelo menos igual a $|\sigma(\gamma)|$. Portanto, com a regra$U\rightarrow\beta$, $U$ deriva de uma cadeia terminal de comprimento pelo menos igual a $|\sigma(\gamma)|$. $\blacksquare$

Uma solução simples

Se você não se importa muito com o número de strings, existe uma solução fácil. Basicamente, para cada produção, geraremos uma string que cubra essa produção.

Como fazemos isso? É um algoritmo simples de lista de trabalho. Suponha que queremos cobrir a produção$A ::= BCx$. Basicamente, fazemos uma pesquisa abrangente desde o início não terminal$S$ para encontrar uma derivação que inclua o terminal $A$ no lado direito: inicialmente, todos os não terminais são desmarcados e o conjunto de não terminais alcançáveis ​​é $\{S\}$; em cada iteração, escolhemos um não terminal acessível não marcado, digamos$X$e para cada produção com $X$ no lado esquerdo, adicionamos todos os não terminais à direita ao conjunto de terminais alcançáveis ​​e depois marcamos $X$. Repita até que esse processo encontre$A$está acessível. Quando isso ocorre, ao rastrear, você obtém uma derivação do formulário$S \to \cdots A \cdots$. Você pode estender isso para uma derivação do formulário$S \to \cdots A \cdots \to \cdots BCx \cdots$.

Em seguida, precisamos concluir a derivação, escolhendo uma maneira de concluí-la para ser todos não terminais. Isso também é fácil. Para cada não terminal, encontramos a string mais curta que está no idioma gerado por esses não terminais. Isso pode ser obtido por uma iteração da lista de trabalho. Deixei$\ell(A)$ denotam o comprimento da string mais curta que encontramos até agora no idioma gerado por $A$. Inicialmente, definimos$\ell(A)=\infty$ para todos os não terminais $A$, a menos que haja uma produção $A ::= xyz$onde todos os símbolos no lado direito são terminais; nesse caso, definimos$\ell(A)$ em conformidade (por exemplo, $\ell(A)=3$ se a produção nos diz que $xyz$ é em $L(A)$) Agora, iterativamente, procuramos uma maneira de encontrar uma string mais curta. Se você tem uma produção como$A ::= xBCy$, Você sabe disso $\ell(A) \le 2 + \ell(B) + \ell(C)$; portanto, sempre que você encontrar uma nova string mais curta em$L(B)$ ou $L(C)$ (ou seja, sempre que você atualizar $\ell(B)$ ou $\ell(C)$ ser menor), você pode verificar se isso fornece uma nova string mais curta no $L(A)$e, se houver, reduza o valor de $\ell(A)$... que por sua vez pode causar outras alterações em cascata. Continue aplicando todas as alterações em cascata até que nenhuma alteração adicional seja acionada. Nesse ponto, você atingiu um ponto fixo e, retornando, para cada não terminal, você conhece a sequência mais curta (de terminais) que pode ser derivada desse não terminal.

Agora, dada sua derivação do formulário $S \to \cdots BCx \cdots$, encontre uma maneira de concluir a derivação: substitua cada não terminal em $\cdots BCx \cdots$ com a cadeia mais curta (de terminais) que pode ser derivada dela.

Isso fornece uma sequência (de terminais) que cobre a produção $A ::= BCx$. Faça isso uma vez para cada produção, até que todos estejam cobertos.

O número de strings é igual ao número de produções. O tempo de execução é quadrático: o processo é linear para cada produção. (Você provavelmente poderia reduzi-lo a um algoritmo de tempo linear no total, mas eu suspeito que isso seja bom o suficiente na prática.)

Otimizações

Se você deseja reduzir o número de seqüências de caracteres, talvez note que cada sequência abrange muitas produções, portanto um subconjunto dessas sequências provavelmente será suficiente.

Existem várias maneiras de reduzir o número de strings. Uma simples é usar o algoritmo de aproximação padrão ganancioso para a cobertura do conjunto. Comece gerando todas as seqüências de caracteres acima, uma para cada produção e conte quantas produções cada uma delas abrange. Mantenha a corda que cobre mais produções; aquele que você definitivamente deseja, então adicione-o ao seu conjunto de detentores. Agora, algumas das produções são cobertas por esse detentor, então não precisamos de novas strings que as cubram novamente. Portanto, você deve atualizar seu conjunto de contagens para cada string: para string$s$, conte o número de produções cobertas por $s$mas não são cobertos por nenhum detentor. Escolha a sequência que tem o maior número, adicione-a ao seu conjunto de detentores e atualize as contagens novamente. Repita até que todas as produções tenham sido cobertas. Isso provavelmente fornecerá um conjunto significativamente menor de seqüências de caracteres que abrangem todas as produções de sua gramática.