Какой лучший способ написать парсер вручную?

Ответ 1

Я бы очень рекомендовал язык F # в качестве вашего языка для разбора на платформе .NET. Он коренится в семействе языков ML, что означает, что он отлично поддерживает языковое программирование.

Дискриминационные союзы и сопоставление образцов позволяют получить очень сжатую и мощную спецификацию вашего АСТ. Функции более высокого порядка позволяют определять операции разбора и их состав. Первоклассная поддержка монадических типов позволяет управлять государственным управлением, неявно значительно упрощая состав парсеров. Мощный тип-вывод значительно помогает определению этих (сложных) типов. И все это может быть указано и выполнено интерактивно, что позволяет быстро прототипировать.

Стефан Тольксдорф применил это к практике со своей библиотекой комбинаторов парсеров FParsec

Из его примеров видно, как естественно указывается AST:

type expr =
    | Val of string
    | Int of int
    | Float of float
    | Decr of expr

type stmt =
    | Assign of string * expr
    | While of expr * stmt
    | Seq of stmt list
    | IfThen of expr * stmt
    | IfThenElse of expr * stmt * stmt
    | Print of expr

type prog = Prog of stmt list

реализация синтаксического анализатора (частично исключенная) так же кратка:

let stmt, stmtRef = createParserForwardedToRef()

let stmtList = sepBy1 stmt (ch ';')

let assign =
    pipe2 id (str ":=" >>. expr) (fun id e -> Assign(id, e))

let print = str "print" >>. expr |>> Print

let pwhile =
    pipe2 (str "while" >>. expr) (str "do" >>. stmt) (fun e s -> While(e, s))

let seq =
    str "begin" >>. stmtList .>> str "end" |>> Seq

let ifthen =
    pipe3 (str "if" >>. expr) (str "then" >>. stmt) (opt (str "else" >>. stmt))
          (fun e s1 optS2 ->
               match optS2 with
               | None    -> IfThen(e, s1)
               | Some s2 -> IfThenElse(e, s1, s2))

do stmtRef:= choice [ifthen; pwhile; seq; print; assign]


let prog =
    ws >>. stmtList .>> eof |>> Prog

Во второй строке, в качестве примера, stmt и ch являются синтаксическими анализаторами, а sepBy1 - это комбинатор синтаксического анализатора, который принимает два простых синтаксических анализатора и возвращает парсер комбинаций. В этом случае sepBy1 p sep возвращает парсер, который анализирует одно или несколько вхождений p, разделенных символом sep. Таким образом, вы можете увидеть, как быстро мощный синтаксический анализатор можно объединить с простыми парсерами. Поддержка F # для переопределенных операторов также допускает краткую инфиксную нотацию, например. комбинатор последовательности и комбинатор выбора могут быть указаны как >>. и <|>.

Желаем удачи,

Дэнни

Ответ 2

Единственный вид парсера, который может быть написан рукописным человеком разумным человеком, - это рекурсивный спуск. Тем не менее, запись парсера снизу вверх по-прежнему возможна, но очень нежелательна.

Если вы используете парсер RD, вам нужно проверить, что грамматика SQL не является леворекурсивной (и, при необходимости, исключает рекурсию), а затем в основном записывает функцию для каждого правила грамматики. Подробнее см. .

Ответ 3

Рекурсивный спуск даст вам самый простой способ пойти, но я должен согласиться с mouviciel, который сгибает и бизона и определенно стоит изучать. Когда вы узнаете, что у вас есть ошибка в вашей грамматике, определение определения языка в flex/bison будет намного проще, чем переписать ваш рекурсивный код спуска.

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

Ответ 4

Добавление моего голоса к хору в пользу рекурсивного спуска (LL1). Они просты, быстры, и ИМО, и не всегда трудно поддерживать.

Однако, внимательно посмотрите на свой язык, чтобы убедиться, что он LL1. Если у вас есть какой-либо синтаксис, например C, например ((()) foo) []), где вам может потребоваться спустить несколько слоев круглых скобок, прежде чем вы узнаете, тип, переменная или выражение, тогда LL1 будет очень сложным, а выигрыш снизу вверх.

Ответ 5

Анализаторы рекурсивного спуска действительно лучшие, возможно, только парсеры, которые могут быть созданы вручную. Вам все равно придется придираться к тому, что именно формальный, контекстно-свободный язык, и поместить ваш язык в нормальную форму. Я лично предложил бы удалить левую рекурсию и поместить ваш язык в Greibach Normal Form. Когда вы это делаете, синтаксический анализатор сам записывает себя.

Например, это произведение:

A => aC 
A => bD
A => eF

становится чем-то простым:

int A() {
   chr = read();
   switch char
     case 'a': C();
     case 'b': D();
     case 'e': F();
     default: throw_syntax_error('A', chr);
}

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

Anton Link также кажется отличным.

Ответ 6

Если вы хотите написать его вручную, рекурсивный порядочный - самый разумный способ.

Вы можете использовать парсер таблицы, но это будет очень сложно поддерживать.

Пример:

Data = Object | Value;
Value = Ident, '=', Literal;
Object = '{', DataList, '}';
DataList = Data | DataList, Data;


ParseData {
  if PeekToken = '{' then 
    return ParseObject;
  if PeekToken = Ident then
    return ParseValue;
  return Error;
}

ParseValue {
  ident = TokenValue;
  if NextToken <> '=' then 
    return Error;
  if NextToken <> Literal then
    return Error;
  return(ident, TokenValue);
 }

ParseObject {
  AssertToken('{');
  temp = ParseDataList;
  AssertToken('}');
  return temp;
}

ParseDataList {
  data = ParseData;
  temp = []
  while Ok(data) {
    temp = temp + data;
    data = ParseData;
  }
}

Ответ 7

Я предлагаю вам не писать lexer с помощью гибкого использования или подобного. Задача распознавания жетонов не так уж трудно сделать вручную, но я не думаю, что вы многое выиграли.

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

Я уверен, что ANTLR в любом случае реализует рекурсивный парсер спуска: там упоминание о нем в интервью об ANTLR 3.0.

Я также нашел серию сообщений в блоге о написании парсера на С#. Это кажется довольно нежным.

Ответ 8

Рискуя оскорблять ОП, написание парсера для большого langauge, например, определенного конкретного поставщика SQL вручную, когда доступны инструменты генератора синтаксического анализатора (такие как ANTLR), просто сумасшедшие. Вы потратите гораздо больше времени на переписывание своего парсера вручную, чем исправление "крайних случаев" с использованием генератора парсера, и вам всегда придется возвращаться и пересматривать парсер в любом случае по мере того, как стандарты SQL двигаются или вы обнаружите, что вы неправильно поняли что-то другое. Если вы не понимаете свою технологию синтаксического анализа достаточно хорошо, потратьте время, чтобы понять это. Вам не зайдут месяцы, чтобы выяснить, как бороться с крайними случаями с генератором синтаксического анализатора, и вы уже признались, что готовы потратить месяцы на это вручную.

Сказав это, если вы чертовски переделаете его вручную, использование рекурсивного парсера спуска - лучший способ сделать это вручную.

(ПРИМЕЧАНИЕ: ОП разъяснено ниже, что он хочет выполнить ссылочную реализацию. ИМХО, вы НИКОГДА не должны кодировать ссылочную реализацию грамматики процедурно, поэтому рекурсивный спуск отсутствует.)

Ответ 9

Нет "одного наилучшего" способа. В зависимости от ваших потребностей вам может понадобиться снизу вверх (LALR1) или рекурсивный спуск (LLk). Статьи такие как этот, приводят личные причины для предпочтения LALR (1) (снизу вверх) до LL (k). Однако каждый тип анализатора имеет свои преимущества и недостатки. Обычно LALR будет быстрее, чем finite-state_machine создается как таблица поиска.

Чтобы выбрать, какое право для вас исследует вашу ситуацию; ознакомьтесь с инструментами и технологиями. Начиная с некоторого LALR и LL Статьи в Википедии - неплохой выбор. В обоих случаях вы должны ВСЕГДА начать с указания грамматики в BNF или EBNF. Я предпочитаю EBNF за его лаконичность.

После того, как вы увлеклись тем, что хотите, и как представить его в виде грамматики (BNF или EBNF), попробуйте несколько различных инструментов и запустите их через репрезентативные образцы текста для анализа.

Занимательно:

Однако я слышал, что LL (k) более гибкий. Я никогда не удосужился узнать для себя. Из моих опытов по созданию парсеров я заметил, что если LALR или LL (k) лучше всего выбрать то, что лучше всего подходит вам, начните с написания грамматики. Я написал свою собственную библиотеку шаблонов шаблонов парсеров для сценариев Java С++ EBNF, использовал Lex/YACC и закодировал небольшой парсер R-D. Это было распространено в течение большей части 15 лет, и я провел не более двух месяцев в самом длинном из трех проектов.

Ответ 10

В C/Unix традиционным способом является использование lex и yacc. С GNU эквивалентными инструментами являются flex и bison. Я не знаю, для Windows/С#.

Ответ 11

Если бы я был вами, я бы попробовал еще один ANTLRv3, используя GUI ANTLRWorks, который дает вам очень удобный способ проверки вашей грамматики. Мы используем ANTLR в нашем проекте, и хотя кривая обучения может быть немного крутой в начале, как только вы узнаете, что это довольно удобно. Также в их бюллетене электронной почты есть много людей, которые очень полезны.

PS. IIRC у них также есть SQL-грамматика, на которую вы можете взглянуть.

HTH

Ответ 12

Ну, если вы не возражаете использовать другой компилятор компилятора, например ANTLR, я предлагаю вам взглянуть на Coco/R

Я использовал его в прошлом, и это было очень хорошо...

Ответ 13

Причина, по которой вам не нужен парсер, ориентированный на таблицы, заключается в том, что вы не сможете создавать разумные сообщения об ошибках. Это нормально для сгенерированного языка, но не для тех, в которых задействованы люди. Сообщения об ошибках, создаваемые c-подобными языковыми компиляторами, дают достаточные доказательства того, что люди могут адаптироваться к чему угодно, независимо от того, насколько они плохи.

Ответ 14

Я также проголосую за использование существующего парсера + лексера.

Единственная причина, по которой я могу это сделать вручную:

• если вы хотите что-то относительно простое (например, проверка/разбор некоторого ввода)
• чтобы узнать/понять принципы.

Ответ 15

JFlex - это гибкая реализация для Java, и теперь есть порт С# этого проекта http://sourceforge.net/projects/csflex/. Там также появляется С# порт CUP, который можно найти здесь: http://sourceforge.net/projects/datagraph/

Я бы тоже рекомендовал избегать ручной обработки вашего собственного решения. Я попробовал это однажды сам для очень простого языка (часть университетского проекта), и это было невероятно трудоемким и сложным. Это также чрезвычайно сложно поддерживать и изменять после написания.

Использование существующего генератора синтаксического анализа - это путь, так как основная часть тяжелой работы была выполнена и была хорошо проверена на протяжении многих лет.

Ответ 16

Посмотрите на генераторы gplex и gppg, lexer и parser для .NET. Они работают хорошо и основаны на том же (и почти совместимом) вводе как lex и yacc, который относительно прост в использовании.