parsing - gnu bison

Desarrollando un analizador simple

Question

Mi trabajo diario incluye trabajar para desarrollar un compilador similar a Pascal. He estado trabajando todo el tiempo en optimizaciones y generación de código.

También me gustaría comenzar a aprender a construir un analizador simple para el mismo idioma. Sin embargo, no estoy muy seguro de cómo hacerlo. Flex y Bison parecen ser la opción. Pero, ¿no es posible escribir un analizador usando C ++ o C #? Estoy un poco escalofriante con C.

Yacc ++ admite C #, pero es uno con licencia. Estoy buscando toda la ayuda que puedo encontrar en este sentido. Las sugerencias serían muy apreciadas.

Answer 1

Creo que puedes usar ANTLR con C #. Nunca lo intenté yo mismo (todavía), sin embargo, hay un tutorial aquí que puede orientarlo en la dirección correcta.

Answer 2

En realidad puedes usar flex & bison con C ++. En este tutorial , por ejemplo, puede ver que la sección 5 está dedicada a ese asunto. Simplemente busque google, y estoy seguro de que encontrará muchos ejemplos.

Answer 3

Si lo estuvieras escribiendo en Java, recomendaría ANTLR. Es un buen generador de analizadores de LL (*) escrito en Java. También hay un excelente libro para Amazon.

Answer 4

bison & flex son los generadores de analizadores canónicos. Si estás interesado en C ++, he encontrado útil el espíritu de impulso . Nunca lo he usado para nada tan complejo como un compilador. Estoy seguro de que otros tendrán sugerencias interesantes para otros idiomas, como C # ...

Answer 5

En su clásico texto de programación, Algorithms + Data Structures = Programs , Niklaus Wirth desarrolla un analizador de descenso recursivo completo (en Pascal) para un lenguaje simple parecido a Pascal0.

Answer 6

Personalmente, saco mi propio lector y analizador (LL). Aquí hay un ejemplo muy abreviado. Está en C ++, pero espero que puedas adaptarlo. Hace uso de una macro PARSE_HIGHER para facilitar la inserción de operadores en diferentes niveles de precedencia sin mucho cambio de código.

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

Se ha agregado una sintaxis de sentencia estilo 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 */
  }
}

Aún necesita sintaxis para la indexación de matrices, la declaración de variables y la definición de funciones, pero espero que esté claro cómo hacerlo.

Answer 7

He escrito un analizador XSLT con flex y bison. Más últimamente estoy haciendo un proyecto usando ANTLR, sin embargo:

¿La sintaxis del lenguaje JFig es eficiente y clara (y mejor que la XML DSL de Spring-Framework)?

Me gustó trabajar en ANTLR mucho más que Flex y Bison. ANTLR te pone en un nivel más alto de abstracción en algunos aspectos. Las definiciones léxicas y la gramática del analizador pueden ir en un solo archivo. (ANTLR generará el archivo token)

Uno de los elementos clave es la capacidad de definir gramáticas arbóreas. Básicamente, usted hace un análisis gramatical sobre el idioma de entrada y tiene acciones que se reescriben en una salida de árbol AST altamente óptima (que permanecen como estructuras de datos vinculadas en la memoria). A continuación, puede pasar este árbol a otro analizador definido en un archivo analizador de árbol separado. El analizador de árbol es donde realiza el trabajo real de los elementos de acción que desea.

Este es un enfoque agradable ya que puede mantener el formulario AST y reprocesarlo repetidamente según sea necesario, eliminando nodos de subárbol específicos para procesar en función de acciones posteriores, etc. Piense en algo así como un intérprete de lenguaje. En lugar de entrar en un bucle for y procesar el lenguaje desde cero una y otra vez, solo puede procesar a través de su representación AST.

En mi caso, he ideado una fábrica de frijoles para hacer la inyección de dependencia de IoC. Mi fábrica de beans mantiene el AST de un descriptor de beans en tiempo de ejecución. Cuando necesita crear (o recuperar) una nueva instancia de bean, simplemente paso el subárbol AST de descriptor de bean a mi analizador de árbol: el resultado es la instancia de bean deseada (hay muchos factores que influyen para determinar cómo crear una instancia del beans solicitados, incluyendo hacer otros beans a los que se hace referencia y / o aplicar otros comportamientos especiales a través de meta atributos).

Finalmente, mi fábrica actual de beans está orientada a Java, pero quiero apuntar a ActionScript3 y C # .NET. ANTLR tiene soporte para hacerlo.

Como se mencionó, Terrence Parr ha escrito un libro sobre cómo usar ANTLR. Está dirigido a programadores que trabajan y necesitan hacer algo práctico con ANTLR (a diferencia de un tratamiento académico del tema).

Answer 8

Si quieres C # según esta Pregunta, prueba Gardens Point GPPG y GPLEX.

Answer 9

Cuando usas Lex y Yacc, en realidad no escribes mucho de nada en C. Lex es su propio idioma, como lo es Yacc. Entonces escribes el analizador léxico en Lex y el analizador en Yacc . Sin embargo, para Pascal, las entradas Lex y Yacc ya están disponibles .

El analizador y el lexer resultantes tienen interfaces C, eso es cierto. Sin embargo, la mayoría de los lenguajes, incluido C ++, tienen formas simples de invocar (o envolver) las interfaces C.

No soy un experto en eso, pero estoy seguro de que todo lo anterior también se aplica a ANTLR.

Si estás pidiendo hacerlo en "puro C ++" (lo que sea que eso signifique), busca usar el espíritu de impulso. Realmente no veo el punto en pureza teórica si causa mucho trabajo.

Escribir sus propios lexers y analizadores a mano es en realidad un poco divertido. Un lexer es una de las pocas situaciones en las que puede justificar el uso tanto de goto como del preprocesador. Sin embargo, no lo sugeriría para un lenguaje completo como Pascal si puedes evitarlo. Eso sería mucho trabajo. Estoy hablando de años hombre.