Reconnaissance de grammaires

**Superne0** · 04/09/2009, 18h45

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**ram-0000** · 04/09/2009, 19h30

Je suppose que lex et yacc (flex et bison) sont interdits ?

**Superne0** · 04/09/2009, 19h47

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 ?

**souviron34** · 04/09/2009, 23h15

euh...

en C les fonctions strchr ou strstr

**ram-0000** · 05/09/2009, 00h59

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.

**Superne0** · 14/09/2009, 20h53

Bonsoir à tous.
Bon évidemment, pas droit d'utiliser Flex/Bison au final

... donc avec les moyens du bord.
Une question :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
ArrayList<String[][]> gramatica;
 
    private int paso = 0;
    ArrayList<String> contenido;
    ArrayList<String> contenidoConv;

en Java est-il équivalent à

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

?
Merci

**Médinoc** · 15/09/2009, 12h25

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

Ça correspondrait plus à ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

**Superne0** · 15/09/2009, 18h26

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

gramatica.add(line)

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

?
Pour ça je ne comprends pas pourquoi 4 astérisques à la déclaration de "gramatica"

**Médinoc** · 15/09/2009, 23h53

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.

**Superne0** · 18/09/2009, 20h01

Salut, quand je déclare dans le programme principal (main)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
char** test
call(test[0])

avec la fonction call

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

void call(char* testl)

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
char**** test
call(test[0][0][0])

avec la fonction call

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

void call(char*** test)

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
test.c: In function ‘main’:
test.c:24: attention : passing argument 1 of ‘addLinea’ from incompatible pointer type

**Médinoc** · 18/09/2009, 20h09

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

**Superne0** · 18/09/2009, 20h21

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Médinoc** · 18/09/2009, 21h01

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++...

**Superne0** · 18/09/2009, 21h12

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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);
}

**Médinoc** · 18/09/2009, 21h18

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)...

**Superne0** · 30/09/2009, 18h28

Projet terminé, merci beaucoup Médinoc

Reconnaissance de grammaires

Générateurs de compilateur

Discussions similaires

Partager

Partager