Acta Scientiarum. Technology
ISSN: 1806-2563
[email protected]
Universidade Estadual de Maringá
Brasil
Guse Scós Venske, Sandra Mara; de Ré, Angelita Maria; Schram, Giovani; Tosatti, Murilo Augusto;
Kultz, Rene
Inferência gramatical usando uma técnica evolutiva
Acta Scientiarum. Technology, vol. 33, núm. 2, 2011, pp. 163-169
Universidade Estadual de Maringá
Maringá, Brasil
Disponível em: http://www.redalyc.org/articulo.oa?id=303226531009
Como citar este artigo
Número completo
Mais artigos
Home da revista no Redalyc
Sistema de Informação Científica
Rede de Revistas Científicas da América Latina, Caribe , Espanha e Portugal
Projeto acadêmico sem fins lucrativos desenvolvido no âmbito da iniciativa Acesso Aberto
DOI: 10.4025/actascitechnol.v33i2.4799
Inferência gramatical usando uma técnica evolutiva
Sandra Mara Guse Scós Venske*, Angelita Maria de Ré, Giovani Schram, Murilo Augusto
Tosatti e Rene Kultz
Departamento de Ciência da Computação, Universidade Estadual do Centro-Oeste, Cx. Postal 3010, 85015-430, Guarapuava,
Paraná, Brasil. *Autor para correspondência. E-mail: [email protected]
RESUMO. Num processo de inferência, busca-se encontrar uma resposta genérica
baseando-se na análise de uma amostra de fatos. A inferência gramatical visa obter uma
gramática para uma determinada linguagem baseada em exemplos de cadeias que pertencem
ou não à linguagem analisada. Neste trabalho propõe-se um algoritmo para o uso de
inferência em gramáticas livres de contexto baseadas em uma cadeia exemplo não
pertencente à linguagem. A técnica evolutiva de algoritmos genéticos foi aplicada no
processo com o objetivo de auxiliar na criação das regras de produção para as gramáticas,
atendendo às restrições impostas pela cadeia exemplo. Uma aplicação do algoritmo de
inferência está relacionada a linguagens que possuem padrões específicos pré-definidos,
como é o caso de documentos XML no contexto de esquemas. A eficiência do algoritmo
proposto é mostrada através de pequenos testes onde são obtidas gramáticas geneticamente
geradas.
Palavras-chave: gramática livre de contexto, algoritmo genético, XML.
ABSTRACT. Grammatical inference using an evolutionary technical. Inference
process try to find a generic answer based on a sample of facts. This process aims to achieve
a grammar for a particular language based in string samples that belong or not belong to the
specific language. In this work we propose an algorithm for context-free grammars
inference based in only one sample string that not belongs to the language. The genetic
algorithm evolutive technical was applied in order to assist the generation of production
rules for grammars. This process must to validate the sample string restrictions. Inference
algorithm proposed can be applied in computer languages that have specific pre-defined
standards, like schemas for XML documents. Suitability of the proposed algorithm is shown
by small experiments where grammars are genetically obtained and generated.
Keywords: context-free grammar, genetic algorithm, XML.
Introdução
Inferir significa encontrar uma resposta genérica
baseando-se na análise de uma amostra dos fatos e
não em todos eles. A inferência de gramáticas (ou
indução gramatical ou aprendizado de linguagem)
visa obter uma gramática de uma determinada
linguagem baseada em exemplos de cadeias que
pertencem ou não à linguagem analisada.
Pesquisadores têm desenvolvido algoritmos
especialmente para indução de linguagens regulares
(DUPONT,
1994;
HINGSTON,
2001;
BONGARD; LIPSON, 2005). O aprendizado de
gramáticas livres de contexto é ainda um desafio em
inferência gramatical, principalmente devido ao fato
de que somente exemplos positivos e negativos não
são suficientes para que o processo de inferência seja
executado com sucesso.
A inferência gramatical tem um vasto campo de
aplicação. Uma dessas aplicações é na identificação
de padrões em um espaço de amostras, sendo que
Acta Scientiarum. Technology
tais padrões correspondem naturalmente aos
símbolos não-terminais em uma gramática. Assim,
são exemplos de aplicações de reconhecimento de
padrões: identificar sequências de DNA, realçar
padrões em contagens musicais (CRUZALCÁZAR; VIDAL, 1998), descobrir propriedades
de linguagem de textos e reconhecimento de voz,
dentre outros (MICLET et al., 2004).
Outra aplicação de inferência gramatical está
relacionada com linguagens que possuem padrões
específicos pré-definidos, como é o caso de
documentos XML no contexto de DTDs (Definições
de Tipo de Documento) e XML Schema (SILVA et
al., 2007). A alteração e evolução de esquemas de
documentos XML foi o que motivou esta pesquisa de
inferência de gramáticas. Alguns trabalhos usando este
foco são: Bouchou et al. (2004), Silva et al. (2007) e
Venske et al. (2007a e b).
Em Venske et al. (2007a) e Venske et al. (2007b)
são apresentados trabalhos iniciais de indução
Maringá, v. 33, n. 2, p. 163-169, 2011
164
gramatical para gramáticas livres de contexto
usando o algoritmo de parser LR(0); este trabalho
resulta num algoritmo indutivo (chamado ILR(0)
– Inductive LR(0) para validação de uma cadeia.
Kultz et al. (2007) apresenta um algoritmo de
indução semelhante, mas usando o algoritmo de
parser SLR(1). Em Silva et al. (2007) é explorada a
correspondência entre esquemas de documentos
XML (XML Schema e DTD) e gramáticas livres
de contexto, implementando uma extensão do
algoritmo de parser LL(1). Para todos estes casos
são utilizados métodos exatos na inferência.
Os algoritmos genéticos são uma família de
modelos computacionais inspirados na evolução
(GOLDBERG, 1989), que incorporam uma solução
potencial para um problema específico numa
estrutura semelhante a de um cromossomo e
aplicam operadores de seleção, mutação e
cruzamento a essas estruturas de forma a preservar
informações críticas relativas à solução do problema.
Em geral, os algoritmos genéticos são vistos como
otimizadores de funções, embora a quantidade de
problemas para os quais eles se aplicam seja bastante
abrangente.
Em Dupont (1994) foi utilizada uma abordagem
genética para inferir gramáticas de linguagens regulares.
O resultado foi comparado com o algoritmo de
inferência regular positiva e negativa proposto em
Oncina e García (1991) que pode identificar qualquer
linguagem regular em um limite.
Em Mernik et al. (2003a) e Mernik et al. (2003b)
propõe-se uma abordagem evolucionária para
indução de gramáticas livres de contexto no formato
BNF (Backus-Naur Form) e EBNF (Extended
Backus-Naur Form), com operadores heurísticos de
mutação e cruzamento.
Outros exemplos de tentativas de aprendizado
de gramáticas livres de contexto e indução usando
algoritmos evolucionários são Javed et al. (2004),
Javed (2005), Keller e Lutz (2005), Giles et al.
(2001), Carrasco et al. (2001) e Lucas e Reynolds
(2005).
Neste trabalho utiliza-se inferência para obter
várias gramáticas livres de contexto baseadas em
somente uma cadeia exemplo não pertencente à
linguagem. Neste processo, foi utilizada a técnica
evolutiva de algoritmos genéticos, objetivando
encontrar gramáticas que atendessem às restrições
impostas pela cadeia exemplo. O controle do
processo de inferência foi realizado por um parser,
sendo que o algoritmo genético auxiliou na
criação das regras de produção para a nova
gramática.
Acta Scientiarum. Technology
Venske et al.
Material e métodos
Num processo de inferência, busca-se encontrar
uma resposta genérica baseando-se na análise de
uma amostra de fatos. Este processo visa obter uma
gramática para uma determinada linguagem baseada
em exemplos de cadeias que pertencem ou não à
linguagem analisada. No contexto dos problemas de
aprendizado computacional a inferência gramatical é
uma abordagem importante.
Propõe-se neste trabalho o uso de inferência para
gramáticas livres de contexto baseadas em somente
uma cadeia exemplo não pertencente à linguagem. A
técnica evolutiva de algoritmos genéticos foi aplicada
ao processo a fim de auxiliar na criação das regras de
produção para novas gramáticas, atendendo às
restrições impostas pela cadeia exemplo. São
utilizadas e geradas gramáticas livres de contexto,
validando cadeias através do algoritmo de parser
SLR(1) (AHO et al., 1986).
O algoritmo SLR(1) (AHO et al., 1986) consiste
em construir, a partir da gramática, um autômato
finito determinístico que reconheça prefixos viáveis.
Em seguida, agrupam-se esses itens em conjuntos,
os quais dão origem aos estados do analisador
sintático SLR. Esses itens podem ser vistos como os
estados do autômato que reconhecem os prefixos
viáveis. O agrupamento desses itens é o processo de
construção de subconjuntos.
Segundo Louden (2004) uma gramática é SLR(1)
se para qualquer estado s as seguintes condições
forem satisfeitas:
1. Para qualquer item A  X em s em que
X for um terminal, não existe um item
completo B em s com X em
Seqüência(B).
2. Para quaisquer dois itens completos A   e
B  em s, Sequência(A)  Sequência(B)
é vazio.
O algoritmo de inferência desenvolvido tem
como entrada uma gramática livre de contexto G e
uma cadeia de caracteres w, inicialmente não
aceita pela gramática1. Em primeiro lugar, é feita a
chamada do parser SLR(1) para verificar em que
ponto de w ocorreu o erro de validação em G. Em
seguida, ocorre a seleção dos itens onde foram
encontrados os erros, para que o algoritmo
genético crie novos itens que façam com que G
passe a aceitar w. Durante a execução do
algoritmo genético as soluções válidas encontradas
(que geram gramáticas inéditas) são adicionadas ao
conjunto de soluções. A Figura 1 ilustra o
1
Caso w seja aceita por G, o processo é encerrado.
Maringá, v. 33, n. 2, p. 163-169, 2011
Inferência em gramáticas livres de contexto
esquema de funcionamento do algoritmo de
inferência. Nas subseções seguintes são
apresentados os detalhes pertinentes.
165
O estado no topo da pilha (5) possui o item
completo:
F  a
Fazendo a redução através deste item, a pilha
de análise sintática apresenta a seguinte
configuração:
$0
E1
+6
F3
O estado no topo da pilha (3) possui o item
completo:
T  F 
Figura 1. Esquema do funcionamento.
Verificação e seleção de itens
O primeiro passo do algoritmo é a verificação da
cadeia w através do parser SLR(1). Se w for aceita
por G, o processo é encerrado, caso contrário, é
iniciado o processo de inferência.
Descoberto o ponto onde ocorreu o erro na
validação de w, é feita a seleção dos itens a serem
modificados. Estes itens são a base para a geração de
novas regras de produção para o aceite de w.
O procedimento de seleção de itens inicia-se
recuperando o elemento do topo da pilha de análise
sintática, obtendo-se, assim, o número do estado do
autômato finito determinístico onde ocorreu o erro
e, conseqüentemente, o conjunto de itens do estado.
Dentre estes, são selecionados todos os itens de
carregar que começam com um terminal a partir do
meta-símbolo e os itens completos que não possuam
como não-terminal o símbolo inicial da gramática.
Em seguida, é realizada a redução da pilha de
análise sintática a partir dos itens completos
selecionados. Se a redução for bem sucedida, todos
os itens pertencentes ao estado corrente serão
selecionados. Este processo de seleção de itens é
executado repetidamente, realizando novas reduções
até encontrar um estado isento de itens de redução.
Seja G a gramática definida pelas regras de
produção a seguir e o autômato finito determinístico
de itens mostrado na Figura 2.
EE+T|T
TT*F|F
F(E)|a
Para a cadeia “w = a + a / a”, o estado da pilha de
análise sintática onde ocorreu o erro é:
0
E1
+6
Acta Scientiarum. Technology
A5
O processo de redução e seleção de itens
continua até o ponto em que não é possível realizar
novas reduções. Ao final, obtém-se o seguinte
conjunto de itens:
Fa
TF
TT*F
EE+T
EE+T
Este conjunto de itens representa todos os
possíveis pontos passíveis de modificação pelo
algoritmo genético.
Aplicação do algoritmo genético
Selecionados os itens, é feita a chamada ao
algoritmo genético. Um esquema genérico de um
algoritmo evolutivo pode ser dado pelos passos a
seguir (GOLDBERG, 1989):
1. Geração da população inicial de indivíduos.
2. Avaliação da população inicial (fitness).
3. Teste de condição de parada do algoritmo.
4. Seleção indivíduos a serem reproduzidos.
5. Aplicação dos operadores genéticos (mutação
e cruzamento).
6. Avaliação dos novos indivíduos gerados.
7. Construção da nova população através da
população anterior e dos novos indivíduos
gerados.
8. Retorno ao passo 3. ~
A população inicial para esta solução proposta é
gerada de forma aleatória. O indivíduo é
representado por uma cadeia de caracteres, que pode
ser composta por qualquer um dos elementos dentre
todos os terminais e não-terminais da gramática G,
além de qualquer símbolo novo encontrado na
cadeia de entrada w.
Maringá, v. 33, n. 2, p. 163-169, 2011
166
Venske et al.
Figura 2. Autômato Finito Determinístico.
O indivíduo representa o complemento do item
selecionado no processo descrito na seção 3.1. Por
exemplo, no item:
S a B  a b
O complemento gerado (indivíduo) substitui o
lado direito do meta-símbolo; no caso do exemplo,
representado pelos caracteres “a b”.
Na criação do gene, um dos itens selecionados na
Seção 3.1 entra como parâmetro. O comprimento
do gene varia entre zero e o dobro da média do
comprimento das produções da gramática de
entrada. A combinação dos caracteres do gene
obedece a uma probabilidade de 70% de terminais e
30% de não-terminais, em qualquer ordem,
ocupando quaisquer posições do cromossomo.
A função de fitness calculada indica quão bem a
gramática gerada com as novas regras de produção se
adequa no processo de validação da cadeia.
Inicialmente, todos os itens já possuem valores de
fitness iguais a 1. Caso a gramática seja SLR(1),
soma-se mais três a esse valor. Em seguida, faz-se a
verificação da cadeia na gramática com o parser.
Caso a gramática aceite a cadeia, soma-se 10 ao valor
Acta Scientiarum. Technology
de fitness. Caso contrário, soma-se 1. Desta forma,
as seguintes situações podem ocorrer:
- Gramáticas não-SLR(1) recebem valor de fitness
igual a 1.
- Gramáticas SLR(1) que não aceitam a cadeia
recebem fitness igual a 5.
- Gramáticas SLR(1) que aceitam a cadeia recebem
fitness igual a 14.
Cada gramática gerada com fitness igual a 14 é
armazenada em um conjunto de soluções durante a
execução do algoritmo genético. Neste caso, sempre
é verificado se a solução é inédita, ou seja, se ela não
foi gerada anteriormente.
A taxa de cruzamento utilizada foi de 80% e o
tipo utilizado foi de 1-ponto. A taxa de mutação foi
de 50%, sendo a probabilidade de 65% de ser
mudado para um terminal, 25% de ser mudado para
um não-terminal e 10% de ser eliminado, tornando
a regra de produção mais curta. Estas porcentagens
foram escolhidas por apresentarem melhores
resultados nos testes realizados.
A seleção dos indivíduos foi feita usando o
método da roleta. Entretanto, para a mutação a
seleção foi feita de maneira aleatória, de modo a
aumentar a diversificação da população como um
Maringá, v. 33, n. 2, p. 163-169, 2011
Inferência em gramáticas livres de contexto
todo. Os números de indivíduos e de gerações foram
fixados em 50.
Para o exemplo da seção 3.1, o algoritmo
genético gerou as regras de produção que deram
origem às gramáticas apresentadas na Tabela 1. As
regras
em
destaque
foram
as
geradas
geneticamente.
É importante observar que este conjunto de
soluções representa a execução de uma instância
do algoritmo genético. Outras execuções podem
produzir resultados diferentes. Além disso,
observa-se a diversidade proporcionada pela
técnica, que permite a inserção de generalizações
em vários pontos das soluções.
Tabela 1. Conjunto de Soluções geradas para o exemplo.
E
T
F
E
T
F
E
T
F
E
T
F












E
T
(
E
T
(
E
T
(
E
T
(
+
*
E
+
*
E
+
*
E
+
*
E
T
F
)
T
F
)
T
F
)
T
F
)
|
|
|
|
|
|
|
|
|
|
|
|
T
F
a
T
F
a
T
F
a
T
F
a
| a / F
| T / a
| E / F
E
T
F
E
T
F
E
T
F









E
T
(
E
T
(
E
T
(
+
*
E
+
*
E
+
*
E
T
F
)
T
F
)
T
F
)
|
|
|
|
|
|
|
|
|
T
F | F / a
a
T
F | E + T / F
a
T | E + T / T
F
a
| E / a
Resultados e discussão
Esta seção descreve um teste completo de
execução do algoritmo proposto para demonstrar a
sua eficiência.
Foram utilizadas 19 gramáticas para a realização
dos testes. A Tabela 2 contém os resultados obtidos
para as gramáticas compostas pelas regras de
produção mostradas a seguir:
Gramática 1:
EE+T|T
TT*F|F
F(E)|a
167
Tabela 2. Amostra dos resultados de alguns testes.
Gramática 1
Cadeia
*a+a*(a)
-a*a+a
a*a+*a+(a)
a+(a)-(a+a)
a*a+(aa
a+(a+a)+a*a+b
Soluções
4
4
5
4
2
1
Gramática 2
Cadeia
a((a))
(b(a)))
((b))
(a
((ab)
((()))
Soluções
2
2
2
0
1
3
Gramática 3
Cadeia
{i=i*i;}
{i=i*i;}
{i+=i-n;}
{i=i-i;r(x);}
{i=i+n}
{i=x+i;r(i);}
Soluções
1
1
0
1
1
1
Na Tabela 2 podem ser notadas três divisões
mais abrangentes, cada qual contendo os
resultados para uma das gramáticas descritas.
Dentro destas regiões, cada linha consiste dos
resultados obtidos de uma execução do algoritmo,
utilizando como parâmetros a gramática
correspondente e a cadeia. A segunda coluna
indica a quantidade de gramáticas válidas e
inéditas geradas para o teste.
É possível perceber por meio dos resultados que
a aplicação e uso do algoritmo genético gerou regras
de produções válidas para a maioria dos testes
realizados, encontrando resposta para o problema
abordado.
Com o uso do algoritmo genético verificou-se
também que os genes se apresentam bastante
sensíveis aos operadores genéticos de mutação e
cruzamento. Por exemplo, uma mutação em um
único gene pode fazer com que uma gramática que
antes aceitava a cadeia, deixe de ser SLR(1), fazendo
sua posição no ranking de seleção mudar da melhor
para a pior posição.
Gramática 2:
A(A)|a
Conclusão
Gramática 3:
P  { S }
S  T S | T
Ti=E;|r(L);|w(I);
LiL|i
IEI|E
EFOF
F(E)|i|n
O+|-
Neste trabalho utilizou-se inferência gramatical
para obter gramáticas livres de contexto, baseadas em
somente uma cadeia exemplo não pertencente à uma
determinada linguagem. Para atingir este objetivo,
foi escolhida a técnica evolutiva de algoritmos
genéticos, a fim de encontrar gramáticas que
atendessem às restrições impostas pela cadeia
exemplo.
O uso da técnica de algoritmo genético se
mostrou eficaz no processo de inferência escolhido e
Acta Scientiarum. Technology
Maringá, v. 33, n. 2, p. 163-169, 2011
168
apresentou resultados satisfatórios no sentido de que
gerou resposta (regras de produções para gramáticas)
para a maioria dos testes realizados.
Uma importante questão verificada no caso da
inferência gramatical usando abordagem evolutiva é
o fato de que os genes são bastante sensíveis aos
operadores genéticos. A aplicação de um operador
(mutação ou cruzamento) pode fazer com que uma
gramática melhore ou piore drasticamente sua
posição no ranking.
O algoritmo proposto pode ser aplicado na
inferência de padrões no contexto de esquemas para
documentos XML, por exemplo.
Agradecimentos
Este trabalho foi parcialmente apoiado pelo
CNPq.
Referências
AHO, A.; SETHI, R.; ULLMAN, J. D. Compiladores:
princípios, técnicas e ferramentas. Rio de Janeiro: LTC,
1986.
BONGARD, J.; LIPSON, H. Active co-evolutionary
learning of deterministic finite automata. Journal of
Machine Learning Research, v. 6, n. 1, p. 1651-1678,
2005.
BOUCHOU, B.; DUARTE, D.; ALVES, M. H F.;
LAURENT, D.; MUSICANTE, M. A. Schema evolution
for xml: a consistency-preserving approach. In:
MATHEMATICAL
FOUNDATIONS
OF
COMPUTER
SCIENCE,
29.,
2004,
Praga.
Proceedings… Praga: Springer Verlag Berlim and
Heidelberg, 2004. p. 876-888.
CARRASCO, R.; ONCINA, J.; CALERA-RUBIO, J.
Stochastic inference of regular tree languages. Machine
Learning, v. 44, n. 1-2, p. 185-197, 2001.
CRUZ-ALCÁZAR, P. P.; VIDAL, E. Learning regular
grammars to model musical style: comparing different
coding
schemes.
In:
INTERNATIONAL
COLLOQUIUM ON GRAMMATICAL INFERENCE,
4., 1998, Ames. Proceedings... London: Springer-Verlag
Berlim and Heidelberg, 1998. p. 211-222.
DUPONT, P. Regular grammatical inference from
positive and negative samples by genetic search: the GIG
method. In INTERNATIONAL COLLOQUIUM ON
GRAMMATICAL INFERENCE, 2., 1994, Alicante.
Proceedings... London: Springer-Verlag Berlim and
Heidelberg, 1994. p. 236-245.
GILES, C. L.; LAWRENCE, S.; TSOI, A. C. Noisy time
series prediction using recurrent neural networks and
grammatical inference. Machine Learning, v. 44, n. 1-2,
p. 161-183, 2001.
GOLDBERG, D. Genetic algorithms in search,
optimization, and machine learning. Boston:
Addison-Wesley Publishing Company, 1989.
Acta Scientiarum. Technology
Venske et al.
HINGSTON, P. Inference of regular languages using
model simplicity. In: AUSTRALASIAN COMPUTER
SCIENCE CONFERENCE, 24., 2001, Gold Coast.
Proceedings... Washington, D.C.: IEEE Computer
Society, 2001. p. 69-76.
JAVED, F. Inferring context-free grammars for domainspecific
languages.
In:
OBJECT
ORIENTED
PROGRAMMING, SYSTEMS, LANGUAGES AND
APPLICATIONS, 20., 2005, San Diego. Proceedings...
New York: ACM-Association for Computing Machinery,
2005. p. 242-243.
JAVED, F.; BRYANT, B. R., CREPINSEK, M.;
MERNIK, M.; SPRAGUE, A. Context-free grammar
induction using genetic programming. In: SOUTHEAST
REGIONAL CONFERENCE, 42., 2004, Huntsville.
Proceedings... New York: ACM-Association for
Computing Machinery, 2004. p. 404-405.
KELLER, B.; LUTZ, R. Evolutionary induction of
stochastic context free grammars. Elsevier - Pattern
Recognition, v. 38, n. 9, p.1393-1406, 2005.
KULTZ, R.; TOSATTI, M. A.; SCHRAM, G.; VENSKE,
S. M.; RÉ, A. M. Implementação de um parser utilizando
Java. In: ESCOLA REGIONAL DE INFORMÁTICA,
14., 2007, Guarapuava. Anais... Guarapuava: SBCSociedade Brasileira de Computação, 2007. p. 111-122.
LOUDEN, K. C. Compiladores: princípios e práticas.
São Paulo: Thomson Learning, 2004.
LUCAS, S.; REYNOLDS, T. J. Learning Deterministic
Finite Automata with a Smart State Labeling Evolutionary
Algorithm. IEEE Transactions on Pattern Analysis
and Machine Intelligence, v. 27, n. 7, p. 1063-1074,
2005.
MERNIK, M.; CREPINSEK, M.; GERLIC, G.;
ZUMER, V.; BRYANT, B. R.; SPRAGUE, H. Learning
context-free grammars using an evolutionary
approach. Birmingham: University of Maribor and
University of Alabama, 2003a. (Technical Report).
MERNIK, M.; GERLIC, G.; ZUMER, V.; BRYANT, B.
R. Can a parser be generated from examples?. In:
SYMPOSIUM ON APPLIED COMPUTING, 18., 2003,
Melbourne. Proceedings... New York: ACM-Association
for Computing Machinery, 2003b. p. 1063-1067.
MICLET, L.; ONCINA, J.; CARRASCO, R.;
CASACUBERTA, P.; EYRAUD, R.; EZEQUEL, P.;
FERNAU, H.; MURGUE, T.; THOLLARD, F.; VIDAL,
E. Applications of grammatical inference. In:
INTERNATIONAL
COLLOQUIUM
ON
GRAMMATICAL INFERENCE, 7., 2004, Atenas.
Proceedings... London: Springer-Verlag Berlim and
Heidelberg, 2004.
ONCINA, J.; GARCÍA, P. Inferring regular languages in
polynomial updated time. In: SANFELIU, A.; PÉREZ DE
LA BLANCA, N.; VIDAL, E. (Ed.). Pattern recognition
and image analysis. Singapore: World Scientific
Publishing, 1991. p. 49-61.
SILVA, J. C. T.; MUSICANTE, M. A.; POZO, A. T. R.;
VERGILIO, S. R. XML schema evolution by context-free
grammar inference. In: SOFTWARE ENGINEERING
Maringá, v. 33, n. 2, p. 163-169, 2011
Inferência em gramáticas livres de contexto
AND KNOWLEDGE ENGINEERING, 19., 2007,
Boston. Proceedings... Skokie: Knowledge Systems
Institute Graduate School, 2007. p. 444-449.
VENSKE, S.; BOSS, S.; MUSICANTE, M.; SOARES, I.;
AGNER, L.; RÉ, A.; HAUAGGE, J. Uma extensão do
algoritmo de parser LR(0). Publicatio UEPG, v. 13, n. 1,
p. 59-69, 2007a.
VENSKE, S.; BOSS, S.; SOARES, I.; AGNER, L.;
HAUAGGE, J.; RÉ, A.; MUSICANTE, M. Inductive
Acta Scientiarum. Technology
169
inference of LR(0) grammars. Hífen, v. 30, n. 58, p. 17-24,
2007b.
Received on August 28, 2008.
Accepted on October 6, 2009.
License information: This is an open-access article distributed under the terms of the Creative
Commons Attribution License, which permits unrestricted use, distribution, and reproduction
in any medium, provided the original work is properly cited.
Maringá, v. 33, n. 2, p. 163-169, 2011