bit编译原理语法分析实验

语法分析是编译原理中的重要环节，它的主要任务是将词法分析器输出的词法单元序列转换为语法分析树或语法分析图，以便于后续的语义分析和代码生成。语法分析器的实现方式有多种，其中最常用的是基于文法的自上而下的递归下降分析法和基于文法的自下而上的移进-归约分析法。

在本实验中，我们将使用C++语言实现一个简单的递归下降分析法的语法分析器，实现对类C语言的一个子集进行语法分析。该子集包含了整型变量声明、赋值语句、算术表达式、条件语句和循环语句等基本语法结构。

1. 文法定义

我们定义的子集语法规则如下：

<program> ::= <stmt_list>
<stmt_list> ::= <stmt> | <stmt> <stmt_list>
<stmt> ::= <decl_stmt> | <assign_stmt> | <if_stmt> | <while_stmt>
<decl_stmt> ::= int <id>;
<assign_stmt> ::= <id> = <expr>;
<if_stmt> ::= if (<condition>) <stmt>
<while_stmt> ::= while (<condition>) <stmt>
<condition> ::= <expr> <rel_op> <expr>
<expr> ::= <term> | <term> <add_op> <expr>
<term> ::= <factor> | <factor> <mult_op> <term>
<factor> ::= <int> | <id> | (<expr>)
<id> ::= <letter> | <id> <letter> | <id> <digit>
<int> ::= <digit> | <int> <digit>
<letter> ::= a | b | ... | z | A | B | ... | Z
<digit> ::= 0 | 1 | ... | 9
<add_op> ::= + | -
<mult_op> ::= * | /
<rel_op> ::= < | > | <= | >= | == | !=

其中，<program>是整个程序的入口，<stmt_list>表示语句列表，<stmt>表示语句，<decl_stmt>表示变量声明语句，<assign_stmt>表示赋值语句，<if_stmt>表示条件语句，<while_stmt>表示循环语句，<condition>表示条件表达式，<expr>表示算术表达式，<term>表示项，<factor>表示因子，<id>表示标识符，<int>表示整数常量，<letter>表示字母，<digit>表示数字，<add_op>表示加减运算符，<mult_op>表示乘除运算符，<rel_op>表示关系运算符。

2. 代码实现

在实现递归下降分析法的语法分析器时，我们需要实现对以上语法规则的递归下降分析函数，每个函数对应一个语法规则。

首先，我们需要定义一个词法分析器，用于将源代码转换为词法单元序列。在本实验中，我们将使用一个简单的词法分析器，它可以处理int关键字、标识符、整数常量、加减乘除运算符、关系运算符、左右括号和分号等词法单元。

#include <iostream>
#include <string>
#include <vector>
#include <stdexcept>

using namespace std;

// 定义词法单元类型
enum TokenKind {
    TK_INT,     // int关键字
    TK_ID,      // 标识符
    TK_NUM,     // 整数常量
    TK_PLUS,    // +
    TK_MINUS,   // -
    TK_MUL,     // *
    TK_DIV,     // /
    TK_LT,      // <
    TK_GT,      // >
    TK_LE,      // <=
    TK_GE,      // >=
    TK_EQ,      // ==
    TK_NE,      // !=
    TK_LPAREN,  // (
    TK_RPAREN,  // )
    TK_SEMICOLON // ;
};

// 定义词法单元结构体
struct Token {
    TokenKind kind; // 词法单元类型
    string str;     // 词法单元字符串
};

// 定义词法分析器
class Lexer {
public:
    Lexer(const string& source) : src(source), pos(0) {}

    // 获取下一个词法单元
    Token getNextToken() {
        // 跳过空白字符
        while (isspace(src[pos])) pos++;

        // 处理数字
        if (isdigit(src[pos])) {
            string numStr;
            while (isdigit(src[pos])) {
                numStr += src[pos++];
            }
            return { TK_NUM, numStr };
        }

        // 处理标识符
        if (isalpha(src[pos])) {
            string idStr;
            while (isalnum(src[pos])) {
                idStr += src[pos++];
            }
            return { TK_ID, idStr };
        }

        // 处理运算符和括号
        switch (src[pos]) {
            case '+': pos++; return { TK_PLUS, "+" };
            case '-': pos++; return { TK_MINUS, "-" };
            case '*': pos++; return { TK_MUL, "*" };
            case '/': pos++; return { TK_DIV, "/" };
            case '<':
                if (src[pos + 1] == '=') {
                    pos += 2;
                    return { TK_LE, "<=" };
                } else {
                    pos++;
                    return { TK_LT, "<" };
                }
            case '>':
                if (src[pos + 1] == '=') {
                    pos += 2;
                    return { TK_GE, ">=" };
                } else {
                    pos++;
                    return { TK_GT, ">" };
                }
            case '=':
                if (src[pos + 1] == '=') {
                    pos += 2;
                    return { TK_EQ, "==" };
                } else {
                    throw runtime_error("invalid token");
                }
            case '!':
                if (src[pos + 1] == '=') {
                    pos += 2;
                    return { TK_NE, "!=" };
                } else {
                    throw runtime_error("invalid token");
                }
            case '(':
                pos++;
                return { TK_LPAREN, "(" };
            case ')':
                pos++;
                return { TK_RPAREN, ")" };
            case ';':
                pos++;
                return { TK_SEMICOLON, ";" };
            default:
                throw runtime_error("invalid token");
        }
    }

private:
    string src; // 源代码
    size_t pos; // 当前位置
};

接下来，我们依次实现递归下降分析函数。函数的实现方式为：首先获取当前词法单元，然后根据语法规则进行分析，如果符合规则则继续获取下一个词法单元，否则抛出异常。

class Parser {
public:
    Parser(const string& source) : lexer(source) {}

    // 解析程序
    void parseProgram() {
        parseStmtList();
    }

private:
    // 解析语句列表
    void parseStmtList() {
        parseStmt();
        Token token = lexer.getNextToken();
        if (token.kind != TK_SEMICOLON) {
            throw runtime_error("missing semicolon");
        }
        if (token.kind != TK_EOF) {
            parseStmtList();
        }
    }

    // 解析语句
    void parseStmt() {
        Token token = lexer.getNextToken();
        switch (token.kind) {
            case TK_INT:
                parseDeclStmt();
                break;
            case TK_ID:
                parseAssignStmt();
                break;
            case TK_IF:
                parseIfStmt();
                break;
            case TK_WHILE:
                parseWhileStmt();
                break;
            default:
                throw runtime_error("invalid statement");
        }
    }

    // 解析变量声明语句
    void parseDeclStmt() {
        Token token = lexer.getNextToken();
        if (token.kind != TK_ID) {
            throw runtime_error("missing identifier");
        }
        token = lexer.getNextToken();
        if (token.kind != TK_SEMICOLON) {
            throw runtime_error("missing semicolon");
        }
    }

    // 解析赋值语句
    void parseAssignStmt() {
        Token token = lexer.getNextToken();
        if (token.kind != TK_ASSIGN) {
            throw runtime_error("missing assignment operator");
        }
        parseExpr();
        token = lexer.getNextToken();
        if (token.kind != TK_SEMICOLON) {
            throw runtime_error("missing semicolon");
        }
    }

    // 解析条件语句
    void parseIfStmt() {
        Token token = lexer.getNextToken();
        if (token.kind != TK_LPAREN) {
            throw runtime_error("missing left parenthesis");
        }
        parseCondition();
        token = lexer.getNextToken();
        if (token.kind != TK_RPAREN) {
            throw runtime_error("missing right parenthesis");
        }
        parseStmt();
    }

    // 解析循环语句
    void parseWhileStmt() {
        Token token = lexer.getNextToken();
        if (token.kind != TK_LPAREN) {
            throw runtime_error("missing left parenthesis");
        }
        parseCondition();
        token = lexer.getNextToken();
        if (token.kind != TK_RPAREN) {
            throw runtime_error("missing right parenthesis");
        }
        parseStmt();
    }

    // 解析条件表达式
    void parseCondition() {
        parseExpr();
        Token token = lexer.getNextToken();
        switch (token.kind) {
            case TK_LT:
            case TK_GT:
            case TK_LE:
            case TK_GE:
            case TK_EQ:
            case TK_NE:
                parseExpr();
                break;
            default:
                throw runtime_error("missing relational operator");
        }
    }

    // 解析算术表达式
    void parseExpr() {
        parseTerm();
        Token token = lexer.getNextToken();
        while (token.kind == TK_PLUS || token.kind == TK_MINUS) {
            parseTerm();
            token = lexer.getNextToken();
        }
        lexer.ungetToken();
    }

    // 解析项
    void parseTerm() {
        parseFactor();
        Token token = lexer.getNextToken();
        while (token.kind == TK_MUL || token.kind == TK_DIV) {
            parseFactor();
            token = lexer.getNextToken();
        }
        lexer.ungetToken();
    }

    // 解析因子
    void parseFactor() {
        Token token = lexer.getNextToken();
        switch (token.kind) {
            case TK_NUM:
            case TK_ID:
                break;
            case TK_LPAREN:
                parseExpr();
                token = lexer.getNextToken();
                if (token.kind != TK_RPAREN) {
                    throw runtime_error("missing right parenthesis");
                }
                break;
            default:
                throw runtime_error("invalid factor");
        }
    }

private:
    Lexer lexer; // 词法分析器
};

3. 测试样例

我们编写以下测试样例，用于测试语法分析器的正确性。

int main() {
    string source = "int a; a = 1 + 2 * 3; if (a < 10) { a = a + 1; } while (a < 20) { a = a + 2; }";
    Parser parser(source);
    parser.parseProgram();
    return 0;
}

以上测试样例包含了变量声明、赋值语句、算术表达式、条件语句和循环语句等基本语法结构，用于测试语法分析器的正确性。

4. 总结

本实验通过实现一个简单的递归下降分析法的语法分析器，实现了对类C语言的一个子集进行语法分析。递归下降分析法是编译原理中最常用的语法分析方法之一，它的实现方式简单直观，易于理解和实现，但是它存在递归调用深度过大等问题，需要注意优化和调试。