BNF 到 Lex 到 C 语言的解析器

Question

我正在尝试学习概念以及如何从 BNF 表示法而不是 EBNF 在 C 中创建词法分析器和解析器。我想用 C 语言学习它。

谁能向我解释一下我用来放入 C 中的词法分析器和解析器的 BNF 部分以及将它们放在哪里？比如也可以使用一个例子？我发现在解析器中，你放置了终端、非终端、标记、类型等...

地方

如果不清楚或其他什么，我很抱歉，我的头在这个谢谢你的

。 BNF 我有

<for_statement> ::= FOR <identifier> 
IS <expression> BY <expression> TO <expression> DO <statement_list> ENDFOR

词法分析器代码片段

ENDP                   printf("keyword: ENDP\n");
DECLARATIONS           printf("keyword: DECLARATIONS\n");
CODE                   printf("keyword: CODE\n");
"OF TYPE"              printf("keyword: OF TYPE\n");

Answer 1

前提：我认为了解您所说的概念的更好方法可能是将可用的工具投入使用。您可以从基础知识开始，例如 flex/bison，或者更好-一些最近的免费工具，例如 GOLD。

如今，由于底层状态机的复杂性，词法分析器和解析器不是手动实现的。但是出于学习目的，正如帕斯卡“之父”Niklaus Wirth 所倡导的那样，或者“引导”SW 链工具，或者（过去）出于效率原因，词法分析器/解析器有时是手动实现的。词法分析器通常采用许多大开关的形式，并且可以使用 ungetc() 简单地实现前瞻：

#include <stdio.h>
enum token {Num, Sym};

token getnum() {
 char c;
 for ( ; ; )
  switch (c = getc()) {
  case '0':
  ...
  case '9':
   break;
  default:
   ungetc(c);
   return Num;
  }
}
token getsym() {
 char c;
 for ( ; ; )
  switch (c = getc()) {
  case '0':
  ...
  case '9':
   break;
  default:
   ungetc(c);
   return Sym;
 }
}
token lex() {
 char c;
 switch (c = getc()) {
 case '0':
 ...
 case '9':
  return getnum();
 case 'A':
 ...
 case 'Z':
 case 'a':
 ...
 case 'z':
 case '_':
  return getsym();
 }

最简单的解析器是自上而下的递归，这要求您的语法为 LL(1)。值得注意的是 Pascal 解析器就是这种类型（当然，Wirth 适当地设计了该语言）。我们需要为每个非终结符提供一个函数，以及 1 个标记的前瞻。解析器变成了一组相互递归的过程（这里完全是虚构的伪代码）：

void A(token t);
void B(token t);

void B(token t)
{
 if (t == Sym)
 {
  t = lex();
  B(t);
 }
 else if (t == Num)
 {
  t = lex();
  A(t);
 }
 else
  syntaxerr();
}
void A(token t)
{
 if (t == Num)
 {
  t = lex();
  B(t);
 }
 else
  syntaxerr();
}

int main(int argc, char **argv)
{
 A(lex());
}

我们总是可以在BFN中重写EBNF，引入服务非终端。