S-表达式解析

Question

S-表达式解析

4

今天早些时候我遇到了这个问题：this question。

示例输入：我遇到了乔和吉尔，然后我们去购物。示例输出：[TOP [S [S [NP [PRP I]] [VP [VBD ran] [PP [IN into] [NP [NNP Joe] [CC and] [NNP Jill]]]]] [CC and] [S [ADVP [RB then]] [NP [PRP we]] [VP [VBD went] [NP [NN shopping]]]]]]

我本来想建议将预期输出（看起来像是一个s表达式）解析成对象（在我们的情况下是一棵树），然后使用简单的LINQ方法对其进行处理。但是，令我惊讶的是，我找不到一个C# s表达式解析器。

我唯一能想到的就是使用Clojure来解析它，因为它可以编译到clr，但我不确定这是否是一个好的解决方案。

顺便说一句，我不介意答案的输出类型是dynamic。我在这里找到的所有答案都是用于反序列化成特定架构的。

总之我的问题是： 我需要在C#中反序列化s表达式（如果能够序列化就更好了，以便未来的读者）。

- Benjamin Gruenbaum

Danny，感谢您的编辑（虽然我不确定为什么图片相关，但我会相信您有更多经验）。我在您的描述中看到您了解LISP和.NET，我很想听听您的建议。 - Benjamin Gruenbaum

你是指已经以 [TOP [S [S [NP [PRP I]] [VP [VBD ran] [PP [IN into] [NP [NNP Joe] [CC and] [NNP Jill]]]]] [CC and] [S [ADVP [RB then]] [NP [PRP we]] [VP [VBD went] [NP [NN shopping]]]]]] 形式序列化/反序列化的表达式，还是指输入表达式？ - Danny Varod

我想要能够通用地序列化/反序列化s表达式，对于这种情况，是的，我想要能够反序列化上述表达式（将(替换为[，将)替换为]）。 - Benjamin Gruenbaum

2个回答

2

我编写了一个开源的S-Expression解析器，可以在S-Expression.NET上获取。由于它使用OMeta#生成解析器，因此您可以快速尝试添加新功能。

- sw.

你知道如何修改 .ometacs 以支持包括下划线字符和点（也适用于数字）在内的符号吗？ - weirdgyn

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Danny Varod · Accepted Answer

看起来你需要一个这样的数据结构：

public class SNode
{
    public String Name { get; set; }

    private readonly List<SNode> _Nodes = new List<SNode>();
    public ICollection<SNode> Nodes { get { return _Nodes; } }
}

一个表单的序列化器

public String Serialize(SNode root)
{
    var sb = new StringBuilder();
    Serialize(root, sb);
    return sb.ToString();
}

private void Serialize(SNode node, StringBuilder sb)
{
    sb.Append('(');

    sb.Append(node.Name);

    foreach (var item in node.Nodes)
        Serialize(item, sb);

    sb.Append(" )");
}

一个形式的反序列化器:

public SNode Deserialize(String st)
{
    if (String.IsNullOrWhiteSpace(st))
        return null;

    var node = new SNode();

    var nodesPos = String.IndexOf('(');
    var endPos = String.LastIndexOf(')');

    var childrenString = st.SubString(nodesPos, endPos - nodesPos);

    node.Name = st.SubString(1, (nodesPos >= 0 ? nodePos : endPos)).TrimEnd();

    var childStrings = new List<string>();

    int brackets = 0;
    int startPos = nodesPos;
    for (int pos = nodesPos; pos++; pos < endPos)
    {
        if (st[pos] == '(')
            brackets++;
        else if (st[pos] == ')')
        {
            brackets--;

            if (brackets == 0)
            {
                childStrings.Add(st.SubString(startPos, pos - startPos + 1));
                startPos = pos + 1;
            }
        }
    }

    foreach (var child in childStrings)
    {
        var childNode = Deserialize(this, child);
        if (childNode != null)
            node.Nodes.Add(childNode);
    }

    return node;
}

如果您还没有测试或编译此代码，不过，这大致是它可能如何工作的。