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 .