85 lines
2.8 KiB
C
85 lines
2.8 KiB
C
|
#include "nfa_mccluskey.h"
|
||
|
|
|
||
|
|
#include <stdio.h>
|
||
|
|
|
||
|
|
#include "regexp.h"
|
||
|
|
|
||
|
|
mccluskey_auto *nfa_to_mccluskey(nfa *thenfa) {
|
||
|
|
uint n = thenfa->trans->size_graph;
|
||
|
|
|
||
|
|
mccluskey_auto *mccluskey =
|
||
|
|
(mccluskey_auto *)malloc(sizeof(mccluskey_auto));
|
||
|
|
mccluskey->size = n + 2;
|
||
|
|
mccluskey->matrix = (regexp ***)malloc(mccluskey->size * sizeof(regexp **));
|
||
|
|
|
||
|
|
for (uint i = 0; i < mccluskey->size; i++) {
|
||
|
|
mccluskey->matrix[i] =
|
||
|
|
(regexp **)malloc(mccluskey->size * sizeof(regexp *));
|
||
|
|
for (uint j = 0; j < mccluskey->size; j++)
|
||
|
|
mccluskey->matrix[i][j] = NULL;
|
||
|
|
}
|
||
|
|
for (uint q = 0; q < n; q++) {
|
||
|
|
for (uint a = 0; a < thenfa->trans->size_alpha; a++) {
|
||
|
|
dequeue *transitions = thenfa->trans->edges[q][a];
|
||
|
|
for (uint k = 0; k < size_dequeue(transitions); k++) {
|
||
|
|
uint r = lefread_dequeue(transitions, k);
|
||
|
|
mccluskey->matrix[q + 2][r + 2] =
|
||
|
|
reg_letter(thenfa->alpha_names[a]);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
for (uint i = 0; i < size_dequeue(thenfa->initials); i++) {
|
||
|
|
uint initial_state = lefread_dequeue(thenfa->initials, i);
|
||
|
|
mccluskey->matrix[0][initial_state + 2] = reg_epsilon();
|
||
|
|
}
|
||
|
|
|
||
|
|
for (uint i = 0; i < size_dequeue(thenfa->finals); i++) {
|
||
|
|
uint final_state = lefread_dequeue(thenfa->finals, i);
|
||
|
|
mccluskey->matrix[final_state + 2][1] = reg_epsilon();
|
||
|
|
}
|
||
|
|
|
||
|
|
return mccluskey;
|
||
|
|
}
|
||
|
|
|
||
|
|
regexp *nfa_mccluskey(nfa *thenfa) {
|
||
|
|
mccluskey_auto *gen_auto = nfa_to_mccluskey(thenfa);
|
||
|
|
uint n = gen_auto->size;
|
||
|
|
regexp ***matrix = gen_auto->matrix;
|
||
|
|
|
||
|
|
for (uint k = 2; k < n; ++k) {
|
||
|
|
for (uint i = 0; i < n; ++i) {
|
||
|
|
for (uint j = 0; j < n; ++j) {
|
||
|
|
if (matrix[i][k] != NULL && matrix[k][j] != NULL) {
|
||
|
|
regexp *new_expr;
|
||
|
|
// Gestion des étoiles
|
||
|
|
if (matrix[k][k] != NULL && i == j && i == k && j == k) {
|
||
|
|
new_expr = reg_star(matrix[k][k]);
|
||
|
|
}
|
||
|
|
// Gestions des concaténations
|
||
|
|
else if (matrix[k][k] == NULL ||
|
||
|
|
(matrix[k][k] != NULL && i != j && i == k)) {
|
||
|
|
new_expr = reg_concat(matrix[i][k], matrix[k][j]);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Gestion des unions
|
||
|
|
if (matrix[i][j] != NULL && matrix[k][k] == NULL) {
|
||
|
|
new_expr = reg_union(matrix[i][j], new_expr);
|
||
|
|
}
|
||
|
|
|
||
|
|
matrix[i][j] = new_expr;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
regexp *final_regexp = matrix[0][1];
|
||
|
|
|
||
|
|
for (uint i = 0; i < n; ++i)
|
||
|
|
if (matrix[i] != NULL) free(matrix[i]);
|
||
|
|
|
||
|
|
if (matrix != NULL) free(matrix);
|
||
|
|
if (gen_auto != NULL) free(gen_auto);
|
||
|
|
|
||
|
|
return final_regexp;
|
||
|
|
}
|