Вопрос

В мою повседневную работу входит разработка компилятора, подобного Паскалю.Я все время работал над оптимизацией и генерацией кода.

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

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

Это было полезно?

Решение

Я считаю, что вы можете использовать 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 */
  }
}

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

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

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

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

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

Я написал парсер 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 (в отличие от академической трактовки предмета).

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top