Как написать парсер в С#?

Ответ 1

Я реализовал несколько парсеров в С# - рукописный и сгенерированный инструмент.

Очень хороший вводный учебник по разбору в целом - Let Build the Compiler - он демонстрирует, как создать рекурсивный парсер спуска; и концепции легко перевести с его языка (я думаю, это был Pascal) на С# для любого компетентного разработчика. Это научит вас, как работает рекурсивный парсер спуска, но совершенно непрактично писать полный парсер языка программирования вручную.

Вы должны изучить некоторые инструменты для генерации кода для вас - если вы решите написать классический рекурсивный парсер спуска (TinyPG, Coco/R, Irony). Имейте в виду, что теперь есть другие способы написания парсеров, которые обычно работают лучше - и имеют более простые определения (например, разбор TDOP или Monadic Parsing).

По вопросу о том, подходит ли С# для задачи - у С# есть одни из лучших текстовых библиотек. Множество парсеров сегодня (на других языках) имеют непристойный код для работы с Unicode и т.д. Я не буду слишком много комментировать код JIT, потому что он может стать довольно религиозным - однако вы должны быть в порядке. IronJS является хорошим примером парсера/времени выполнения на CLR (хотя его написано в F #), и его производительность просто застенчива. V8.

Боковое примечание: Парсеры разметки - совершенно разные животные по сравнению с парсерами языка - они в большинстве случаев написаны вручную - и на уровне сканера/парсера очень просты; они обычно не являются рекурсивным нисходящим - и особенно в случае XML лучше, если вы не пишете рекурсивный парсер спуска (чтобы избежать, а также потому, что "плоский" парсер можно использовать в режиме SAX/push).

Ответ 2

Sprache - мощная, но легкая структура для написания парсеров в .NET. Существует также пакет Sprache NuGet. Чтобы дать вам представление о структуре здесь, это один из samples, который может анализировать простое арифметическое выражение в дерево выражений .NET. Довольно удивительно, что я бы сказал.

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

Ответ 3

С# - почти достойный функциональный язык, поэтому не так много реализовать в нем что-то вроде Parsec. Вот один из примеров того, как это сделать: http://jparsec.codehaus.org/NParsec+Tutorial

Также возможно реализовать комбинацию Packrat, но на этот раз сохранить глобальное синтаксическое состояние где-то вместо того, чтобы делать чистый функциональный материал. В моей (очень простой и ad hoc) реализации это было достаточно быстро, но, конечно, генератор кода, такой как this, должен работать лучше.

Ответ 4

Я знаю, что немного опоздал, но я только что опубликовал библиотеку генераторов парсера/грамматики/AST по имени Ve Parser. вы можете найти его в http://veparser.codeplex.com или добавить в свой проект, набрав "Install-Package veparser" в консоли диспетчера пакетов. Эта библиотека является своего рода рекурсивным спускающим парсером, который призван быть простым в использовании и гибким. Поскольку его источник доступен для вас, вы можете узнать его исходники. Надеюсь, это поможет.

Ответ 5

На мой взгляд, существует лучший способ реализовать парсеры, чем традиционные методы, которые приводят к более простому и понятному коду, и особенно упрощает расширение любого языка, который вы разыгрываете, просто подключив новый класс в очень объектно-ориентированный. Одна статья большей серии, которую я написал, фокусируется на этом методе синтаксического анализа, а полный исходный код включен для анализатора С# 2.0: http://www.codeproject.com/Articles/492466/Object-Oriented-Parsing-Breaking-With-Tradition-Pa

Ответ 6

Ну... с чего начать с этого....

Прежде всего, напишите парсер, хорошо, что очень широкое выражение, особенно с вопросом, который вы задаете.

Ваше вступительное выражение состояло в том, что вам нужен простой арифметический "парсер", а технически это не парсер, он лексический анализатор, похожий на то, что вы можете использовать для создания нового языка. (http://en.wikipedia.org/wiki/Lexical_analysis) Я понимаю, где именно может возникнуть путаница в том, что это одно и то же. Важно отметить, что Лексический анализ ТАКЖЕ, что вы хотите понять, если вы собираетесь писать парсы языка /script тоже, это строго не анализирует, потому что вы интерпретируете инструкции, а не используете их.

Вернуться к вопросу разбора....

Это то, что вы будете делать, если вы берете жестко определенную файловую структуру для извлечения из нее информации.

В общем, вам действительно не нужно писать парсер для XML/HTML, потому что его уже много, и, тем более, если ваш синтаксический анализ XML создается во время выполнения .NET, тогда вы не даже нужно разбирать, вам просто нужно "сериализовать" и "де-сериализовать".

В интересах обучения, однако, разбор XML (или что-то подобное, как html) очень просто в большинстве случаев.

если мы начнем со следующего XML:

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

мы можем загрузить данные в XElement следующим образом:

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

вы можете получить в корневом элементе 'фильмы, используя ' myXML.Root '

MOre интересно однако, вы можете легко использовать Linq для получения вложенных тегов:

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

Предоставляет вам var XElements, каждый из которых содержит один "...", который вы можете использовать при использовании somthing like:

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

Для чего-либо другого, кроме XML, как структуры данных, то я боюсь, что вам придётся начать изучать искусство регулярных выражений, такой инструмент, как "Regular Expression Coach", поможет вам в истинности (http://weitz.de/regex-coach/) или один из наиболее употребительных аналогичных инструментов.

Вам также нужно будет познакомиться с объектами регулярного выражения .NET(http://www.codeproject.com/KB/dotnet/regextutorial.aspx) должно дать вам хороший старт.

Как только вы знаете, как работает ваш рег-ex файл, в большинстве случаев это простой случай чтения в файлах по одной строке за раз и с пониманием того, с каким методом вы себя чувствуете.

Хороший бесплатный источник форматов файлов для всего, что вы можете себе представить, можно найти на (http://www.wotsit.org/)

Ответ 7

Для записи я реализовал генератор синтаксического анализатора в С# только потому, что не смог найти работу, которая была бы нормальной или похожей на YACC (см. http://sourceforge.net/projects/naivelangtools/).

Однако после некоторого опыта работы с ANTLR я решил пойти с LALR вместо LL. Я знаю, что теоретически LL проще реализовать (генератор или парсер), но я просто не могу жить со стеком выражений, чтобы выразить приоритеты операторов (например, * идет до + в "2 + 5 * 3" ). В LL вы говорите, что mult_expr встроен в add_expr, что для меня не кажется естественным.