Version imprimable
bonjour tout le monde voila j'ai un petit probléme et je sais pas par ou commencer a le resoudre on nous a demander de faire un prgramme a qui on introduit n'importe quelle grammaire et un mot alors le pgm doit nous repondre si ce mot appartient a cette grammaire ou pas.voila essayez de m'initier svp! au moins le debut!
voila merci pour vos contributions
Bonjour et bienvenue sur le forum de developpez.com.
Ca dépend à quel point tu souhaites réaliser la chose. Si tu veux réaliser cela rapidement, je te conseilles d'utiliser le couple LEX/Yacc (ou Flex/Bison) qui sont respectivement un analyseur lexical et un analyseur syntaxique.
merci bien!
ben moi je crois que je veux progrmmer un analyseur syntaxique c'est a dire j'introduis une grammaire quelconque et un mot quelconque aussi et le role de ce programme (analyseur syntaxique) de nous dire si ce mot appartient a cette grammaire ou pas!
je sais pas si j'etais plus clair ou pas en tout cas une chose et sur on utilse pas le Flex
Donc, tu ne souhaites utiliser aucune bibliothèque externe pour t'aider dans ta tâche ?
Dans ce cas, c'est plus compliqué, il faut implémenter des automates normaux pour l'analyse lexical et des automates à piles pour l'analyse syntaxique. Cette partie est difficile, il y a plein de cas à gérer (par exemple si la grammaire est récursive à gauche dans le cas d'une analyse LL), et construire la table d'analyse prédictive.
Lex et Yacc te construisent directement tout ça avec une grammaire donnée.
que voulez vous dire par bibliothéque externe ??MAIIS je vais encore simplifier on introduit une grammaire de type LL(1); et qui n'est pass recursive a gauche et qui est factorisée on a pas ce probléme ensuite il suffit juste de calculer l'ensemble des premiers et suivant aprés la table d'analyse...etc mais moi j'hésite toujours sur la structure de donnée que je dois utilser pour la grammaire te pour le mot que j'introduit :roll: voila je sais plus par ou commencer
En fait, il me semble qu'une analyse LL n'est pas super pratique pour générer automatiquement des analyseurs syntaxiques. Et que la technique LR(1) était plus pratique (en utilisant un automate shift-reduce)
Ce n'est pas ma spécialité mais, je sais que si l'ensemble des règles est raisonnable, prolog peut s'acquitter très bien de cette tâche. Ce post, excusez en anglais, confirme mon allégation.
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
En fait, le post provenait du forum C (je l'ai déplacé ici car il demandait plutôt un algorithme ou une implémentation générale, plutôt qu'une question spécifique au C).
Je pense qu'il souhaite plutôt une implémentation de type langage impératif (ou objet) que logique ;)
Mais ça reste intéressant de savoir que c'est aisément réalisable en prolog ;)
En fait pour réaliser une grammaire, tu as plusieurs solutions.
Si elle est LL(1) comme tu le dis, un automate à pile devrait suffire. Si ta grammaire n'est pas trop compliquée (ETN par ex), tu peux utiliser des fonctions récursives.
A mon avis, la solution la plus facile est l'automate à pile. Tu calcules les ensembles FIRST et FOLLOW, ensuite tu construis ta table d'action et tu traite token par token (j'ai considéré que tu ne faisais que l'analyse syntaxique et que la lexicale était faîte)
voila c'est a peu prés ce que je veux faire c'est correct mais pour commencer mon algorithme faut d'abord que je trouve la bonne strucure de données pour la grammaire que je vais introduire et pour le mot que je vais introduire aussi j'ai pensé a un arbre planaire mais que je vais représenter avec liste chainée a 2 dimensions ce qui n'est pas facile a gerer alors je me damandais si vous n'auriez pas une autre idée pour la structure et pour le langage ça sera peut étre en pascal ou C je métrise que ça pour le moment!