Comment implémenter Lexical Analysis en version javascript

Salut, merci de lire

Je tente actuellement de faire une calculatrice Google-style. Vous entrez une chaîne, elle détermine si elle peut être calculée et renvoie le résultat.

J'ai commencé lentement avec les bases: + - / * et la gestion des parenthèses.

Je suis prêt à améliorer la calculatrice avec le temps, et après avoir appris un peu l'analyse lexicale, j'ai construit une liste de tokens et des modèles d'expression réguliers associés.

Ce type de travail est facilement applicable avec des langages tels que Lex et Yacc, sauf que je développe une application de Javascript uniquement.

J'ai essayé de transcrire l'idée dans Javascript, mais je ne peux pas comprendre comment gérer tout d'une manière propre et belle, en particulier les parenthèses imbriquées.

Une analyse

Définissons ce qu'est une requête de calculatrice:

 // NON TERMINAL EXPRESSIONS // query -> statement query -> ε // means end of query statement -> statement operator statement statement -> ( statement ) statement -> prefix statement statement -> number number -> integer number -> float // TERMINAL EXPRESSIONS // operator -> [+*/%^-] prefix -> - integer -> [0-9]+ float -> [0-9]+[.,][0-9]+

Javascript

L'analyse Lexique consiste à vérifier qu'il n'y a rien qui ne ressemble à aucune des expressions de terminal: opérateur, préfixes, entier et flotteur. Ce qui peut être raccourci à une expression régulière:

(J'ai ajouté des espaces pour le rendre plus lisible)

 var calcPat = /^ (\s* ( ([+/*%^-]) | ([0-9]+) | ([0-9]+[.,][0-9]+) | (\() | (\)) ) )+ \s* $/;

Si ce test passe, la requête est lisiblement correcte et doit être vérifiée par grammaire pour déterminer si elle peut être calculée. C'est la partie délicate

Je ne vais pas coller le code parce qu'il n'est pas propre ni facile à comprendre, mais je vais expliquer le processus que j'ai suivi et pourquoi je suis coincé:

J'ai créé une méthode appelée isStatement(string) censée s'appeler elle-même récursivement. L'idée principale est de diviser la chaîne en déclarations «potentielles» et de vérifier si elles sont vraiment des déclarations et en forment l'une.
Le processus est le suivant:

-Si les deux premiers jetons sont un nombre suivi d'un opérateur:

-Alors,
– Si le reste n'est qu'un jeton et c'est un nombre:
— Ensuite, c'est une déclaration.
— Sinon, vérifiez si les jetons restants forment une déclaration (appel récursif)

-Else, Si le premier jeton est une parenthèse
– Ensuite, recherchez les parenthèses de clôture correspondantes et vérifiez si ce qui est à l'intérieur est une déclaration (récursivité)
– Vérifiez également s'il y a quelque chose après la fermeture des parenthèses et si elle forme une déclaration lorsqu'elle est associée à la structure des parenthèses.

Quel est le problème ?

Mon problème, c'est que je ne trouve pas de parenthèses adéquates lorsqu'il existe des structures imbriquées. Comment puis je faire ça ? En outre, comme vous le voyez, ce n'est pas un algorithme de vérification de grammaire particulièrement générique et propre. Avez-vous une idée pour améliorer ce modèle?

Merci beaucoup d'avoir pris le temps de tout lire. Gaël

(PS: Comme vous l'avez probablement remarqué, je ne suis pas un locuteur natif anglais! Désolé pour les erreurs et pour tous!)

Vous avez la bonne idée de l'analyse lexicale, mais vous semblez avoir été confus quant à la distinction entre la grammaire symbolique et la grammaire linguistique . Ce sont deux choses différentes.

La grammaire symbolique est l'ensemble des motifs (généralement des expressions régulières) qui décrivent les jetons de la langue à analyser. Les expressions régulières sont des expressions sur un jeu de caractères.
La grammaire de la langue (ou la grammaire cible , je suppose) est la grammaire de la langue que vous souhaitez analyser. Cette grammaire est exprimée en termes de jetons.

Vous ne pouvez pas écrire une expression régulière pour analyser la notation algébrique. Vous ne pouvez tout simplement pas. Vous pouvez écrire une grammaire pour cela, mais ce n'est pas une grammaire régulière . Ce que vous voulez faire, c'est reconnaître des jetons séparés, ce qui, dans votre cas, pourrait être fait avec une expression régulière comme ce que vous avez. L'astuce est que vous n'appliquez pas vraiment cette expression à la phrase globale à analyser. Au lieu de cela, vous souhaitez associer un jeton au point actuel de la phrase.

Maintenant, parce que vous avez des expressions régulières de Javascript pour travailler avec, vous pourriez proposer une expression régulière conçue pour correspondre à une chaîne de jetons. Le truc avec cela trouvera un moyen d'identifier quel jeton a été assorti de la liste des possibilités. Le moteur de regex Javascript peut vous donner des tableaux de groupes, alors peut-être que vous pourriez construire quelque chose en plus.

Edit – J'essaie de déterminer comment créer un (un) générateur de tokenizer à usage général, à partir d'une liste d'expressions régulières distinctes (une pour chaque jeton). C'est peut-être pas très compliqué, et il serait très amusant d'avoir autour.