π
<-
Chat plein-écran
[^]

Analyse lexicale et syntaxique -nouveau langage oncalc ti83p

Assembleur, Axe, C/C++, ICE...

Analyse lexicale et syntaxique -nouveau langage oncalc ti83p

Unread postby newprog_creator » 04 Sep 2021, 18:36

Bonjour à la communauté ti,
Par le passé, j'ai déjà créer un langage de programmation qui s'appelle Newprog (Ti89).
Je reviens dans ce forum pour poser une question assez pointue. Je m'intéresse à créer un langage de programmation sur ti83pce ou sur nspire cx qui serait pour commencer interprété (en byte code type java, python ou Newprog sur ti89). Je souhaiterai que le code de ce nouveau langage de programmation soit codé en texte pur (par exemple, l'instruction 'for' codée en 3 lettres) et non pas en utilisant les mots clés prédéfinis.
Pour la TI83pce, je connais bien le fameux ICE Compiler, très bien par ailleurs, mais qui est pour moi trop rigide dans l'écriture de ses expressions. Je souhaiterai un langage permettant la saisie de commande plus complexes et élégantes à la manière de tout langage évolué (c, tibasic (ti89))
Pour le langage Newprog, je n'ai pas eu a coder un lexer/parser car j'utilisais celui du Tibasic de l'os de la calculatrice ti89. Mais sur ti83pce, je ne peux pas car la calculatrice ne fonctionne pas de la même manière.
Pour combler ce manque, je me suis mis à la tâche pour tenter de coder ces fonctionnalités. Il m'était impossible d'utiliser les lexers parsers du monde pc (type lex bison) car il ne peuvent pas être utilisés avec les compilateurs c des calculatrices. Il existe bien celui codé sur visual basic v6 par kevin koffler mais il m'est impossible de le traduire en langage c (visual basic v6 trop vieux pour trouver des convertisseurs de langages). Alors j'ai codé un lexeur ce qui n'a pas été trop compliqué mais je bloque durablement sur le parser. C'est une tâche très ardue et je ne trouve pas de code source c le codant de a à z (cad sans bison par exemple).
Quelqu'un pourrait t-il me donner des infos pour coder ce parser ?
Je sais c"est très pointu...
Merci par avance
User avatar
newprog_creator
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 17.2%
 
Posts: 49
Joined: 29 Mar 2014, 19:07
Gender: Not specified
Calculator(s):
Class: bac+13

Re: Analyse lexicale et syntaxique -nouveau langage oncalc t

Unread postby Bisam » 05 Sep 2021, 10:00

As-tu déjà établi une grammaire du langage ?
Sais-tu déjà comment tu vas représenter les différents éléments de ton arbre de syntaxe abstraite ? ainsi que l'arbre lui-même ?
User avatar
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Level up: 67.4%
 
Posts: 5604
Joined: 11 Mar 2008, 00:00
Location: Lyon
Gender: Male
Calculator(s):

Re: Analyse lexicale et syntaxique -nouveau langage oncalc t

Unread postby newprog_creator » 05 Sep 2021, 11:57

Merci pour la réponse.
Je souhaiterai utiliser la même grammaire que le tibasic de la ti89 avec en plus quelques emprunts au c tels que les opérateurs suivants :
=(affectation) == < > <= >=
<< >> ++ -- += -= *= /=
Ces opérateurs ascii permettraient de pouvoir coder sur pc directement dans le bloc note.

Pour l'arbre, je souhaite le même que celui utilisé par le tibasic de la ti89 également.
Merci pour votre aide
User avatar
newprog_creator
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 17.2%
 
Posts: 49
Joined: 29 Mar 2014, 19:07
Gender: Not specified
Calculator(s):
Class: bac+13

Re: Analyse lexicale et syntaxique -nouveau langage oncalc t

Unread postby Bisam » 05 Sep 2021, 13:34

En fait, je me demandais si tu avais fait un travail plus approfondi à ce sujet.

Pour ce qui est de la grammaire :
  • Quelles sont les types d'unités lexicales ? Quels types parmi ceux-ci constituent des classes fermées ? ouvertes ?
  • Quels sont les délimiteurs ?
  • Quelles sont les règles permettant de retrouver les syntagmes à partir des unités lexicales ?

Pour ce qui est de la représentation de l'AST :
  • Quel langage vas-tu utiliser pour interpréter ?
  • Dans ce langage, as-tu besoin de gérer la mémoire "à la main" ?
  • Dans ce langage, quels sont les types d'objets que tu vas utiliser pour représenter les lexèmes ? les syntagmes ?
  • Vas-tu interpréter "à la volée", ou bien vas-tu d'abord construire la totalité de l'arbre puis interpréter l'arbre ?

On ne peut pas répondre à toutes ces questions à ta place.
Je te conseille de lire des cours de compilation, d'analyse lexicale et syntaxique en informatique, par exemple celui-ci, même s'il est un peu "vieux".
User avatar
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Level up: 67.4%
 
Posts: 5604
Joined: 11 Mar 2008, 00:00
Location: Lyon
Gender: Male
Calculator(s):

Re: Analyse lexicale et syntaxique -nouveau langage oncalc t

Unread postby newprog_creator » 05 Sep 2021, 14:50

Pour les trois premières questions, la réponse est idem tibasic ti68k.
Dans l'idéal, je souhaiterai la même chose que ce que faisait "tokens ocx" de Kevin kofler mais qui soit en langage c pour pouvoir être exécuté oncalc (et non en visual basic 6). L'ajout des opérateurs ascii cités plus hauts serait un plus.
Pour informations, le compilateur Newprog se basait sur l'arbre tibasic et le modifiait plutôt légèrement pour gagner en temps d'exécution.
Pour les quatres dernières questions :
-Toujours comme en Newprog, le langage d'interprétation est le c
-La mémoire sera toujours gérée à la main
-Idem tibasic
-L'arbre est créé en totalité avant exécution

J'ai pris connaissance du cours que tu m'as transmis. Je me sens pas capable d'ingérer tant d'informations. J'ai bien peur du coup que si je fasse le fasse moi même, j'abandonne le projet. L'idéal serait de s'inspirer de travaux déjà réalisés s'inspirant du tibasic ti68k, mais je n'en ai pas trouvé sur internet (par contre j'en ai vu pour le tibasic ti83).
Ca s'avère très compliqué.... :-(
User avatar
newprog_creator
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 17.2%
 
Posts: 49
Joined: 29 Mar 2014, 19:07
Gender: Not specified
Calculator(s):
Class: bac+13

Re: Analyse lexicale et syntaxique -nouveau langage oncalc t

Unread postby newprog_creator » 13 Sep 2021, 21:00

Je déterre le fil.

Je reviens vers vous car je crois que j'ai trouvé une solution qui me permettrait de résoudre en grande partie mon problème.
J'ai trouvé que l'algorithme de shunting-yard est assez simple à implémenter et pourrait me convenir (avec quelques ajustements). D'ailleurs c'est l'algorithme utilisé par l'axe parser.
Un arbre postfix ainsi généré (ou rpn si j'ai bien compris) me suffirait comme base pour mon nouveau langage.
J'ai trouvé sur wikipédia l'algorithme (qui permet l'utilisation de fonctions, ce qui est indispensable pour mon projet), le voici recopié :

tant qu’il y a des tokens à lire :
lire le token.
si c’est un nombre l’ajouter à la sortie.
si c'est une fonction, le mettre sur la pile.
si c'est un séparateur d'arguments de fonction (par exemple une virgule) :
jusqu'à ce que l'élément au sommet de la pile soit une parenthèse gauche, retirer l'élément du sommet de la pile et l'ajouter à la sortie. Si toute la pile est dépilée sans trouver de parenthèse gauche, c’est qu’il y a un mauvais parenthésage.
si c’est un opérateur o1 alors
1) tant qu’il y a un opérateur o2 sur le haut de la pile et si l’une des conditions suivantes est remplie.
o1 est associatif ou associatif à gauche et sa priorité est inférieure ou égale à celle d’o2, ou
o1 est associatif à droite et sa priorité est inférieure à celle d’o2,
retirer o2 de la pile pour le mettre dans la sortie
2) mettre o1 sur la pile
si le token est une parenthèse gauche, le mettre sur la pile.
si le token est une parenthèse droite, alors dépiler les opérateurs et les mettre dans la sortie jusqu’à la parenthèse gauche qui elle aussi sera dépilée, mais pas mise dans la sortie. Après cela, si le token au sommet de la pile est une fonction, le dépiler également pour l'ajouter à la sortie. Si toute la pile est dépilée sans trouver de parenthèse gauche c’est qu’il y a un mauvais parenthésage.
après la lecture du dernier token, s'il reste des éléments dans la pile il faut tous les dépiler pour les mettre dans la sortie (il ne doit y avoir que des opérateurs. Si on trouve une parenthèse gauche alors il y a eu un mauvais parenthésage).

Il y a un point que je ne parviens pas à comprendre. Ce point doit pourtant être trivial car personne sur le net ne l'explique. Ce sont les termes "opérateurs o1 et o2". Quels sont les différences entre les deux ?
Je pense que quelqu'un d'aviser pourra facilement me répondre.
Merci par avance...
User avatar
newprog_creator
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 17.2%
 
Posts: 49
Joined: 29 Mar 2014, 19:07
Gender: Not specified
Calculator(s):
Class: bac+13

Re: Analyse lexicale et syntaxique -nouveau langage oncalc t

Unread postby SlyVTT » 13 Sep 2021, 22:21

o1 et o2 sont des opérateurs quelconques , par exemple addition + ou division /.
Il faut donc analyser leur priorisation

C'est un défaut de traduction, regarde cet article en anglais qui me semble plus limpide : https://brilliant.org/wiki/shunting-yard-algorithm/
Developing the GUI Toolkit for nSpire
see current revision here : https://github.com/SlyVTT/Widget-for-TI-NSpire

And for the GUI Toolkit NF (New Foundation), this is here https://github.com/SlyVTT/Widgets-Spire-NF

Image Image Image Image
User avatar
SlyVTTPremium
Niveau 11: LV (Légende Vivante)
Niveau 11: LV (Légende Vivante)
Level up: 3.7%
 
Posts: 226
Images: 0
Joined: 19 Jan 2021, 09:41
Gender: Male
Calculator(s):

Re: Analyse lexicale et syntaxique -nouveau langage oncalc t

Unread postby rentech7289 » 15 Sep 2021, 17:22

Ce point doit pourtant être trivial car personne sur le net ne l'explique. Ce sont les termes "opérateurs o1 et o2". Quels sont les différences entre les deux ?

La différence est l'ordre de priorité entre les opérateurs et les différentes fonctions disponibles. Il s'agit de décomposer une formule de calcul en un arbre logique respectant celles-ci, puis de le traduire en une formule linéaire directement calculable par la machine. C'est la traduction informatique de la façon scolaire de décomposer un calcul en une suite d'opérations. Dans la NPI, la différence étant que les opérateurs viennent après les variables.
https://fr.wikipedia.org/wiki/Notations_infix%C3%A9e,_pr%C3%A9fix%C3%A9e,_polonaise_et_postfix%C3%A9e
La section Analogue en langage naturel de la la partie Notation postfixée illustre mieux ce principe que l'Illustration de l'algorithme de la page https://fr.wikipedia.org/wiki/Algorithme_Shunting-yard.
User avatar
rentech7289
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 66.4%
 
Posts: 107
Joined: 16 Aug 2021, 02:40
Location: Lorraine luxembourgeoise
Gender: Male
Calculator(s):

Re: Analyse lexicale et syntaxique -nouveau langage oncalc t

Unread postby newprog_creator » 18 Sep 2021, 16:48

Merci pour la réponse avec un peu de retard.
J'ai codé l'algorithme de shunting-yard d'après les instructions suivantes :
Code: Select all
While there are tokens to be read:
        Read a token
        If it's a number add it to queue
        If it's an operator
               While there's an operator on the top of the stack with greater precedence:
                       Pop operators from the stack onto the output queue
               Push the current operator onto the stack
        If it's a left bracket push it onto the stack
        If it's a right bracket
            While there's not a left bracket at the top of the stack:
                     Pop operators from the stack onto the output queue.
             Pop the left bracket from the stack and discard it
While there are operators on the stack, pop them to the queue


Voci le code :

Code: Select all
uint8_t shuntingYard(void)
{
    Stack queue_stack,operator_stack; //Queue_stack pour les nombre, operator_stack pour les opérateurs
    uint8_t *ptr_lexer,*ptr_parser,o1,o2,*temp_token_ptr;   
    //parser is the output, lexer is the enter
    ptr_lexer=output_lexer_tokens;
    ptr_parser=output_parser_tokens;
    parser_size=0;  //in bytes
    while(ptr_lexer<output_lexer_tokens+lexer_size)
    {
        if(is_number_token(ptr_lexer))
        {
            ptr_parser=push_value(get_value_no_isz(ptr_lexer),ptr_parser,&parser_size);
        }
        if(is_operator_token(ptr_lexer))
        {
            o1=*ptr_lexer;
            while(operator_stack.nb_elem>0 && is_operator_token(get_top_stack_without_poping(&operator_stack)) && op_priority[*get_top_stack_without_poping(&operator_stack)]>op_priority[o1])
            {
                ptr_parser=push_quantum(*pop_Stack(&operator_stack),ptr_parser,&parser_size);
            }
            push_Stack(&operator_stack,ptr_lexer);
        }
        if(*ptr_lexer==parenthesis_open_tag)
        {
            push_Stack(&operator_stack,ptr_lexer);
        }
        if(*ptr_lexer==parenthesis_close_tag)
        {
            while(*get_top_stack_without_poping(&operator_stack)!=parenthesis_open_tag)
            {
                temp_token_ptr=pop_Stack(&operator_stack);
                if(is_operator_token(temp_token_ptr)) ptr_parser=push_quantum(*temp_token_ptr,ptr_parser,&parser_size);  //mets à la sortie
            }
            pop_Stack(&operator_stack); //pop the left bracket
        }

        ptr_lexer=skip_arg(ptr_lexer);
    }
    while(operator_stack.nb_elem>0)
    {
        if(is_operator_token(temp_token_ptr=pop_Stack(&operator_stack)))
             ptr_parser=push_quantum(*temp_token_ptr,ptr_parser,&parser_size);
    }
}

Pour la commande suivante : 1 * ( 2 + 3 * 4 ) + 5
La sortie (correcte) du lexer est :
{ UINT8_TAG[1] MUL_TAG (_TAG UINT8_TAG[2] ADD_TAG UINT8_TAG[3] MUL_TAG UINT8_TAG[4] )_TAG ADD_TAG UINT8_TAG[5] TERMINATED }

Mais à la sortie on a la séquence erronée :
{ UINT8_TAG[1] UINT8_TAG[2] UINT8_TAG[3] UINT8_TAG[4] MUL_TAG ADD_TAG UINT8_TAG[5] ADD_TAG MUL_TAG TERMINATED }
On devrait plutot avoir :
UINT8_TAG[1] UINT8_TAG[2] UINT8_TAG[3] UINT8_TAG[4] MUL_TAG ADD_tAG MUL_TAG UINT8_TAG[5] ADD_TAG TERMINATED }

Je pense cependant avoir respecté l'algorithme à la lettre, je ne comprends pas mon erreur. Si quelqu'un pourrait y jeter un oeil.
Merci par avance
User avatar
newprog_creator
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 17.2%
 
Posts: 49
Joined: 29 Mar 2014, 19:07
Gender: Not specified
Calculator(s):
Class: bac+13

Re: Analyse lexicale et syntaxique -nouveau langage oncalc t

Unread postby rentech7289 » 18 Sep 2021, 21:54

En NPI, ce calcul donne : 3 4 mul 2 add 1 mul 5 add.
Je n'utilise plus de langage de la famille C depuis plus de quinze ans pour Java à cause de l'Unicode, alors lire ton code... De plus il n'est pas exclu qu'il y ait un problème de pointeur. Pourquoi ne pas l'avoir codé en Java ou en python qui ont des collections appropriées (les arbres par exemple) pour gérer ce genre de situation?
User avatar
rentech7289
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 66.4%
 
Posts: 107
Joined: 16 Aug 2021, 02:40
Location: Lorraine luxembourgeoise
Gender: Male
Calculator(s):

Next

Return to Langages alternatifs

Who is online

Users browsing this forum: No registered users and 4 guests

-
Search
-
Social
-
Featured topics
Concours de l'Avent 2021 "l'énigme des 3 portes". Viens prendre connaissance des indices et bouts de code Python chaque jour. Sois parmi les 7 premiers à trouver et franchir l'une des 3 portes pour remporter de superbes lots : équipements complets en calculatrices Python couleur et/ou accessoires exclusifs !
Concours Geometry Dash - 2 équipements complets en calculatrices TI (+ goodies et accessoires) à gagner pour les 2 meilleurs niveaux créés
Concours de dessin de Noël 2021 Jusqu'au 7 janvier 2022 inclus par Casio. Dessine ta liste au Père Noël sur calculatrice/émulateur Graph 90/35+E II en Python ou fx-92+ Spéciale Collège. Ouvert aux élèves et enseignants, classement séparé. À gagner 2 consoles Nintendo Switch, 2 trottinettes électriques, 10 calculatrices Graph 90/35+E II au choix, 72 montres Casio G-Shock ou Vintage. Pas de perdant, goodies Casio pour tous les autres !
Coque NumWorks édition limitée Décembre 2021 à gagner.
Comparaisons des meilleurs prix pour acheter sa calculatrice !
12345
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...
Donate
Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
617 utilisateurs:
>590 invités
>22 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)

-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)