logo标签列表

开发一个简单的解析器

parsingbisonflex-lexer
4

我的日常工作包括开发类似Pascal的编译器。我一直在优化和代码生成方面工作。

我还想开始学习为同一语言构建一个简单的解析器。然而，我不太确定如何着手。Flex和Bison似乎是首选。但是，使用C++或C#编写解析器是否可能？我对C有点生疏。

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

这个问题有点奇怪。你正在为一种语言构建一个编译器，但是你没有该语言的解析器？这种情况是如何出现的？ - S.Lott
那就是现实。我不认为我应该在这里谈论我的雇主的决定。他们显然有一些错误，但没关系，项目正在顺利进行。 - DevStash
Pascal解析器作为近似LL（1）语言通常采用递归下降。有关几个解析器的示例（编译器级别或更多地侧重于文档和语法高亮显示），请参见Free Pascal / Lazarus项目。据我所知，他们的文档解析器是库的一部分，因此受到轻松许可证（LGPL +静态链接例外）的保护。 - Marco van de Voort
9个回答
6

我相信你可以在C#中使用ANTLR。虽然我自己从未尝试过，但这里有一个教程here可能会指引你正确的方向。

我自己从未使用过ANTLR，但听说它很不错。如果我能像使用lex+yacc一样找到预先制作的Pascal语法，那么在你的位置上，我可能会尝试使用它。 - T.E.D.
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 */
  }
}

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

2
这种类型的解析器在处理简单表达式时还可以，但一旦语言变得比较复杂，涉及到循环、条件语句、函数等等，代码就会变得非常棘手。也许如果实现得当还好，但是什么才是“正确”的呢？ - user21826
1
好的，就像我说的那样，这只是一个非常简略的例子。它没有问题处理任何LL1语法。这个例子处理表达式语法。如果你愿意，我可以加入一些语句语法。这就是使用SeeWord词法分析器的地方。 - Mike Dunlavey
好的，我添加了一些语句语法。希望你能看懂并继续完成。 - Mike Dunlavey
1
重点是，当涉及到超越简单过程式编程的语言时，使用类似LEX和YACC这样的工具可能更容易且更易于维护。 - user21826
YACC对于LR（移位-规约）语言是必要的，特别是那些具有复杂类型声明语法的语言，例如C、C ++、Java、C#。如果您正在使用Pascal或自己的语言，如果找不到您喜欢的工具，上述技术可以做任何LL解析器，可以证明如此。 - Mike Dunlavey
就可维护性而言，LL解析器生成器中的规则1-1映射到递归例程（如上所述），事实上这就是它们可以生成的内容。除此之外，说它易于维护只是说它是个人偏好。但还是感谢您的意见。 - Mike Dunlavey
1
在他的经典编程著作《算法+数据结构=程序》中，尼古劳斯·维尔特为一种类似于Pascal0的简单语言开发了一个完整的递归下降解析器（使用Pascal语言实现）。
0
如果你要用Java写的话，我会推荐ANTLR。它是一个很好的LL(*)解析器生成器，用Java编写。在亚马逊上还有一本非常棒的书。
我很喜欢使用Java。但是，我已经爱上了C++和C#。然而，ANTLR似乎是正确的选择。既然这是一个业余项目，我会考虑用Java来构建它。谢谢。在我开始之前还有什么建议吗？ - DevStash
1
ANTLR可以为许多目标生成代码：http://www.antlr.org/wiki/display/ANTLR3/Code+Generation+Targets - gimel
0

bison和flex是经典的解析器生成器。如果你对C++感兴趣，我发现boost spirit很有用。虽然我从未将其用于像编译器这样复杂的东西。我相信其他人会对其他语言（如C#）提出有趣的建议...

0

您实际上可以在C++中使用Flex和Bison。例如，在这个教程中，您可以看到第5节专门介绍了这个问题。只需在谷歌上搜索，我相信您会找到很多例子。

0
当你使用Lex和Yacc时，实际上你不需要在C中写很多东西。Lex是自己的语言，Yacc也是如此。因此，你可以在Lex中编写词法分析器，在Yacc中编写解析器。然而，对于Pascal，Lex和Yacc的输入已经可用。
生成的解析器和词法分析器具有C接口，这是真的。然而，大多数语言，包括C++，都有简单的方法来调用（或包装）C接口。
我不是专家，但我相信以上所有内容也适用于ANTLR。
如果你想要在“纯C ++”中进行（无论那意味着什么），请考虑使用boost spirit。但是，如果这会导致更多的工作量，我真的看不出理论纯度的意义所在。

手写自己的词法分析器和语法分析器其实挺有趣的。词法分析器是极少数情况下可以正当使用goto和预处理器的场景之一。然而，如果可以避免的话，我不建议在像Pascal这样的完整语言中使用它。那将需要大量工作，我说的是人年。

0

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

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

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

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

这是一个不错的方法，因为您可以保持AST形式，并根据需要重复处理它 - 基于后续操作从中剥离特定子树节点进行处理等。将其视为语言解释器。与其进入for循环并一遍又一遍地从头开始处理语言，可以通过其AST表示仅处理它。

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

最后，我的当前bean工厂面向Java，但我想面向ActionScript3和C# .NET。ANTLR支持这样做。

正如提到的那样，Terrence Parr编写了一本有关如何使用ANTLR的书。它旨在面向需要在ANTLR上实现实际操作的工作程序员（而不是学术性的主题阐述）。

0
如果你想要使用C#，可以尝试使用Gardens Point GPPG和GPLEX。问题。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接