编译原理语法分析思维导图

本文将从以下几个方面详细阐述编译原理语法分析思维导图：

一、语法分析介绍

1.1 语法分析的定义

语法分析是编译器中将输入的字符流转换成抽象语法树的一个过程。该过程的目的是确保输入符合预定义的语法规则。

1.2 语法分析的分类

根据处理输入符号串的方式，语法分析可分为自上而下的语法分析和自下而上的语法分析。

1.3 自上而下的语法分析

自上而下的语法分析是指在分析过程中从语法规则的最顶部开始逐渐向下推导的过程。

void parse_statement()
{
    switch(get_next_token())
    {
        case IF:
            parse_if_statement();
            break;
        case WHILE:
            parse_while_statement();
            break;
        case ASSIGN:
            parse_assign_statement();
            break;
        default:
            error("Unexpected token!");
    }
}

1.4 自下而上的语法分析

自下而上的语法分析是指在分析过程中从语法规则的最底部开始逐渐推导出语句的过程。

void parse_expression()
{
    parse_term();
    while(lookahead == ADD_OP || lookahead == SUB_OP)
    {
        match(lookahead);
        parse_term();
    }
}

二、语法分析思维导图

下面是一张常用的语法分析思维导图：

三、语法分析实例

3.1 产生式

产生式是一种形如 “A → α” 的语法规则，其中A是非终结符，α是由终结符和非终结符构成的推导式。

// 产生式
E → E + T | E - T | T
T → T * F | T / F | F
F → ( E ) | id

3.2 FIRST集和FOLLOW集

FIRST集：对于非终结符A和字符串α，FIRST(α)是以α开头的所有终结符集合。

FOLLOW集：对于非终结符A，FOLLOW(A)是所有可紧随在非终结符A后面的终结符的集合。

FIRST(E + T) = { + }
FIRST(E - T) = { - }
FIRST(T) = FIRST(F) = { (, id }
FOLLOW(E) = { $, ) }
FOLLOW(T) = { +, -, ), $ }
FOLLOW(F) = { *, /, +, -, ), $ }

3.3 语法分析器

下面给出一个基于预测分析法的简单语法分析器实现：

// 预测分析表
vector<vector> predict_table = {
    { 1, -1, 2 },
    { -1, -1, -1 },
    { -1, 3, -1 }
};
map terminal = {
    { 0, "+" }, { 1, "-" }, { 2, "id" }, { 3, "$" }
};
map non_terminal = {
    { 0, "E" }, { 1, "T" }, { 2, "F" }
};
stack stk;
int lookahead;
string expr;

int get_terminal(string s)
{
    for(auto t : terminal)
        if(t.second == s) return t.first;
    return -1;
}

int get_non_terminal(string s)
{
    for(auto t : non_terminal)
        if(t.second == s) return t.first;
    return -1;
}

void shift(int s)
{
    stk.push(s);
    lookahead = get_terminal(string(1, expr.front()));
    expr = expr.substr(1);
}

void reduce(int idx)
{
    for(int i = 0; i < predict_table[idx].size() - 1; i++)
        stk.pop();
    stk.push(predict_table[idx].back());
}

void parse()
{
    stk.push(0);
    lookahead = get_terminal(string(1, expr.front()));
    while(true)
    {
        int s = stk.top();
        int t = get_terminal(non_terminal[s]);
        if(s == lookahead)
        {
            stk.pop();
            if(s == 3) break;
            lookahead = get_terminal(string(1, expr.front()));
            expr = expr.substr(1);
        }
        else if(t == -1) break;
        else if(predict_table[s][t] == -1) break;
        else if(predict_table[s][t] >= 0) reduce(predict_table[s][t]);
        else if(predict_table[s][t] < 0) shift(-predict_table[s][t]);
    }
}
</vector

四、总结

语法分析是编译器中非常重要的一个过程，本文介绍了语法分析的定义、分类以及一些相关术语的概念。此外，还给出了一个预测分析法的语法分析器的示例代码。学习语法分析算法，对于理解编译原理有非常重要的意义。