Comment écrire un analyseur en C #?

Question

Comment puis-je écrire un Analyseur syntaxique (Descente Récursive?) en C#? Pour l'instant je veux juste un simple de parser un analyseur de expressions arithmétiques (et lit les variables?). Bien plus tard, j'ai l'intention d'écrire un fichier xml et html parser (à des fins d'apprentissage). Je fais cela à cause de la vaste gamme de choses dans lequel les analyseurs sont utiles. Développement Web. Langage De Programmation Interprètes. Interne De L'Entreprise Outils. Les Jeux Moteurs. Carte et Vignette Éditeurs etc. Quelle est donc la base de la théorie de l'écriture analyseurs? Et comment puis-je mettre en œuvre un en C#? Est C#, au droit de la langue pour les analyseurs (une fois, j'ai écrit une arithmétique simple analyseur en C++ et il a été efficace, qui sera compilation JIT prouver tout aussi bon?). Toutes les ressources utiles et des articles. Et le meilleur de tous les exemples de code (ou des liens vers des exemples de code).

Remarque: par curiosité, quelqu'un a la réponse à cette question jamais mis en œuvre un analyseur syntaxique en C#?

Answer 1

J'ai mis en place plusieurs analyseurs en C# écrit à la main et de l'outil généré.

Un très bon tutoriel d'introduction sur l'analyse en général nous allons Construire un Compilateur - il montre comment construire une descente récursive de l'analyseur; et les concepts sont facilement traduits de sa langue (je pense que c'était Pascal) à C# pour n'importe quel développeur compétent. Cela va vous apprendre comment faire un appel récursif à la descente de l'analyseur fonctionne, mais il est complètement impossible d'écrire une pleine langage de programmation de l'analyseur à la main.

Vous devriez examiner certains des outils pour générer le code pour vous - si vous êtes déterminé à écrire un classique de la descente récursive de l'analyseur (TinyPG, Coco/R, Ironie). Gardez à l'esprit qu'il existe d'autres façons d'écrire des analyseurs de maintenant, qui a l'habitude de faire mieux et avoir plus facilement des définitions (par ex. TDOP analyse ou Monadique de l'Analyse syntaxique).

Sur la question de savoir si C# est pour la tâche - C# est l'une des meilleures bibliothèques de texte. Beaucoup de les analyseurs aujourd'hui (en d'autres langues) ont un montant obscène de code Unicode etc. Je ne commenterai pas trop sur JITted code, car il peut faire très religeous - cependant, vous devriez être bien. IronJS est un bon exemple d'un analyseur/runtime sur le CLR (même s'il est écrit en F#) et sa performance est juste timide de Google V8.

Note de côté: le Balisage des analyseurs sont complètement différents des bêtes quand par rapport à la langue analyseurs - ils sont, dans la majorité des cas, écrit par la main et à le scanner/analyseur de niveau très simple, ils ne sont généralement pas récursive descente - et en particulier dans le cas de XML, il est préférable si vous n'écrivez pas un appel récursif à la descente de l'analyseur (pour éviter les débordements de pile, et parce que "à plat" de l'analyseur peut être utilisé dans SAX/mode push).

Answer 2

Sprache est un puissant, mais léger cadre pour la rédaction des analyseurs .NET. Il y a aussi un Language package NuGet. Pour vous donner une idée du cadre ici est l'un des échantillons qui peuvent analyser une expression arithmétique simple dans un .NET arborescence d'expression. Assez étonnant, je dirais.

using System;
using System.Linq.Expressions;
using Sprache;

namespace LinqyCalculator
{
    static class ExpressionParser
    {
        public static Expression<Func<decimal>> ParseExpression(string text)
        {
            return Lambda.Parse(text);
        }

        static Parser<ExpressionType> Operator(string op, ExpressionType opType)
        {
            return Parse.String(op).Token().Return(opType);
        }

        static readonly Parser<ExpressionType> Add = Operator("+", ExpressionType.AddChecked);
        static readonly Parser<ExpressionType> Subtract = Operator("-", ExpressionType.SubtractChecked);
        static readonly Parser<ExpressionType> Multiply = Operator("*", ExpressionType.MultiplyChecked);
        static readonly Parser<ExpressionType> Divide = Operator("/", ExpressionType.Divide);

        static readonly Parser<Expression> Constant =
            (from d in Parse.Decimal.Token()
             select (Expression)Expression.Constant(decimal.Parse(d))).Named("number");

        static readonly Parser<Expression> Factor =
            ((from lparen in Parse.Char('(')
              from expr in Parse.Ref(() => Expr)
              from rparen in Parse.Char(')')
              select expr).Named("expression")
             .XOr(Constant)).Token();

        static readonly Parser<Expression> Term = Parse.ChainOperator(Multiply.Or(Divide), Factor, Expression.MakeBinary);

        static readonly Parser<Expression> Expr = Parse.ChainOperator(Add.Or(Subtract), Term, Expression.MakeBinary);

        static readonly Parser<Expression<Func<decimal>>> Lambda =
            Expr.End().Select(body => Expression.Lambda<Func<decimal>>(body));
    }
}

Answer 3

C# est presque un décent fonctionnelle de la langue, de sorte qu'il n'est pas une grosse affaire, de mettre en œuvre quelque chose comme Parsec. Voici l'un des exemples de la façon de le faire: http://jparsec.codehaus.org/NParsec+Tutoriel

Il est également possible de mettre en œuvre un combinateur à base de Packrat, d'une manière très similaire, mais cette fois en gardant un mondial de l'analyse de l'état quelque part au lieu de faire un pur fonctionnel des choses. Dans mon (très basique et ad hoc) mise en œuvre, il a été assez rapide, mais bien sûr, un générateur de code comme cela doit faire mieux.

Answer 4

Je sais que je suis un peu en retard, mais je viens de publier une bibliothèque de générateur d'analyseur syntaxique / grammaire / AST appelée Ve Parser. vous pouvez le trouver à l' adresse http://veparser.codeplex.com ou l'ajouter à votre projet en tapant 'Install-Package veparser' dans la console du gestionnaire de packages. Cette bibliothèque est une sorte d’analyseur de descente récursive qui se veut simple d’utilisation et souple. Comme sa source est disponible, vous pouvez apprendre de ses codes source. J'espère que ça aide.

Answer 5

Bon... par où commencer avec celui-ci....

Le premier à écrire un analyseur syntaxique, eh bien, c'est un très large relevé en particulier avec la question de votre demande.

Votre déclaration d'ouverture a été que vous souhaitiez une simple arithmatic "parser" , bien que techniquement ce n'est pas un analyseur, il est un analyseur lexical, similaire à ce que vous pouvez utiliser pour créer un nouveau langage. ( http://en.wikipedia.org/wiki/Lexical_analysis ) je comprends cependant exactement où la confusion est la même chose peut venir de la. Il est important de noter que l'analyse Lexicale est AUSSI ce que vous aurez envie de comprendre si vous allez écrire la langue/script analyseurs de trop, ce n'est strictement pas l'analyse parce que vous êtes à interpréter les instructions plutôt que de faire usage d'entre eux.

De retour à l'analyse de la question....

C'est ce que vous allez faire si vous prenez un rigidement définis structure du fichier pour en extraire les informations.

En général, vous vraiment n'avez pas à écrire un parser XML / HTML, car il y a déjà une tonne d'entre eux autour, et d'autant plus si votre analyse de XML produit par le .NET moment de l'exécution, alors vous n'avez même pas besoin d'analyser, vous avez juste besoin de "serialise" et "de-serialise".

Dans l'intérêt de l'apprentissage cependant, l'analyse de XML (Ou quelque chose de similaire comme le html) est très simple dans la plupart des cas.

si nous commençons avec le fichier XML suivant:

    <movies>
      <movie id="1">
        <name>Tron</name>
      </movie>
      <movie id="2">
        <name>Tron Legacy</name>
      </movie>
    <movies>

nous pouvons charger les données dans un XElement comme suit:

    XElement myXML = XElement.Load("mymovies.xml");

ensuite, vous pouvez obtenir à la "films" de l'élément racine à l'aide de 'myXML.Root'

Plus intéressant, toutefois, vous pouvez utiliser Linq facilement pour obtenir les balises imbriquées:

    var myElements = from p in myXML.Root.Elements("movie")
                     select p;

Vous donnera une var de XElements contenant chacun un " ... " que vous pouvez obtenir à l'aide de quelque chose comme:

    foreach(var v in myElements)
    {
      Console.WriteLine(string.Format("ID {0} = {1}",(int)v.Attributes["id"],(string)v.Element("movie"));
    }

Pour rien d'autre que XML comme structure de données, alors je crains que vous allez avoir à commencer à apprendre l'art des expressions régulières, un outil comme "Expression Régulière Coach" va vous aider à imensly ( http://weitz.de/regex-coach/ ) ou de l'un des plus uptodate d'outils similaires.

Vous aurez également besoin de se familiariser avec le .NET expression régulière objets, ( http://www.codeproject.com/KB/dotnet/regextutorial.aspx ) devrait vous donner un bon départ.

Une fois que vous savez comment votre reg-ex ça marche alors dans la plupart des cas, c'est un cas simple cas de la lecture dans les fichiers ligne par ligne et de donner un sens à eux en utilisant toujours la méthode que vous sentez à l'aise avec.

Une bonne source libre de formats de fichiers pour presque tout ce que vous pouvez imaginer peut être trouvé à la ( http://www.wotsit.org/ )