33

我正在尝试用 C# 编写一个非常简单的解析器。

我需要一个词法分析器——它可以让我将正则表达式与标记相关联,因此它可以读取正则表达式并返回符号。

似乎我应该能够使用 Regex 来完成实际的繁重工作,但我看不到一个简单的方法来做到这一点。一方面,Regex 似乎只适用于字符串,而不适用于流(为什么会这样!?!?)。

基本上,我想要以下接口的实现:

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

所以,请发送 codz...
不,说真的,我即将开始编写上述接口的实现,但我发现很难相信在 .NET (2.0) 中已经没有一些简单的方法可以做到这一点.

那么,对于执行上述操作的简单方法有什么建议吗?(另外,我不想要任何“代码生成器”。性能对于这件事并不重要,我不想在构建过程中引入任何复杂性。)

4

7 回答 7

27

我在此处作为答案发布的原始版本存在一个问题,即它仅在有多个与当前表达式匹配的“正则表达式”时才有效。也就是说,只要只有一个 Regex 匹配,它就会返回一个令牌 - 而大多数人希望 Regex 是“贪婪的”。对于诸如“引用的字符串”之类的内容尤其如此。

位于 Regex 之上的唯一解决方案是逐行读取输入(这意味着您不能拥有跨越多行的标记)。我可以忍受这个——毕竟,这是一个穷人的词法分析器!此外,在任何情况下,从 Lexer 中获取行号信息通常很有用。

因此,这是一个解决这些问题的新版本。也归功于

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

示例程序:

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

输出:

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: )
于 2009-03-23T14:46:55.530 回答
6

这可能是矫枉过正,但看看CodePlex 上的Irony

Irony 是一个在 .NET 平台上实现语言的开发工具包。它利用 c# 语言和 .NET Framework 3.5 的灵活性和强大功能来实现一种全新的、流线型的编译器构造技术。与大多数现有的 yacc/lex 风格的解决方案不同,Irony 不使用任何扫描器或解析器代码生成来自以专门的元语言编写的语法规范。在 Irony 中,目标语言语法直接用 C# 编码,使用运算符重载来表达语法结构。Irony 的扫描器和解析器模块使用编码为 c# 类的语法来控制解析过程。请参阅表达式语法示例以获取 c# 类中的语法定义示例,并在工作解析器中使用它。

于 2009-03-23T15:03:53.367 回答
5

除非你有一个非常规的语法,否则我强烈建议不要使用你自己的词法分析器/解析器。

我通常发现 C# 的词法分析器/解析器真的很缺乏。但是,F# 附带 fslex 和 fsyacc,您可以在本教程中了解如何使用它们。我用 F# 编写了几个词法分析器/解析器,并在 C# 中使用它们,而且它很容易做到。

我想它并不是一个穷人的词法分析器/解析器,因为你必须学习一门全新的语言才能开始,但它是一个开始。

于 2009-03-23T12:30:27.620 回答
2

改变我原来的答案。

看看具有不同语法类型的解析器的SharpTemplate,例如

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

它对每种类型的令牌使用正则表达式:

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

像这样使用哪个

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

    ....
}

它从堆栈中推送和弹出以保持状态。

于 2009-03-23T12:41:23.367 回答
2

Malcolm Crowe在此处为 C# 提供了出色的 LEX/YACC 实现。通过为 LEX 创建正则表达式来工作...

直接下载

于 2009-03-23T13:07:53.507 回答
0

如果您查看我的WPF 转换器库中的 ExpressionConverter ,它具有 C# 表达式的基本词法分析和解析。从记忆中不涉及正则表达式。

于 2009-03-23T12:01:16.397 回答
0

可以将 Flex 和 Bison 用于 C#。

爱尔兰大学的一位研究人员开发了一个部分实现,可以在以下链接中找到:Flex/Bison for C#

它绝对可以被认为是一个“可怜的人词法分析器”,因为他的实现似乎仍然存在一些问题,例如没有预处理器、“悬空其他”案例的问题等。

于 2009-03-23T12:57:39.663 回答