Reconnaissance de grammaires

Version imprimable

Bonjour à tous,
Sur un projet de reconnaissance de grammaires (type 0, 1, 2, ou 3; lié à la compilation), je dispose de fichiers textes qu'il faut ouvrir puis analyser.
Les fichiers sont de la forme

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
S ::= a A | a B
 
A ::= a C | a D  |  a E
 
B ::= a D | a C | a E | a F
 
C ::= c 
 
D ::= d 
 
E ::= e 
 
F ::= a | a B

ou encore

Code:

1
2
3
S ::= aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
 
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ::= b

Mon problème n'est pas (pour l'instant) les algoritmes de reconnaissance de chaque grammaire, mais plutôt de savoir comment faire pour stocker chaque caractère à gauche des ::=, puis chaque combinaison de droite, séparées par les | pour pouvoir ensuite les réutiliser dans le programme.

Si quelqu'un a ne serait-ce qu'un soupçon d'idée là-dessus, je suis preneur ;)
Merci beaucoup.

04/09/2009, 19h30
ram-0000

Je suppose que lex et yacc (flex et bison) sont interdits ?
04/09/2009, 19h47
Superne0

Non, rien n'est interdit !
Par contre c'est la 1ere fois que j'entends parler de Flex/Bison.
Ce sont des librairies associées à C ?
04/09/2009, 23h15
souviron34

euh...

en C les fonctions strchr ou strstr
05/09/2009, 00h59
ram-0000

Citation:

Envoyé par Superne0

Non, rien n'est interdit !
Par contre c'est la 1ere fois que j'entends parler de Flex/Bison.
Ce sont des librairies associées à C ?

Flex et bison sont 2 utilitaires plutôt issus du monde Unix qui permettent de générer des analyseurs lexicographiques (reconnaissance de mot clés) et syntaxiques (combinaison des mots clés entre eux).

A partir d'une spécification de grammaire qui ressemble étrangement à ce que tu as donné, ils génère du code C ou C++ qui sait analyser un flux et dire si ce flux est conforme à la grammaire donnée.

Bonsoir à tous.
Bon évidemment, pas droit d'utiliser Flex/Bison au final :( ... donc avec les moyens du bord.
Une question :
Code:

1 2 3 4 5 ArrayList<String[][]> gramatica; private int paso = 0; ArrayList<String> contenido; ArrayList<String> contenidoConv;
en Java est-il équivalent à
Code:

1 2 3 4 5 6 struct gramatica{ int paso; char* conten; char* conten_conv; struct gramatica *next; };
en C, ou bien plus simplement
Code:

1 2 3 4 char** gramatica; int paso = 0; char* contenido; char* contenidoConv;
?
Merci

@Superne0: Sûrement pas le premier, qui correspondrait à une liste chaînée.

Ça correspondrait plus à ceci:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct StringArray
{
	char **pStrings;
	size_t arrayLength;
};
 
struct StringArrayArray
{
	struct StringArray * pStringArrays;
	size_t arrayLength;
};
 
struct ArrayList_StringArrayArray
{
	struct StringArray* pStringArrayArrays;
	size_t listCapacity;
	size_t listLength;
};
 
struct ArrayList_String
{
	char ** pStrings;
	size_t listCapacity;
	size_t listLength;
};
 
...
ArrayList_StringArrayArray gramatica;
int paso = 0;
ArrayList_String contenido;
ArrayList_String contenidoConv;

Ou, si tu préfères "plus simple":

Code:

1
2
3
4
char * ** * gramatica; /* oui, quatre astérisques (!!) */
int paso = 0;
char ** contenido;
char ** contenidoConv;

PS: Je suppose que tu n'as pas droit au C++ non plus?

15/09/2009, 18h26
Superne0

Non, juste du C a éxécuté en ligne de commande.
Pourquoi 4 astérisques ?
Je dispose du code source en Java (en gros je dois faire de la traduction vers C :S), et à un moment donné j'éxécute

Code:

gramatica.add(line)

, où line est un String [ ][ ] (en Java).
Donc l'équivalent en C ne serait-il pas

Code:

&gramatica = &line, avec char** gramatica et char** line

?
Pour ça je ne comprends pas pourquoi 4 astérisques à la déclaration de "gramatica"
15/09/2009, 23h53
Médinoc

Quatre astérisques, parce que tu as une liste de tableaux de tableaux de chaînes de caractères.

Autrement dit, une liste de tableaux de tableaux de tableaux de char.
18/09/2009, 20h01
Superne0
Salut, quand je déclare dans le programme principal (main)
Code:

1 2 char** test call(test[0])
avec la fonction call

Code:

void call(char* testl)

cela fonctionne parfaitement.
Par contre, quand je mets dans le main
Code:

1 2 char**** test call(test[0][0][0])
avec la fonction call

Code:

void call(char*** test)

cela ne fonctionne pas.
Voici l'unique erreur que me renvoit le terminal :
Code:

1 2 test.c: In function ‘main’: test.c:24: attention : passing argument 1 of ‘addLinea’ from incompatible pointer type
18/09/2009, 20h09
Médinoc

C'est parce qu'il faut juste passer test[0].

en passant test[0], j'obtiens le résultat suivant dans le terminal :
Code:

1 2 3 4 5 6 7 8 9 test.c: In function ‘main’: test.c:24: attention : passing argument 1 of ‘addLinea’ from incompatible pointer type et quand j'éxécute : r r r Erreur de segmentation

18/09/2009, 21h01
Médinoc

Si ce n'est pas initialisé, c'est normal.

C n'est pas java. Si tu veux avoir une chance de ne pas laisser ta santé mentale là-dedans, tu aurais plutôt intéret à y aller en C++...

Pas mal le coup de la santé mentale, mais c'est vrai que ça prend la tête !
Sinon, voici le code test que j'essaye de faire fonctionner :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
void call(char*** test){
	int i,j,k;
	for(i=0;i<=2;i++){
		for(j=0;j<=2;j++){
			for(k=0;k<=2;k++){
				test[i][j][k] = 'r';
				printf("%c\n",test[i][j][k]);
			}
		}
	}
}
 
 
int main() {
	int i,j,k;
	char test[2][2][2][2];
	//for(i=0;i<3;i++){	
	//	for(j=0;j<3;j++){
	//		for(k=0;k<3;k++){
				call(test[0]);
	//		}
	//	}
	//}
	return(0);
}

18/09/2009, 21h18
Médinoc

Conseil: Utilise plutôt les structures que je t'aies montrées, ça sera plus facile à gérer et à relire.
N'oublie pas que le C ne fait pas de gestion automatique de la mémoire, et ne mémorise pas lui-même la taille des tableaux alloués (du moins, pas de manière accessible)...
30/09/2009, 18h28
Superne0

Projet terminé, merci beaucoup Médinoc ;)