c - Flex 和 Bison 如何找到命令的深度级别

Question

我在 Bison 中遇到了大问题 - 我需要在 if 语句中找到命令 (P) 的最大深度级别。 所以我为 language.l (FLEX) 编写了这个代码

    %{
#include "jazyk.tab.h"
int max = 0;
int j = 0;
%}
%%
[ \t]+
[Bb][Ee][Gg][Ii][Nn]            return(LBEGIN);
[Ee][Nn][Dd]                    return(LEND);
[Ii][Ff]                        {j++; if(j>max)max=j; return(LIF);}
[Tt][Hh][Ee][Nn]                return(LTHEN);
// command to find max depth level in If statement 
[Pp]                            return(LP);
// V is statement
[Vv]                            return(LV);
[.]                             return(.);
[;]                             return(;);
[-+&~|^/%*(),!]                { printf("unknown character in input: %c\n", *yytext);} 
[\n]                    yyterminate();
%%

void maximum()
{
printf("Maximum depth level of command(P): %i\n", max);
} 

这适用于 language.y (BISON)

%{
#include <stdio.h>
#define YYSTYPE float
void koniec(YYSTYPE);
extern char *yytext;
int counterIf;
int counterP;

%}
// define the "terminal symbol" token types (in CAPS by convention)
%token LBEGIN   
%token LEND
%token LIF
%token LTHEN
%token LP
%token LV
%token .
%token ;
%start PROGRAM

%%
// the first rule defined is the highest-level rule 
PROGRAM: LBEGIN prikazy LEND .
prikazy: prikaz ; prikazy
prikaz: LIF LV LTHEN prikaz {counterIf++;}
prikaz:
prikaz: LP 
%%

int main() {
    counterIf = 0;
    counterP = 0;
    printf("Examples to better copy in console: \n");
    printf("begin p; p; end. \n");
    printf("begin if v then p; end.\n");
    printf("begin p; if v then if v then p; p; end.\n");
    printf("\n");
    if (yyparse()==0){
        printf("Sucesfull \n");
        printf("If counter: \n");
        printf("%d \n", counterIf);
        printf("Maximal depth level of command(P): \n");
        printf("%d \n", counterP);
        maximum();
    }
    else
        printf("Wrong \n");

}

例如功能 - 当我写 begin if v then p; 时结果必须是:IF: 1; P最大深度级别:2； 或者:

begin
p;
if v then
if v then p;
p;
end. 

结果:如果:2；最大深度:3；

我现在真的很绝望。请帮助我使用深度计数器:-((很抱歉，它不是全部都是英文的)

Answer 1

不要尝试计算扫描仪中的深度。扫描仪不知道程序的结构。解析器理解嵌套，因此您应该在其中计算深度。

由于您当前没有对任何内容使用语义值，因此我冒昧地将它们用于统计数据。如果您有真正的语义值，您可以将统计结构添加为成员，或使用位置值。

当解析器遇到 if 语句时，它知道还有一个 if 语句，并且当前嵌套深度比目标的嵌套深度多 1 if 的。

我添加了带有 block 的 if 语句的语法，因为它很简单，而且使程序变得更有趣。当解析器向 block 添加语句时，它需要将该 block 的当前 if 计数与新语句的 if 计数相加，并计算最大深度:两个深度中的最大值。函数 merge_statistics 可以做到这一点。

我不太明白你的嵌套深度应该是多少； {0, 0} 可能应为 {0, 1}。 (在空 block 的情况下，我假设嵌套深度为 0，因为没有语句。但也许你甚至不允许空 block 。)

您需要使用理解 C99 的编译器(-std=c99 或 -std=c11 如果您使用 gcc)进行编译，因为我使用复合文字。

我还从扫描仪中删除了 yyterminate 调用并修复了它，以便它坚持在标记之间保留空格，尽管您可能不关心这一点。

扫描仪

%option noinput nounput noyywrap yylineno nodefault
%{
  #include "jazyk.tab.h"
%}
%%
[[:space:]]+
[Bb][Ee][Gg][Ii][Nn]    return(LBEGIN);
[Ee][Nn][Dd]            return(LEND);
[Ii][Ff]                return(LIF);
[Tt][Hh][Ee][Nn]        return(LTHEN);
[Pp]                    return(LP);
[Vv]                    return(LV);
[[:alpha:]]+            { printf("Unknown token: %s\n", yytext); }
[.;]                    return(*yytext);
.                       { printf("unknown character in input: %c\n", *yytext);}

解析器

%{
  #include <stdio.h>
  typedef struct statistics {
    int if_count;
    int max_depth;
  } statistics;
  statistics merge_statistics(statistics a, statistics b) {
    return (statistics){a.if_count + b.if_count,
                        a.max_depth > b.max_depth ? a.max_depth : b.max_depth};
  }

  #define YYSTYPE statistics
  extern int yylineno;
  int yylex();
  void yyerror(const char* message);
%}

%token LIF "if" LTHEN "then" LBEGIN "begin" LEND "end"
%token LV
%token LP                       
%start program                  

%%

program: block '.'                    { printf("If count: %d, max depth: %d\n",
                                               $1.if_count, $1.max_depth); }
block: "begin" statements "end"       { $$ = $2; }
statements: /* empty */               { $$ = (statistics){0, 0}; }
          | statements statement ';'  { $$ = merge_statistics($1, $2); }
statement : LP                        { $$ = (statistics){0, 1}; }
          | block
          | "if" LV "then" statement  { $$ = (statistics){$4.if_count + 1,
                                                          $4.max_depth + 1}; }
%%

void yyerror(const char* message) {
  printf("At %d: %s\n", yylineno, message);
}

int main(int argc, char** argv) {
  int status = yyparse();
  /* Unnecessary because yyerror will print an error message */
  if (status != 0) printf("Parse failed\n");
  return status;
}

测试运行:

$ ./jazyk <<<'begin if v then p; end.'
If count: 1, max depth: 2
$ ./jazyk <<<'begin p; if v then if v then p; p; end.'
If count: 2, max depth: 3
$ ./jazyk <<<'begin if v then begin if v then p; p; end; end.'
If count: 2, max depth: 3
$ ./jazyk <<<'begin if v then begin p; if v then p; end; end.'
If count: 2, max depth: 3
$ ./jazyk <<<'begin if v then begin if v then p; if v then p; end; end.'
If count: 3, max depth: 3