Skip to content

CP-Homework3

:material-circle-edit-outline: 约 178 个字 :fontawesome-solid-code: 282 行代码 :material-clock-time-two-outline: 预计阅读时间 4 分钟

[!ABSTRACT]

Modern Compiler Implementation in C.pdf P113

3220104929 250317

4.2

image-20250317143737740

image-20250327114318238

  1. 原文法存在左递归，增加非终结符 exps_t，exp_t，stm_t：
prog : stm
    ;

stm : ID ASSIGN exp stm_t
    | PRINT LPAREN exps RPAREN stm_t
    ;

stm_t : SEMICOLON stm stm_t
    | 
    ;

exps : exp exps_t
    ;

exps_t : COMMA exp exps_t
    | 
    ;

exp : INT exp_t
    | ID exp_t
    | stm COMMMA exp exp_t
    | LPAREN exp RPAREN exp_t
    ;

exp_t : PLUS exp exp_t
    | MINUS exp exp_t
    | TIMES exp exp_t
    | DIV exp exp_t
    |
    ;

  1. PROGRAM4.4 使用了优先级策略，参考 SysY 语言文法处理优先级的思路，我们引入额外的非终结符 term ，term_t，factor 来解决优先级的问题：

    exp : term exp_t
 | stm COMMMA exp exp_t
 | stm COMMMA exp term_t
 ;

exp_t : PLUS term exp_t
      | MINUS term exp_t
      | 
      ;

term : factor term_t
     ;

term_t : TIMES factor term_t
       | DIV factor term_t
       | 
       ;

factor : INT
       | ID
       | LPAREN exp RPAREN
       ;

实际程序未能实现优先级处理

  1. 考虑错误恢复功能，需要确认各非终结符的 Follow 集合：
Follow(stm) = {SEMICOLON, COMMMA}
Follow(stm_t) = {SEMICOLON}
Follow(exp) = {COMMA, SEMICOLON, RPAREN, PLUS, MINUS, TIMES, DIV}
Follow(exps) = {RPAREN}
Follow(exp_t) = {COMMA, SEMICOLON, RPAREN, PLUS, MINUS, TIMES, DIV}
Follow(exps_t) = {RPAREN}

基于上面的准备工作，我们可以得到该文法的递归下降分析器的主要部分：

#include<iostream>
#include<string>
#include<cassert>
using namespace std;

typedef struct table *Table_;
Table_ {string id; int value; Table_ tail};
Table_ Table(string id, int value, struct table *tail);
Table_ table=NULL;
int lookup(Table_ table, string id) {
    assert(table!=NULL);
    if (id==table.id) return table.value;
    else return lookup(table.tail, id);
}
void update(Table_ *tabptr, string id, int value) {
    *tabptr = Table(id, value, *tabptr);
}

enum token {INT, ID, ASSIGN, PRINT, LPAREN, RPAREN, SEMICOLON, PLUS, MINUS, TIMES, DIV, COMMA};
union tokenval {int num; string id;}

enum token tok;
union tokenval tokval;

extern enum token get_token();
void advance() {tok = get_token();}
void eat(int t) {
    if(tok == t) {
        advance();
    } else {
        cout << "Error: Expected token " << t << endl;
        exit(1);
    }
}

void prog(){
    stm();
}

int stm_follow[] = {SEMICOLON, COMMA};
void stm(){
    switch(tok){
        case ID:{
            if(lookahead() == ASSIGN){
                eat(ASSIGN);
                update(table, tokval.id, exp());
            }else{
                cout << "Error: Expected ASSIGN" << endl;
                skipto(stm_follow);
            }
            stm_t();
            break;
        }
        case PRINT:{
            if(lookahead() == LPAREN){
                eat(LPAREN);
                exps();
                if(lookahead() == RPAREN){
                    eat(RPAREN);
                }else{
                    cout << "Error: Expected RPAREN" << endl;
                    skipto(stm_follow);
                }
            }else{
                cout << "Error: Expected LPAREN" << endl;
                skipto(stm_follow);
            }
            stm_t();
            printf("\n");
            break;
        }
        default:{
            cout << "Error: Expected ID or PRINT" << endl;
            skipto(stm_follow);
        }
    }
}

int stm_t_follow[] = {SEMICOLON};
void stm_t(){
    switch(tok){
        case SEMICOLON:{
            eat(SEMICOLON);
            stm();
            stm_t();
            break;
        }
        default:
    }
}

int exps_follow[] = {RPAREN};
void exps(){
    printf("%d ", exp());
    exps_t();
}

int exps_t_follow[] = {RPAREN};
void exps_t(){
    switch(tok){
        case COMMA:{
            eat(COMMA);
            printf("%d ", exp());
            exps_t();
            break;
        }
        default:
    }
}

int exp_follow[] = {COMMA, SEMICOLON, RPAREN, PLUS, MINUS, TIMES, DIV};
int exp(){
    int res;
    switch(tok){
        case INT:{
            eat(INT);
            res = tokval.num;
            if(lookahead() == PLUS || lookahead() == MINUS || lookahead() == TIMES || lookahead() == DIV){
                res = exp_t(res);
            }else{
                exp_t(0);
            }
            break;
        }
        case ID:{
            if(lookahead() == ASSIGN){
                eat(ASSIGN);
                res = lookup(table, tokval.id);
                if(lookahead() == PLUS || lookahead() == MINUS || lookahead() == TIMES || lookahead() == DIV){
                    res = exp_t(res);
                }else{
                    exp_t(0);
                }
            }else{
                cout << "Error: Expected ASSIGN" << endl;
                skipto(exp_follow);
            }
            break;
        }
        case LPAREN:{
            eat(LPAREN);
            res = exp();
            if(lookahead() == RPAREN){
                eat(RPAREN);
                if(lookahead() == PLUS || lookahead() == MINUS || lookahead() == TIMES || lookahead() == DIV){
                    res = exp_t(res);
                }else{
                    exp_t(0);
                }            
            }else{
                cout << "Error: Expected RPAREN" << endl;
                skipto(exp_follow);
            }
            break;
        }
        default:{
            stm();
            if(lookahead() == COMMA){
                eat(COMMA);
                res = exp();
                exp_t();
            }else{
                cout << "Error: Expected COMMA" << endl;
                skipto(exp_follow);
            }
        }
    }

    return res;
}

int exp_t_follow[] = {SEMICOLON, RPAREN, COMMA, PLUS, MINUS, TIMES, DIV};
int exp_t(int num_a){
    int res;

    switch(tok){
        case PLUS:{
            eat(PLUS);
            res = num_a + exp();

            if(lookahead() == PLUS || lookahead() == MINUS || lookahead() == TIMES || lookahead() == DIV){
                res = exp_t(res);
            }else{
                exp_t(0);
            }            
            break;
        }
        case MINUS:{
            eat(MINUS);
            res = num_a - exp();

            if(lookahead() == PLUS || lookahead() == MINUS || lookahead() == TIMES || lookahead() == DIV){
                res = exp_t(res);
            }else{
                exp_t(0);
            }   
            break;
        }
        case TIMES:{
            eat(TIMES);
            res = num_a * exp();

            if(lookahead() == PLUS || lookahead() == MINUS || lookahead() == TIMES || lookahead() == DIV){
                res = exp_t(res);
            }else{
                exp_t(0);
            }   
            break;
        }
        case DIV:{
            eat(DIV);
            res = num_a / exp();

            if(lookahead() == PLUS || lookahead() == MINUS || lookahead() == TIMES || lookahead() == DIV){
                res = exp_t(res);
            }else{
                exp_t(0);
            }   
            break;
        }
        default: res = 0;
    }

    return res;
}

int yyparse_fake(){
    prog();
    return 0;
}