Làm thế nào để tôi thực hiện nếu tuyên bố trong Flex/bison

Question

Tôi không nhận được lỗi, xin vui lòng bạn có thể giúp tôi ra, đây là .l và .y file.thanks.

%{ 
#include "ifanw.tab.h" 
extern int yylval; 
%} 
%% 
"="  { return EQ; } 
"!="  { return NE; } 
"<"  { return LT; } 
"<="  { return LE; } 
">"  { return GT; } 
">="  { return GE; } 
"+"  { return PLUS; } 
"-"  { return MINUS; } 
"*"  { return MULT; } 
"/"  { return DIVIDE; } 
")"  { return RPAREN; } 
"("  { return LPAREN; } 
":="  { return ASSIGN; } 
";"  { return SEMICOLON; } 
"IF"  { return IF; } 
"THEN" { return THEN; } 
"ELSE" { return ELSE; } 
"FI"  { return FI; } 
"WHILE" { return WHILE; } 
"DO"  { return DO; } 
"OD"  { return OD; } 
"PRINT" { return PRINT; } 
[0-9]+ { yylval = atoi(yytext); return NUMBER; } 
[a-z] { yylval = yytext[0] - 'a'; return NAME; } 
\  { ; } 
\n  { nextline(); } 
\t  { ; } 
"//".*\n { nextline(); } 
.  { yyerror("illegal token"); } 
%% 

Yacc-file

%start ROOT 

%token EQ 
%token NE 
%token LT 
%token LE 
%token GT 
%token GE 
%token PLUS 
%token MINUS 
%token MULT 
%token DIVIDE 
%token RPAREN 
%token LPAREN 
%token ASSIGN 
%token SEMICOLON 
%token IF 
%token THEN 
%token ELSE 
%token FI 
%token WHILE 
%token DO 
%token OD 
%token PRINT 
%token NUMBER 
%token NAME 

%% 

ROOT: 
    stmtseq { execute($1); } 
    ; 

statement: 
    designator ASSIGN expression { $$ = assignment($1, $3); } 
    | PRINT expression { $$ = print($2); } 
    | IF expression THEN stmtseq ELSE stmtseq FI 
    { $$ = ifstmt($2, $4, $6); } 
    | IF expression THEN stmtseq FI 
    { $$ = ifstmt($2, $4, empty()); } 
    | WHILE expression DO stmtseq OD { $$ = whilestmt($2, $4); } 
    ; 

stmtseq: 
    stmtseq SEMICOLON statement { $$ = seq($1, $3); } 
    | statement { $$ = $1; } 
    ; 

expression: 
expr2 { $$ = $1; } 
    | expr2 EQ expr2 { $$ = eq($1, $3); } 
    | expr2 NE expr2 { $$ = ne($1, $3); } 
    | expr2 LT expr2 { $$ = le($1, $3); } 
    | expr2 LE expr2 { $$ = le($1, $3); } 
    | expr2 GT expr2 { $$ = gt($1, $3); } 
    | expr2 GE expr2 { $$ = gt($1, $3); } 
    ; 

expr2: 
    expr3 { $$ == $1; } 
    | expr2 PLUS expr3 { $$ = plus($1, $3); } 
    | expr2 MINUS expr3 { $$ = minus($1, $3); } 
    ; 

expr3: 
    expr4 { $$ = $1; } 
    | expr3 MULT expr4 { $$ = mult($1, $3); } 
    | expr3 DIVIDE expr4 { $$ = divide ($1, $3); } 
    ; 

expr4: 
    PLUS expr4 { $$ = $2; } 
    | MINUS expr4 { $$ = neg($2); } 
    | LPAREN expression RPAREN { $$ = $2; } 
    | NUMBER { $$ = number($1); } 
    | designator { $$ = $1; } 
    ; 

designator: 
    NAME { $$ = name($1); } 
    ; 
%% 

---

Tôi có một câu hỏi khác, là có một khả năng để thực hiện một hướng dẫn với flex/bò rừng bizon JMP như thế nào trong Assembler để đi đến một nhãn như ví dụ của tôi , Cảm ơn bạn đã giúp đỡ.

:L1 
IF FLAG AND X"0001" 
    EVT 23; 
ELSE 
    WAIT 500 ms; 
    JMP L1; 
END IF; 

Answer 1

EDIT: Tôi đưa ra câu trả lời cũ đến hết

Đây là hứa dụ chi tiết hơn:

thường tôi bắt đầu với một tập tin ví dụ về ngôn ngữ mong muốn:

# example.toy 
begin # example of the simple toy language 
    x = 23; 
    while x > 0 do begin 
     x = x - 1; 
     print(x*x); 
    end; 
end; 

Bước tiếp theo là tạo kết hợp lexer + parser ở vị trí cũ file ious .

Ở đây có dấu lexer (tạo nguồn với flex -o lexer.c lexer.l). Cũng lưu ý rằng nguồn lexer phụ thuộc vào các nguồn phân tích cú pháp (vì TOKEN_ * hằng số), vì vậy bò rừng phải được chạy trước khi biên dịch nguồn lexer:

%option noyywrap 

%{ 
#include "parser.h" 
#include <stdlib.h> 
%} 

%% 

"while" return TOKEN_WHILE; 
"begin" return TOKEN_BEGIN; 
"end" return TOKEN_END; 
"do" return TOKEN_DO; 
[a-zA-Z_][a-zA-Z0-9_]* {yylval.name = strdup(yytext); return TOKEN_ID;} 
[-]?[0-9]+ {yylval.val = atoi(yytext); return TOKEN_NUMBER;} 
[()=;] {return *yytext;} 
[*/+-<>] {yylval.op = *yytext; return TOKEN_OPERATOR;} 
[ \t\n] {/* suppress the output of the whitespaces from the input file to stdout */} 
#.* {/* one-line comment */} 

và phân tích cú pháp (biên dịch với bison -d -o parser.c parser.y, các -d nói với bò rừng để tạo ra các tập tin tiêu đề parser.h với một số công cụ lexer cần)

%error-verbose /* instruct bison to generate verbose error messages*/ 
%{ 
/* enable debugging of the parser: when yydebug is set to 1 before the 
* yyparse call the parser prints a lot of messages about what it does */ 
#define YYDEBUG 1 
%} 

%union { 
    int val; 
    char op; 
    char* name; 
} 

%token TOKEN_BEGIN TOKEN_END TOKEN_WHILE TOKEN_DO TOKEN_ID TOKEN_NUMBER TOKEN_OPERATOR 
%start program 

%{ 
/* Forward declarations */ 
void yyerror(const char* const message); 


%} 

%% 

program: statement';'; 

block: TOKEN_BEGIN statements TOKEN_END; 

statements: 
    | statements statement ';' 
    | statements block';'; 

statement: 
     assignment 
    | whileStmt 
    | block 
    | call; 

assignment: TOKEN_ID '=' expression; 

expression: TOKEN_ID 
    | TOKEN_NUMBER 
    | expression TOKEN_OPERATOR expression; 

whileStmt: TOKEN_WHILE expression TOKEN_DO statement; 

call: TOKEN_ID '(' expression ')'; 

%% 

#include <stdlib.h> 

void yyerror(const char* const message) 
{ 
    fprintf(stderr, "Parse error:%s\n", message); 
    exit(1); 
} 

int main() 
{ 
    yydebug = 0; 
    yyparse(); 
} 

Sau gcc parser.c lexer.c -o toylang-noop tiếng gọi của toylang-noop < example.toy phải chạy mà không có bất kỳ lỗi. Vì vậy, bây giờ trình phân tích cú pháp hoạt động và có thể phân tích cú pháp tập lệnh mẫu.

Bước tiếp theo là tạo một cây cú pháp trừu tượng được gọi là ngữ pháp. Tại thời điểm này, tôi bắt đầu với việc tăng thêm phân tích cú pháp bằng cách xác định các loại khác nhau cho các mã thông báo và các quy tắc, cũng như chèn các quy tắc cho từng bước phân tích cú pháp.

%error-verbose /* instruct bison to generate verbose error messages*/ 
%{ 
#include "astgen.h" 
#define YYDEBUG 1 

/* Since the parser must return the AST, it must get a parameter where 
* the AST can be stored. The type of the parameter will be void*. */ 
#define YYPARSE_PARAM astDest 
%} 

%union { 
    int val; 
    char op; 
    char* name; 
    struct AstElement* ast; /* this is the new member to store AST elements */ 
} 

%token TOKEN_BEGIN TOKEN_END TOKEN_WHILE TOKEN_DO 
%token<name> TOKEN_ID 
%token<val> TOKEN_NUMBER 
%token<op> TOKEN_OPERATOR 
%type<ast> program block statements statement assignment expression whileStmt call 
%start program 

%{ 
/* Forward declarations */ 
void yyerror(const char* const message); 


%} 

%% 

program: statement';' { (*(struct AstElement**)astDest) = $1; }; 

block: TOKEN_BEGIN statements TOKEN_END{ $$ = $2; }; 

statements: {$$=0;} 
    | statements statement ';' {$$=makeStatement($1, $2);} 
    | statements block';' {$$=makeStatement($1, $2);}; 

statement: 
     assignment {$$=$1;} 
    | whileStmt {$$=$1;} 
    | block {$$=$1;} 
    | call {$$=$1;} 

assignment: TOKEN_ID '=' expression {$$=makeAssignment($1, $3);} 

expression: TOKEN_ID {$$=makeExpByName($1);} 
    | TOKEN_NUMBER {$$=makeExpByNum($1);} 
    | expression TOKEN_OPERATOR expression {$$=makeExp($1, $3, $2);} 

whileStmt: TOKEN_WHILE expression TOKEN_DO statement{$$=makeWhile($2, $4);}; 

call: TOKEN_ID '(' expression ')' {$$=makeCall($1, $3);}; 

%% 

#include "astexec.h" 
#include <stdlib.h> 

void yyerror(const char* const message) 
{ 
    fprintf(stderr, "Parse error:%s\n", message); 
    exit(1); 
} 

int main() 
{ 
    yydebug = 0; 
    struct AstElement *a; 
    yyparse(&a); 
} 

Như bạn có thể thấy, phần chính khi tạo AST là tạo ra các nút của AST khi một quy tắc nhất định của phân tích cú pháp đã được thông qua. Kể từ bò rừng duy trì một chồng của quá trình phân tích hiện bản thân, được chỉ cần thiết để gán tình trạng phân tích hiện tại để các phần tử của stack (đây là những $$=foo(bar) lines)

Mục tiêu là cấu trúc sau đây trong bộ nhớ :

ekStatements 
    .count = 2 
    .statements 
    ekAssignment 
     .name = "x" 
     .right 
     ekNumber 
      .val = 23 
    ekWhile 
     .cond 
     ekBinExpression 
     .left 
      ekId 
      .name = "x" 
     .right 
      ekNumber 
      .val=0 
     .op = '>' 
     .statements 
     ekAssignment 
      .name = "x" 
      .right 
      ekBinExpression 
       .left 
       ekId 
        .name = "x" 
       .right 
       ekNumber 
        .val = 1 
       .op = '-' 
     ekCall 
      .name = "print" 
      .param 
      ekBinExpression 
       .left 
       ekId 
        .name = "x" 
       .right 
       ekId 
        .name = "x" 
       .op = '*' 

Để có được biểu đồ này, có mã tạo cần thiết, astgen.h:

#ifndef ASTGEN_H 
#define ASTGEN_H 

struct AstElement 
{ 
    enum {ekId, ekNumber, ekBinExpression, ekAssignment, ekWhile, ekCall, ekStatements, ekLastElement} kind; 
    union 
    { 
     int val; 
     char* name; 
     struct 
     { 
      struct AstElement *left, *right; 
      char op; 
     }expression; 
     struct 
     { 
      char*name; 
      struct AstElement* right; 
     }assignment; 
     struct 
     { 
      int count; 
      struct AstElement** statements; 
     }statements; 
     struct 
     { 
      struct AstElement* cond; 
      struct AstElement* statements; 
     } whileStmt; 
     struct 
     { 
      char* name; 
      struct AstElement* param; 
     }call; 
    } data; 
}; 

struct AstElement* makeAssignment(char*name, struct AstElement* val); 
struct AstElement* makeExpByNum(int val); 
struct AstElement* makeExpByName(char*name); 
struct AstElement* makeExp(struct AstElement* left, struct AstElement* right, char op); 
struct AstElement* makeStatement(struct AstElement* dest, struct AstElement* toAppend); 
struct AstElement* makeWhile(struct AstElement* cond, struct AstElement* exec); 
struct AstElement* makeCall(char* name, struct AstElement* param); 
#endif 

astgen.c:

#include "astgen.h" 
#include <stdio.h> 
#include <stdlib.h> 
#include <assert.h> 

static void* checkAlloc(size_t sz) 
{ 
    void* result = calloc(sz, 1); 
    if(!result) 
    { 
     fprintf(stderr, "alloc failed\n"); 
     exit(1); 
    } 
} 

struct AstElement* makeAssignment(char*name, struct AstElement* val) 
{ 
    struct AstElement* result = checkAlloc(sizeof(*result)); 
    result->kind = ekAssignment; 
    result->data.assignment.name = name; 
    result->data.assignment.right = val; 
    return result; 
} 

struct AstElement* makeExpByNum(int val) 
{ 
    struct AstElement* result = checkAlloc(sizeof(*result)); 
    result->kind = ekNumber; 
    result->data.val = val; 
    return result; 
} 

struct AstElement* makeExpByName(char*name) 
{ 
    struct AstElement* result = checkAlloc(sizeof(*result)); 
    result->kind = ekId; 
    result->data.name = name; 
    return result; 
} 

struct AstElement* makeExp(struct AstElement* left, struct AstElement* right, char op) 
{ 
    struct AstElement* result = checkAlloc(sizeof(*result)); 
    result->kind = ekBinExpression; 
    result->data.expression.left = left; 
    result->data.expression.right = right; 
    result->data.expression.op = op; 
    return result; 
} 

struct AstElement* makeStatement(struct AstElement* result, struct AstElement* toAppend) 
{ 
    if(!result) 
    { 
     result = checkAlloc(sizeof(*result)); 
     result->kind = ekStatements; 
     result->data.statements.count = 0; 
     result->data.statements.statements = 0; 
    } 
    assert(ekStatements == result->kind); 
    result->data.statements.count++; 
    result->data.statements.statements = realloc(result->data.statements.statements, result->data.statements.count*sizeof(*result->data.statements.statements)); 
    result->data.statements.statements[result->data.statements.count-1] = toAppend; 
    return result; 
} 

struct AstElement* makeWhile(struct AstElement* cond, struct AstElement* exec) 
{ 
    struct AstElement* result = checkAlloc(sizeof(*result)); 
    result->kind = ekWhile; 
    result->data.whileStmt.cond = cond; 
    result->data.whileStmt.statements = exec; 
    return result; 
} 

struct AstElement* makeCall(char* name, struct AstElement* param) 
{ 
    struct AstElement* result = checkAlloc(sizeof(*result)); 
    result->kind = ekCall; 
    result->data.call.name = name; 
    result->data.call.param = param; 
    return result; 
} 

Bạn có thể thấy ở đây việc tạo các phần tử AST là công việc khá đơn điệu . Sau khi thực hiện xong bước này, chương trình vẫn không làm gì cả, nhưng AST có thể là được xem trong trình gỡ lỗi.

Bước tiếp theo là viết trình thông dịch. Đây là astexec.h:

#ifndef ASTEXEC_H 
#define ASTEXEC_H 

struct AstElement; 
struct ExecEnviron; 

/* creates the execution engine */ 
struct ExecEnviron* createEnv(); 

/* removes the ExecEnviron */ 
void freeEnv(struct ExecEnviron* e); 

/* executes an AST */ 
void execAst(struct ExecEnviron* e, struct AstElement* a); 

#endif 

Điều này có vẻ thân thiện. Bản thân thông dịch viên rất đơn giản, mặc dù nó dài . Hầu hết các chức năng chỉ đề cập đến một loại AstElement cụ thể. Chức năng chính xác được chọn bởi công cụExpressExpress và dispatchStatement . Các hàm điều phối tìm kiếm hàm đích trong các mảng valExecs và runExecs.

astexec.c:

#include "astexec.h" 
#include "astgen.h" 
#include <stdlib.h> 
#include <assert.h> 
#include <stdio.h> 

struct ExecEnviron 
{ 
    int x; /* The value of the x variable, a real language would have some name->value lookup table instead */ 
}; 

static int execTermExpression(struct ExecEnviron* e, struct AstElement* a); 
static int execBinExp(struct ExecEnviron* e, struct AstElement* a); 
static void execAssign(struct ExecEnviron* e, struct AstElement* a); 
static void execWhile(struct ExecEnviron* e, struct AstElement* a); 
static void execCall(struct ExecEnviron* e, struct AstElement* a); 
static void execStmt(struct ExecEnviron* e, struct AstElement* a); 

/* Lookup Array for AST elements which yields values */ 
static int(*valExecs[])(struct ExecEnviron* e, struct AstElement* a) = 
{ 
    execTermExpression, 
    execTermExpression, 
    execBinExp, 
    NULL, 
    NULL, 
    NULL, 
    NULL 
}; 

/* lookup array for non-value AST elements */ 
static void(*runExecs[])(struct ExecEnviron* e, struct AstElement* a) = 
{ 
    NULL, /* ID and numbers are canonical and */ 
    NULL, /* don't need to be executed */ 
    NULL, /* a binary expression is not executed */ 
    execAssign, 
    execWhile, 
    execCall, 
    execStmt, 
}; 

/* Dispatches any value expression */ 
static int dispatchExpression(struct ExecEnviron* e, struct AstElement* a) 
{ 
    assert(a); 
    assert(valExecs[a->kind]); 
    return valExecs[a->kind](e, a); 
} 

static void dispatchStatement(struct ExecEnviron* e, struct AstElement* a) 
{ 
    assert(a); 
    assert(runExecs[a->kind]); 
    runExecs[a->kind](e, a); 
} 

static void onlyName(const char* name, const char* reference, const char* kind) 
{ 
    if(strcmp(reference, name)) 
    { 
     fprintf(stderr, 
      "This language knows only the %s '%s', not '%s'\n", 
      kind, reference, name); 
     exit(1); 
    } 
} 

static void onlyX(const char* name) 
{ 
    onlyName(name, "x", "variable"); 
} 

static void onlyPrint(const char* name) 
{ 
    onlyName(name, "print", "function"); 
} 

static int execTermExpression(struct ExecEnviron* e, struct AstElement* a) 
{ 
    /* This function looks ugly because it handles two different kinds of 
    * AstElement. I would refactor it to an execNameExp and execVal 
    * function to get rid of this two if statements. */ 
    assert(a); 
    if(ekNumber == a->kind) 
    { 
     return a->data.val; 
    } 
    else 
    { 
     if(ekId == a->kind) 
     { 
      onlyX(a->data.name); 
      assert(e); 
      return e->x; 
     } 
    } 
    fprintf(stderr, "OOPS: tried to get the value of a non-expression(%d)\n", a->kind); 
    exit(1); 
} 

static int execBinExp(struct ExecEnviron* e, struct AstElement* a) 
{ 
    assert(ekBinExpression == a->kind); 
    const int left = dispatchExpression(e, a->data.expression.left); 
    const int right = dispatchExpression(e, a->data.expression.right); 
    switch(a->data.expression.op) 
    { 
     case '+': 
      return left + right; 
     case '-': 
      return left - right; 
     case '*': 
      return left * right; 
     case '<': 
      return left < right; 
     case '>': 
      return left > right; 
     default: 
      fprintf(stderr, "OOPS: Unknown operator:%c\n", a->data.expression.op); 
      exit(1); 
    } 
    /* no return here, since every switch case returns some value (or bails out) */ 
} 

static void execAssign(struct ExecEnviron* e, struct AstElement* a) 
{ 
    assert(a); 
    assert(ekAssignment == a->kind); 
    onlyX(a->data.assignment.name); 
    assert(e); 
    struct AstElement* r = a->data.assignment.right; 
    e->x = dispatchExpression(e, r); 
} 

static void execWhile(struct ExecEnviron* e, struct AstElement* a) 
{ 
    assert(a); 
    assert(ekWhile == a->kind); 
    struct AstElement* const c = a->data.whileStmt.cond; 
    struct AstElement* const s = a->data.whileStmt.statements; 
    assert(c); 
    assert(s); 
    while(dispatchExpression(e, c)) 
    { 
     dispatchStatement(e, s); 
    } 
} 

static void execCall(struct ExecEnviron* e, struct AstElement* a) 
{ 
    assert(a); 
    assert(ekCall == a->kind); 
    onlyPrint(a->data.call.name); 
    printf("%d\n", dispatchExpression(e, a->data.call.param)); 
} 

static void execStmt(struct ExecEnviron* e, struct AstElement* a) 
{ 
    assert(a); 
    assert(ekStatements == a->kind); 
    int i; 
    for(i=0; i<a->data.statements.count; i++) 
    { 
     dispatchStatement(e, a->data.statements.statements[i]); 
    } 
} 

void execAst(struct ExecEnviron* e, struct AstElement* a) 
{ 
    dispatchStatement(e, a); 
} 

struct ExecEnviron* createEnv() 
{ 
    assert(ekLastElement == (sizeof(valExecs)/sizeof(*valExecs))); 
    assert(ekLastElement == (sizeof(runExecs)/sizeof(*runExecs))); 
    return calloc(1, sizeof(struct ExecEnviron)); 
} 

void freeEnv(struct ExecEnviron* e) 
{ 
    free(e); 
} 

Bây giờ người phiên dịch được hoàn tất, và ví dụ có thể chạy, sau khi chức năng chính được cập nhật:

#include <assert.h> 

int main() 
{ 
    yydebug = 0; 
    struct AstElement *a = 0; 
    yyparse(&a); 
    /* Q&D WARNING: in production code this assert must be replaced by 
    * real error handling. */ 
    assert(a); 
    struct ExecEnviron* e = createEnv(); 
    execAst(e, a); 
    freeEnv(e); 
    /* TODO: destroy the AST */ 
} 

Bây giờ người phiên dịch cho các công trình bằng ngôn ngữ này. Lưu ý rằng có một số hạn chế trong dịch này:

• nó chỉ có một biến và một chức năng
  • và chỉ có một tham số để một hàm
• chỉ kiểu int cho các giá trị
• rất khó để thêm hỗ trợ goto, vì đối với mỗi phần tử AST, trình thông dịch gọi hàm giải nghĩa. Goto có thể được thực hiện trong một khối bằng cách hack một cái gì đó vào hàm execStmt, nhưng để nhảy giữa các khối hoặc mức khác nhau, máy móc thực thi phải được thay đổi đáng kể (điều này là do không thể nhảy giữa các khung ngăn xếp khác nhau trong trình thông dịch). Ví dụ, AST có thể được chuyển đổi thành mã byte và mã byte này được giải thích bởi vm.
• một số khác mà tôi sẽ cần phải tra cứu :)

---

Bạn cần phải xác định ngữ pháp cho ngôn ngữ của bạn. Một số điều như thế này (cả lexer và phân tích cú pháp chưa đầy đủ):

 
/* foo.y */ 
%token ID IF ELSE OR AND /* First list all terminal symbols of the language */ 
%% 

statements: /* allow empty statements */ | stm | statements ';' stm; 

stm: ifStatement 
    | NAME 
    | NAME expList 
    | label; 

expList: expression | expList expression; 

label: ':' NAME { /* code to store the label */ }; 

ifStatement: IF expression statements 
      | IF expression statements ELSE statements; 

expression: ID       { /* Code to handle the found ID */ } 
      | expression AND expression { /* Code to con cat two expression with and */ } 
      | expression OR expression 
      | '(' expression ')'; 

Sau đó, bạn biên dịch tập tin này với bison -d foo.y -o foo.c. Công tắc -d hướng dẫn bison tạo tiêu đề với tất cả mã thông báo mà trình phân tích cú pháp sử dụng. Bây giờ bạn tạo lexer của bạn

 
/* bar.l */ 
%{ 
#include "foo.h" 
%} 

%% 

IF return IF; 
ELSE return ELSE; 
OR return OR; 
AND return AND; 
[A-Z]+ { /*store yylval somewhere to access it in the parser*/ return ID; } 

Sau khi bạn đã thực hiện hành động ngữ nghĩa và ngôn ngữ của mình.