編譯原理實驗一詞法分析器設計

源代碼倉庫：CompilePrincipleLearning/experiment_1 · yusixian/CompilePrincipleLearning (github.com)

一。實驗目的#

1．深入理解有限自動機及其應用
2．掌握根據語言的詞法規則構造識別其單詞的有限自動機的方法
3．基本掌握詞法分析程序的開發方法
4．能夠設計詞法掃描器程序，對源程序進行詞法分析，並輸出單詞序列

二。實驗內容及要求#

編寫識別單詞的詞法分析程序。

已知某語言中各類單詞的 DFA 如下圖，編寫程序實現：

1、輸入：txt 文件（存放要分析的源程序）

2、輸出：從輸入的源程序中，識別出各個具有獨立意義的單詞，即基本保留字、標識符、常數、運算符、分隔符五大類。並依次輸出各個單詞的種類碼及單詞符號自身值。（遇到錯誤時可顯示 “Error”，然後跳過錯誤部分繼續顯示）。

輸出格式：每個單詞的表示：（種類碼，單詞符號自身值）

要求：對識別出的每一單詞均單行輸出。

源程序中每類單詞都要有

三。實驗過程#

1、設計的 DFA 轉換圖#

字母與下劃線：letter -> A|B|…|Z|a|b|c|d…|y|z|_

數字：digit1 -> 1~9 digit-> 0~9

標識符定義：id -> letter(letter|digit)*

運算符定義：op -> +-*/%=!&|<>

關鍵字定義：keyword -> int float const bool void char double struct return if else while do static break for switch case default continue true false

界符定義：delimiter -> ; , ' " * */ ? : ( ) [ ] } { .

整型定義：int -> (+|-)(0 | digit1 digit*)

字符常量：char -> letter|digit|……

字符串常量：string -> char*

實型定義：double-> (0|(+|-)digit1 digit*)(.digit*)

我畫的 DFA 如圖

2、採用的數據結構#

輸出 Token 流為類型名稱 + 種類碼 + 值（該關鍵字 / 變量名 / 數字 / 運算符 / 界符），重載輸出流。

struct Token {
    int type;   // 種類碼
    string value;       // 值  關鍵字/變量名/數字/運算符/界符
    string category;    // 種類碼對應的類型名稱
    Token(int type, string value, string category) : type(type), value(value), category(category) {}
    friend ostream& operator<<(ostream& os, const Token& t) {
        os << t.category << ", type: " << t.type << ", value: " << t.value;
        return os;
    }
};

3、頭文件聲明和全局變量定義#

如下，應該非常的一目了然吧。

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <map>
using namespace std;
const string CategoryFileName = "./categoryCode.txt";
const string CodeFileName = "./code.txt";
string keywords[22];  // 關鍵字表 種類碼1-22
string operate[28];  // 運算符表 種類碼23-50
string delimiter[15];  // 界符表 種類碼51-65
map<string, int> categoryCode;  // 種類碼表
const string op = "+-*/%=!&|<>";
const int _EOF_ = -2;
const int _ERROR_ = -1;
enum { 
    _ID_, _INT_, _DOUBLE_, _OPERATOR_, _DELIMITER_, _KEYWORD_, _CHAR_, _STRING_, _COMMENT_, _SPACE_
};  // 類型
string cat[10] = { "id", "int", "double", "operator", "delimiter", "keyword", "char", "string", "comment", "space" };
struct Token {
    int type;   // 種類碼
    string value;       // 值  關鍵字/變量名/數字/運算符/界符
    string category;    // 種類碼對應的類型名稱
    Token(int type, string value, string category) : type(type), value(value), category(category) {}
    friend ostream& operator<<(ostream& os, const Token& t) {
        os << t.category << ", type: " << t.type << ", value: " << t.value;
        return os;
    }
};
int pos, len;  // 當前字符位置和長度
string code, tempToken;  // 當前識別的字符串
vector<Token> tokenList;  // 存儲識別出的token

4、函數彙總#

（1）函數彙總表#

函數名稱	功能簡述
`readFile`	讀取文件函數，返回一個 string 動態數組
`init`	初始化函數，在該函數中進行讀取種類碼文件、關鍵字文件，並進行相應賦值與初始化
`peek`	探測下一個字符，若存在則返回該字符，否則返回 \0 即字符串結束符
`isDigit`	判斷字符 ch 是否為數字 0-9
`isLetter`	判斷字符 ch 是否為字母或下劃線（即 A-Z a-z _ ）
`isKeyword`	判斷字符串 s 是否為關鍵字（在關鍵字表中）
`isOP`	判斷字符 ch 是否為單個運算符（在 op 中）
`isOperator`	判斷字符串 s 是否為運算符（運算符表中）
`isDelimiter`	判斷字符 ch 是否為界符（在 operate 中）
`judge`	核心函數，判斷並返回當前字符（`code[pos]`）的枚舉類型，並對一些特殊的 token 進行處理後直接放入 `tokenList`（如註釋、字符和字符串常量）
`read_next`	核心函數，讀取下一個字符，根據返回的枚舉類型，將對應的 token 放入 `tokenList`
`main`	主程序入口，從此進入，調用 `init`函數初始化

（2）函數的調用關係#

5、實驗結果#

輸入#

code.txt

int main() {
    char ch = 'ss';
    string str = "Hello, World!"
    char ch2 = 's';
    init();
    double x = 10.31;/* some comment */
    int m = 0;
    int y = 310, m = 0.31;
    while(pos < len) {
        int flag = read_next();
        if(flag == _EOF_) break;
        if(flag != _ERROR_) {
            Token t(flag, tempToken);
            tokenList.push_back(t);
            cout << t << endl;
        } else cout << "Error!" << endl;
    }
    return 0;
}

輸出#

$0I3RK{8 N%JNPNA</code></code></code></code></code></code></code></code></code></code></code></code></code></code></code></code>(WB_R.png$

四、實驗總結#

此次實驗還是很有意思的，最終跑通的時候也是非常有成就感，個人感覺不用拘泥於用什麼算法，只需要理清楚自己的思路，如何設計才能使這個程序能正確識別？主要有一個優先級的思路，空格和換行符會被跳過，然後先判斷是否為數字或者字母，在進行相應處理，然後進行一些特殊界符的判斷，如字符串、註釋等。我認為代碼就足以很好的說清楚這個流程。這個程序暫時只使用常用符號（.）來支持小數，如果需要更多，可以在 judge 中的 isdigit () 後進行修改，改起來並不困難。顯然，judge 函數中的函數還可以拆成更細緻的幾個函數，但這就等以後再補全了。

五、思考題回答#

程序設計中哪些環節影響詞法分析的效率？如何提高效率？#

答：有待優化的部分還不少，例如在判斷是否為關鍵字時，目前的方法是把可能為標識符或者關鍵字的字符串讀取完後存放在一個字符數組後再逐個與關鍵字表進行匹配，可改為在讀取的同時判斷，這樣會提高效率。還有就是界符匹配也是同理。

完整代碼#

/*
 * @Author: cos
 * @Date: 2022-04-05 00:10:59
 * @LastEditTime: 2022-04-08 02:37:49
 * @LastEditors: cos
 * @Description: 詞法分析器設計實現
 * @FilePath: \CS\experiment_1\demo\main.cpp
 */
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <map>
using namespace std;
const string CategoryFileName = "./categoryCode.txt";
const string CodeFileName = "./code.txt";
string keywords[22];  // 關鍵字表 種類碼1-22
string operate[28];  // 運算符表 種類碼23-50
string delimiter[15];  // 界符表 種類碼51-65
map<string, int> categoryCode;  // 種類碼表
const string op = "+-*/%=!&|<>";
const int _EOF_ = -2;
const int _ERROR_ = -1;
enum { 
    _ID_, _INT_, _DOUBLE_, _OPERATOR_, _DELIMITER_, _KEYWORD_, _CHAR_, _STRING_, _COMMENT_, _SPACE_
};  // 類型
string cat[10] = { "id", "int", "double", "operator", "delimiter", "keyword", "char", "string", "comment", "space" };
struct Token {
    int type;   // 種類碼
    string value;       // 值  關鍵字/變量名/數字/運算符/界符
    string category;    // 種類碼對應的類型名稱
    Token(int type, string value, string category) : type(type), value(value), category(category) {}
    friend ostream& operator<<(ostream& os, const Token& t) {
        os << t.category << ", type: " << t.type << ", value: " << t.value;
        return os;
    }
};
int pos, len;  // 當前字符位置和長度
string code, tempToken;  // 當前識別的字符串
vector<Token> tokenList;  // 存儲識別出的token
// 讀文件
vector<string> readFile(string fileName) {
    vector<string> res;
    try {
        ifstream fin;
        fin.open(fileName);
        string temp;
        while (getline(fin, temp))
            res.push_back(temp);
        return res;
    } catch(const exception& e) {
        cerr << e.what() << '\n';
        return res;
    }
}
void init() {
    vector<string> res = readFile(CategoryFileName); 
    // cout << "len:" << len << endl;
    for(int i = 0; i < 22; ++i) {
        keywords[i] = res[i];
        categoryCode[res[i]] = i+1;
        // cout << "keyword:" << res[i] << endl;
    }
    for(int i = 0; i < 28; ++i) {
        operate[i] = res[i + 22];
        categoryCode[res[i+22]] = i+23;
        // cout << "operate:" << res[i + 22] << endl;
    }
    for(int i = 0; i < 15; ++i) {
        delimiter[i] = res[i + 50];
        categoryCode[res[i+50]] = i+51;
        // cout << "delimiter:" << res[i + 50] << endl;
    }
    res = readFile(CodeFileName);
    for(int i = 0; i < res.size(); ++i)
        code += res[i]+'\n';
    len = code.size();
}
char peek() {
    if (pos+1 < len) return code[pos+1];
    else return '\0';
}
inline bool isDigit(char c) {
    return c >= '0' && c <= '9';
}
// 是否為字母或下劃線
inline bool isLetter(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_';
}
bool isKeyword(string s) {
    for(int i = 0; i < 22; ++i)
        if (s == keywords[i]) 
            return true;
    return false;
}
bool isOP(char ch) {
    return op.find(ch) != string::npos;
}
bool isOperator(string s) {
    for(int i = 0; i < 28; ++i)
        if (s == operate[i]) return true;
    return false;
}
bool isDelimiter(char ch) {
    for(int i = 0; i < 15; ++i)
        if (ch == delimiter[i][0]) return true;
    return false;
}
int judge(char ch) {
    if(ch == '\n' || ch == ' ') return _SPACE_;
    if(isDigit(ch)) {
        char nextChar = peek();
        if(ch == '0' && nextChar == '.') { // 0.多少
            ++pos;
            if(!isDigit(peek()))   // .後面不是數字
                return _ERROR_;
            tempToken = "0.";
            while(isDigit(peek())) {
                tempToken += peek();
                ++pos;
            }
            return _DOUBLE_;    // 8
        } else if(ch == '0' && !isDigit(nextChar)) { // 不是數字也不是.，說明是單純的一個0
            tempToken = "0";
            return _INT_;   // 5
        } else if(ch != '0') {  // digit1
            tempToken = ch;
            while(isDigit(peek())) {
                tempToken += peek();
                ++pos;
            }
            char nextChar = peek();
            if(nextChar == '.') {
                tempToken += nextChar;
                ++pos;
                nextChar = peek();
                if(isDigit(nextChar)) {
                    tempToken += peek();
                    ++pos;
                    while(isDigit(peek())) {
                        tempToken += peek();
                        ++pos;
                    }
                    return _DOUBLE_;    // 8
                } else return _ERROR_;
            } else return _INT_;    // 6
        } else {    // 0+數字
            ++pos;
            return _ERROR_;         // ERROR
        }
    }
    if(isLetter(ch)) {
        tempToken = ch;
        char nextChar = peek();
        while( isLetter(nextChar) || isDigit(nextChar) ) { // 標識符~
            tempToken += nextChar;
            ++pos;
            nextChar = peek();
        }
        return isKeyword(tempToken) ? _KEYWORD_ : _ID_;
    } 
    if(ch == '\"') {
        tokenList.push_back(Token(54, "\"", cat[_DELIMITER_]));
        tempToken = "";
        char nextChar = peek();
        while(nextChar != '\"') {
            tempToken += nextChar;
            ++pos;
            nextChar = peek();
        }
        tokenList.push_back(Token(69, tempToken, cat[_STRING_]));
        tokenList.push_back(Token(54, "\"", cat[_DELIMITER_]));
        pos += 2;
        return _STRING_;
    }
    if(ch == '\'') {
        tempToken = "";
        ++pos;
        char nextChar = peek();
        if(nextChar == '\'') {
            tokenList.push_back(Token(53, "\'", cat[_DELIMITER_]));
            tempToken += code[pos];
            tokenList.push_back(Token(68, tempToken, cat[_CHAR_]));
            tokenList.push_back(Token(53, "\'", cat[_DELIMITER_]));
            ++pos;
            return _CHAR_;
        } else if(code[pos] == '\'') {
            tokenList.push_back(Token(53, "\'", cat[_DELIMITER_]));
            tokenList.push_back(Token(68, tempToken, cat[_CHAR_]));  // 空字符串
            tokenList.push_back(Token(53, "\'", cat[_DELIMITER_]));
            return _CHAR_;
        } else {
            while(pos < len && nextChar != '\'') {
                ++pos;
                nextChar = peek();
            }
            ++pos;
            return _ERROR_;
        }
    }
    if(ch == '/') {
        if(peek() == '*') {
            ++pos;
            char nextChar = peek();
            ++pos;
            tempToken = "";
            while(pos < len) {
                if(nextChar == '*' && peek() == '/') {
                    tokenList.push_back(Token(55, "/*", cat[_DELIMITER_]));
                    tokenList.push_back(Token(71, tempToken, cat[_COMMENT_]));
                    tokenList.push_back(Token(56, "*/", cat[_DELIMITER_]));
                    ++pos;
                    ++pos;
                    return _COMMENT_;
                } else {
                    tempToken += nextChar;
                    nextChar = peek();
                    ++pos;
                }
            }
            return _ERROR_;
        }
    }

    if(isOP(ch)) {   // op運算符
        tempToken = "";
        tempToken += ch;
        char nextChar = peek();
        if(isOP(nextChar)) {
            if(isOperator(tempToken + nextChar)) {
                tempToken += nextChar;
                ++pos;
                return _OPERATOR_;      // 15
            } else return _OPERATOR_;   // 14
        } else return _OPERATOR_;       // 14
    }
    if(isDelimiter(ch)) {
        tempToken = "";
        tempToken += ch;
        return _DELIMITER_;
    }
    return _ERROR_;  
}
int read_next() {
    int type = judge(code[pos]);
    while(pos < len && type == _SPACE_) {
        ++pos;
        type = judge(code[pos]);
    }
    if(pos >= len) return _EOF_; 
    ++pos;
    if(type == _ERROR_) return _ERROR_;
    if(type == _DOUBLE_) {
        // cout << "double: " << tempToken << endl;
        tokenList.push_back(Token(67, tempToken, cat[_DOUBLE_]));
        return _DOUBLE_;
    }
    if(type == _INT_) {
        // cout << "int: " << tempToken << endl;
        tokenList.push_back(Token(66, tempToken, cat[_INT_]));
        return _INT_;
    }
    if(type == _ID_) {  // 標識符
        // cout << "id: " << tempToken << endl;
        tokenList.push_back(Token(70, tempToken, cat[_ID_]));
        return _ID_;
    }
    if(type == _OPERATOR_ || type == _KEYWORD_ || type == _DELIMITER_) {
        tokenList.push_back(Token(categoryCode[tempToken], tempToken, cat[type]));
        return type;
    }
    return _ERROR_;
}
int main() {
    init();
    while(pos < len) {
        int flag = read_next();
        if(flag == _EOF_) break;
        else if(flag == _ERROR_) tokenList.push_back(Token(_ERROR_, "ERROR!", "ERROR"));
    }
    for(auto t : tokenList)
        cout << t << endl;
    return 0;
}