O processo de geração das sentenças ocorre em duas fases: (1) consiste na tradução da gramática descrita através de uma notação EBNF para uma especificação descrita na linguagem de programação Lua e (2) a especificação Lua é utilizada para a geração das sentenças.
Para um melhor entendimento do funcionamento de LGen, apresentamos um exem- plo prático. A gramática que será utilizada como entrada no gerador é usada para testar as configurações de um software Voip, que é sensível à versão do sistema operacional [Hoffman et al., 2010].
O primeiro passo é especificar a gramática com a notação aceita pela ferramenta. Essa especificação pode ser visualizada através da gramática da Listagem 3.3. A gramática possui 04(quatro) símbolos terminais, 04 (quatro) símbolos não-terminais e 08(oito) regras de produção.
Call = CalerOS, ServerOS,CalleeOS; CallerOS = "Mac" | "Win" ;
ServerOS = "Lin" | "Sun" |"Win" ; CalleeOS = "Mac" | "Win" ;
Listagem 3.3: Gramática em EBNF
Com a gramática EBNF, o próximo passo é a tradução da notação EBNF para uma especificação Lua. A especificação Lua do exemplo pode ser visualizada na Listagem 3.4. Na especificação Lua, a representação de uma sequência (CallerOS, ServerOS,CalleeOS) é feita através da função seq, como pode ser visto em seq(V.CallerOS, seq(V.ServerOS, V.CalleeOS)). As alternativas que são representadas em EBNF pelo símbolo “|”, como está em (‘Lin’ | ‘Sun’ |‘Win’), são definidas na especificação Lua através da função alt, como está expressa em alt( terminal(‘Lin’), terminal(‘Sun’), terminal(‘Win’)). A função
seq é binária, por isso sua representação é feita com uma sequência de dois itens, no caso
da função alt a sua representação é diferente, porque ela é n-ária. Por necessidade de implementação, o nome de cada não-terminal é etiquetado com “G.”, quando aparece na sua definição, e com “V.”, quando é usado na definição de outro não-terminal. Detalhes sobre esta implementação são apresentados em [Hentz, 2010].
Uma vez que a especificação Lua está disponível, é necessário fazer uma configuração manual e só depois essa especificação é passada para o motor de geração, que irá gerar as sentenças. A configuração a ser feita se refere ao símbolo inicial da gramática, que
G.startSymbol = "Call"
G.Call = seq(V.CallerOS, seq(V.ServerOS, V.CalleeOS)) G.CallerOS= alt( terminal("Mac"), terminal("Win"))
G.ServerOS= alt( terminal("Lin"), terminal("Sun"), terminal("Win")) G.CalleeOS= alt( terminal("Mac"), terminal("Win"))
Listagem 3.4: Especificação Lua
precisa ser configurado através do código G.startSymbol = "< StartSymbol >", onde o
< StartSymbol >deve ser substituído pelo símbolo inicial da gramática. A especificação
de entrada para o gerador pode ser visualizada na Listagem 3.4.
No momento da geração, três parâmetros são configurados: (1) o número máximo de recursão para cada símbolo não-terminal da gramática, que determina quantas vezes um não-terminal será repetido recursivamente no processo de geração. Esse parâmetro foi definido na seção 3.1.1, (2) a altura da árvore de derivação. Esse parâmetro foi definido na seção 3.1.1 e o critério de cobertura a ser utilizado na geração. Esse parâmetro foi definido na seção 2.2.2.
Os resultados dos testes serão apresentados em tabelas que contém as seguintes infor- mações:
(1) maxDerivLen representa a altura da árvore de derivação.
(2) Tempo Exec. representa a duração da execução do motor de geração para a
configuração indicada, o tempo segue o formato mm:ss.zz em que mm representa os min- utos, ss os segundos e zz os centésimos de segundos. Se refere ao tempo de processamento da CPU.
(3) C. NT representa a proporção de não-terminais utilizados pelas sentenças ger-
adas. Esta informação será utilizada para traçar uma relação entre a execução apenas com as restrições e a dos critérios de cobertura;
(4) C.Terminais representa o percentual de satisfação do critério de cobertura de
terminais;
(5) C.RP representa o percentual de satisfação do critério de cobertura de regras de
produções;
(6) Num. Sentenças representa o número de sentenças geradas.
Na Tabela 2 são apresentadas as configurações e os resultados obtidos na execução da gramática apenas com as restrições de ciclos e número de passos de derivação. Para esta
gramática todos os não-terminais foram utilizados a partir da execução 1 e o conjunto de sentenças geradas em todas as execuções é idêntico. As sentenças geradas são visualizadas na Tabela 3.
Execução MaxDerivlen Tempo Exec. C.NT C.T erminais C.RP Num.
Sentenças
1 2 0 : 00.01 100% 100% 100% 12
2 3 0 : 00.01 100% 100% 100% 12
3 4 0 : 00.01 100% 100% 100% 12
4 5 0 : 00.01 100% 100% 100% 12
Tabela 2: Resultados da execução da gramática apenas com as restrições de ciclos e número de passos de derivação.
Sentenças T erminais Cobertos Regras de P rodução Cobertas
M ac Lin M ac M ac Lin 1, 2, 4, 7 M ac Lin W in M ac Lin W in 1, 2, 4, 8 M ac Sun M ac M ac Sun 1, 2, 5, 7 M ac Sun W in M ac Sun W in 1, 2, 5, 8 M ac W in M ac M ac W in 1, 2, 6, 7 M ac W in W in M ac W in 1, 2, 6, 8 W in Lin M ac W in Lin M ac 1, 3, 4, 7 W in Lin W in W in Lin 1, 3, 4, 8 W in Sun M ac W in Sun M ac 1, 3, 5, 7 W in Sun W in W in Sun 1, 3, 5, 8 W in W in M ac W in M ac 1, 3, 6, 7 W in W in W in W in 1, 3, 6, 8
TOTAL W in M ac Lin Sun 1...8
Tabela 3: Sentenças geradas apenas com as restrições de ciclos e número de passos de derivação
Utilizando as mesmas configurações anteriores para a execução do gerador, agora fazendo uso do critério de cobertura de terminais, o resultado pode ser visualizado na Tabela 4. O critério de cobertura de terminais foi satisfeito a partir da execução 1. Para esta gramática todos os não-terminais foram utilizados a partir da execução 1. No entanto, foram cobertas apenas 75% das regras de produção. O conjunto de sentenças geradas em todas as execuções é idêntico. Podemos observar uma redução do número de sentenças geradas em relação às execuções utilizando apenas os controles de derivação. As sentenças geradas são visualizadas na Tabela 5.
O último critério de cobertura que utilizamos foi o de regras de produção. Apresen- tamos o seu resultado na Tabela 6. O critério de cobertura de regras de produção foi satisfeito a partir da execução 1. Para esta gramática todos os não-terminais também
Execução MaxDerivlen Tempo Exec. C.NT C.T erminais C.RP Num. Sentenças 1 2 0 : 00.01 100% 100% 75% 3 2 3 0 : 00.01 100% 100% 75% 3 3 4 0 : 00.01 100% 100% 75% 3 4 5 0 : 00.01 100% 100% 75% 3
Tabela 4: Resultados da execução da gramática com o Critério de Cobertura de Terminais
Sentenças geradas T erminais Cobertos Regras de P rodução Cobertas M ac Lin M ac M ac Lin 1, 2, 4, 7
M ac Lin W in M ac Lin W in 1, 2, 4, 8 M ac Sun M ac M ac Sun 1, 2, 5, 7
TOTAL W in M ac Lin Sun 1, 2, 4, 5, 7, 8
Tabela 5: Sentenças Geradas com o Critério de Cobertura de Terminais
foram utilizados a partir da execução 1. O conjunto de sentenças geradas em todas as execuções é idêntico. Também observamos uma redução do número de sentenças geradas em relação às execuções utilizando apenas os controles de derivação. As sentenças geradas são visualizadas na Tabela 7.
Execução MaxDerivlen Tempo Exec. C.NT C.T erminais C.RP Num.
Sentenças
1 2 0 : 00.01 100% 100% 100% 5
2 3 0 : 00.01 100% 100% 100% 5
3 4 0 : 00.01 100% 100% 100% 5
4 5 0 : 00.01 100% 100% 100% 5
Tabela 6: Resultados da execução da gramática com o Critério de Cobertura de Regras de Produção
Sentenças geradas T erminais Cobertos Regras de P rodução Cobertas M ac Lin M ac M ac Lin 1, 2, 4, 7
M ac Lin W in M ac Lin W in 1, 2, 4, 8 M ac Sun M ac M ac Sun 1, 2, 5, 7 M ac W in M ac M ac W in 1, 2, 6, 7 W in Lin M ac W in Lin M ac 1, 3, 4, 7
TOTAL W in M ac Lin Sun 1...8
Tabela 7: Sentenças Geradas com o Critério de Cobertura de Regras de Produção
Como resultado dos testes utilizando a gramática acima, observamos que os critérios de cobertura de terminais e regras de produção foram satisfeitos em 100%. Para os dois casos foi necessária a execução de 2 passos de derivação para a sua satisfação. O número de passos necessários para a maior derivação nesta gramática é 2, assim é justificada a estabilização do processo de geração nas configurações de maxDerivLen em 2, 3, 4 e 5.
Através do uso dos critérios de cobertura foi possível reduzir o número de sentenças geradas em relação ao uso dos controles de derivações. Em relação ao tempo de geração, não houve diferença, isso porque utilizamos uma gramática simples e pequena. Observa- mos também que o número de sentenças que foi gerado varia de acordo com o critério de cobertura utilizado.