ANALYSEUR LEXICAL ET SYNTAXIQUE DES FORMULES PROPOSITIONNELLES [LOGIQUE MATHÉMATIQUE]

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Windows.Forms;

/**********************************************************************************
 * Analyseur lexical & syntaxique de formules propositionnelles (logique propositionnelle)
 * Développé dans les tps du module Logique mathématique (en coop avec Compil)
 * Boutemine Oualid (L3)
 * Guetteche Ali (M1) 
  * *********************************
 * Last code modification 19/01/2009
 **********************************************************************************/
// Chaine de teste: A & B | ~( C => (B <=> ~D)) => A
namespace tpLM
{
        public partial class frmMain : Form
        {

                #region Automates
                private string symbols = "()~|=><=>&";     // les symboles  
                // Automate des connecteurs logiques.
                Regex logicalConnectors = new Regex (@"^\||~|&|=\>|\<=\>$");
                // automate de recherche d'identificateurs.
                Regex identifier = new Regex ("^[a-zA-Z_][a-zA-Z0-9_]*$");
                // automates des parentheses.
                Regex parentheses = new Regex (@"^\(|\)$");
                // automates des unités lexicales. [BUG FIXED:\<=\> must appear befor =\> to identify equivalance before implication]
                Regex lexicalUnits = new Regex (@"[a-zA-Z0-9_]+|\(|\)|\||~|&|\<=\>|=\>");
                // automates des caracteres illegaux.
                Regex illegalChars = new Regex (@"[^a-zA-Z0-9()|~&=><_ ]");
                #endregion


                /// <summary>
                /// Retourne la profondeur de l'arbre d'analyse.
                /// </summary>
                /// <param name="root">Le sommet de l'arbre d'analyse.</param>
                /// <returns>La profondeur de l'arbre.</returns>

                public int GetDepth (TreeNode root)
                {
                        int depth = 0;
                        // Appels recursives.
                        switch (root.Nodes.Count)
                        {
                                case (0):
                                        {
                                                depth = 0;
                                                break;
                                        }
                                case (1):
                                        {
                                                depth += GetDepth (root.Nodes [0]) + 1;
                                                break;
                                        }
                                case (2):
                                        {
                                                depth += Math.Max (GetDepth (root.Nodes [0]), GetDepth (root.Nodes [1])) + 1;
                                                break;
                                        }
                        }
                        return depth;
                }

                /// <summary>
                /// Retourne la longueur de la formule
                /// </summary>
                /// <param name="input">La chaine a comparer.</param>
                /// <returns>Longueur</returns>
                public int GetLength (string input)
                {
                        // Nombre parentheses + Variables propositionnelles + connecteurs logiques
                        return GetParenthesis (input) + GetIdentifiers (input) + GetLogicalConnectors (input);
                }

                /// <summary>
                /// Retourne le nombre de parentheses dans la chaine.
                /// </summary>
                /// <param name="input">Chaine a comparer.</param>
                /// <returns>Nombre de parentheses.</returns>
                public int GetParenthesis (string input)
                {
                        int counter = 0;
                        MatchCollection wordsResult = lexicalUnits.Matches (input);
                        // pour chaque mot dans la formule.
                        foreach (Match word in wordsResult)
                        {
                                if (parentheses.IsMatch (word.Value))
                                        counter++;
                        }
                        return counter;
                }

                /// <summary>
                /// Retourne le nombre d'identificateurs.
                /// </summary>
                /// <param name="input">La chaine a comparer</param>
                /// <returns>Le nombre d'identificateur.</returns>
                public int GetIdentifiers (string input)
                {
                        int counter = 0;
                        MatchCollection wordsResult = lexicalUnits.Matches (input);
                        // pour chaque mot dans la formule.
                        foreach (Match word in wordsResult)
                        {
                                // si c'est un identificateur valide, alors compte le.
                                if (identifier.IsMatch (word.Value))
                                        counter++;
                        }
                        return counter;
                }

                /// <summary>
                ///  Routine de récupération sur les erreurs lexicales
                /// </summary>
                /// <param name="input">La formule propositionnelle</param>
                /// <returns>Dictionnaire d'erreurs.</returns>
                public Dictionary<int, string> GetLexicalErrors (string input)
                {
                        Dictionary<int, string> errors = new Dictionary<int, string> ();
                        // Recherche des caracteres speciaux non reconnues.
                        MatchCollection illegalchars = illegalChars.Matches (input);
                        foreach (Match illegalchar in illegalchars)
                                errors.Add (illegalchar.Index, illegalchar.Value);
                        // Unités lexicales
                        MatchCollection tookens = lexicalUnits.Matches (input);
                        // Pour chaque mot dans la formule
                        foreach (Match tooken in tookens)
                        {
                                // s'il n'est pas un identificateur ou un connecteur ou une parenthese.
                                if (!identifier.IsMatch (tooken.Value) &&
                                    !parentheses.IsMatch (tooken.Value) &&
                                    !logicalConnectors.IsMatch (tooken.Value))
                                        errors.Add (tooken.Index, tooken.Value);
                        }
                        return errors;
                }

                /// <summary>
                /// Retourne le nombre d'operateurs logiques.
                /// </summary>
                /// <param name="input">la formule propositionnelle.</param>
                /// <returns>Le nombre d'operateur</returns>
                public int GetLogicalConnectors (string input)
                {
                        int counter = 0;
                        MatchCollection wordsResults = lexicalUnits.Matches (input);
                        lblDepth.Text = wordsResults.Count.ToString ();
                        // Pour chaque mots dans la formule
                        foreach (Match word in wordsResults)
                        {
                                // si le mot est un connecteur logique alors.
                                if (logicalConnectors.IsMatch (word.Value))
                                        counter++;
                        }
                        return counter;
                }

                /// <summary>
                /// Retourne la complexité de la chaine (Nombre de connecteurs).
                /// </summary>
                /// <param name="input">La chaine a comparer.</param>
                /// <returns>La complexité.</returns>
                public int GetComplexity (string input)
                {
                        return GetLogicalConnectors (input);
                }

                /// <summary>
                /// Représente une production (Regle) dans la grammaire de l'analyseur syntaxique.
                /// </summary>
                public struct GrammarRule
                {
                        /// <summary>
                        /// Créer une nouvelle loie pour la grammaire.
                        /// </summary>
                        /// <param name="value">
                        /// Regle.
                        /// </param>
                        /// <param name="Operator">
                        /// Operateur.
                        /// </param>
                        /// <param name="operandsCount">
                        /// Nombre d'operandes.
                        /// </param>
                        public GrammarRule (string value, string Operator, int operandsCount)
                        {
                                this.Operator = Operator;
                                this.Value = value;
                                this.OperandsCount = operandsCount;
                        }
                        /// <summary>
                        /// Operateur.
                        /// </summary>
                        public string Operator;
                        /// <summary>
                        /// Regle.
                        /// </summary>
                        public string Value;
                        /// <summary>
                        /// Nombre d'operandes.
                        /// </summary>
                        public int OperandsCount;
                }
                /// <summary>
                /// Productions de la grammaire
                /// </summary>
                private List<GrammarRule> grammarRules = new List<GrammarRule> ();
                /// <summary>
                /// Pile des opérations de synthèse d'arbre (Synthese ascendante).
                /// </summary>
                private Stack<TreeNode> nodeStack = new Stack<TreeNode> ();
                /// <summary>
                /// Vérifie si la formule est syntaxiquement correcte.
                /// </summary>
                /// <param name="input">La forume a vérifier</param>
                /// <returns>Retourne le resultat de la vérification.</returns>
                private bool ContainsSyntaxicErrors (string input)
                {
                        bool error = false;
                        // Pile d'analyse de la chaine
                        string buffer = string.Empty;
                        // Jetons par l'analyseur lexicale.
                        MatchCollection tookensResult = lexicalUnits.Matches (input);
                        /******* Analyseur Syntaxique Ascendant LR********
                         * sans précédence d'opérateurs
                         *******/
                        foreach (Match tooken in tookensResult)
                        {
                                // Etape 1: vérifie le type du jeton: (soit symbole (Connecteur ou parenthese) ou variable propositionnelle.
                                // Si c'est un symbole, l'empiler.
                                if (symbols.Contains (tooken.Value))
                                        buffer += tooken.Value;
                                else
                                {
                                        // Si c'est une variable propositionnelle (Identificateur).
                                        buffer += "F";
                                        // Creer un noeud (Nom = Unité Lexicale)
                                        TreeNode node = new TreeNode (tooken.Value);
                                        // Empiler le noeud.
                                        nodeStack.Push (node);
                                }
                        repeat:                // Etape 2: Substitions sur la pile d'entrée.
                                foreach (GrammarRule rule in grammarRules)
                                {
                                        if (buffer.Contains (rule.Value))
                                        {
                                                // substition en F
                                                buffer = buffer.Replace (rule.Value, "F");
                                                // donner pour nom du node l'operateur
                                                TreeNode parentNode = new TreeNode (rule.Operator);
                                                switch (rule.OperandsCount)
                                                {
                                                        case (1):
                                                                {
                                                                        // dépiler le noeud en somment de la pile
                                                                        TreeNode node1 = nodeStack.Pop ();
                                                                        // Mettre le noeud dans les sous-noeuds du parent.
                                                                        parentNode.Nodes.Add (node1);
                                                                        // Empiler le parent
                                                                        nodeStack.Push (parentNode);
                                                                        break;
                                                                }
                                                        case (2):
                                                                {
                                                                        // dépiler le noeud en somment de la pile
                                                                        TreeNode node1 = nodeStack.Pop ();
                                                                        TreeNode node2 = nodeStack.Pop ();
                                                                        // Mettre le noeud dans les sous-noeuds du parent.
                                                                        parentNode.Nodes.Add (node2);
                                                                        parentNode.Nodes.Add (node1);
                                                                        // Empiler le parent
                                                                        nodeStack.Push (parentNode);
                                                                        break;
                                                                }
                                                }
                                                // Répete l'analyse pour le nouveau buffer.
                                                goto repeat;
                                        }
                                }
                        }
                        // analyse syntaxique correcte.
                        error = (buffer != "F");
                        if (!error)
                        {
                                // Affichage de l'arbre.
                                trvSyntaxicTree.Nodes.Clear ();
                                trvSyntaxicTree.Nodes.Add (nodeStack.Pop ());
                        }
                        return error;
                }

                public frmMain ()
                {
                        InitializeComponent ();
                        // Initialization du dictionnaire des productions de la grammaire.
                        grammarRules.Add (new GrammarRule ("F&F", "&", 2));
                        grammarRules.Add (new GrammarRule ("F|F", "|", 2));
                        grammarRules.Add (new GrammarRule ("F=>F", "=>", 2));
                        grammarRules.Add (new GrammarRule ("F<=>F", "<=>", 2));
                        grammarRules.Add (new GrammarRule ("(F)", "", 0));
                        grammarRules.Add (new GrammarRule ("~F", "~", 1));
                }

                private void btnCalculer_Click (object sender, EventArgs e)
                {
                        // netoyage de la liste d'erreurs lexicales.
                        lstLexicalErrors.Items.Clear ();
                        // Traitement d'erreurs lexicales.
                        Dictionary<int, string> errors = GetLexicalErrors (txtFormule.Text);
                        // S'il existe des erreurs lexicales, on les affiche et on sort
                        if (errors.Count != 0)
                        {
                                // affichage des erreurs : lexicales.
                                foreach (KeyValuePair<int, string> error in errors)
                                        lstLexicalErrors.Items.Add ("Position " + error.Key.ToString () + ": " + error.Value.ToString ());
                                // sort.
                                return;
                        }

                        // Traitement des erreurs syntaxiques.
                        if (ContainsSyntaxicErrors (txtFormule.Text))
                        {
                                lblSyntaxicErrors.Text = "La chaine est syntaxiquement incorrecte";
                                return;
                        }

                        /*** Affichage des resultats. ***/
                        // longueur.
                        lblLenght.Text = GetLength (txtFormule.Text).ToString ();
                        // Complexité.
                        lblComplexity.Text = GetComplexity (txtFormule.Text).ToString ();
                        // Profondeur.
                        lblDepth.Text = GetDepth (trvSyntaxicTree.Nodes [0]).ToString ();
                }
        }
}