代码之家 › 专栏 › 技术社区 › dummydev

如何根据下面的内容减少解析器堆栈或“取消移动”当前标记?

bison grammar compiler-construction parsing

dummydev · 技术社区 · 8 年前

给定以下语言:

正式地: (identifier operator identifier+)*
用简单的英语: 零个或多个操作写成标识符(左值),然后写成运算符,再写成一个或更多标识符(右值)

给定任意运算符,该语言中操作序列的一个示例是 @ :

A @ B C X @ Y

空白不重要,也可以写得更清楚:

A @ B C
X @ Y

您将如何使用类似yacc的LALR解析器来解析它?

我迄今为止所做的努力

我知道如何解析 显式分隔 例如,操作 A @ B C ; X @ Y 但我想知道解析上述输入是否可行以及如何进行。以下是使用Flex/Bison的(非功能性)最小示例。

法律l:

%{
#include "y.tab.h"
%}

%option noyywrap
%option yylineno

%%
[a-zA-Z][a-zA-Z0-9_]*   { return ID; }
@                       { return OP; }
[ \t\r\n]+              ; /* ignore whitespace */
.                       { return ERROR; } /* any other character causes parse error */
%%

yacc.y:

%{
#include <stdio.h>

extern int yylineno;
void yyerror(const char *str);
int yylex();
%}

%define parse.lac full
%define parse.error verbose

%token ID OP ERROR
%left OP

%start opdefs

%%
opright:
       | opright ID
       ;

opdef: ID OP ID opright
     ;

opdefs:
      | opdefs opdef
      ;
%%

void yyerror(const char *str) {
    fprintf(stderr, "error@%d: %s\n", yylineno, str);
}

int main(int argc, char *argv[]) {
    yyparse();
}

生成方式: $ flex lex.l && yacc -d yacc.y --report=all --verbose && gcc lex.yy.c y.tab.c

问题: 我无法使解析器不包括下一个左值标识符右值第一次操作。

$ ./a.out
A @ B C X @ Y
error@1: syntax error, unexpected OP, expecting $end or ID

以上内容始终解析为: reduce(A @ B reduce(C X)) @ Y

我有一种感觉,我必须在lookahead令牌上设置一个条件,如果是运算符,则不应移动最后一个标识符,并且应减少当前堆栈:

A @ B C X @ Y
        ^ *    // ^: current, *: lookahead
-> reduce 'A @ B C' !
-> shift 'X' !

我尝试了所有类型的操作员优先安排,但无法实现。

我愿意接受一个同样不适用于野牛的解决方案。

2 回复 | 直到 8 年前

rici 8 年前

该语言的一个基本语法是LALR(2),而bison不会生成LALR的解析器。

任何LALR(2)语法都可以进行机械修改,以生成具有兼容解析树的LALR 1语法,但我不知道有什么自动工具可以做到这一点。

手动进行转换是可能的,但很烦人,但请注意,您需要调整操作以恢复正确的解析树:

%{
  typedef struct IdList  { char* id; struct IdList* next; };
  typedef struct Def     { char* lhs; IdList* rhs; };
  typedef struct DefList { Def* def; struct DefList* next; };
%}
union {
  Def*     def;
  DefList* defs;
  char*    id;
}
%type <def>  ophead
%type <defs> opdefs
%token <id>   ID

%%

prog  : opdefs        { $1->def->rhs = IdList_reverse($1->def->rhs);
                        DefList_show(DefList_reverse($1)); }
ophead: ID '@' ID     { $$ = Def_new($1);
                        $$->rhs = IdList_push($$->rhs, $3); } 
opdefs: ophead        { $$ = DefList_push(NULL, $1); }
      | opdefs ID     { $1->def->rhs = IdList_push($1->def->rhs, $2); }
      | opdefs ophead { $1->def->rhs = IdList_reverse($1->def->rhs);
                        $$ = DefList_push($1, $2); }

讽刺的是,这个精确的问题是 bison 因为制作不需要 ; 终止器。Bison使用自己来生成解析器,它在lexer中解决了这个问题,而不是像上面概述的那样跳过循环。在lexer中,一旦 ID 则扫描继续到下一个非空白字符。如果这是 : ,则lexer返回 identifier-definition 代币否则,非空白字符将返回到输入流 identifier 返回令牌。

这里有一种在lexer中实现的方法:

%x SEEK_AT
%%
  /* See below for explanation, if needed */
  static int deferred_eof = 0;
  if (deferred_eof) { deferred_eof = 0; return 0; }
[[:alpha:]][[:alnum:]_]*  yylval = strdup(yytext); BEGIN(SEEK_AT);
[[:space:]]+              ;                /* ignore whitespace */
   /* Could be other rules here */
.                         return *yytext;  /* Let the parser handle errors */

<SEEK_AT>{
  [[:space:]]+            ;                /* ignore whitespace */
  "@"                     BEGIN(INITIAL); return ID_AT;
  .                       BEGIN(INITIAL); yyless(0); return ID;
  <EOF>                   BEGIN(INITIAL); deferred_eof = 1; return ID;
}

在 SEEK_AT 启动条件,我们只感兴趣 @ 。如果我们找到一个,那么ID就是 def ,我们返回正确的令牌类型。如果我们找到任何其他内容(除了空白),我们将使用 yyless ,并返回 身份证件 令牌类型。请注意 yylval 已从的初始扫描设置 身份证件 ,所以这里不必担心。

上述代码中唯一复杂的部分是 EOF 处理。一旦 地球观测卫星 已检测到,无法将其重新插入输入流 无年 也没有 unputc 。让扫描仪读取 地球观测卫星 再一次因此,它需要得到充分处理。不幸的是,在 查找(_A) 启动条件,充分处理 地球观测卫星 需要发送两个令牌:首先是已检测到的 身份证件 标记,然后是0 yyparse 将识别为输入结束。如果没有push解析器,我们无法从一个扫描程序操作发送两个令牌,因此我们需要注册接收到 地球观测卫星 ,并在下一次呼叫扫描仪时进行检查。

在第一条规则插入顶部之前缩进的代码 yylex 函数,因此它可以声明局部变量,并在扫描开始之前执行任何需要执行的操作。如上所述,这个lexer不是可重入的,但它是可重启的,因为持久状态在 if (deferred_eof) 行动要使其重新进入市场,您只需要将 deferred_eof 在 yystate 结构,而不是使其成为静态局部。

Community rcollyer 7 年前

下列的 rici 的有用评论和回答,下面是我想到的:

法律l:

%{
#include "y.tab.h"
%}

%option noyywrap
%option yylineno

%%
[a-zA-Z][a-zA-Z0-9_]*   { yylval.a = strdup(yytext); return ID; }
@                       { return OP; }
[ \t\r\n]+              ; /* ignore whitespace */
.                       { return ERROR; } /* any other character causes parse error */
%%

yacc.y:

%{
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

extern int yylineno;
void yyerror(const char *str);
int yylex();


#define STR_OP    " @ "
#define STR_SPACE " "

char *concat3(const char *, const char *, const char *);

struct oplist {
    char **ops;
    size_t capacity, count;
} my_oplist = { NULL, 0, 0 };

int oplist_append(struct oplist *, char *);
void oplist_clear(struct oplist *);
void oplist_dump(struct oplist *);
%}

%union {
    char *a;
}

%define parse.lac full
%define parse.error verbose

%token ID OP END ERROR

%start input

%%

opbase: ID OP ID {
         char *s = concat3($<a>1, STR_OP, $<a>3);
         free($<a>1);
         free($<a>3);
         assert(s && "opbase: allocation failed");

         $<a>$ = s;
     }
     ;

ops: opbase {
       $<a>$ = $<a>1;
   }
   | ops opbase {
       int r = oplist_append(&my_oplist, $<a>1);
       assert(r == 0 && "ops: allocation failed");

       $<a>$ = $<a>2;
   }
   | ops ID {
       char *s = concat3($<a>1, STR_SPACE, $<a>2);
       free($<a>1);
       free($<a>2);
       assert(s && "ops: allocation failed");

       $<a>$ = s;
   }
   ;

input: ops {
         int r = oplist_append(&my_oplist, $<a>1);
         assert(r == 0 && "input: allocation failed");
     }
     ;       
%%

char *concat3(const char *s1, const char *s2, const char *s3) {
    size_t len = strlen(s1) + strlen(s2) + strlen(s3);
    char *s = malloc(len + 1);
    if (!s)
        goto concat3__end;

    sprintf(s, "%s%s%s", s1, s2, s3);

concat3__end:
    return s;
}


int oplist_append(struct oplist *oplist, char *op) {
    if (oplist->count == oplist->capacity) {  
        char **ops = realloc(oplist->ops, (oplist->capacity + 32) * sizeof(char *));
        if (!ops)
            return 1;

        oplist->ops = ops;
        oplist->capacity += 32;
    } 

    oplist->ops[oplist->count++] = op;
    return 0;
}

void oplist_clear(struct oplist *oplist) {
    if (oplist->count > 0) {
        for (size_t i = 0; i < oplist->count; ++i)
            free(oplist->ops[i]);
        oplist->count = 0;
    }

    if (oplist->capacity > 0) {
        free(oplist->ops);
        oplist->capacity = 0;
    }
}

void oplist_dump(struct oplist *oplist) {
    for (size_t i = 0; i < oplist->count; ++i)
        printf("%2zu: '%s'\n", i, oplist->ops[i]);
}


void yyerror(const char *str) {
    fprintf(stderr, "error@%d: %s\n", yylineno, str);
}

int main(int argc, char *argv[]) {
    yyparse();

    oplist_dump(&my_oplist);
    oplist_clear(&my_oplist);
}

输出带 A @ B C X @ Y :

 0: 'A @ B C'
 1: 'X @ Y'