4

我的日常工作包括开发一个类似 Pascal 的编译器。我一直致力于优化和代码生成。

我也想开始学习为同一种语言构建一个简单的解析器。但是，我不确定该怎么做。Flex 和 Bison 似乎是首选。但是，难道不能使用 C++ 或 C# 编写解析器吗？我对C有点毛骨悚然。

Yacc++ 支持 C#，但它是一个许可的。我正在寻找在这方面我能找到的所有帮助。建议将不胜感激。

4

9 回答 9

6

我相信您可以将 ANTLR 与 C# 一起使用。我自己（还）从未尝试过，但是这里有一个教程可能会为您指明正确的方向。

于 2008-12-24T14:05:21.953 回答
5

就个人而言，我推出了自己的词法分析器和解析器 (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 */
  }
}

它仍然需要数组索引、变量声明和函数定义的语法，但我希望清楚如何做到这一点。

于 2008-12-24T14:59:31.283 回答
1

在他的经典编程文本Algorithms + Data Structures = Programs中，Niklaus Wirth 为一种简单的类似 Pascal0 的语言开发了一个完整的递归下降解析器（在 Pascal 中）。

于 2008-12-27T05:45:31.477 回答
0

如果您使用 Java 编写它，我会推荐 ANTLR。这是一个用 Java 编写的不错的 LL(*) 解析器生成器。亚马逊上也有一本很棒的书。

于 2008-12-24T13:47:56.280 回答
0

bison & flex 是规范的解析器生成器。如果您对 C++ 感兴趣，我发现boost spirit很有用。不过，我从来没有将它用于像编译器这样复杂的东西。我相信其他人会对其他语言（例如 C#）提出有趣的建议...

于 2008-12-24T13:48:35.357 回答
0

您实际上可以在 C++ 中使用 flex & bison。例如，在本教程中，您可以看到第 5 节专门讨论这个问题。只需 google 一下，我相信你会找到很多例子。

于 2008-12-24T14:02:08.247 回答
0

当您使用 Lex 和 Yacc 时，您实际上并没有用 C 编写任何东西。Lex是它自己的语言，Yacc 也是如此。因此，您在 Lex 中编写词法分析器，在Yacc中编写解析器。但是，对于 Pascal，Lex 和 Yacc 输入已经可用。

生成的解析器和词法分析器具有 C 接口，这是真的。然而，包括 C++ 在内的大多数语言都有调用（或包装）C 接口的简单方法。

我不是这方面的专家，但我确信以上所有内容也适用于 ANTLR。

如果您要求在“纯 C++”（无论这意味着什么）中执行此操作，请考虑使用 boost spirit。如果它导致更多的工作，我真的不明白理论上的纯度有什么意义。

手动编写自己的词法分析器和解析器实际上很有趣。词法分析器是极少数可以同时使用goto和预处理器的情况之一。但是，如果可以避免的话，我不建议将它用于像 Pascal 这样的成熟语言。那将是很多工作。我说的是人年。

于 2008-12-24T14:18:07.903 回答
0

我用 flex 和 bison 编写了一个 XSLT 解析器。不过，最近我正在使用 ANTLR 做一个项目：

JFig 语言语法是否高效且清晰（并且比 Spring-Framework 的 XML DSL 更好）？

比起 Flex 和 Bison，我更喜欢在 ANTLR 工作。ANTLR 在某些方面使您处于更高的抽象级别。词法定义和解析器语法都可以放在一个文件中。（ANTLR 将生成令牌文件。）

关键项目之一是定义树语法的能力。基本上，您对输入语言进行语法分析，并执行重写为高度优化的 AST 树输出的操作（在内存中保留为链接数据结构）。然后，您可以将此树传递给在单独的树解析器文件中定义的另一个解析器。树解析器是您执行所需操作项的实际工作的地方。

这是一种很好的方法，因为您可以保留 AST 表单并根据需要反复对其进行重新处理——根据后面的操作等剥离特定的子树节点以进行处理。想想像语言解释器这样的东西。无需进入 for 循环并一遍又一遍地从头开始处理语言，只需处理它的 AST 表示即可。

在我的例子中，我设计了一个 bean factory 来进行 IoC 依赖注入。我的 bean 工厂在运行时保留 bean 描述符的 AST。当它需要创建（或检索）一个新的 bean 实例时，我只需将 bean 描述符 AST 子树传递给我的树解析器 - 结果是所需的 bean 实例（有很多因素决定如何实例化请求的 bean，包括制作任何其他被引用的 bean 和/或通过元属性应用其他特殊行为）。

最后，我当前的 bean factory 以 Java 为目标，但我想以 ActionScript3 和 C# .NET 为目标。ANTLR 支持这样做。

如前所述，Terrence Parr 写了一本关于如何使用 ANTLR 的书。它面向需要使用 ANTLR 做一些实际事情的工作程序员（而不是对该主题的学术处理）。

于 2008-12-24T19:36:58.493 回答
0

如果您按照这个问题想要 C#，请尝试 Gardens Point GPPG 和 GPLEX。

于 2009-07-02T00:30:58.493 回答