如何用Yacc實現一個Python的編譯器？

01-06

YACC for ansi C 的文法在很多地方都可以找到了。為什麼沒有Python的？如何把Python源代碼中的grammar編譯成yacc的？

理論上是可以的，關鍵點在於您要在Lexer和Parser之間要多加一層，用於分析哪些地方是進入縮進，哪些地方是退出縮進。然後匹配到縮進的時候插入INDENT和DEDENT這樣的Token。

至於分析的方法，您可以先建一個Stack來存放每一層縮進塊的Token，

然後根據Lexer送來的Token中的行號、列號等信息來和Stack棧頂的數據進行對比，

判斷下來是該進入縮進的就push一個INDENT,並這個INDENT插入到輸出的Token流中。

發現是Stack中舊的Token匹配的，就把之前的縮進塊pop出來，並在輸出的Token流中插入DEDENT。

然後在Paser層面處理語句塊的時候可以這樣處理（我只寫大概意思的偽碼，具體您自己看著辦）

block ::= INDENT NLS statements NLS DEDENT

if ::= IF LPAREN expression RPAREN COLON block

1：python這種靠縮進的語言的文法其實是上下文有關的，EBNF是表達不出來的，我不知道yacc是不是有什麼喪心病狂的擴展來給你做這個。

2：每一行前面的tab的數量你不要看成一堆tab，要把他的數量本身看成一個整體，也就是說再作語法分析的時候其實是：

[0]def fuck [1]if true: [2]fuck [1]else: [2]shit

[0]def shit ..

而不是原始的：

def fuck if true: fuck else: shit

def shit ..

3：根據python的標準，一個縮進要用多少個tab多少個space是可以在注釋裡面改的，也就是說你parse到一個地方，看到了那個注釋，這個量就變了，後面呵呵呵。

主要是縮進語法的問題吧，只要先在詞法上把python的縮進改成類似大括弧分界的語法即可，壓力在lex這邊

cpython源碼的token分析是用C手擼的，超長，可以看看源碼

補充一下 @vczh ，因為是上下文有關的，所以Yacc是不行的，不過我通過 peg, ometa 解決什麼問題,ometa-js怎麼入門/正確理解和認知? 這個問題知道 PEG 適合進行。

pyPEG 這個項目的主頁，底下就有對縮進的分析，可以參考一下。

我用C語言實現過一個簡化的python解釋器(https://github.com/linuxmooc/pylite)，用yacc來分析python的思路如下：

1. 在源程序中插入兩個虛擬的TOKEN：TOKEN_BEGIN和TOKEN_END

TOKEN_BEGIN標誌語法塊的開始，TOKEN_END標誌語法塊的結束。看一個例子：

while i &< 100: print i i += 1

在插入虛擬的TOKEN後，以上的Python程序變為：

while i &< 100: TOKEN_BEGIN print i i += 1 TOKEN_END

2. 編寫語法規則

group_clause: TOKEN_BEGIN clause_list TOKEN_END while_clause: TOKEN_WHILE expression : group_clause

因為語法塊以TOKEN_BEGIN作為引導，yacc很容易分析，不會產生歧義。

插入虛擬TOKEN的工作在詞法分析模塊中完成，大致思路如下：
1. Python中可以使用空格、TAB或者兩者混用作為縮進，為了簡單起見，這裡僅僅考慮使用TAB作為縮進的情況
2. 詞法分析器記錄每一行從行首開始的TAB數量
3. 將當前行的TAB數量(this_tabs)與上一行的TAB數量(prev_tabs)進行比較
(1) 如果this_tabs == prev_tabs，表明當前行和上一行的縮進相同，不插入虛擬的TOKEN
(2) 如果this_tabs == prev_tabs + 1，在當前行的行首處插入TOKEN_BEGIN
(3) 如果this_tabs &< prev_tabs，在當前行的行首處插入(prev_tabs - this_tabs)個TOKEN_END

需要注意的是，插入TOKEN_END時，可能會插入多個，比如下面的程序：

1 def main(): 2 while i &< 100: 3 print i 4 i += 1 # 行首有兩個tab, prev_tabs = 2 5 main() # 行首沒有tab, this_tabs = 0

在處理第5行main()的時候，發現prev_tabs=2、this_tabs=0，因此需要插入兩個TOKEN_END，變為：

def main(): TOKEN_BEGIN while i &< 100: TOKEN_BEGIN print i i += 1 TOKEN_END TOKEN_END main()

COOL都日出來了，python算個DIAO啊，文法拿去，玩吧。寫完了我們膜拜一下。

https://github.com/python-git/python/blob/master/Grammar/Grammar

答主現在還需要嗎？

你要找的是這個東西啊PLY (Python Lex-Yacc)

我用ply實現過pl0的編譯器也可以供答主參考：

duduscript/pl0: pl0 compiler writen in python

還不如直接看python源碼里的interpreter好了。

你沒詞法分析怎麼能用 grammar 呢

還是看看文檔吧

2. Lexical analysis

python/lexical_analysis.rst at master · python-git/python · GitHub

裡面有前面的人所說的 INDENT DEDENT token 的產生過程

以及他們漏掉的 NEWLINE token

－－－

先匿名把回頭再把坑填了