10:17 Mot de passe oublié ?

1

Je viens de commencer le cours de compilation et on nous demande d'écrire un analyseur lexical pour commencer. J'ai pensé alors réutiliser le petit parseur de regexp incomplet que j'avais fait dans le train et qui n'a jamais servi.
J'ai défini des éléments de base pour analyser un truc tout bête: 
comment = //[^\n]*
kwBegin = begin
integerLitteral = $digit+
symbol = [a-zA-Z_][a-zA-Z0-9_]*
whitespace = (\ |\n)+
digit = [0-9]

Ca se comprend facilement, les symboles précédés d'un $ sont non terminaux. Ca semble une bonne idée tout ça, mettons que je veux lui faire analyser la phrase suivante:
begin 1//fini
Ca fonctionne: 
Found 'begin' (type motBegin)
Found ' ' (type whitespace)
Found '1' (type integer_litteral)
Found '//fini' (type comment)

Par contre ça merde à pas mal de niveaux, par exemple si je fais ceci:
1b
1 est détecté comme un entier puis b comme un symbole, alors qu'en fait c'est lexicalement incorrect. Pareil si j'écris beginthat il va détecter le begin puis le that. Il faudrait je pense avoir un mécanisme de séparation des mots, mais pas pour tous, par exemple une parenthèse n'est pas nécessairement suivie d'un caractère spécial.
Bref je sais pas si je suis sur la bonne voie (déjà) et quelle serait la meilleure solution pour répondre à mon problème.
Bref si vous avez des conseils c'est volontiers smile
avatar
Highway Runners, mon jeu de racing à la Outrun qu'il est sorti le 14 décembre 2016 ! N'hésitez pas à me soutenir :)

https://itunes.apple.com/us/app/highway-runners/id964932741

2

1b, pourquoi il serait lexicalement incorrect?

c'est bien un nombre suivi d'une chaine!

une entrée lexicalement correcte n'est pas forcément syntaxiquement correcte!

x=3y=4 passerait ton analyseur sans difficulté si tu reconnaissais aussi le "="

cette "erreur" n'est pas détectable à ce niveau. elle le sera au niveau syntaxique smile
avatar

3

Hmm ok.
Mais de toute façon c'est faux comme manière de faire, parce que comme je l'ai dit si je mets beginthat il va reconnaître le mot "begin" (réservé) puis that comme identificateur, alors que ça devrait être un seul mot... :/
Ce que je peux faire c'est pour quasi tous les éléments reconnus dire qu'il faut un séparateur à la fin, style: 
motBegin = begin$sep
entier = $chiffre+$sep
sep = [^A-Za-z0-9_]

Mais du coup le séparateur est ajouté (par exemple j'aurai 'begin[espace]'). Alors j'ai rajouté un truc perso à mes regexp, le ! qui dit que le caractère doit être là mais pas mangé.
motBegin = begin$sep!
Mais ça fait lourd et bidouillis, il n'y aurait pas mieux?
avatar
Highway Runners, mon jeu de racing à la Outrun qu'il est sorti le 14 décembre 2016 ! N'hésitez pas à me soutenir :)

https://itunes.apple.com/us/app/highway-runners/id964932741

4

à mon avis pour les mots-clés, le plus simple serait de faire en deux passes :

1 - tu définis une classe "symbole" avec une regexp qui matche tous tes mots-clés, comme "[A-Za-z_][0-9A-Za-z_]*" par exemple
2 - après avoir trouvé un symbole, tu regardes s'il s'agit d'un mot-clé ou bien d'un symbole quelconque

de cette façon, ton lexeur ira toujours "au bout" de son analyse ; quand tu as "beginthat", il ne s'arrêtera pas en plein milieu après "begin" en pensant avoir trouvé un mot-clé
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

5

J'aime bien l'idée smile Merci ^^
avatar
Highway Runners, mon jeu de racing à la Outrun qu'il est sorti le 14 décembre 2016 ! N'hésitez pas à me soutenir :)

https://itunes.apple.com/us/app/highway-runners/id964932741

6

l'idee du separateur vient du probleme que tu fais ca avec des regexp je pense, mais en general, tu aurais:
stmt ::= <sub_stmt_1> [SEP] <sub_stmt_2>
sauf autre cas a preciser ({} etc. pr des grammaires comme C)
avatar

7

STMT? confus
En fait ce que dit Zeph est intelligent parce que si je définis: 
keyword ::= 'begin' | 'truc' | 'chouette'
identifier ::= (minuscule | majuscule | '_') (minuscule | majuscule | nombre | '_')

La grammaire est bêtement ambiguë, puisque "begin" peut se référer à keyword ou identifier... wink
Donc je vais prendre sa solution. J'ai pour l'instant du mal à voir à quel niveau je me situe avec ça, par exemple j'avais commencé à définir des tuples (expr, expr) mais c'est une mauvaise idée on dirait, je pense que c'est plus sage d'assembler les trucs plus tard.
Merci smile
avatar
Highway Runners, mon jeu de racing à la Outrun qu'il est sorti le 14 décembre 2016 ! N'hésitez pas à me soutenir :)

https://itunes.apple.com/us/app/highway-runners/id964932741

8

À mon avis ta solution n'est pas mauvaise, on peut considérer chaque lexème comme étant caractérisé par deux informations :

- Son expression
- Son type (opérateur, identifiant, mot-clé...)

Le traitement se fait alors en deux passes : premièrement la récupération de l'expression, qui peut tout à fait se faire à coups de regexp et qui te permet de récupérer tes lexèmes un à un depuis le code source (à ce niveau-là, tu n'as encore aucune idée de leur type). Ensuite, pour chaque expression ainsi récupérée, tu peux avoir un deuxième mécanisme qui l'analyse pour déterminer son type. Ça n'est qu'au moment de cette seconde étape que la différence entre "aaa" (identifiant) et "begin" (mot-clé) apparaît.

Si tu programmes en objet, tu peux concevoir tout ça avec un superbe "LexemFactory" qui possède une méthode statique prenant une chaine de caractères (l'expression) et retournant le lexème correspondant. Reste à voir ce que ça donne une fois codé, mais sur papier ça me semble plutôt joli ^^
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

9

Zephyr (./4) :
1 - tu définis une classe "symbole" avec une regexp qui matche tous tes mots-clés, comme "[A-Za-z_][0-9A-Za-z_]*" par exemple 2 - après avoir trouvé un symbole, tu regardes s'il s'agit d'un mot-clé ou bien d'un symbole quelconque


C'est la solution adoptée par tous les compilos dont j'ai vu et compris le source, y compris javacc qui prend la liste des mots clés séparément.

stmt = statement = instruction, et encore une fois attention à ne pas confondre parser (grammaire) et lexer (regex).

le lexer sort des lexèmes, il n'a aucune idée de leur signification, de la notions d'instructions, de blocs, etc.
tout ce qu'il connait c'est en général IDENTIFICATEUR, ENTIER et les signes de ponctuation.

nb: par définition une regex ne pourra jamais parser des trucs à blocs imbriqués, on s'en occupe PAS en analyse lexicale.

dans la regex qui reconnait les identifiants, on va en général appeler un code qui cherche cet identifiant dans une table et retourne le code du mot clé si il est trouvé

en pseudo langage ça donnerait

when([a-zA-Z][a-zA-Z0-9]* as token) => {
if listemotsreserves.contains(token) return mot_reserves.getinstance(token)
else return new identifiant(token)
}

avec une liste qui associerait "for" à TOKEN_FOR, "if" à TOKEN_IF, etc

je suis sans doute très dur à comprendre mais

tl;dr:
les mots clés et les identifiants sont reconnus par la même regex, et on fait la différence après.
avatar

10

je sais pas pourquoi tu enfonces autant de portes ouvertes, mais personne n'a parlé de confusion entre lexeur et parseur dans ce topic ? il était juste question de décomposer la reconnaissance des lexèmes, comme le suggère pourtant très bien le titre confus
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

11

nEUrOO (./6) :
l'idee du separateur vient du probleme que tu fais ca avec des regexp je pense, mais en general, tu aurais:
stmt ::= [SEP] sauf autre cas a preciser ({} etc. pr des grammaires comme C)

Brunni (./7) :
La grammaire est bêtement ambiguë,


avatar

12

ah ok, au temps pour moi (mais je ne trouve quand même pas que ton intervention apporte grand chose grin)
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

13

(certes, j'ai juste repris ce que t'as dit pour mieux le confirmer)
avatar

14

ah bah alors justement, il y a bien confusion : à aucun moment je n'ai parlé de grammaire ^^
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

15

oué, bon, bref, le but de mon post était de crayonner
squalyl (./9) :
Zephyr (./4) :
1 - tu définis une classe "symbole" avec une regexp qui matche tous tes mots-clés, comme "[A-Za-z_][0-9A-Za-z_]*" par exemple 2 - après avoir trouvé un symbole, tu regardes s'il s'agit d'un mot-clé ou bien d'un symbole quelconque


mais après je suis parti dans les détails embarrassed
avatar

16

("un petit pencil vaut mieux qu'un long discours")
avatar
— Zeroblog —

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

17

squalyl (./11) :
nEUrOO (./6) :
l'idee du separateur vient du probleme que tu fais ca avec des regexp je pense, mais en general, tu aurais:
stmt ::= [SEP] sauf autre cas a preciser ({} etc. pr des grammaires comme C)

Brunni (./7) :
La grammaire est bêtement ambiguë,

Hum c'est une confusion de ma part. Je me rappelle avoir eu des problèmes similaires en traitant de la grammaire avec EBNF. En fait là je suis juste à un niveau en-dessous si je comprends bien (quoique EBNF permettant de définir des terminaux ainsi que la grammaire... sorry). Mais bon niveau terminologie c'est bien de me reprendre, parce que vois les concepts mais j'ai de la peine à faire des recherches si les termes que j'utilise sont incorrects :/
Bon sinon c'est comme ça que j'ai fait smile A la deuxième passe je vire les commentaires, les whitespaces et autres par la même occasion, c'est pratique hehe
avatar
Highway Runners, mon jeu de racing à la Outrun qu'il est sorti le 14 décembre 2016 ! N'hésitez pas à me soutenir :)

https://itunes.apple.com/us/app/highway-runners/id964932741
Aide Charte Contacts Crédits Réalisé avec yAronet 47 ms