cref - summary example c#

Cómo escribir un analizador en C#?

Question

¿Cómo hago para escribir un Analizador (Descenso recursivo?) En C #? Por ahora solo quiero un analizador simple que analiza expresiones aritméticas (y lee variables?). Aunque más tarde tengo la intención de escribir un analizador xml y html (para fines de aprendizaje). Estoy haciendo esto debido a la amplia gama de elementos en los que los analizadores son útiles: desarrollo web, intérpretes de lenguajes de programación, herramientas internas, motores de juegos, editores de mapas y mosaicos, etc. ¿Cuál es la teoría básica de los analizadores sintácticos y cómo puedo implementar uno en C #? Es C # el lenguaje correcto para los analizadores sintácticos (una vez escribí un analizador sintáctico aritmético simple en C ++ y fue eficiente. ¿La compilación de JIT será igual de buena?). Todos los recursos y artículos útiles. Y lo mejor de todo, ejemplos de código (o enlaces a ejemplos de código).

Nota: por curiosidad, ¿alguien que haya respondido a esta pregunta alguna vez implementó un analizador sintáctico en C #?

Answer 1

Bueno ... por dónde empezar con este ...

En primer lugar, escribir un analizador, bueno, esa es una afirmación muy amplia, especialmente con la pregunta que hace.

Su declaración inicial fue que usted quería un "analizador sintáctico" aritmático simple, técnicamente no es un analizador sintáctico, es un analizador léxico, similar al que puede usar para crear un nuevo idioma. ( http://en.wikipedia.org/wiki/Lexical_analysis ) Sin embargo, entiendo exactamente de dónde puede venir la confusión de que sean lo mismo. Es importante tener en cuenta que el análisis léxico TAMBIÉN es lo que querrá saber si también va a escribir analizadores de lenguaje / script, esto no es un análisis porque está interpretando las instrucciones en lugar de utilizarlas.

De vuelta a la pregunta de análisis ....

Esto es lo que harás si tomas una estructura de archivo rígidamente definida para extraer información de ella.

En general, no es necesario escribir un analizador sintáctico para XML / HTML, porque ya hay un montón de ellos disponibles, y más aún si su XML de análisis producido por el tiempo de ejecución de .NET, entonces ni siquiera necesita Parse, solo necesita "serializar" y "eliminar la serialización".

Sin embargo, para aprender, analizar XML (o algo similar como html) es muy sencillo en la mayoría de los casos.

si comenzamos con el siguiente XML:

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

podemos cargar los datos en un XElement de la siguiente manera:

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

entonces puede obtener el elemento raíz ''películas'' usando ''myXML.Root''

Sin embargo, es interesante, puedes usar Linq fácilmente para obtener las etiquetas anidadas:

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

Le dará una variedad de XElements que contienen cada uno ''...'' que puede obtener usando algo como:

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

Para cualquier otra cosa que no sea XML como las estructuras de datos, me temo que tendrá que empezar a aprender el arte de las expresiones regulares, una herramienta como "Entrenador de expresión regular" le ayudará imensly ( http://weitz.de/regex-coach/ ) o una de las herramientas similares más uptodate.

También deberá familiarizarse con los objetos de expresiones regulares de .NET, ( http://www.codeproject.com/KB/dotnet/regextutorial.aspx ) debería darle una buena ventaja.

Una vez que sepa cómo funcionan sus registros, en la mayoría de los casos se trata de un simple caso de leer en los archivos una línea a la vez y darles sentido utilizando el método con el que se sienta cómodo.

Puede encontrar una buena fuente gratuita de formatos de archivo para casi cualquier cosa que pueda imaginar en ( http://www.wotsit.org/ )

Answer 2

C # es casi un lenguaje funcional decente, por lo que no es tan importante implementar algo como Parsec en él. Este es uno de los ejemplos de cómo hacerlo: http://jparsec.codehaus.org/NParsec+Tutorial

También es posible implementar un Packrat basado en combinador, de una manera muy similar, pero esta vez manteniendo un estado de análisis global en algún lugar en lugar de hacer un trabajo puramente funcional. En mi implementación (muy básica y ad hoc) fue razonablemente rápido, pero por supuesto un generador de código como this debe funcionar mejor.

Answer 3

En mi opinión, hay una mejor manera de implementar analizadores que los métodos tradicionales que resultan en un código más simple y fácil de entender, y especialmente hace que sea más fácil extender el lenguaje que está analizando simplemente conectando una nueva clase en un objeto muy complejo. camino orientado Un artículo de una serie más grande que escribí se centra en este método de análisis sintáctico, y el código fuente completo se incluye para un analizador C # 2.0: http://www.codeproject.com/Articles/492466/Object-Oriented-Parsing-Breaking-With-Tradition-Pa

Answer 4

He implementado varios analizadores en C #, escritos a mano y generados por herramientas.

Un muy buen tutorial introductorio sobre el análisis en general es Construyamos un compilador : demuestra cómo construir un analizador de descenso recursivo; y los conceptos se traducen fácilmente de su lenguaje (creo que fue Pascal) a C # para cualquier desarrollador competente. Esto le enseñará cómo funciona un analizador de descenso recursivo, pero es completamente impráctico escribir un analizador de lenguaje de programación completo a mano.

Debería buscar algunas herramientas para generar el código para usted, si está decidido a escribir un analizador de descenso recursivo clásico ( TinyPG , Coco/R , Irony ). Tenga en cuenta que hay otras maneras de escribir analizadores ahora, que normalmente funcionan mejor y tienen definiciones más fáciles (por ejemplo, análisis TDOP o análisis monádico ).

Sobre el tema de si C # está listo para la tarea, C # tiene algunas de las mejores bibliotecas de texto que existen. Muchos de los analizadores de hoy (en otros idiomas) tienen una cantidad obscena de código para tratar con Unicode, etc. No haré mucho comentario sobre el código JIT porque puede ser bastante religioso, sin embargo, debería estar bien. IronJS es un buen ejemplo de un analizador / tiempo de ejecución en el CLR (aunque está escrito en F #) y su rendimiento es apenas inferior al de Google V8.

Nota al margen : los analizadores de marcado son bestias completamente diferentes en comparación con los analizadores de lenguaje; en la mayoría de los casos, están escritos a mano, y en el nivel de escáner / analizador son muy simples; por lo general, no son de descendencia recursiva, y especialmente en el caso de XML, es mejor si no se escribe un analizador de descenso recursivo (para evitar desbordamientos de pila, y porque se puede usar un analizador "plano" en modo SAX / push).

Answer 5

Para el registro, implementé el generador de analizadores en C # solo porque no pude encontrar ninguno que funcionara de manera adecuada o similar a YACC (ver: http://sourceforge.net/projects/naivelangtools/ ).

Sin embargo, después de un poco de experiencia con ANTLR decidí ir con LALR en lugar de LL. Sé que teóricamente LL es más fácil de implementar (generador o analizador) pero simplemente no puedo vivir con una pila de expresiones solo para expresar las prioridades de los operadores (como * va antes + en "2 + 5 * 3"). En LL dices que mult_expr está incrustado en add_expr, lo que no me parece natural.

Answer 6

Sé que llegué un poco tarde, pero acabo de publicar una biblioteca de generador de gramática / AST llamada Ve Parser. puede encontrarlo en http://veparser.codeplex.com o agregarlo a su proyecto al escribir ''Install-Package veparser'' en Package Manager Console. Esta biblioteca es una especie de analizador de descenso recursivo que pretende ser fácil de usar y flexible. Como su fuente está disponible para usted, puede aprender de sus códigos fuente. Espero que ayude.

Answer 7

Sprache es un marco potente pero ligero para escribir analizadores en .NET. También hay un paquete de Sprache NuGet . Para darle una idea del marco aquí, hay una de las samples que puede analizar una expresión aritmética simple en un árbol de expresiones .NET. Bastante sorprendente, diría yo.

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));
    }
}