Comment écrire un parsingur en C #?

Comment puis-je écrire un parsingur syntaxique (descente récursive?) En C #? Pour l’instant je veux juste un parsingur simple qui parsing les expressions arithmétiques (et lit les variables?). Bien que plus tard je compte écrire un parsingur xml et html (à des fins d’apprentissage). Je le fais parce que les parsingurs sont très utiles: développement Web, interpréteurs de langages de programmation, outils internes, moteurs de jeux, éditeurs de cartes et de mosaïques, etc. Quelle est la théorie de base de l’écriture des parsingurs syntaxiques? en implémenter un en C #? Est-ce que C # est le bon langage pour les parsingurs (j’ai écrit un simple parsingur arithmétique en C ++ et c’était efficace. La compilation de JIT sera-t-elle aussi bonne?). Toutes les ressources et articles utiles. Et surtout, des exemples de code (ou des liens vers des exemples de code).

Note: Par curiosité, quelqu’un ayant répondu à cette question a-t-il déjà implémenté un parsingur en C #?

J’ai implémenté plusieurs parsingurs en C # – écrits à la main et générés par des outils.

Un très bon tutoriel d’introduction à l’parsing en général est Let’s Comstackr un compilateur – il montre comment créer un parsingur de descente récursif; et les concepts sont facilement traduits de sa langue (je crois que c’était Pascal) à C # pour tout développeur compétent. Cela vous apprendra comment fonctionne un parsingur récursif de descente, mais il est impossible d’écrire manuellement un parsingur complet de langage de programmation.

Vous devriez regarder dans certains outils pour générer le code pour vous – si vous êtes déterminé à écrire un parsingur de descente récursif classique ( TinyPG , Coco / R , Irony ). Gardez à l’esprit qu’il existe d’autres moyens d’écrire les parsingurs maintenant, qui fonctionnent généralement mieux et ont des définitions plus simples (par exemple, parsing TDOP ou parsing monadique ).

Sur le sujet de savoir si C # est prêt pour la tâche – C # possède certaines des meilleures bibliothèques de texte. Un grand nombre des parsingurs d’aujourd’hui (dans d’autres langues) ont une quantité de code obscène pour traiter Unicode, etc. Je ne ferai pas trop de commentaires sur le code JITted, car cela peut devenir assez religieux. IronJS est un bon exemple d’un parsingur / runtime sur le CLR (même s’il est écrit en F #) et ses performances sont juste inférieures à celles de Google V8.

Note latérale: Les parsingurs de balisage sont complètement différents des parsingurs syntaxiques – ils sont, dans la majorité des cas, écrits à la main – et au niveau du scanner / parsingur très simple; ils ne sont généralement pas récursifs – et surtout dans le cas de XML, il est préférable de ne pas écrire un parsingur de descente récursif (pour éviter les débordements de stack et parce qu’un parsingur «plat» peut être utilisé en mode SAX / push).

Sprache est un framework puissant mais léger pour écrire des parsingurs dans .NET. Il existe également un package Sprache NuGet . Pour vous donner une idée du cadre, voici l’un des exemples pouvant parsingr une expression arithmétique simple dans un arbre d’expression .NET. Assez incroyable je dirais.

using System; using System.Linq.Expressions; using Sprache; namespace LinqyCalculator { static class ExpressionParser { public static Expression> ParseExpression(ssortingng text) { return Lambda.Parse(text); } static Parser Operator(ssortingng op, ExpressionType opType) { return Parse.Ssortingng(op).Token().Return(opType); } static readonly Parser Add = Operator("+", ExpressionType.AddChecked); static readonly Parser Subtract = Operator("-", ExpressionType.SubtractChecked); static readonly Parser Multiply = Operator("*", ExpressionType.MultiplyChecked); static readonly Parser Divide = Operator("/", ExpressionType.Divide); static readonly Parser Constant = (from d in Parse.Decimal.Token() select (Expression)Expression.Constant(decimal.Parse(d))).Named("number"); static readonly Parser 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 Term = Parse.ChainOperator(Multiply.Or(Divide), Factor, Expression.MakeBinary); static readonly Parser Expr = Parse.ChainOperator(Add.Or(Subtract), Term, Expression.MakeBinary); static readonly Parser>> Lambda = Expr.End().Select(body => Expression.Lambda>(body)); } } 

C # est presque un langage fonctionnel décent, il n’est donc pas très important d’y implémenter quelque chose comme Parsec. Voici un exemple de la façon de le faire: http://jparsec.codehaus.org/NParsec+Tutorial

Il est également possible d’implémenter un Packrat basé sur un combinateur, de manière très similaire, mais en gardant cette fois un état d’parsing global quelque part au lieu de faire des choses fonctionnelles pures. Dans mon implémentation (très basique et ad hoc), c’était assez rapide, mais bien sûr, un générateur de code comme celui-ci doit être plus performant.

Je sais que je suis un peu en retard, mais je viens de publier une bibliothèque de générateurs d’parsingur / grammaire / AST nommée Ve Parser. vous pouvez le trouver sur http://veparser.codeplex.com ou l’append à votre projet en tapant «Install-Package veparser» dans la console du gestionnaire de packages. Cette bibliothèque est une sorte d’parsingur récursif de descente conçu pour être facile à utiliser et flexible. Comme sa source est à votre disposition, vous pouvez apprendre de ses codes sources. J’espère que ça aide.

À mon avis, il existe un meilleur moyen d’implémenter des parsingurs que les méthodes traditionnelles qui simplifient et facilitent la compréhension du code, et facilitent en particulier l’extension du langage que vous parsingz en branchant simplement une nouvelle classe dans un object. manière orientée. Un article d’une série plus importante que j’ai écrit met l’accent sur cette méthode d’parsing, et le code source complet est inclus pour un parsingur C # 2.0: http://www.codeproject.com/Articles/492466/Object-Oriented-Parsing-Breaking-With -Tradition-Pa

Eh bien … par où commencer avec celui-ci ….

Tout d’abord, en écrivant un parsingur, eh bien, c’est une déclaration très large, surtout avec la question que vous posez.

Votre déclaration liminaire était que vous vouliez un simple “parsingur” arithmatique, bien que techniquement, ce ne soit pas un parsingur, c’est un parsingur lexical, similaire à ce que vous pouvez utiliser pour créer un nouveau langage. ( http://en.wikipedia.org/wiki/Lexical_analysis ) Je comprends toutefois exactement la source de la confusion. Il est important de noter que l’parsing Lexical est ÉGALEMENT ce que vous voudrez comprendre si vous allez également écrire des parsingurs de langage / script, ce n’est ssortingctement pas une parsing car vous interprétez les instructions plutôt que de les utiliser.

Retour à la question d’parsing …

C’est ce que vous allez faire si vous prenez une structure de fichiers définie de manière rigide pour en extraire des informations.

En général, vous n’avez pas besoin d’écrire un parsingur pour XML / HTML, car il y en a déjà une tonne, et encore plus si votre parsing XML produite par le runtime .NET, vous n’avez même pas besoin de Parse, il vous suffit de “sérialiser” et de “désérialiser”.

Dans l’intérêt de l’apprentissage, cependant, l’parsing XML (ou quelque chose de similaire, comme le HTML) est très simple dans la plupart des cas.

si on commence avec le XML suivant:

    Tron   Tron Legacy   

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

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

vous pouvez alors accéder à l’élément racine “movies” en utilisant “myXML.Root”

Plus intéressant, cependant, vous pouvez utiliser Linq facilement pour obtenir les tags nesteds:

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

Vous donnera une var de XElements contenant chacun un “…” que vous pouvez utiliser en utilisant quelque chose comme:

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

Pour toute autre chose que XML comme les structures de données, alors je crains que vous deviez commencer à apprendre l’art des expressions régulières, un outil comme “Regular Expression Coach” vous aidera énormément ( http://weitz.de/regex -coach / ) ou l’un des outils similaires les plus récents.

Vous devrez également vous familiariser avec les objects d’expression régulière .NET ( http://www.codeproject.com/KB/dotnet/regextutorial.aspx ), qui vous donneront une bonne longueur d’avance.

Une fois que vous connaissez le fonctionnement de vos fichiers reg-ex, dans la plupart des cas, il s’agit simplement de lire les fichiers une ligne à la fois et de les utiliser en utilisant la méthode qui vous convient le mieux.

Vous trouverez une bonne source gratuite de formats de fichiers pour presque tout ce que vous pouvez imaginer sur ( http://www.wotsit.org/ )

Pour le compte rendu, j’ai implémenté un générateur d’parsingur en C # simplement parce que je ne trouvais aucun fonctionnement correct ou similaire à YACC (voir: http://sourceforge.net/projects/naivelangtools/ ).

Cependant, après quelques expériences avec ANTLR, j’ai décidé de partir avec LALR au lieu de LL. Je sais que théoriquement LL est plus facile à implémenter (générateur ou parsingur syntaxique) mais je ne peux tout simplement pas vivre avec une stack d’expressions pour exprimer les priorités des opérateurs (comme * va avant + dans “2 + 5 * 3”). Dans LL, vous dites que mult_expr est incorporé dans add_expr, ce qui ne me semble pas naturel.