编译原理第一次实验

0x01 实验目的

构造一个从中缀表达式到后缀形式的表达式翻译器，初步了解递归下降语法分析原理及语法制导翻译的过程。

0x02 实验内容

• 程序功能
  • 将中缀表达式转换为后缀表达式的翻译器
• 程序输入
  • 常数、变量以及'+'、'-'、"*"、"\"、"("、")"、空格构成的中缀表达式
  • 程序使用词法分析功能
• 原始文法描述
  • expr -->
    • expr + term
    • expr - term
    • term
  • term -->
    • term * factor
    • term / factor
    • factor
  • factor -->
    • (expr)
    • ID
    • NUM
• 消除左递归后的语法制导定义
  • 
  • 在原文法的基础上引入rest和t_rest，便于实现递归向下地进行翻译
• 程序代码：

#include <stdio.h>  
#include <stdlib.h>  
#include <string>  
using std::string;  
  
#include <ctype.h>  
  
  
using namespace std;  
  
#define TKN_NUM 500  
#define TKN_ID  600  
#define TKN_BRACKET 700  
  
void Expr(string & ExprSyn);  
  
int LookAhead; //存放当前的词法单元的类型  
int tokenval = 0; char lexeme[1024];  
  
int GetToken() {  
    while (true) {  
        int t = getchar();  
        if (t == ' ' || t == '\t') continue;  
        else if (isdigit(t)) {  
            tokenval = 0;  
            do {  
                tokenval = tokenval * 10 + t -'0';  
                t = getchar();  
            } while (isdigit(t));  
            if (isalpha(t)) {  
                printf("\n非法变量名\n");  
                exit(1);  
            }  
            ungetc(t, stdin);  
            return TKN_NUM;  
        } else if (t == '(') {  
            string expr_syn_T;  
            LookAhead = GetToken();  
            Expr(expr_syn_T);  
            if( LookAhead !=')' ) {  
                printf("\n输入的括号不匹配\n");  
                exit(1);  
            }  
            for (int i=0; i<expr_syn_T.length(); i++) {  
                lexeme[i] = expr_syn_T[i];  
            }  
            lexeme[expr_syn_T.length()] = '\0';  
            return TKN_BRACKET;  
        } else if (isalpha(t)) {  
            int idx = 0;  
            do {  
                lexeme[idx++]=t;  
                t = getchar();  
            } while(isdigit(t) || isalpha(t));  
            lexeme[idx] = '\0';  
            ungetc(t, stdin);  
            return TKN_ID;  
        } else {  
            tokenval = 0;  
            return t;  
        }  
    }  
}  
  
void Match(int t)  
{  
    if( LookAhead==t )  
        LookAhead = GetToken();  
    else {  
        printf("\n表达式错误:Match失败。\n");  
        system("pause");  
        exit(1);  
    }  
  
}  
  
void Factor(string & FactorSyn) {  
    char buf[100];  
    if( LookAhead==TKN_NUM ) {  
        sprintf(buf,"%d ", tokenval);  
        FactorSyn = buf; Match(LookAhead);  
    }  
    else if( LookAhead==TKN_ID || LookAhead==TKN_BRACKET) {  
        sprintf(buf,"%s ",lexeme);  
        FactorSyn = buf; Match(LookAhead);  
    }  
    else {  
        printf("\n表达式错误:这里需要一个整数或变量或是一个在括号内的表达式。\n" );  
        system("pause");  
        exit(1);  
    }  
}  
  
void T_Rest(string & T_RestSyn) {  
    string factor_syn, t_rest_syn;  
    switch (LookAhead) {  
        case '*':  
            Match('*'); Factor(factor_syn); T_Rest(t_rest_syn);  
            T_RestSyn = factor_syn + "* " + t_rest_syn;  
            break;  
        case '/':  
            Match('/'); Factor(factor_syn); T_Rest(t_rest_syn);  
            T_RestSyn = factor_syn + "/ " + t_rest_syn;  
            break;  
        default:  
            T_RestSyn = "";  
            break;  
    }  
}  
  
void Term(string & TermSyn) {  
    string factor_syn, t_rest_syn;  
    Factor(factor_syn);  
    T_Rest(t_rest_syn);  
    TermSyn = factor_syn + t_rest_syn;  
}  
  
void Rest(string & RestSyn) {  
    string term_syn, rest_syn;  
    switch (LookAhead) {  
        case '+':  
            Match('+'); Term(term_syn); Rest(rest_syn);  
            RestSyn = term_syn + "+ " + rest_syn;  
            break;  
        case '-':  
            Match('-'); Term(term_syn); Rest(rest_syn);  
            RestSyn = term_syn + "- " + rest_syn;  
            break;  
        case '\n':  
        case ')':  
            RestSyn = "";  
            break;  
        default:  
            printf("非法字符");  
            exit(1);  
    }  
}  
  
void Expr(string & ExprSyn) {  
    string term_syn, rest_syn;  
    Term(term_syn);  
    Rest(rest_syn);  
    ExprSyn = term_syn + rest_syn;  
}  

int main() {  
    string expr_syn;  
    printf("请输入中缀表达式:\n");  
    LookAhead = GetToken();  
  
    Expr(expr_syn);  
    printf("其后缀表达式为: ");  
    printf( "%s", expr_syn.c_str() );  
  
    if( LookAhead !='\n' ) {  
        printf("\n输入的表达式错误\n");  
        exit(1);  
    }  
  
    printf("\n表达式分析成功！\n");  
    system("pause");  
    return 0;  
}

• 功能实现：

  • 完成对中缀表达式向后缀表达式的翻译
    • 
  • 检查括号
    • 
  • 校验变量名
    • 
  • 校验num
    • 
  • 检查非法字符
    • 
  • 表达式错误
    • 

• 程序逻辑讲解

  • Expr(string & ExprSyn)
    • 将expr看成term 和 rest两部分
    • 前后分别执行Term()和Rest()进行翻译
  • Term(string & TermSyn)
    • 将term看成factor 和 t_rest两部分
    • 前后分别执行Factor()和T_Rest()进行翻译
  • Factor(string & FactorSyn)
    • 若词法分析取出的token是num或者Id或者括号括起来的表达式，直接将对应值赋予FactorSyn
    • 括号表达式的处理：
      • 在GetToken()时，若读取到左括号，则认定接下来一段为括号表达式，执行Expr()函数，将括号表达式翻译成后缀形式，将其赋予lexeme（只是为了方便，与id共用变量）
  • Rest(string & RestSyn)
    • 对Expr剩余部分进行处理，同样把剩余部分分成term和rest1，根据LookAhead确定执行程序
      • 若是'+'或者'-'，则执行RestSyn = term_syn +/- "+ " + rest_syn
      • 否则说明表达式结束，若还有除了换行符和右括号以外的字符，说明表达式错误
  • T_Rest(string & T_RestSyn)
    • 与Rest类似，对Term剩余部分进行处理，把剩余部分分成factor和t_rest1，根据LookAhead确定执行程序
  • 程序开始，会先获取第一个token，然后执行Expr()，将表达式递归翻译成后缀形式

• 解决问题

  • 问题1：如何解决+、-、*、\、括号的优先级问题
    • 引入rest、t_rest、并把括号表达式视为factor
  • 问题2：如何检查括号是否匹配
    • 
    • 每次读取完括号表达式时，检查下一个字符是否是右括号，若否，说明括号不匹配

0x03 实验总结

通过本次实验，在仔细阅读示例代码后，写出优化版的中缀表达式到后缀形式的表达器翻译器，这让我更加理解了递归下降语法，也熟悉了语法制导翻译的流程。