編譯原理語法分析思維導圖

本文將從以下幾個方面詳細闡述編譯原理語法分析思維導圖：

一、語法分析介紹

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

四、總結

語法分析是編譯器中非常重要的一個過程，本文介紹了語法分析的定義、分類以及一些相關術語的概念。此外，還給出了一個預測分析法的語法分析器的示例代碼。學習語法分析演算法，對於理解編譯原理有非常重要的意義。