Flex與Bison快速入門深入並打造腳本編程語言前端詳情 - flex,bison,c,編程語言,編譯原理愚人貓Idiomeo 動態日志

Flex 與 Bison 快速入門：打造腳本語言前端

一、介紹

在現代軟件開發中，編譯器和解釋器是許多高級語言的基礎架構。而詞法分析和語法分析則是編譯器前端的核心組成部分。Flex 和 Bison 作為開源的詞法分析器和語法分析器生成工具，為開發者提供了高效構建語言解析系統的能力。

Flex（Fast Lexical Analyzer）是一個詞法分析器生成工具，能夠根據正則表達式規則生成詞法分析器代碼。Bison 則是一個語法分析器生成工具，能夠根據上下文無關文法生成語法分析器代碼。這兩個工具的結合使用，能夠幫助開發者快速構建完整的語言解析系統。

本教程將引導有編程基礎的開發者，特別是熟悉 C 語言的讀者，從零開始掌握 Flex 和 Bison 的使用方法，並最終實現一個簡單的腳本語言前端。

二、環境準備：安裝與配置

在開始學習 Flex 和 Bison 之前，我們需要先配置學習與開發環境。

安裝 Flex 和 Bison

Linux(Ubuntu/Debian)

Flex 和 Bison 在大多數 Linux 發行版中都可以通過包管理器直接安裝。

對於 Ubuntu/Debian 系統，可以使用以下命令進行安裝：

sudo apt-get install flex bison

MacOS

對於 macOS 系統，可以使用 Homebrew 進行安裝：

brew install flex bison

Windows

步驟 1：下載 Winflexbison

訪問 Winflexbison 的官網或項目地址：

官網/項目地址：https://gitcode.com/gh\_mirrors/wi/winflexbison
或直接下載：Winflexbison GitHub Releases

步驟 2：解壓文件

下載後解壓到任意目錄，例如：

D:\tools\winflexbison

步驟 3：配置環境變量

打開：控制面板 → 系統 → 高級系統設置 → 環境變量
在“系統變量”中找到 Path，點擊編輯
添加你解壓的路徑，例如：D:\tools\winflexbison\bin

安裝完成後，可以通過以下命令驗證安裝是否成功：

flex -hbison -h

如果看到輸出信息，説明安裝成功。

開發環境配置

為了方便開發，建議創建一個專門的工作目錄，用於存放本教程的所有代碼示例。可以使用以下命令創建並進入該目錄：

mkdir flex-bison-tutorialcd flex-bison-tutorial

在本教程中，我們將使用標準的 C 語言開發工具鏈，包括 gcc 編譯器。確保你的系統已經安裝了 gcc：

gcc --version

如果沒有安裝，可以在網上搜索安裝教程或者詢問AI。

三、Flex 基礎：詞法分析器構建

詞法分析原理

詞法分析是編譯過程的第一個階段，其主要任務是將輸入的字符流轉換為有意義的詞法單元（token）序列。這些 token 是語言的基本語法單元，如關鍵字、標識符、常量、運算符等。

詞法分析器的工作原理可以簡單描述為：

從輸入流中讀取字符
根據預定義的正則表達式模式匹配最長可能的字符序列
將匹配的字符序列轉換為對應的 token 類型
返回 token 及其相關信息（如值、位置等）

Flex 作為詞法分析器生成工具，能夠根據用户提供的正則表達式規則自動生成高效的詞法分析器代碼。

Flex 程序結構

Flex 程序通常分為三個部分：定義部分、規則部分和用户子程序部分，這三個部分用兩個%%分隔：

定義部分
%%
規則部分
%%
用户子程序部分

定義部分：包含選項、文字塊、開始條件、轉換等。其中，以%{和%}包裹的內容會被直接複製到生成的 C 代碼中。

規則部分：包含正則模式行和模式匹配時執行的 C 代碼。每個規則由一個正則表達式和一個動作組成。

用户子程序部分：包含在模式規則匹配時執行的 C 代碼調用的函數，這部分內容會被直接複製到生成的 C 代碼中。

Flex 簡單示例：單詞計數

讓我們從一個簡單的 Flex 程序開始，該程序用於統計輸入中的字符數、單詞數和行數。

首先，創建一個名為count.l的文件，內容如下：

%{
#include <stdio.h>

int chars = 0;
int words = 0;
int lines = 0;
%}

%%
[a-zA-Z]+ { words++; chars += strlen(yytext); }
\n       { chars++; lines++; }
.        { chars++; }
%%

int main() {
    yylex();
    printf("Chars: %d, Words: %d, Lines: %d\n", chars, words, lines);
    return 0;
}

這個程序的結構如下：

定義部分：包含必要的頭文件和全局變量聲明。
規則部分：

[a-zA-Z]+匹配一個或多個字母，作為單詞，增加單詞計數和字符計數。
\n匹配換行符，增加字符計數和行計數。
.匹配任意單個字符，增加字符計數。

用户子程序部分：包含main函數，調用yylex()啓動詞法分析。

要生成詞法分析器並編譯運行，可以使用以下命令：

flex count.l
gcc lex.yy.c -o count
./count

輸入一些文本後按 Ctrl+D 結束輸入，程序會輸出統計結果。

Flex 生成代碼簡析

Flex 生成的代碼主要包含以下幾個部分：

yylex()函數：詞法分析器的主入口，不斷從輸入流中讀取字符，匹配正則表達式規則，返回 token。
yytext變量：指向當前匹配的文本。
yyleng變量：表示當前匹配文本的長度。
yyin變量：指向當前輸入流，默認為stdin。
yyout變量：指向當前輸出流，默認為stdout。

理解這些基本元素有助於後續編寫更復雜的詞法分析器。

Flex 高級特性

定義部分選項

Flex 提供了多種選項來控制生成代碼的行為，例如：

%option noyywrap：禁止生成yywrap()函數，適用於不需要處理多個輸入文件的情況。
%option yylineno：自動維護行號信息，保存在yylineno變量中。
%option reentrant：生成可重入的詞法分析器，適用於多線程環境。

開始條件

Flex 允許定義不同的分析狀態，稱為開始條件，用於在不同上下文中使用不同的詞法規則。例如：

%x COMMENT

%%
"/*" { BEGIN(COMMENT); }
<COMMENT>"*/" { BEGIN(INITIAL); }
<COMMENT>.|\n { /* 忽略註釋內容 */ }

詞法值傳遞

Flex 允許通過yylval變量將詞法單元的值傳遞給語法分析器。例如：

[0-9]+ { yylval = atoi(yytext); return NUMBER; }

Flex 實戰：簡單計算器詞法分析器

現在，讓我們構建一個簡單計算器的詞法分析器，作為後續學習 Bison 的基礎。

創建calc.l文件，內容如下：

%{
#include "calc.tab.h"
%}

%%
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
"+"    { return ADD; }
"-"    { return SUB; }
"*"    { return MUL; }
"/"    { return DIV; }
"("    { return OP; }
")"    { return CP; }
\n     { return EOL; }
[ \t]  { /* 忽略空白字符 */ }
.      { printf("未知字符: %c\n", *yytext); }
%%

這個詞法分析器定義了以下 token：

NUMBER：匹配一個或多個數字，轉換為整數。
運算符+、-、*、/。
括號(和)。
換行符\n。
空白字符被忽略。
其他字符會被報告為未知字符。

四、Bison 基礎：語法分析器構建

語法分析原理

語法分析是編譯過程的第二個階段，其主要任務是根據語言的語法規則，將詞法分析器生成的 token 序列轉換為抽象語法樹（AST）或執行語義動作。

Bison 作為語法分析器生成工具，基於 LALR (1) 算法，能夠根據用户提供的上下文無關文法生成高效的語法分析器代碼。

Bison 程序結構

Bison 程序通常分為三個部分：定義部分、規則部分和用户子程序部分，同樣用兩個%%分隔：

定義部分
%%
規則部分
%%
用户子程序部分

定義部分：包含選項、文字塊、聲明（如 token 類型、優先級、結合性等）。

規則部分：包含語法規則和對應的語義動作。

用户子程序部分：包含錯誤處理函數等。

Bison 簡單示例：計算器語法分析器

讓我們繼續之前的計算器示例，創建 Bison 文件calc.y：

%{
#include <stdio.h>
void yyerror(char *s);
extern int yylex();
%}

%token NUMBER
%token ADD SUB MUL DIV OP CP EOL

%left ADD SUB
%left MUL DIV

%%

calclist: /* 空規則 */
        | calclist expr EOL { printf("= %d\n", $2); }
        ;

expr: term
    | expr ADD term { $$ = $1 + $3; }
    | expr SUB term { $$ = $1 - $3; }
    ;

term: factor
    | term MUL factor { $$ = $1 * $3; }
    | term DIV factor { $$ = $1 / $3; }
    ;

factor: NUMBER
      | OP expr CP { $$ = $2; }
      ;

%%

void yyerror(char *s) {
    fprintf(stderr, "錯誤: %s\n", s);
}

int main() {
    printf("簡單計算器. 輸入表達式後按回車計算.\n");
    yyparse();
    return 0;
}

這個程序的結構如下：

定義部分：聲明 token 類型和運算符優先級。
規則部分：

calclist規則處理多個表達式，每個表達式後跟換行符。
expr規則處理加法和減法。
term規則處理乘法和除法。
factor規則處理數字和括號內的表達式。

用户子程序部分：包含yyerror()錯誤處理函數和main()函數。

要生成語法分析器並編譯運行，可以使用以下命令：

bison -d calc.y
flex calc.l
gcc lex.yy.c calc.tab.c -o calc
./calc

現在可以輸入簡單的算術表達式進行計算，如1+2*3，程序會輸出結果。

Bison 生成代碼簡析

Bison 生成的代碼主要包含以下幾個部分：

yyparse()函數：語法分析器的主入口，調用詞法分析器獲取 token，根據語法規則進行分析。
$$變量：表示規則左部的值。
$1、\$2等變量：表示規則右部各部分的值。
yyerror()函數：用户必須實現的錯誤處理函數。

Bison 高級特性

運算符優先級和結合性

在 Bison 中，可以通過%left、%right和%nonassoc聲明來指定運算符的優先級和結合性。例如：

%left ADD SUB  /* 左結合，優先級較低 */
%left MUL DIV  /* 左結合，優先級較高 */
%right NEG     /* 右結合，用於一元負號 */

抽象語法樹構建

更復雜的語法分析器通常會構建抽象語法樹，而不僅僅是計算結果。例如：

expr: expr ADD term { $$ = create_node(ADD_NODE, $1, $3); }
    | term { $$ = $1; }
    ;

其中create\_node()函數用於創建樹節點。

錯誤處理和恢復

Bison 提供了error符號來處理語法錯誤並進行恢復：

calclist: calclist error EOL { yyerrok; }
        | calclist expr EOL { printf("= %d\n", $2); }
        ;

Bison 實戰：擴展計算器功能

讓我們擴展之前的計算器，添加以下功能：

一元負號
指數運算
變量支持

修改calc.l以支持變量：

%{
#include "calc.tab.h"
%}

%%
[a-zA-Z] { yylval = *yytext - 'a'; return VARIABLE; }
[0-9]+   { yylval = atoi(yytext); return NUMBER; }
"+"      { return ADD; }
"-"      { return SUB; }
"*"      { return MUL; }
"/"      { return DIV; }
"^"      { return POW; }
"("      { return OP; }
")"      { return CP; }
"="      { return ASSIGN; }
\n       { return EOL; }
[ \t]    { /* 忽略空白字符 */ }
.        { printf("未知字符: %c\n", *yytext); }
%%

修改calc.y以支持新功能：

%{
#include <stdio.h>
#include <math.h>
void yyerror(char *s);
extern int yylex();
int sym[26] = {0}; // 存儲26個變量a-z的值
%}

%token NUMBER VARIABLE
%token ADD SUB MUL DIV POW ASSIGN OP CP EOL

%left ADD SUB
%left MUL DIV
%left POW
%right NEG // 一元負號

%%

calclist: /* 空規則 */
        | calclist expr EOL { printf("= %d\n", $2); }
        ;

expr: term
    | expr ADD term { $$ = $1 + $3; }
    | expr SUB term { $$ = $1 - $3; }
    ;

term: factor
    | term MUL factor { $$ = $1 * $3; }
    | term DIV factor { $$ = $1 / $3; }
    | term POW factor { $$ = pow($1, $3); }
    ;

factor: NUMBER
      | VARIABLE { $$ = sym[$1]; }
      | OP expr CP { $$ = $2; }
      | SUB factor %prec NEG { $$ = -$2; } // 一元負號
      | VARIABLE ASSIGN expr { sym[$1] = $3; $$ = $3; }
      ;

%%

void yyerror(char *s) {
    fprintf(stderr, "錯誤: %s\n", s);
}

int main() {
    printf("高級計算器. 支持變量、指數、一元負號.\n");
    printf("示例: a=5, b=3, a + b^2 - -5\n");
    yyparse();
    return 0;
}

重新生成並編譯：

bison -d calc.y
flex calc.l
gcc lex.yy.c calc.tab.c -lm -o calc
./calc

現在可以輸入包含變量、指數和一元負號的表達式，如a=5, b=3, a + b^2 - -5，程序會正確計算並輸出結果。

五、Flex 與 Bison 協同工作

Flex 與 Bison 的通信機制

Flex 和 Bison 之間通過以下方式進行通信：

yylex()函數：由 Flex 生成，被 Bison 的yyparse()調用，返回下一個 token。
yylval變量：由 Flex 設置，傳遞 token 的值給 Bison。
yyerror()函數：由用户實現，處理語法錯誤。

數據類型管理

在 Flex 和 Bison 中，可以通過%union聲明來管理不同類型的數據：

%union {
    int int_val;
    char char_val;
    // 其他類型...
}

%token <int_val> NUMBER
%token <char_val> VARIABLE

這樣可以確保不同類型的 token 被正確處理。

錯誤處理與恢復

在複雜的語言解析中，錯誤處理和恢復至關重要。可以通過以下方式實現：

yyerror()函數：報告錯誤信息。
error符號：在語法規則中使用error符號來匹配錯誤並恢復。
yyerrok宏：重置錯誤狀態，允許繼續解析。

可重入分析器

在多線程環境中，需要使用可重入版本的 Flex 和 Bison：

Flex：使用%option reentrant選項。
Bison：使用%define api.pure full選項。
接口變化：yylex()和yyparse()函數將接受額外的上下文參數。

六、構建完整的腳本語言前端

設計語言語法

在構建完整的腳本語言前端之前，需要先設計語言的語法。假設我們要設計一個簡單的腳本語言，支持以下特性：

變量聲明和賦值
基本數據類型（整數、浮點數、字符串）
控制結構（if-else、循環）
函數定義和調用
表達式運算

可以使用 EBNF（擴展巴科斯範式）來描述語法：

program ::= { statement }
statement ::= var_decl | assign | if_stmt | while_stmt | func_decl | expr_stmt
var_decl ::= "var" IDENTIFIER (":" TYPE)? ("=" expr)? ";"
assign ::= IDENTIFIER "=" expr ";"
if_stmt ::= "if" "(" expr ")" block ("else" block)?
while_stmt ::= "while" "(" expr ")" block
func_decl ::= "func" IDENTIFIER "(" [param_list] ")" block
param_list ::= IDENTIFIER ("," IDENTIFIER)*
block ::= "{" { statement } "}"
expr_stmt ::= expr ";"
expr ::= ...

詞法分析器設計

根據設計的語法，需要定義詞法分析器的規則：

關鍵字：var、if、else、while、func等。
標識符：以字母開頭的字母數字序列。
字面量：整數、浮點數、字符串。
運算符：算術、比較、邏輯運算符。
分隔符：括號、分號、逗號等。

語法分析器設計

根據設計的語法，需要定義語法分析器的規則：

優先級和結合性：正確設置運算符的優先級和結合性。
抽象語法樹節點類型：為每種語法結構定義對應的 AST 節點。
語義動作：在語法規則中執行語義動作，如生成中間代碼或直接執行。

抽象語法樹構建

構建抽象語法樹是語言前端的核心任務，可以使用結構體來定義不同類型的 AST 節點：

typedef enum {
    NODE_EXPR,
    NODE_VAR_DECL,
    NODE_ASSIGN,
    NODE_IF,
    NODE_WHILE,
    NODE_FUNC_DECL,
    NODE_CALL,
    // 其他節點類型...
} NodeType;

typedef struct Node {
    NodeType type;
    // 通用屬性
    int line;
    // 具體節點屬性
    union {
        ExprNode expr;
        VarDeclNode var_decl;
        AssignNode assign;
        IfNode if_node;
        WhileNode while_node;
        FuncDeclNode func_decl;
        CallNode call;
    };
} Node;

代碼生成與解釋執行

構建完抽象語法樹後，可以選擇以下方式處理：

解釋執行：直接遍歷 AST 並執行相應的操作。
中間代碼生成：將 AST 轉換為中間表示（如字節碼），然後由虛擬機執行。
目標代碼生成：將 AST 直接轉換為機器碼。

七、進階話題與最佳實踐

錯誤處理優化

在實際應用中，錯誤處理至關重要。可以考慮以下優化：

錯誤定位：記錄錯誤的行號和位置。
錯誤恢復策略：如同步點恢復、短語級恢復等。
友好的錯誤信息：提供有幫助的錯誤描述。

性能優化

對於大規模代碼，性能優化必不可少：

詞法分析優化：使用狀態壓縮、減少回溯等。
語法分析優化：緩存常見結構、減少冗餘計算。
內存管理優化：合理使用內存池、避免頻繁分配釋放。

調試技巧

在開發複雜的解析器時，調試技巧非常有用：

跟蹤輸出：在關鍵位置添加調試輸出。
斷言檢查：在代碼中添加斷言，確保邏輯正確性。
調試工具：使用 Flex 和 Bison 提供的調試選項。

現代擴展與替代方案

隨着技術的發展，Flex 和 Bison 也有一些現代擴展和替代方案：

Flex 替代品：如 re2c，生成速度更快的詞法分析器。
Bison 替代品：如 ANTLR，支持更多語法分析算法和語言。
集成工具鏈：如 LLVM，提供完整的編譯工具鏈支持。

八、實戰項目：實現簡單腳本語言

項目結構規劃

創建以下項目文件結構：

simple-script/
├── lexer.l
├── parser.y
├── ast.h
├── interpreter.c
└── Makefile

詞法分析器實現

編寫lexer.l文件：

%{
#include "parser.tab.h"
#include <string.h>

int line_num = 1;
%}

%option noyywrap

%%

"var"          { return VAR; }
"if"           { return IF; }
"else"         { return ELSE; }
"while"        { return WHILE; }
"func"         { return FUNC; }
"return"       { return RETURN; }
"true"         { yylval.bool_val = 1; return BOOL; }
"false"        { yylval.bool_val = 0; return BOOL; }
"nil"          { return NIL; }

[a-zA-Z_][a-zA-Z0-9_]* {
    strncpy(yylval.str_val, yytext, sizeof(yylval.str_val)-1);
    yylval.str_val[sizeof(yylval.str_val)-1] = '\0';
    return IDENTIFIER;
}

[0-9]+ {
    yylval.int_val = atoi(yytext);
    return INTEGER;
}

[0-9]+\.[0-9]* | \.[0-9]+ {
    yylval.float_val = atof(yytext);
    return FLOAT;
}

\"([^\\"]|\\.)*\" {
    strncpy(yylval.str_val, yytext+1, sizeof(yylval.str_val)-2);
    yylval.str_val[sizeof(yylval.str_val)-1] = '\0';
    // 處理轉義字符...
    return STRING;
}

"=="  { return EQ; }
"!="  { return NE; }
"<="  { return LE; }
">="  { return GE; }
"&&"  { return AND; }
"||"  { return OR; }

[=+\-*/%<>!&|^~] { return *yytext; }
[();{},.]        { return *yytext; }
\n               { line_num++; }
[ \t]            { /* 忽略空白 */ }
.                { fprintf(stderr, "Line %d: Unknown character '%c'\n", line_num, *yytext); }
%%

語法分析器實現

編寫parser.y文件：

%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ast.h"

void yyerror(char *s);
extern int yylex();
extern int line_num;

Node *root = NULL;
%}

%union {
    int int_val;
    float float_val;
    char str_val[64];
    int bool_val;
    Node *node;
    NodeList *nodelist;
}

%token <int_val> INTEGER
%token <float_val> FLOAT
%token <str_val> STRING IDENTIFIER
%token <bool_val> BOOL
%token VAR IF ELSE WHILE FUNC RETURN NIL

%token EQ NE LE GE AND OR

%type <node> program block statement expr
%type <nodelist> statements

%start program

%%

program: statements { root = $1; }
       ;

statements: statement { $$ = create_node_list($1); }
          | statements statement { $$ = append_node_list($1, $2); }
          ;

statement: var_decl ";" { $$ = $1; }
         | assign ";" { $$ = $1; }
         | if_stmt { $$ = $1; }
         | while_stmt { $$ = $1; }
         | func_decl { $$ = $1; }
         | expr ";" { $$ = $1; }
         | RETURN expr ";" { $$ = create_return_node($2); }
         ;

var_decl: VAR IDENTIFIER ":" type { $$ = create_var_decl_node($2, $4, NULL); }
        | VAR IDENTIFIER "=" expr { $$ = create_var_decl_node($2, NULL, $4); }
        | VAR IDENTIFIER ":" type "=" expr { $$ = create_var_decl_node($2, $4, $6); }
        ;

type: IDENTIFIER { $$ = create_type_node($1); }
    ;

assign: IDENTIFIER "=" expr { $$ = create_assign_node($1, $3); }
      ;

if_stmt: IF "(" expr ")" block %prec THEN { $$ = create_if_node($3, $5, NULL); }
        | IF "(" expr ")" block ELSE block { $$ = create_if_node($3, $5, $7); }
        ;

while_stmt: WHILE "(" expr ")" block { $$ = create_while_node($3, $5); }
          ;

func_decl: FUNC IDENTIFIER "(" [params] ")" block { $$ = create_func_decl_node($2, $4, $6); }
         ;

params: IDENTIFIER { $$ = create_param_node($1); }
      | params "," IDENTIFIER { $$ = append_param_node($1, $3); }
      ;

block: "{" statements "}" { $$ = $2; }
     ;

expr: expr "||" expr { $$ = create_binary_node(OR_OP, $1, $3); }
    | expr "&&" expr { $$ = create_binary_node(AND_OP, $1, $3); }
    | expr "==" expr { $$ = create_binary_node(EQ_OP, $1, $3); }
    | expr "!=" expr { $$ = create_binary_node(NE_OP, $1, $3); }
    | expr "<" expr { $$ = create_binary_node(LT_OP, $1, $3); }
    | expr ">" expr { $$ = create_binary_node(GT_OP, $1, $3); }
    | expr LE expr { $$ = create_binary_node(LE_OP, $1, $3); }
    | expr GE expr { $$ = create_binary_node(GE_OP, $1, $3); }
    | expr "+" expr { $$ = create_binary_node(ADD_OP, $1, $3); }
    | expr "-" expr { $$ = create_binary_node(SUB_OP, $1, $3); }
    | expr "*" expr { $$ = create_binary_node(MUL_OP, $1, $3); }
    | expr "/" expr { $$ = create_binary_node(DIV_OP, $1, $3); }
    | expr "%" expr { $$ = create_binary_node(MOD_OP, $1, $3); }
    | "-" expr %prec NEG { $$ = create_unary_node(NEG_OP, $2); }
    | "!" expr { $$ = create_unary_node(NOT_OP, $2); }
    | INTEGER { $$ = create_literal_node(INT_TYPE, &$1); }
    | FLOAT { $$ = create_literal_node(FLOAT_TYPE, &$1); }
    | STRING { $$ = create_literal_node(STRING_TYPE, $1); }
    | BOOL { $$ = create_literal_node(BOOL_TYPE, &$1); }
    | NIL { $$ = create_literal_node(NIL_TYPE, NULL); }
    | IDENTIFIER { $$ = create_identifier_node($1); }
    | "(" expr ")" { $$ = $2; }
    | IDENTIFIER "(" [args] ")" { $$ = create_call_node($1, $3); }
    ;

args: expr { $$ = create_arg_node($1); }
    | args "," expr { $$ = append_arg_node($1, $3); }
    ;

%%

void yyerror(char *s) {
    fprintf(stderr, "Line %d: Error: %s\n", line_num, s);
}

int main() {
    yyparse();
    if (root) {
        interpret(root);
        free_node(root);
    }
    return 0;
}

抽象語法樹實現

編寫ast.h文件：

#ifndef AST_H
#define AST_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum {
    INT_TYPE,
    FLOAT_TYPE,
    STRING_TYPE,
    BOOL_TYPE,
    NIL_TYPE,
    TYPE_TYPE,
    VAR_DECL_NODE,
    ASSIGN_NODE,
    IF_NODE,
    WHILE_NODE,
    FUNC_DECL_NODE,
    RETURN_NODE,
    BINARY_OP,
    UNARY_OP,
    IDENTIFIER_NODE,
    CALL_NODE,
    NODE_LIST
} NodeType;

typedef struct Node Node;
typedef struct NodeList NodeList;

typedef struct Node {
    NodeType type;
    union {
        // 字面量節點
        struct {
            NodeType data_type;
            void *value;
        } literal;
        // 類型節點
        struct {
            char type_name[64];
        } type;
        // 變量聲明節點
        struct {
            char name[64];
            Node *type;
            Node *init_value;
        } var_decl;
        // 賦值節點
        struct {
            char name[64];
            Node *value;
        } assign;
        // if節點
        struct {
            Node *condition;
            Node *consequent;
            Node *alternative;
        } if_node;
        // while節點
        struct {
            Node *condition;
            Node *body;
        } while_node;
        // 函數聲明節點
        struct {
            char name[64];
            NodeList *params;
            Node *body;
        } func_decl;
        // 返回節點
        struct {
            Node *value;
        } ret;
        // 二元運算節點
        struct {
            NodeType op;
            Node *left;
            Node *right;
        } bin_op;
        // 一元運算節點
        struct {
            NodeType op;
            Node *operand;
        } un_op;
        // 標識符節點
        struct {
            char name[64];
        } ident;
        // 函數調用節點
        struct {
            char name[64];
            NodeList *args;
        } call;
        // 節點列表
        struct {
            Node *head;
            struct NodeList *tail;
        } list;
    };
} Node;

typedef struct NodeList {
    Node *head;
    struct NodeList *tail;
} NodeList;

Node *create_literal_node(NodeType data_type, void *value);
Node *create_type_node(char *type_name);
Node *create_var_decl_node(char *name, Node *type, Node *init_value);
Node *create_assign_node(char *name, Node *value);
Node *create_if_node(Node *condition, Node *consequent, Node *alternative);
Node *create_while_node(Node *condition, Node *body);
Node *create_func_decl_node(char *name, NodeList *params, Node *body);
Node *create_return_node(Node *value);
Node *create_binary_node(NodeType op, Node *left, Node *right);
Node *create_unary_node(NodeType op, Node *operand);
Node *create_identifier_node(char *name);
Node *create_call_node(char *name, NodeList *args);
NodeList *create_node_list(Node *node);
NodeList *append_node_list(NodeList *list, Node *node);
NodeList *create_arg_node(Node *node);
NodeList *append_arg_node(NodeList *list, Node *node);
void free_node(Node *node);
void interpret(Node *node);

#endif

解釋器實現

編寫interpreter.c文件：

#include "ast.h"

// 簡單的符號表實現
typedef struct Symbol {
    char name[64];
    Node *value;
    struct Symbol *next;
} Symbol;

Symbol *sym_table = NULL;

Node *lookup_symbol(char *name) {
    Symbol *s = sym_table;
    while (s) {
        if (strcmp(s->name, name) == 0) {
            return s->value;
        }
        s = s->next;
    }
    return NULL;
}

void insert_symbol(char *name, Node *value) {
    Symbol *s = malloc(sizeof(Symbol));
    strcpy(s->name, name);
    s->value = value;
    s->next = sym_table;
    sym_table = s;
}

// 解釋器核心函數
void interpret(Node *node) {
    if (!node) return;

    switch (node->type) {
        case NODE_LIST:
            interpret(node->list.head);
            interpret(node->list.tail);
            break;
        case VAR_DECL_NODE:
            if (node->var_decl.init_value) {
                interpret(node->var_decl.init_value);
                insert_symbol(node->var_decl.name, node->var_decl.init_value);
            } else {
                insert_symbol(node->var_decl.name, NULL);
            }
            break;
        case ASSIGN_NODE:
            interpret(node->assign.value);
            insert_symbol(node->assign.name, node->assign.value);
            break;
        case IF_NODE:
            interpret(node->if_node.condition);
            if (node->if_node.condition->literal.value) {
                interpret(node->if_node.consequent);
            } else if (node->if_node.alternative) {
                interpret(node->if_node.alternative);
            }
            break;
        case WHILE_NODE:
            while (1) {
                interpret(node->while_node.condition);
                if (!node->while_node.condition->literal.value) break;
                interpret(node->while_node.body);
            }
            break;
        case RETURN_NODE:
            interpret(node->ret.value);
            exit(0);
            break;
        case BINARY_OP:
            interpret(node->bin_op.left);
            interpret(node->bin_op.right);
            switch (node->bin_op.op) {
                case ADD_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value +
                        *(int*)node->bin_op.right->literal.value;
                    break;
                case SUB_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value -
                        *(int*)node->bin_op.right->literal.value;
                    break;
                case MUL_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value *
                        *(int*)node->bin_op.right->literal.value;
                    break;
                case DIV_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value /
                        *(int*)node->bin_op.right->literal.value;
                    break;
                case MOD_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value %
                        *(int*)node->bin_op.right->literal.value;
                    break;
                case EQ_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value ==
                        *(int*)node->bin_op.right->literal.value;
                    break;
                case NE_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value !=
                        *(int*)node->bin_op.right->literal.value;
                    break;
                case LT_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value <
                        *(int*)node->bin_op.right->literal.value;
                    break;
                case GT_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value >
                        *(int*)node->bin_op.right->literal.value;
                    break;
                case LE_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value <=
                        *(int*)node->bin_op.right->literal.value;
                    break;
                case GE_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value >=
                        *(int*)node->bin_op.right->literal.value;
                    break;
                case AND_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value &&
                        *(int*)node->bin_op.right->literal.value;
                    break;
                case OR_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        *(int*)node->bin_op.left->literal.value ||
                        *(int*)node->bin_op.right->literal.value;
                    break;
            }
            break;
        case UNARY_OP:
            interpret(node->un_op.operand);
            switch (node->un_op.op) {
                case NEG_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        -*(int*)node->un_op.operand->literal.value;
                    break;
                case NOT_OP:
                    node->literal.value = malloc(sizeof(int));
                    *(int*)node->literal.value = 
                        !*(int*)node->un_op.operand->literal.value;
                    break;
            }
            break;
        case IDENTIFIER_NODE:
            node->literal.value = lookup_symbol(node->ident.name);
            break;
        case CALL_NODE:
            // 這裏需要實現函數調用邏輯，暫時簡單處理
            printf("Calling function %s\n", node->call.name);
            break;
        case LITERAL_NODE:
            // 字面量節點不需要解釋
            break;
        default:
            fprintf(stderr, "Unknown node type\n");
            exit(1);
    }
}

// 節點創建函數實現...（為節省篇幅，此處省略具體實現）

編譯與測試

編寫Makefile：

all: simple-script

simple-script: lexer.l parser.y ast.h interpreter.c
    flex lexer.l
    bison -d parser.y
    gcc lex.yy.c parser.tab.c interpreter.c -o simple-script

clean:
    rm -f lex.yy.c parser.tab.c parser.tab.h simple-script

編譯並運行：

make
./simple-script

測試示例代碼：

var a = 10;
var b = 20;
if (a < b) {
    print("a is less than b");
} else {
    print("a is greater than or equal to b");
}

while (a < 20) {
    a = a + 1;
}

func add(x, y) {
    return x + y;
}

print(add(a, b));

九、總結與展望

未來學習方向

如果你對編譯技術感興趣，可以繼續學習以下方向：

高級語法分析算法：如 GLR、Earley 等。
中間表示和優化：如 SSA 形式、數據流分析等。
代碼生成技術：如 LLVM IR 生成、JIT 編譯等。
特定領域語言（DSL）：如何設計和實現特定領域的語言。

進階資源推薦

以下是一些推薦的學習資源：

書籍：《Compilers: Principles, Techniques, and Tools》（龍書）、《Flex & Bison》。
工具文檔：Flex 和 Bison 官方文檔。
開源項目：如 LLVM、GCC、ANTLR 等。
在線課程：Coursera 的編譯原理課程、MIT 的 6.035 等。

通過不斷學習和實踐，你將能夠構建出更復雜、更高效的語言處理系統，為軟件開發帶來更多可能性。

共勉！

博客原文

愚人貓Idiomeo 動態日志

@idiomeo

標簽

人工智能 (486)

windows (60)

llm (53)

c (48)

visual-studio-code (32)

編程語言 (31)

flex (17)

編譯原理 (3)

bug修復 (3)

bison (2)

問題解決 (1)

動態

Flex與Bison快速入門深入並打造腳本編程語言前端 - 動態 詳情

Flex 與 Bison 快速入門：打造腳本語言前端

一、介紹

二、環境準備：安裝與配置

安裝 Flex 和 Bison

Linux(Ubuntu/Debian)

MacOS

Windows

步驟 1：下載 Winflexbison

步驟 2：解壓文件

步驟 3：配置環境變量

開發環境配置

三、Flex 基礎：詞法分析器構建

詞法分析原理

Flex 程序結構

Flex 簡單示例：單詞計數

Flex 生成代碼簡析

Flex 高級特性

定義部分選項

開始條件

詞法值傳遞

Flex 實戰：簡單計算器詞法分析器

四、Bison 基礎：語法分析器構建

語法分析原理

Bison 程序結構

Bison 簡單示例：計算器語法分析器

Bison 生成代碼簡析

Bison 高級特性

運算符優先級和結合性

抽象語法樹構建

錯誤處理和恢復

Bison 實戰：擴展計算器功能

五、Flex 與 Bison 協同工作

Flex 與 Bison 的通信機制

數據類型管理

錯誤處理與恢復

可重入分析器

六、構建完整的腳本語言前端

設計語言語法

詞法分析器設計

語法分析器設計

抽象語法樹構建

代碼生成與解釋執行

七、進階話題與最佳實踐

錯誤處理優化

性能優化

調試技巧

現代擴展與替代方案

八、實戰項目：實現簡單腳本語言

項目結構規劃

詞法分析器實現

語法分析器實現

抽象語法樹實現

解釋器實現

編譯與測試

九、總結與展望

未來學習方向

進階資源推薦

Add a new 評論

Flex與Bison快速入門深入並打造腳本編程語言前端 - 動態詳情