Discussion :

[javalhoussain]

Bonjour,

J'aimerais faire un programme qui analyse une chaine de caractère et qui affiche si cette chaine appartient á un grammaire ou non .

Si vous pouvez m aider a savoir comment procéder et structure de données á utiliser pour réaliser veuillez me renseigner merci pour votre aide .

[Ivelios]

Pour vérifier seulement un chaine de caractère tu peux utiliser les expression régulière. ( ici )

Si tu veux faire un compilateur il faut utiliser des librairies externes spécialisées pour ça. antlr par exemple

[javalhoussain]

Bonjour,

Je vous remercie pour ces informations utiles, mais moi je veux partir d'un grammaire pour aboutir á la fin á un compilateur, en utilisant bien sur java comme langage d'implémentation.

si vous pouvez me donner les étapes á suivre et le traitement á faire sur la grammaire pour simplifier analyse descendent.

[Invité]

Salut,

Pour générer un parser à partir d'une grammaire, il faut utiliser un générateur de parser dont l'un d'eux t'a été donné par Ivelios ci dessus. Pour une liste (non exhaustive) et une petite discussion tu peux regarder ici.

Ensuite quand tu as ton parser tu n'as toujours pas ton compilo en entier. Tu peux faire la suite à la main en traversant l'AST produit avec (souvent) un (des) visiteur(s) et créer toutes les choses utiles genre table des symboles et faire tes analyses et transformations différentes.
Tu peux aussi te tourner vers des outils du genre JastAdd si tu veux utiliser des grammaires attribuées pour implémenter ton compilateur.

A plus

[javalhoussain]

Bonjour,

Je vous remercie pour votre aide et soutien j'utilise ANTLRWORKS mais j'ai des problèmes avec ce dernier sous windows, problème de genre : grammaire est recursive .... etc

Si vous connaissez un autre utilitaire gratuit veuillez m'informer, et si quelqu'un peut me donner un exemple déjà qui marche bien sous ANTLR sera le bienvenue.

Merci d'avance .

[Invité]

Antlr c'est une analyse LL(k) donc la récursivité gauche est interdite de par la nature même de l'analyse utilisée.
Donc si tu veux utiliser antlr il va falloir remanier ta grammaire pour le rendre non récursive gauche. C'est pas très dur (algo ci-dessous) mais ça peut rendre ta grammaire plus dur à lire.
Sinon tu peux regarder un autre outil qui accepte des grammaire LALR(1) comme SableCC ou Beaver (et qui, à mon humble avis, sont plus simples d'utilisation que antlr, mais tout ça est une affaire de gout).

Comment transformer une règle récursive gauche en récursive droite
Imagine que tu as une règle du type (notation EBNF)

Code :

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

1
2
 
<A> ::= <A> t1 | <A> t2 | ... | <A> tk | nr1 | ... | nrn

où t1.. tk sont des termes, soit terminaux soit non terminaux et les membres nr1 ... nrn sont non récursifs gauches pour A
Une grammaire équivalente est

Code :

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

1
2
3
 
<A> ::= nr1 <A1> | ... | nrn <A1>
<A1> ::= t1 <A1> | ... | tk <A1> | /\

où /\ est la règle vide.
Les deux régles sont équivalentes mais la lecture de la deuxième est moins aisée.

A plus

[javalhoussain]

Bonjour,

ici vous voyez la grammaire que je suis entrain d'étudier mais je s pas quel modification á faire pour qu'elle soit LL(1):

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
PROGRAMM    := PROGRAMM ident VARDECLLIST FUNCDECLLIST INSTR
VARDECLLIST           := ^| VARDECL ; VARDECLLIST
VARDECL                 := var IDENTLIST ; TYPENAME
IDENTLIST               := ident | ident , IDENTLIST
TYPENAME               := ATOMICTYPE | ARRAYTYPE
ATOMICTYPE            := unit | bool | int 
ARRAYTYPE              := array [RANGELIST] of ATOMICTYPE 
RANGELIST               := int..int | int .. int, RANGELIST
FUNCDECLLIST          := ^ | FUNCDECL ; FUNCDECLLIST
FUNCDECL                := function ident (ARGLIST) : ATOMICTYPE VARDECLLIST INSTR
ARGLIST                  := ^ | ARG | ARG , ARGLIST
ARG                        := ident : TYPENAME| ref ident : TYPENAME 
INSTR                     :=  if EXPR then do INSTR 
                                | if EXPR then do INSTR else INSTR 
				| while EXPR do INSTR 
				| LVALUE :=EXPR 
				| return EXPR 
				| return
				| ident (EXPRLIST)|begin SEQUENCE end | begin end 
SEQUENCE               := INSTR ; SEQUENCE | INSTR ; | INSTR 
LVALUE                   := ident | ident [EXPRLIST]
EXPRLIST                := EXPR | EXPR , EXPRLIST
EXPR                      := cte |(EXPR)|EXPR opb EXPR | opu EXPR | ident (EXPRLIST)| ident [EXPRLIST]

Bon ya pas de chose á modifier mais par exemple la première règle nécessite une modification mais comment ??
Aussi la syntaxe déjà n'est pas accepte par ANTLR notamment le vide (^).Merci de m'aider à avancer dans ce travail .

[Invité]

Salut,

modifier la première règle est facile... il suffit de mettre PROGRAMM à la fin et d'ajouter une alternative vide. De toute façon, là ta grammaire ne peut faire autrement que de ne jamais terminer avec une première règle comme ça...
Mais j'ai des questions :
Tu sembles t'entêter dans antlr, pourquoi pas, mais connais tu la syntaxe ? as-tu lu la documentation ? testé des tutoriels (je pense notamment au quick start accessible facilement depuis la page d'accueil qui couvre le cas de la récursivité gauche et sa solution dans la syntaxe antlr...) ? est-ce le meilleur outil dans ton cas ?

Le code que tu me montres est une description de grammaire qui n'est pas la syntaxe utilisée par antlr, tu devrais lire de la documentation avant de te lancer là dedans.

A plus

[Shotman]

Bonjour,
Pour rebondir sur le post de javalhoussain, j'ai fait une grammaire sous Antlr, généré mon arbre abstrait. On me demande de générer une table des symboles mais je ne sais pas comment ça se fait. Auriez vous un exemple s'il vous plait sur lequel je pourrais m'appuyer.

Je vous remercie.

[Invité]

Une table des symboles c'est tout bête : c'est une table qui à un symbole (son nom souvent) associe des informations sur ce symbole, tel que le type par exemple.
Donc il n'y a rien d'autre à faire que de représenter la table des symboles comme une map hiérarchique. Hiérarchique car dans beaucoup de langage avec scope, il est possible de redéfinir un symbole dans un scope inférieur dans lequel on cherche en priorité avant de déléguer au parent si on ne trouve pas.
Pour remplir cette table, un parcours de ton arbre devrait suffire. Tu crées la hiérarchie au fur et à mesure du parcours.
Je ne connais pas le langage que tu souhaite supporter mais typiquement, on entre dans un nouveau scope quand on parcourt un nouveau package ou namespace, puis une nouvelle classe, puis une nouvelle méthode, puis un nouveau bloc, ...

La gestion de la table des symboles se fait à la main et il n'y a pas d'outil permettant de le faire automatiquement car c'est pas très dur à faire soi même, et la façon dont tu vas le gérer dépend vraiment de ton langage... Des outils tel que JastAdd mettent des outils à disposition qui permettent une implémentation à travers une grammaire attribuée.

Un truc tout simple est:

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
 
public class SymbolTable {
  private SymbolTable parent;
  private Map<String,Info> map;
  public SymbolTable(SymbolTable parent) {
    this.parent = parent;
    map = new HashMap<String, Info>();
  }
  public void addSymbol(String name, Info info) {
    map.put(name, info);
  }
  public Info lookup(String name) {
    Info res = map.get(name);
    if(res == null && parent != null) {
      res = parent.lookup(name);
    }
    return res;
  }
}

Mais bon après tout dépend de ton cas particulier

[javalhoussain]

Bonjour,

Merci pour votre aide mtn je suis arrivé à utiliser antlr mais j ai encore des problèmes avec la grammaire j ai fait quelques modifications mais ya autre chose qui marche plus voila ce que j ai fait :

grammar grammaire;
//PROGRAMM : PROGRAMM 'ident' VARDECLLIST FUNCDECLLIST INSTR;
PROGRAMM : '{'PROGRAMM'ident' VARDECLLIST FUNCDECLLIST INSTR'}';
VARDECLLIST : EOF| VARDECL ';' VARDECLLIST;
VARDECL : 'var' IDENTLIST ';' TYPENAME;
IDENTLIST : 'ident' | 'ident' ',' IDENTLIST;
TYPENAME : ATOMICTYPE | ARRAYTYPE;
ATOMICTYPE : 'unit' | 'bool'
| 'int';
ARRAYTYPE : 'array' '['RANGELIST']' 'of' ATOMICTYPE;
RANGELIST : 'int..int' |' int .. int,' RANGELIST;
FUNCDECLLIST : EOF| FUNCDECL ';' FUNCDECLLIST;
FUNCDECL : 'function ident ('ARGLIST') : 'ATOMICTYPE VARDECLLIST INSTR;
//ARGLIST : EOF| ARG
// | ARG ',' ARGLIST;
ARGLIST : ARG K;
K :','ARGLIST|EOF;
ARG : 'ident :' TYPENAME| 'ref ident :' TYPENAME;
//INSTR : 'if' EXPR 'then do 'INSTR
// | 'if' EXPR 'then do' INSTR ' else' INSTR
// | 'while' EXPR' do' INSTR
// | LVALUE' :='EXPR
// | 'return' EXPR
// | 'return'
// | 'ident ('EXPRLIST')'|'begin' SEQUENCE 'end' | 'begin end';
INSTR : 'if' EXPR 'then do 'INSTR SUITE
| 'while' EXPR' do' INSTR
| LVALUE' :='EXPR
| 'return' X
| 'ident ('EXPRLIST')'|'begin' SEQUENCE 'end' | 'begin end';
SUITE :EOF|' else' INSTR ;
X :EXPR|EOF;
//SEQUENCE : INSTR' ; 'SEQUENCE | INSTR ';'
// | INSTR;
SEQUENCE : INSTR SUIV;
SUIV : ';'SEQUENCE|';'|EOF;

LVALUE : 'ident' | 'ident ['EXPRLIST']';
//EXPRLIST : EXPR | EXPR ',' EXPRLIST;
EXPRLIST : EXPR T;
T :','EXPRLIST |EOF;
EXPR : 'cte' | '('EXPR')'
| R EXPR
| 'ident ('EXPRLIST')'
| 'ident ['EXPRLIST']';
R : 'opb'|'opu';
//EXPR : 'cte' |'('EXPR')'
// | EXPR 'opb' EXPR
// | 'opu' EXPR
// | 'ident ('EXPRLIST')'
// | 'ident ['EXPRLIST']' ('opb' EXPR)*

Si vous avez autre idées veuillez me répondre et merci.Antlr souligne encore des récursivités au niveau de la grammaire .