Разработка простого парсера

Я считаю, что вы можете использовать ANTLR с C #. Сам (пока) не пробовал, но есть учебник здесь, которая может указать вам правильное направление.

Лично я накатываю свой лексер и парсер (LL). Вот очень сокращенный пример. Он написан на C ++, но, надеюсь, вы сможете его адаптировать. Он использует макрос PARSE_HIGHER, чтобы упростить вставку операторов с разными уровнями приоритета без значительного изменения кода.

 // routine to scan over whitespace/comments
void ScanWhite(const char* &pc){
  while(true){
    if(0);
    else if (WHITESPACE(*pc)) pc++;
    else if (pc[0]=='/' && pc[1]=='/'){
      while(*pc && *pc++ != '\n');
    }
    else break;
  }
}
// routine to lex an identifier
bool SeeId(const char* &pc, string sId){
  ScanWhite(pc);
  const char* pc0 = pc;
  if (alpha(*pc)){
    sId = "";
    while(alphanum(*pc)) sId += (*pc++);
    return true;
  }
  pc = pc0;
  return false;
}
// routine to lex a number
bool SeeNum(const char* &pc, double &dNum){
  ScanWhite(pc);
  const char* pc0 = pc;
  if (digit(*pc)){
    dNum = 0;
    while(digit(*pc)) dNum = dNum * 10 + (*pc++ - '0');
    if (*pc == '.'){
      double divisor = 1, frac = 0;
      while(digit(*pc)){
        divisor *= 0.1;
        frac += (*pc++ - '0') * divisor;
      }
      dNum += frac;
    }
    return true;
  }
  pc = pc0;
  return false;
}
// routine to lex some constant word
bool SeeWord(const char* &pc, const char* sWord){
  ScanWhite(pc);
  const char* pc0 = pc;
  int len = strlen(sWord);
  if (strncmp(pc, sWord, len)==0 && !alphanum(pc[len])){
    pc += len;
    return true;
  }
  pc = pc0;
  return false;
}
// routine to lex a single character like an operator
bool SeeChar(const char* &pc, const char c){
  ScanWhite(pc);
  const char* pc0 = pc;
  if (*pc == c){
    pc++;
    return true;
  }
  pc = pc0;
  return false;
}
// primitive expression parser
void ParsePrimitiveExpr(const char* &pc, CNode* &p){
  double dNum;
  char sId[100];
  if (0);
  else if (SeeNum(pc, dNum)){
    p = new CNode(dNum);
  }
  else if (SeeId(pc, sId)){
    // see if its a function call
    if (SeeChar(pc, '(')){
      p = MakeNewFunctionCallNode(sId);
      while(!SeeChar(pc, ')')){
        CNode* p1 = null;
        ParseExpression(pc, p1);
        AddArgumentExprToFunctionCallNode(p, p1);
        SeeChar(pc, ','); /* optional comma separator */
      }
    }
    // otherwise its just a variable reference
    else {
      p = new CNode(sId);
    }
  }
  // handle embedded expressions
  else if (SeeChar(pc, '(')){
    ParseExpression(pc, p);
    if (!SeeChar(pc, ')')) /* deal with syntax error */
  }
}
#define PARSE_HIGHER ParsePrimitiveExpr
// product parser
void ParseProduct(const char* &pc, CNode* &p){
  PARSE_HIGHER(pc, p);
  while(true){
    if (0);
    else if (SeeChar(pc, '*')){
      CNode p1 = null;
      PARSE_HIGHER(pc, p1);
      p = new CNode('*', p, p1);
    }
    else if (SeeChar(pc, '/')){
     CNode p1 = null;
     PARSE_HIGHER(pc, p1);
     p = new CNode('/', p, p1);
   }
   else break;
  }
}
#undef  PARSE_HIGHER
#define PARSE_HIGHER ParseProduct
// sum parser
void ParseSum(const char* &pc, CNode* &p){
  PARSE_HIGHER(pc, p);
  while(true){
    if (0);
    else if (SeeChar(pc, '+')){
      CNode p1 = null;
      PARSE_HIGHER(pc, p1);
      p = new CNode('+', p, p1);
    }
    else if (SeeChar(pc, '-')){
      CNode p1 = null;
      PARSE_HIGHER(pc, p1);
      p = new CNode('-', p, p1);
    }
   else break;
  }
}
#undef  PARSE_HIGHER
// can insert more routines like the above
// to handle move operators
#define PARSE_HIGHER ParseSum
// overall expression parser
void ParseExpression(const char* &pc, CNode* &p){
  PARSE_HIGHER(pc, p);
}

Добавлен синтаксис операторов в стиле Паскаля:

void ParseStatement(const char* &pc){
  char sId[100];
  if(0);
  else if (SeeWord(pc, "begin")){
    while(!SeeWord(pc, "end")){
      ParseStatement(pc);
      SeeChar(pc, ';');
    }
  }
  else if (SeeWord(pc, "while")){
    CNode* p1 = null;
    ParseExpression(pc, p1);
    ParseStatement(pc);
    /* semantics for while statement */
  }
  else if (SeeWord(pc, "if")){
    CNode* p1 = null;
    ParseExpression(pc, p1);
    ParseStatement(pc);
    if (SeeWord(pc, "else")){
      ParseStatement(pc);
    }
    /* semantics for if statement */
  }
  else if (SeeWord(pc, "for")){
    /* you do it */
  }
  // handle assignments and subroutine calls
  else if (SeeId(pc, sId)){
    if(0);
    else if (SeeChar(pc, '=')){
      CNode* p1 = null;
      ParseExpression(pc, p1);
      /* semantics for assignment statement */
    }
    else if (SeeChar(pc, '(')){
      CNode* p = MakeNewFunctionCallNode(sId);
      while(!SeeChar(pc, ')')){
        CNode* p1 = null;
        ParseExpression(pc, p1);
        AddArgumentExprToFunctionCallNode(p, p1);
        SeeChar(pc, ','); /* optional comma separator */
      }
    }
    else {
      /* we have a 1-word statement, which is OK in pascal */
    }
  }
  else {
    /* syntax error */
  }
}

Ему по-прежнему нужен синтаксис для индексации массивов, объявления переменных и определения функций, но я надеюсь, что понятно, как это сделать.

В своем классическом тексте по программированию Алгоритмы + структуры данных = Программы Никлаус Вирт разрабатывает полный рекурсивный анализатор спуска (на Паскале) для простого языка, подобного Паскалю.

Если бы вы писали это на Java, я бы порекомендовал ANTLR. Хороший парсер-генератор LL (*), написанный на Java. На Amazon тоже есть потрясающая книга.

bison и flex - канонические генераторы парсеров. Если вас интересует C ++, я нашел полезным boost spirit. Однако я никогда не использовал его для чего-то более сложного, чем компилятор. Я уверен, что у других появятся интересные предложения для других языков, таких как C # ...

На самом деле вы можете использовать flex & bison с C ++. Например, в этом руководстве вы можете увидеть, что раздел 5 посвященный этому вопросу. Просто погуглите, и я уверен, что вы найдете множество примеров.

Я написал синтаксический анализатор XSLT с помощью flex и bison. Однако в последнее время я делаю проект с использованием ANTLR:

является эффективным синтаксисом языка JFig и ясно (и лучше, чем XML DSL Spring-Framework)?

Мне гораздо больше понравилось работать в ANTLR, чем в Flex и Bison. ANTLR в некоторых отношениях поднимает вас на более высокий уровень абстракции. Лексические определения и грамматика парсера могут храниться в одном файле. (ANTLR сгенерирует файл токена.)

Одним из ключевых моментов является возможность определять древовидные грамматики. В основном вы выполняете синтаксический анализ грамматики на языке ввода и выполняете действия, которые переписываются в высокооптимальное дерево вывода AST (которое остается в виде связанных структур данных в памяти). Затем вы можете передать это дерево другому парсеру, определенному в отдельном файле парсера дерева. Анализатор дерева - это то место, где вы выполняете реальную работу с элементами действий, которые вам нужны.

Это хороший подход, поскольку вы можете сохранить форму AST и повторно обрабатывать ее по мере необходимости - отслаивая определенные узлы поддерева для обработки на основе последних действий и т. Д. Подумайте о чем-то вроде интерпретатора языка. Вместо того, чтобы заходить в цикл for и снова и снова обрабатывать язык с нуля, можно просто обрабатывать его AST-представление.

В моем случае я разработал bean-фабрику для внедрения зависимостей IoC. Моя фабрика компонентов хранит AST дескриптора компонента во время выполнения. Когда ему нужно создать (или получить) новый экземпляр компонента, я просто передаю поддерево AST дескриптора компонента своему парсеру дерева - результатом является желаемый экземпляр компонента (существует множество факторов, которые влияют на определение того, как создать экземпляр объекта). запрошенный bean-компонент, включая создание любых других bean-компонентов, на которые есть ссылки, и / или применение других специальных действий через метаатрибуты).

Наконец, моя текущая фабрика компонентов ориентирована на Java, но я хочу ориентироваться на ActionScript3 и C # .NET. ANTLR поддерживает это.

Как уже упоминалось, Терренс Парр написал книгу о том, как использовать ANTLR. Он предназначен для работающих программистов, которым нужно делать что-то практическое с ANTLR (в отличие от академического подхода к предмету).

Если вы хотите C # в соответствии с этим вопросом попробуйте Gardens Point GPPG и GPLEX.

Когда вы используете Lex и Yacc, вы практически ничего не пишете на C. Lex это его собственный язык, как и Yacc. Итак, вы пишете лексический анализатор в Lex, а парсер в Yacc. Однако для Pascal входы Lex и Yacc уже доступны.

Получившийся синтаксический анализатор и лексер имеют интерфейсы C. Это правда. Однако в большинстве языков, включая C ++, есть простые способы вызова (или переноса) интерфейсов C.

Я не эксперт в этом, но уверен, что все вышеперечисленное относится и к ANTLR.

Если вы просите сделать это на "чистом C ++" (что бы это ни значило), попробуйте использовать дух boost. . Я действительно не вижу смысла в теоретической чистоте, если она требует еще больше работы.

Написание собственных лексических анализаторов и парсеров вручную на самом деле довольно забавно. Лексический анализатор - одна из немногих ситуаций, в которых можно оправдать использование как goto, так и препроцессора. Однако я бы не стал предлагать это для полноценного языка, такого как Паскаль, если вы можете этого избежать. Это будет много работы. Я говорю о человеко-годах.