IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

programmer une grammaire!


Sujet :

Algorithmes et structures de données

  1. #1
    Inactif
    Inscrit en
    Janvier 2007
    Messages
    98
    Détails du profil
    Informations personnelles :
    Âge : 37

    Informations forums :
    Inscription : Janvier 2007
    Messages : 98
    Points : 70
    Points
    70
    Par défaut programmer une grammaire!
    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

  2. #2
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    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.
    Je ne répondrai à aucune question technique en privé

  3. #3
    Inactif
    Inscrit en
    Janvier 2007
    Messages
    98
    Détails du profil
    Informations personnelles :
    Âge : 37

    Informations forums :
    Inscription : Janvier 2007
    Messages : 98
    Points : 70
    Points
    70
    Par défaut
    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

  4. #4
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    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.
    Je ne répondrai à aucune question technique en privé

  5. #5
    Inactif
    Inscrit en
    Janvier 2007
    Messages
    98
    Détails du profil
    Informations personnelles :
    Âge : 37

    Informations forums :
    Inscription : Janvier 2007
    Messages : 98
    Points : 70
    Points
    70
    Par défaut
    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 voila je sais plus par ou commencer

  6. #6
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    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)
    Je ne répondrai à aucune question technique en privé

  7. #7
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 76
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut Prolog
    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 : 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
    n article <1991Apr23.140427.5416@iecc.cambridge.ma.us> elk@cblpn.att.com (Edwin Lewis King +1 614 860 3394) writes:
    >I'm interesting in generating strings that are described by a BNF (OK,
    >YACC) grammar.
     
    How proficient are you in Prolog? Prolog is a very nice environment to
    do this sort of thing.
     
    I recently took a bnf specification (written in prolog) of an intermediate
    language an modified it to be a generator for the same language. The
    specification was an executable program which succeeded iff the input was
    in the language given by the bnf. It was a simple matter to replace a few
    low level test rules such as
    register(r(I)) :- integer(I).
    with generators such as
    register(r(0)).
    register(r(1)).
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  8. #8
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    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
    Je ne répondrai à aucune question technique en privé

  9. #9
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Points : 6 486
    Points
    6 486
    Par défaut
    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)

  10. #10
    Inactif
    Inscrit en
    Janvier 2007
    Messages
    98
    Détails du profil
    Informations personnelles :
    Âge : 37

    Informations forums :
    Inscription : Janvier 2007
    Messages : 98
    Points : 70
    Points
    70
    Par défaut Merci Promu@ld
    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!

Discussions similaires

  1. Programmer un analyseur syntaxique pour une grammaire donnée
    Par mohamed seddik dans le forum Débuter
    Réponses: 10
    Dernier message: 25/01/2009, 13h28
  2. Programmer une boucle de saisie chaine de caractère.
    Par Spike Spiegel dans le forum C
    Réponses: 30
    Dernier message: 02/10/2005, 18h46
  3. Programmer une attente de quelques secondes
    Par themust dans le forum Assembleur
    Réponses: 1
    Dernier message: 07/12/2004, 15h37
  4. Programmer une pause brève
    Par NeoMan dans le forum Assembleur
    Réponses: 14
    Dernier message: 28/04/2003, 02h59
  5. comment programmer une progressbar
    Par Choucas dans le forum Paradox
    Réponses: 3
    Dernier message: 13/11/2002, 12h07

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo