我想自己用C/C++做一個腳本語言解釋器，但是不知道需要什麼知識？
我想自己用C/C++做一個腳本語言解釋器，但是不知道需要什麼知識？是一個解釋型腳本語言解析器，但是我發現關於編譯原理的書籍都是在講編譯型語言的，不知解釋型語言會不會有什麼特別不同的地方。
我會C/C++和數據結構，在讀大學（坑爹學校）的時候沒有編譯原理的課程，後來有看一些關於編譯原理的書籍，但是還是覺得缺少了什麼東西。希望各位可以給我指點一下如何入門~修正問題：解析器 -&> 解釋器。
題主原本的問題：
我想自己用C/C++做一個腳本語言解析器，但是不知道需要什麼知識？
首先，請問題主想寫的是「解析器」（parser）還是「解釋器」（interpreter）？
在編程語言實現的上下文里，「解析」其實通常是指「語法分析」；「解釋」才是跟執行代碼相關的名詞。這倆名詞經常被各種混用，是不對的。其次，編譯器跟解釋器是怎樣的關係，我想放這個傳送門：Java為什麼解釋執行時不直接解釋源碼？ - RednaxelaFX 的回答 裡面我舉了個簡單的例子講一個「一般的編譯器」的工作流程是如何可以一點點轉變為一個「解釋器」。可以看到，解釋器里許多概念其實還是跟編譯器共同的，只是有些事情可以省略不做，或者本來應該在編譯器里做的分析留到了運行時由解釋器來做而已。具體請跳傳送門看。
再次，寫解釋器需要怎樣的知識。前面有不少靠譜的答案，題主可以參考它們先練手試試看。像是說寫個簡易的LISP實現/Scheme實現，很容易上手。這條路子讀讀《Structure and Interpretationof Computer Programs》和《The Little Schemer》作為輔助都挺好。如果想實現個類似C的語法的命令式語言的解釋器，那可以從最基礎的地方出發慢慢練習。下面是一個假想的順序：
- 簡單的四則混合運算計算器，支持加減乘除、運算符優先順序（乘除優先於加減、括弧。例如可以運算 "12+3*5-6" 這樣的表達式，不用考慮空格之類的問題。
- 此時需要的知識非常簡單：知道如何使用數據結構的「棧」就可以了。用兩個棧就可以求出這樣表達式的值，一個用來放操作數，一個用來放運算符；這種演算法叫做Shunting-yard algorithm。「詞法分析」「語法分析」之類的概念都可以先不用管——儘管這個概念中實際上已經做了詞法和語法分析，但還很簡單，不用特別學什麼。
- 在上述基礎上擴展，更好的支持「詞法分析」的概念，例如允許空格的出現
- 繼續擴展，添加變數、賦值的支持。此時可以解釋執行像是：
a = 1 + 2;
b = a + 3 * 4;
的代碼。此時就需要添加兩種支持：
- 更正式的語法分析：要能切分出賦值語句，然后里面的混合運算還是跟之前一樣處理
- 變數表：要有一個記錄 (變數名 -&> 值) 的表
- 繼續擴展，添加控制流語句，例如 if-else 語句。事情從這裡開始就好玩了：之前的步驟里，所有代碼都會按順序被執行；而一旦添加了控制流語句的支持，輸入的程序里就可能會有一些被條件執行，這要如何處理就有許多發揮空間了，例如說要不要引入抽象語法樹（AST）。
- 續集擴展，支持循環語句。
- 續集擴展，支持函數的聲明與調用。
做完上面步驟之後，一個初具雛形的解釋器就出來了。
正巧，近來 @許式偉 做的《一周一語言》演講也是以類似的思路演化出一門語言的解釋器實現。題主感興趣也可以參考他的經驗。他做的qlang解釋器的實現思路我在另一個回答里也提到了一點，有興趣請讀讀看：有哪些關於c4 - C in four function 編譯器的文章？ - RednaxelaFX 的回答
寫 Lisp 解釋器的話倒是很容易你需要下面幾樣東西：Read - 包括 Reader，Tokenizer， Parser，etc.Eval - 主要就是實現 EvalPrint 和 Loop 太 trivial 了就不說了然後你就有了一個 Lisp 的 REPL把 Reader 的輸入從 stdin 改成從文件輸入你就有一個解釋器了
GitHub - Cheukyin/TemlatedPL: A Simple Functional Programming Language Interpreter Based On C++ Template
若是不拘泥於正統的解釋器，只為學習之用，
也是可以用c++模板元編程實現一個Lisp解釋器的，比如上面我寫的這個
基本的closure、lambda、call/cc等等都支持，而且所有運算都是在編譯期完成，raw speed，
當然，缺點就是沒手寫parser的靈活，畢竟受限於模板的語法，不過括弧語言也沒多少語法嘛原理其實和正經的解釋器實現差不多，都是解釋AST，
不過既然是基於模板，所以就需要把語句表達成C++中的類型，然後eval就轉化成類型運算，核心代碼在 TemlatedPL/evaluator.hpp at master · Cheukyin/TemlatedPL · GitHub實現closure的話，就按SICP的環境模型，
當然模板並無現成數據結構可用，環境鏈的搜索與插入需要點tricks實現call/cc有點難度，
可以將每種continuation表達成不同的類型，eval時做CPS變換即可可以看看語法模樣，
比如下面定義一個Y Combinator：λf.( λx.(f λy. ((x x) y)) λx.(f λy.((x x) y)) )
自製編程語言
謝邀。既然你已經看過一些編譯原理的書籍，那應該知道寫一個編譯器的大概流程了。那何不通過寫一個現有語言的解析器來玩玩當作入門？
推薦Brainfuck語言，語法簡單，寫個Parser是分分鐘的事，然後直接寫一個基於棧的虛擬機解析執行也是分分鐘的事，基本上就是現在馬上就可以動手做起來了。做完之後可以考慮寫一個後端把它編譯成機器碼，或者加個JIT，玩法很多。從表達式 eval 做起。先找一個演算法把前端實現出來，用遞歸下降或調度場都好。然後遍歷 AST，計算表達式的值，並且支持代入變數。
然後有兩條一般的路徑：
1. 實現控制流，做成腳本語言；
2. 實現同像，做成 Lisp 方言；其實解釋器（和不帶靜態分析的編譯器）沒什麼門檻，編程剛入門的小孩就能做了。只要你硬著頭皮往下寫，會查資料就好。這個答案旨在把一些編譯器方面的概念串起來講成一個過程，請高手校正。
----正文----
先有一個狀態機的概念：你可以想像有一個無窮多個抽屜的柜子，柜子裡面可以放東西。一個程序基本上就是在這個柜子、這些抽屜裡面搞小動作，拉開抽屜開一下，放點東西進去，又去搞下一個。
那麼，要如何對這個狀態機機型操作呢？常見的方式有這兩種：
1. 自己發明一套指令集，來描述這個狀態機可以理解的基本操作
2. 通過抽象語法樹（Abstract Syntax Tree, 簡稱 AST）以及一個存儲「符號-狀態」的字典來操作如果走路線1，你可以先參考一下其他真實存在的CPU指令或者其他虛擬機指令，例如 Lua，.NET, Python, Java 什麼的，設計出一個你自己想要的指令集。這應該是比較難的路線，然而做得到位的話威力比較大。所以，如果你知道怎麼設計指令集，那麼我這個回答對你來說基本上沒什麼實際價值——後面我想說的，幾乎可以假設你懂了吧？
如果走路線2那就簡單得多了，基本上跟寫一個代數式求值器差不多，加減乘除就是代數式AST中的非葉子節點
（如果你沒做過代數式求值器，那麼建議你先試試這個入門練習再來求答案）。
那麼在你自製的腳本語言裡面，所有東西經過語法分析後，都會成為 AST 中的一個或者多個節點；所以只要你的解釋器能夠識別 AST 中的每一個節點所要求的動作，在遍歷 AST 的時候根據這些動作來操作「符號-狀態」字典，就相當於解釋執行了代碼。
所以你就要問了， AST 是什麼鬼？我的自製語言的代碼如何變成一個 AST？
以這個圖表示的語言為例，你的解釋器得先識別出 「while" "y" "Block" 這些東西（也就是 Lexer 的工作），再把這些 Lexical Token 組織成一個 AST ( Parser 的工作）。
為了簡單起見，你可以把 Lexer 和 Parser 還有 AST Walker 分開三個部分來寫。譬如 Lexer 打開文件並解析之後，輸出的是一個 Lexical Token 的鏈表。然後 Parser 的輸入就是這個鏈表，然後輸出的就是 AST。最後，Interpreter 也就是你的解釋器接收 AST 輸入，就執行了，沒有輸出。你可以試試用逆波蘭式裸奔：
1 2 add # 1+2的結果放入棧頂
3 4 mul # 3x4的結果放入棧頂
div # 棧頂兩個值相除，即3 / 12，結果放入棧頂
print # 列印棧頂的值
比較容易和runtime的邏輯直接對應。
詳情參見PostScript，超爽的。如果只是為了練習編譯原理，其實沒必要按書上的來，就算用C++也麻煩了，如果你會其他語言比如java，python，強烈建議不要用C++，會有很多不必要的麻煩詞法分析其實沒必要一定理解自動機什麼的，現在各種語言都有自己的正則庫，一個表達式搞定：
#用於解析token的正則表達式
_TOKEN_RE = re.compile(
#浮點數
r"""(d+.?d*[eE][+-]?w+|""" +
r""".d+[eE][+-]?w+|""" +
r"""d+.w*|""" +
r""".dw*)|""" +
#符號
r"""(!=|==|&<&<=|&<&<|&<=|&>&>=|&>&>|&>=|[-%^*+|/]=|||||++|--|W)|""" +
#整數
r"""(dw*)|""" +
#詞，關鍵字或標識符
r"""([a-zA-Z_]w*)""")
GitHub - paladin-t/my_basic: Easy extendable lightweight BASIC script interpreter written with C. It"s able to use it as a standalone interpreter or integrate it with existing projects. It fits well with Workstation, PC, Tablet, Pad, Mobile Phone, PDA, Video Game Console, Raspberry Pi, Intel Edison, Arduino and even MCU; totally portable to a dozen of operating systems.
我記得linux下有lex 和yacc可以用，自己百度下。
既然是腳本語言解析器，為何不從Lisp入手？Peter Norvig有兩篇文章，介紹了Lisp的簡單實現，簡單粗暴，同編譯原理基礎一起學習，對題主想必更有益處：
- (How to Write a (Lisp) Interpreter (in Python))
- (An ((Even Better) Lisp) Interpreter (in Python)
最重要的，題主想要用C++來做一個腳本語言解釋器，Norvig大神有一個Java版本的Lisp實現，思路同其兩篇文章中所寫完全一致，代碼極易理解，轉化為C++代碼也不會很複雜：
- JScheme: Scheme implemented in Java
最後，題主也可以結合Python源代碼閱讀陳儒先生的Python源碼剖析 (豆瓣)，看一下現實中的腳本語言是如何實現的，其中涉及到編程語言的方方面面，想必題主定能受益匪淺。
just for fun的話，先從最簡單的做起，等你支持了幾個常見語法後，再回去看書，會有趣很多。
題主可以看看這篇文章：
用C語言寫解釋器（一）——我們的目標作者用 C 語言寫了一個類似 BASIC 語言的解釋器，講得很詳細，很適合學習。我也參考這篇文章，自己寫了一個解釋器：創造一門程序設計語言，寫一個解釋器這是我寫的，修改了一些部分。這兩個都不是編譯型的。ChaiScript ChaiScript - Easy to use scripting for C++. 是一個用 c++ 開發的類 c++ 語法的腳本。特點是 header only, thread safe, open source。它的源代碼回答了題主所有的問題。去讀吧。
遊戲腳本高級編程 (豆瓣) 看看這個本書也不錯，非常簡單。
編譯原理課後花了一個周末寫的KunLang http://github.com/neonum/kun
https://github.com/morrow1nd/luax/ 一個lua的精簡版，6000行代碼，文檔全面
有一個很小的BASIC解釋器——ubasic，你可以了解一下，很容易懂的。
題主是個好程序員，實現腳本解釋器其實不難，基本就是按照 @RednaxelaFX的思路，一步一步細化，每一步難度都不大，不太需要什麼理論指導，有比較強的編程能力就行。
我這有一個自己實現的解釋器（工作之餘愛好所作），語法吸收了js、java、c++各自的特點，已有比較完備的語法支持，添加了不少新的語法特性（如：循環表達式、不限位整數、引用重置、冪運算符，等等）。下面為實現的粗略過程：
1、表達式的解析和計算 a、定義要支持的表達式特性和數據類型。搞清楚雙目運算符、單目運算符、括 號、優先順序，以及運算符和操作數等的語法意義，可以先考慮最簡單的+-*/和 括弧。要點：操作數可以是子表達式，關於優先順序，普通雙目 &< 單目 &< 成員 訪問符，普通雙目的優先順序可以任意設定。 b、錯誤處理機制（錯誤類型需逐步添加，實現的過程中會遇到各種各樣的錯誤 類型）。 c、定義標識符、常數、常量字元串等的書寫規則。詞法分析，獲取最小語義單 詞序列。實現要點：標識符的識別，注釋處理，空白字元串處理，常數識別 計算。 d、根據最小語義序列建立表達式計算樹。實現要點：遞歸分析或循環分析都可 以。 e、計算表達式計算樹。實現要點：主要為遞歸計算。2、多語句腳本的解析和執行
a、定義要支持的語句。必須的如：if/else/else if，while/for/break/continue，函 數。後期可引入結構體/類，成員函數等。 b、設計變數的定義語法和內存模式，執行堆棧設計，函數的實現方式。 c、分析語句序列，存儲到線性表。 d、設計執行入口方式，找到入口點，解釋執行。每條普通語句就是一個表達 式，調用步驟1的庫即可。實現要點：if/else/else if，while，for等就用原生 語言的同等語法實現。 當然每個過程都需要有好的軟體架構模塊設計，各個過程需要經常反覆回溯細化改進。將代碼轉換為抽象語法樹，然後遞歸解釋執行即可，閉包的實現有些難度。
寫腳本無非是想利用自己已經寫好的程序資源，來運行我們希望的流程。如果宏代碼只是為了實現某種目的，並不需要自己實現複雜的解釋器，因為有編譯器可以利用，將你的腳本先翻譯成源碼，然後動態調用編譯器把他編譯成執行文件或庫執行，是一個好辦法。。。 當然還有就是自行實現位元組碼，將自己的腳本進行語法分析，然後轉換位元組碼，由自己寫的一個虛擬機來執行，這是一個不錯的辦法，在不利用編譯器的情況，運行速度也有保證，但缺點就是難度很大。。 我覺得你應該試著用第一種方法，這個難度不大，很多程序也是這麼實現腳本功能的，腳本寫的幾乎就是源碼，畢竟你不能指望腳本解決任何問題，他是解決你希望的一類問題。。。。
推薦閱讀：
※c語言中實際上不存在賦值語句？
※為什麼GCC會把0xBE-0x33解釋為浮點數？
※c語言中指針指向的非指針變數不能使用++或--嗎?
※指針是如何記住步長的？
※C中有沒有將一個函數轉變為另一個函數的函數(例如求導運算)?