Pobre hombre "lexer" para C#

regex

Question

Intento escribir un analizador muy simple en C #.

Necesito un lexer, algo que me permita asociar expresiones regulares con tokens, por lo que se lee en expresiones regulares y me devuelve símbolos.

Parece que debería poder usar Regex para hacer el trabajo pesado, pero no veo una manera fácil de hacerlo. Por un lado, Regex solo parece funcionar en cadenas, no en flujos (¿por qué es eso?).

Básicamente, quiero una implementación de la siguiente interfaz:

interface ILexer : IDisposable
{
    /// <summary>
    /// Return true if there are more tokens to read
    /// </summary>
    bool HasMoreTokens { get; }
    /// <summary>
    /// The actual contents that matched the token
    /// </summary>
    string TokenContents { get; }
    /// <summary>
    /// The particular token in "tokenDefinitions" that was matched (e.g. "STRING", "NUMBER", "OPEN PARENS", "CLOSE PARENS"
    /// </summary>
    object Token { get; }
    /// <summary>
    /// Move to the next token
    /// </summary>
    void Next();
}

interface ILexerFactory
{
    /// <summary>
    /// Create a Lexer for converting a stream of characters into tokens
    /// </summary>
    /// <param name="reader">TextReader that supplies the underlying stream</param>
    /// <param name="tokenDefinitions">A dictionary from regular expressions to their "token identifers"</param>
    /// <returns>The lexer</returns>
    ILexer CreateLexer(TextReader reader, IDictionary<string, object> tokenDefinitions);
}

Por lo tanto, pluz enviar el codz ...
No, en serio, estoy a punto de comenzar a escribir una implementación de la interfaz anterior, pero me cuesta creer que ya no exista una manera simple de hacerlo en .NET (2.0).

Entonces, ¿alguna sugerencia para una forma simple de hacer lo anterior? (Además, no quiero ningún "generador de códigos". El rendimiento no es importante para esto y no quiero introducir ninguna complejidad en el proceso de compilación).

Answer 1

A menos que tengas una gramática muy poco convencional, te recomiendo encarecidamente no rodar tu propio lexer / analizador.

Normalmente encuentro que los lexers / analizadores sintácticos para C # son realmente deficientes. Sin embargo, F # viene con fslex y fsyacc, que puede aprender a usar en este tutorial . Escribí varios lexer / analizadores en F # y los usé en C #, y es muy fácil de hacer.

Supongo que no es realmente un lexer / analizador de un pobre, ya que tienes que aprender un idioma completamente nuevo para empezar, pero es un comienzo.

Answer 2

Cambiando mi respuesta original.

Eche un vistazo a SharpTemplate que tiene analizadores para diferentes tipos de sintaxis, por ejemplo

#foreach ($product in $Products)
   <tr><td>$product.Name</td>
   #if ($product.Stock > 0)
      <td>In stock</td>
   #else
     <td>Backordered</td>
   #end
  </tr>
#end

Utiliza expresiones regulares para cada tipo de token:

public class Velocity : SharpTemplateConfig
{
    public Velocity()
    {
        AddToken(TemplateTokenType.ForEach, @"#(foreach|{foreach})/s+/(/s*(?<iterator>[a-z_][a-z0-9_]*)/s+in/s+(?<expr>.*?)/s*/)", true);
        AddToken(TemplateTokenType.EndBlock, @"#(end|{end})", true);
        AddToken(TemplateTokenType.If, @"#(if|{if})/s+/((?<expr>.*?)/s*/)", true);
        AddToken(TemplateTokenType.ElseIf, @"#(elseif|{elseif})/s+/((?<expr>.*?)/s*/)", true);
        AddToken(TemplateTokenType.Else, @"#(else|{else})", true);
        AddToken(TemplateTokenType.Expression, @"/${(?<expr>.*?)}", false);
        AddToken(TemplateTokenType.Expression, @"/$(?<expr>[a-zA-Z_][a-zA-Z0-9_/.@]*?)(?![a-zA-Z0-9_/.@])", false);
    }
}

Que se usa así

foreach (Match match in regex.Matches(inputString))
{
    ...

    switch (tokenMatch.TokenType)
    {
        case TemplateTokenType.Expression:
            {
                currentNode.Add(new ExpressionNode(tokenMatch));
            }
            break;

        case TemplateTokenType.ForEach:
            {
                nodeStack.Push(currentNode);

                currentNode = currentNode.Add(new ForEachNode(tokenMatch));
            }
            break;
        ....
    }

    ....
}

Empuja y aparece desde una pila para mantener el estado.

Answer 3

Es posible usar Flex y Bison para C #.

Un investigador de la Universidad de Irlanda ha desarrollado una implementación parcial que se puede encontrar en el siguiente enlace: Flex / Bison para C #

Definitivamente podría considerarse un "pobre mans lexer" ya que parece tener algunos problemas con su implementación, como sin preprocesador, problemas con un caso de "colgado de otro", etc.

Answer 4

La versión original que publiqué aquí como respuesta tenía un problema, ya que solo funcionaba cuando había más de un "Regex" que coincidía con la expresión actual. Es decir, tan pronto como solo un Regex coincida, devolverá un token, mientras que la mayoría de la gente quiere que el Regex sea "codicioso". Este fue especialmente el caso de cosas como "cadenas citadas".

La única solución que se encuentra en la parte superior de Regex es leer la línea de entrada por línea (lo que significa que no puede tener tokens que abarcan varias líneas). Puedo vivir con esto, es, después de todo, ¡un lexer de un pobre! Además, en general es útil obtener información del número de línea del Lexer en cualquier caso.

Entonces, aquí hay una nueva versión que aborda estos problemas. El crédito también va a this

public interface IMatcher
{
    /// <summary>
    /// Return the number of characters that this "regex" or equivalent
    /// matches.
    /// </summary>
    /// <param name="text">The text to be matched</param>
    /// <returns>The number of characters that matched</returns>
    int Match(string text);
}

sealed class RegexMatcher : IMatcher
{
    private readonly Regex regex;
    public RegexMatcher(string regex) => this.regex = new Regex(string.Format("^{0}", regex));

    public int Match(string text)
    {
        var m = regex.Match(text);
        return m.Success ? m.Length : 0;
    }
    public override string ToString() => regex.ToString();
}

public sealed class TokenDefinition
{
    public readonly IMatcher Matcher;
    public readonly object Token;

    public TokenDefinition(string regex, object token)
    {
        this.Matcher = new RegexMatcher(regex);
        this.Token = token;
    }
}

public sealed class Lexer : IDisposable
{
    private readonly TextReader reader;
    private readonly TokenDefinition[] tokenDefinitions;

    private string lineRemaining;

    public Lexer(TextReader reader, TokenDefinition[] tokenDefinitions)
    {
        this.reader = reader;
        this.tokenDefinitions = tokenDefinitions;
        nextLine();
    }

    private void nextLine()
    {
        do
        {
            lineRemaining = reader.ReadLine();
            ++LineNumber;
            Position = 0;
        } while (lineRemaining != null && lineRemaining.Length == 0);
    }

    public bool Next()
    {
        if (lineRemaining == null)
            return false;
        foreach (var def in tokenDefinitions)
        {
            var matched = def.Matcher.Match(lineRemaining);
            if (matched > 0)
            {
                Position += matched;
                Token = def.Token;
                TokenContents = lineRemaining.Substring(0, matched);
                lineRemaining = lineRemaining.Substring(matched);
                if (lineRemaining.Length == 0)
                    nextLine();

                return true;
            }
        }
        throw new Exception(string.Format("Unable to match against any tokens at line {0} position {1} /"{2}/"",
                                          LineNumber, Position, lineRemaining));
    }

    public string TokenContents { get; private set; }
    public object Token   { get; private set; }
    public int LineNumber { get; private set; }
    public int Position   { get; private set; }

    public void Dispose() => reader.Dispose();
}

Programa de ejemplo:

string sample = @"( one (two 456 -43.2 "" /"" quoted"" ))";

var defs = new TokenDefinition[]
{
    // Thanks to [steven levithan][2] for this great quoted string
            // regex
    new TokenDefinition(@"([""''])(?:///1|.)*?/1", "QUOTED-STRING"),
    // Thanks to http://www.regular-expressions.info/floatingpoint.html
    new TokenDefinition(@"[-+]?/d*/./d+([eE][-+]?/d+)?", "FLOAT"),
    new TokenDefinition(@"[-+]?/d+", "INT"),
    new TokenDefinition(@"#t", "TRUE"),
    new TokenDefinition(@"#f", "FALSE"),
    new TokenDefinition(@"[*<>/?/-+/A-Za-z->!]+", "SYMBOL"),
    new TokenDefinition(@"/.", "DOT"),
    new TokenDefinition(@"/(", "LEFT"),
    new TokenDefinition(@"/)", "RIGHT"),
    new TokenDefinition(@"/s", "SPACE")
};

TextReader r = new StringReader(sample);
Lexer l = new Lexer(r, defs);
while (l.Next())
    Console.WriteLine("Token: {0} Contents: {1}", l.Token, l.TokenContents);

Salida:

Token: LEFT Contents: (
Token: SPACE Contents:
Token: SYMBOL Contents: one
Token: SPACE Contents:
Token: LEFT Contents: (
Token: SYMBOL Contents: two
Token: SPACE Contents:
Token: INT Contents: 456
Token: SPACE Contents:
Token: FLOAT Contents: -43.2
Token: SPACE Contents:
Token: QUOTED-STRING Contents: " /" quoted"
Token: SPACE Contents:
Token: RIGHT Contents: )
Token: RIGHT Contents: )

Answer 5

Malcolm Crowe tiene una gran implementación de LEX / YACC para C # here . Funciona mediante la creación de expresiones regulares para el LEX ...

Descarga directa

Answer 6

Puede ser excesivo, pero eche un vistazo a Irony en CodePlex.

Irony es un kit de desarrollo para implementar idiomas en la plataforma .NET. Utiliza la flexibilidad y la potencia del lenguaje c # y .NET Framework 3.5 para implementar una tecnología de compilación completamente nueva y simplificada. A diferencia de la mayoría de las soluciones yacc / lex-style, Irony no emplea ningún escáner o generación de código analizador a partir de especificaciones gramaticales escritas en un metalenguaje especializado. En Irony, la gramática del idioma de destino se codifica directamente en c # utilizando la sobrecarga del operador para expresar construcciones gramaticales. Los módulos analizador y analizador de Irony utilizan la gramática codificada como clase c # para controlar el proceso de análisis sintáctico. Consulte la muestra de gramática de expresión para ver un ejemplo de definición de gramática en la clase c # y utilícela en un analizador en funcionamiento.

Answer 7

Si echa un vistazo al ExpressionConverter en mi biblioteca de Conversor WPF , tiene lexing básico y análisis de expresiones C #. No hay expresiones regex involucradas, de memoria.