c - BNF 到 Lex 到 C 语言的解析器

Question

很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它， visit the help center 。

已关闭 11 年前。

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

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

抱歉，如果不清楚或有什么问题，我的脑子里到处都是

谢谢

ps。我有 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，引入服务非终端。