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

Question

Моя дневная работа включает в себя работу по разработке Pascal-подобного компилятора Я все время работал над оптимизацией и генерацией кода.

Я также хотел бы начать учиться создавать простой парсер для того же языка. Я, однако, не совсем уверен, как это сделать. Флекс и Бизон, кажется, выбор. Но разве нельзя написать парсер с использованием C ++ или C #? Я немного жуткий с C.

Yacc ++ поддерживает C #, но он лицензирован. Я ищу всю помощь, которую я могу найти в этом отношении. Предложения будут высоко оценены.

Answer 1

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

Answer 2

Лично я катаю свой собственный лексер и парсер (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);
}

Добавлен некоторый синтаксис операторов в стиле Pascal:

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 */
  }
}

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

Answer 3

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

Answer 4

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

Answer 5

Я написал XSLT-парсер с flex и bison. Позже я делаю проект с использованием ANTLR, хотя:

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

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

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

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

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

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

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

Answer 6

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

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

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

Если вы просите сделать это на «чистом C ++» (что бы это ни значило), изучите использование boost spirit . На самом деле я не вижу смысла в теоретической чистоте, если это вызывает массу работы.

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

Answer 7

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

Answer 8

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

Answer 9

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