編譯原理

將高級編程語言編寫的源代碼轉換成機器可執行的代碼(二進制或匯編代碼)

核心任務:

詞法分析(正則表達式和有限自動機):

示例Token分類：關鍵字：if, while
運算符：+, =
標識符：變量名

? ? ? ? ? ? ? ? 分解源代碼為單詞 識別 其中關鍵字 變量名 運算符 等

語法分析(上下文無關文法CFG):

示例CFG規則：
E → E + T | T
T → T * F | F
F → (E) | id

? ? ? ? ? ? ? ? ? ? ? 根據語法規則 構建抽象語法樹(AST) 檢查程序結構 是否正確??

語義分析(語法制導翻譯):

驗證類型匹配,變量聲明等語義規則

代碼優化(數據流分析):

刪除冗余代碼、循環優化等技術提升程序性能。

目標代碼生成:

優化過后轉換成二進制或者匯編

應用場景:

編譯器開發(GCC.LLVM等工具鏈實現)

靜態分析工具(檢測代碼風格和漏洞 如:ESLint)

領域特定語言(DSL快速構建小型語言的處理工具)

使用現有的工具和庫(如:Lex/Yacc/Bison/Flex)實踐編譯器開發

Windows環境安裝工具flex bison

CMD管理員輸入以下代碼

choco install winflexbison3

當出現

Do you want to run the script?([Y]es/[A]ll - yes to all/[N]o/[P]rint):

回復A 運行所有腳本

如果遇到運行問題可把以下地址添加到PATH(環境變量))默認路徑為?C:\Program Files (x86)\WinFlexBison 主要下圖信息輸出 比如說我的電腦 安裝位置就為

C:\ProgramData\chocolatey\lib\winflexbison3\tools

檢測是否安裝成功

win_flex --version
win_bison --version

實戰項目AI：實現一個簡單的計算器（支持加減乘除）

編寫?calc.l（Flex 文件）

%{
#include "y.tab.h"  // 包含 Yacc/Bison 生成的頭文件，用于 token 類型定義// 文件名可能是 y.tab.h 或 calc.tab.h，取決于 Yacc/Bison 文件配置
%}
%option noyywrap  // 禁用 yywrap 函數，簡化 Lex 程序
%%
// 模式匹配規則部分
[0-9]+      { yylval = atoi(yytext); return NUMBER; }  // 匹配數字并轉換為整數
"+"         { return ADD; }  // 匹配加號運算符
"-"         { return SUB; }  // 匹配減號運算符
"*"         { return MUL; }  // 匹配乘號運算符
"/"         { return DIV; }  // 匹配除號運算符
"("         { return LPAREN; }  // 匹配左括號
")"         { return RPAREN; }  // 匹配右括號
[ \t\n]     ; // 忽略空格、制表符和換行符
.           { printf("未知字符: %s\n", yytext); }  // 處理其他未定義字符
%%
// 用戶代碼部分（此處為空）

編寫?calc.y（Bison 文件）

%{
#include <stdio.h>
#include <stdlib.h>
extern int yylex();      // 聲明詞法分析器函數
extern FILE *yyin;       // 輸入文件指針
void yyerror(const char *msg) {   // 錯誤處理函數
fprintf(stderr, "Error: %s\n", msg);
}
%}
%token ADD SUB MUL DIV LPAREN RPAREN  NUMBER  // 定義token類型
%left '+' '-'     // 定義運算符優先級和結合性
%left '*' '/'     // 乘法除法優先級高于加減法
%%
input:            // 輸入規則
/* 空輸入 */
| input line  // 多行輸入處理
;
line:             // 行處理規則
'\n'          // 空行
| expr '\n' { printf("= %d\n", $1); }  // 表達式行，輸出計算結果;
expr:             // 表達式規則
NUMBER            { $$ = $1; }  // 數字直接返回
| expr '+' expr   { $$ = $1 + $3; }  // 加法運算
| expr '-' expr   { $$ = $1 - $3; }  // 減法運算
| expr '*' expr   { $$ = $1 * $3; }  // 乘法運算
| expr '/' expr   { if ($3 == 0) yyerror("Division by zero"); else $$ = $1 / $3; }  // 除法運算，檢查除零錯誤
| '(' expr ')'    { $$ = $2; }  // 括號表達式
;
%%
主程序部分
int main(int argc, char **argv) {
if (argc > 1) {          // 如果有命令行參數
yyin = fopen(argv[1], "r");  // 打開文件作為輸入
} else {
yyin = stdin;        // 否則使用標準輸入
}// 啟用 Bison 調試模式yydebug = 1;yyparse();               // 調用語法分析器
return 0;}

Windows安裝的工具需要在原代碼調用的前提上添加 win_ 這樣才會識別

下圖是因為編譯時被安全軟件攔截生成的提示?

1.生成?.c?文件

//修改前  以下代碼 Windows 環境不會識別
flex calc.l         # 生成 calc.yy.c
bison -dy calc.y    # 生成 calc.tab.c 和 calc.tab.h
//修改后 正常生成,如果出現還是不識別 返回文章前面尋找路徑添加到 環境變量
win_flex calc.l
win_bison -dy calc.y

• yylex()：由詞法分析器提供，負責返回詞法單元。
• yyerror()：用戶需實現的錯誤處理函數
• yylval/yylloc：用于傳遞詞法單元的屬性和位置信息。
• yyparse()?是由語法分析器生成工具（如 Bison 或 Yacc）自動生成的函數，用于執行語法分析過程。它通常與詞法分析器（如 Lex 或 Flex 生成的?yylex()）配合使用，構成編譯器或解釋器的核心部分。

可以看到生成了三個文件

• lex.yy.c（由 Flex 生成）
• y.tab.c（由 Bison 生成）
• y.tab.h（定義 token）

?

?2.編譯鏈接?

gcc lex.yy.c y.tab.c -o calc   //正常鏈接gcc lex.yy.c y.tab.c -DYYDEBUG=1 -o calc  //打開調試開關的鏈接
//lex.yy.c：由Lex（或Flex）生成的詞法分析器源代碼，負責將輸入字符流分解為標記（tokens）。
//y.tab.c：由Yacc（或Bison）生成的語法分析器源代碼，包含語法規則和語義動作，通常依賴詞法分析器的輸出。

可以看到生成了一個exe程序

?

?點擊運行并輸入算式:

Starting parse       // 開始語法分析（調用 yyparse()）
Entering state 0     // 進入狀態 0（初始狀態）
Stack now 0          // 當前狀態棧：[0]Reducing stack by rule 1 (line 15):   // 根據規則 1 歸約（對應 input 規則）-> $$ = nterm input ()             // 將 input 規約為一個非終結符（空輸入）Entering state 1     // 狀態變為 1
Stack now 0 1        // 狀態棧更新為 [0, 1]Reading a token      // 開始讀取第一個 token
5 + 3                // 用戶輸入內容（注意這行是你手動或從文件輸入的內容）Next token is token NUMBER ()        // 下一個 token 是 NUMBER（數字 5）
Shifting token NUMBER ()             // 將該 token 移入棧中
Entering state 3                     // 進入狀態 3
Stack now 0 1 3                      // 狀態棧變為 [0, 1, 3]Reducing stack by rule 5 (line 23):  // 根據規則 5 歸約（exp: NUMBER）$1 = token NUMBER ()              // 使用 NUMBER 值（即 5）構造 exp-> $$ = nterm exp ()              // 將 NUMBER 歸約為 exp（表達式）Entering state 7                     // 進入狀態 7
Stack now 0 1 7                      // 狀態棧變為 [0, 1, 7]Reading a token      // 繼續讀取下一個 tokenNext token is token '+' ()           // 下一個 token 是 '+'（加號）
Shifting token '+' ()                // 將 '+' 移入棧中
Entering state 9                     // 進入狀態 9
Stack now 0 1 7 9                    // 狀態棧變為 [0, 1, 7, 9]Reading a token      // 繼續讀取下一個 tokenNext token is token NUMBER ()  
// 下一個讀取到的 token 是 NUMBER（即數字 "3"）Shifting token NUMBER ()
// 將這個 token（數字 3）移入解析棧中Entering state 3
// 當前狀態變為 3（通常是處理 NUMBER 的狀態）Stack now 0 1 7 9 3  
// 當前解析棧的狀態序列：[0, 1, 7, 9, 3]
// 表示當前處于狀態 3，前面是狀態 0 → 1 → 7 → 9 → 3Reducing stack by rule 5 (line 23):  
// 根據語法規則第 5 條進行歸約（對應 exp: NUMBER）$1 = token NUMBER ()  
// 使用當前 token 的值（即 3）作為規則中的第一個操作數-> $$ = nterm exp ()  
// 將 NUMBER 歸約為非終結符 exp（表達式）
// 即：把數字 3 看作是一個“表達式”expEntering state 15  
// 歸約完成后進入新狀態 15（通常是由 exp '+' exp 后匹配到新的 exp）Stack now 0 1 7 9 15  
// 當前狀態棧更新為 [0, 1, 7, 9, 15]Reading a token  
// 準備讀取下一個 token（輸入結束或換行）