Dada uma sequência e um CFG, que caracteres podem seguir a sequência (nas formas sentenciais do CFG)?

Seja o conjunto de terminais e o conjunto de símbolos não terminais de alguma gramática livre de contexto .$\Sigma$$N$$G$

Digamos que eu tenho uma string tal que que e são as formas de sentenciais .$a \in (\Sigma \cup N)^+$$x a y \in \mathcal{S}(G)$$x,y\in (\Sigma \cup N)^*$$\mathcal{S}(G)$$G$

Dado , eu gostaria de determinar um conjunto .$G$$C = \{ b \mid wabz \in \mathcal{S}(G), b \in \Sigma \cup N \}$

Para esclarecer, neste caso, são cadeias de terminais e não terminais é de comprimento um.$w, x, y, z, a, b$$b$

Eu posso ver como fazer isso se também é do comprimento um; cada é um membro do conjunto a seguir de (incluindo não terminais).$a$$b$$a$

No entanto, estou curioso para saber se é possível uma sequência de caracteres. Para a minha candidatura, a seqüência de não é muito mais do que o lado direito das produções em .$a$$G$

A distinção entre terminais e não terminais é um tanto muda no meu aplicativo porque estou usando uma gramática generativa; e acredito que isso não vai gerar muitos problemas, já que é do tamanho um.$b$

Vou descrever um algoritmo que funciona. É tempo de execução não deve ser tão ruim. Você pode pré-calcular bastante disso também.

Suponho que não contenha termos não terminais (embora provavelmente seja fácil se adaptar a esse caso) e que você não saiba , ou a derivação de . Também assumirei que sua gramática não contém produções que nunca são usadas em nenhuma derivação ( por exemplo).$a$$x$$y$$a$$A \rightarrow A$

A questão principal é realmente analisar , como você deseja saber em que tipo de estados você termina, para saber o que pode seguir . Isso não é tão fácil quanto você não conhece .$a$$a$$x$

Usamos uma adaptação do algoritmo de Earley . Você vai querer entender esse algoritmo primeiro. Nosso algoritmo funciona quase da mesma maneira, exceto que nossas etapas de inicialização e conclusão são diferentes.

Para a inicialização, semeamos nosso primeiro conjunto com um item Earley para cada ocorrência de (o primeiro caractere em ) em qualquer produção de sua gramática. Definimos o ponteiro de trás deste item como -1, um valor inválido. Isso é importante em nossa conclusão modificada. Essencialmente, o -1 significa 'não faço ideia de onde essa produção foi iniciada'.$a_1$$a$

Agora, executamos o algoritmo Earley separadamente para cada item inicial possível de Earley. Não podemos simplesmente fazer todos eles ao mesmo tempo, pois as análises podem interferir entre si. Não consigo ver facilmente um método mais rápido do que voltar atrás aqui.

Para a etapa de conclusão, precisamos apenas fazer uma modificação para manipular -1 ponteiros de volta. Como concluímos uma produção cuja origem não sabemos, estamos com problemas. No entanto, o método usado para calcular os conjuntos$LALR(1)$ de visores da Pennello e DeRemer nos salva: o que precisamos aqui é exatamente os conjuntos de visores . Cada item desses conjuntos de visores tem uma posição correspondente na gramática, que por sua vez corresponde a uma possível continuação da produção concluída.$LALR(1)$

Infelizmente, não vejo outra opção senão voltar aqui novamente. Para todas as posições no conjunto de lookahead, você executa a etapa de conclusão com essa posição e continua a análise a partir daí. Você faz isso separadamente para cada análise. Observe que, se sua gramática for , sua cabeça determinada determinará em qual posição você deve ir, para que você não precise voltar atrás.$LALR(1)$

Você continua o algoritmo acima, um caractere além de , onde considera esse caractere virtual extra como 'qualquer caractere', o que imediatamente fornece o conjunto de 'follow' que você procura - sempre que a fase do scanner encontrar algo para este final conjunto, você pode adicionar esse caractere ao seu conjunto de respostas.$a$

Edit: Acho que encontrei o método que remove a maior parte da sobrecarga introduzida pelo backtracking. Associamos a cada item de Earley um conjunto de identificadores, que são cadeias, pois precisaremos usar prefixos desses identificadores. Na inicialização, adicionamos todos os itens iniciais ao conjunto Earley e associamos um identificador exclusivo a cada conjunto.

Nas etapas do scanner e do preditor, os identificadores são transferidos para novos itens. Os itens Earley no mesmo conjunto Earley que diferem apenas em seus identificadores são mesclados, mesclando-os. Observe que podemos executar etapas de scanner e preditor nesses novos itens com identificadores, sem precisar executar esta etapa para cada identificador separadamente.

O completador considera os identificadores separadamente e somente conclui um item se o item correspondente no conjunto de itens anterior tiver um identificador que seja um prefixo do identificador. Para cada conclusão possível (portanto, para cada item do conjunto de ), anexamos um caractere exclusivo aos identificadores dos itens concluídos.$LALR(1)$

Essencialmente, fazemos o backtracking usando esses identificadores, para não trabalharmos duas vezes nas etapas do scanner e do preditor.