設計類Python編譯器時如何處理tab和space縮進?

func fab(number):

if(number == 1):
return 1

if(number == 2):
return 2

return fab(number-1) + fab(number-2)

所設計語言如上圖。

執行以下C++代碼:

string text = readline(2)
for(i = 0;i &< text.length();i++){ cout&<&

得到該結果,tab應該如何識別?

在設計中的縮進考慮中,有必要將space和tab同時考慮嗎?


Python的做法大體是在tokenizer裡面做hack,大體思路就是解析行首有多少個space,再依靠縮進的歷史紀錄發射INDENT/DEDENT token.

Python為縮進定義了兩種額外的token類型,INDENT和DEDENT,你可以認為類似C的{, }. Tokenzier會在掃描字元流的同時注意當前縮進層級的變化,從而在適當的時候發射出INDENT和DEDENT token. Python的token類型定義見Include/token.h [projects] Contents of /python/trunk/Include/token.h

將題主貼出的那段代碼送入這樣的tokenizer解析,得到的token序列應該是這樣的(注意被插入的INDENT和DEDENT)

token [NAME]: func
token [NAME]: fab
token [LPAR]: (
token [NAME]: number
token [RPAR]: )
token [COLON]: :
token [NEWLINE]:
token [INDENT]:
token [NAME]: if
token [LPAR]: (
token [NAME]: number
token [EQEQUAL]: ==
token [NUMBER]: 1
token [RPAR]: )
token [COLON]: :
token [NEWLINE]:
token [INDENT]:
token [NAME]: return
token [NUMBER]: 1
token [NEWLINE]:
token [DEDENT]:
token [NAME]: if
token [LPAR]: (
token [NAME]: number
token [EQEQUAL]: ==
token [NUMBER]: 2
token [RPAR]: )
token [COLON]: :
token [NEWLINE]:
token [INDENT]:
token [NAME]: return
token [NUMBER]: 2
token [NEWLINE]:
token [DEDENT]:
token [NAME]: return
token [NAME]: fab
token [LPAR]: (
token [NAME]: number
token [MINUS]: -
token [NUMBER]: 1
token [RPAR]: )
token [PLUS]: +
token [NAME]: fab
token [LPAR]: (
token [NAME]: number
token [MINUS]: -
token [NUMBER]: 2
token [RPAR]: )
token [NEWLINE]:
token [DEDENT]:

為了識別出縮進層級的變化,Tokenzier維護了一個有界的indent stack以記錄每個縮進層級的空格數目(見Parser/tokenizer.h, struct tok_state [projects] Contents of /python/trunk/Parser/tokenizer.h),如果發現當前位置是行首,則讀入這一行前面的所有空白符並統計這些空白符能換算成多少個空格(如果遇見whitespace則認為是一個空格,如果遇見tabstop還需要進行一番七葷八素的運算(col = (col/tok-&>tabsize + 1) * tok-&>tabsize) )。如果這一行不全是空白或者注釋接下來就可以利用當前行的行首col和indstack棧頂的值決定是否要發射INDENT/DEDENT token了。

發射INDENT/DEDENT token的規則也簡單。如果當前行的行首位置col比indstack棧頂大,則將col壓入indstack並發射一個INDENT token; 如果col比indstack棧頂小,則不斷彈棧直到indstack.tos == col,每次彈棧都發射一個DEDENT token以表示一個層級的結束(注意這個步驟可能會發射不止一個DEDENT token)當然彈棧中可能會發現層級不一致的情況,此時可以直接爆"unindent does not match any outer indentation level."

(順提一下那個indstack是有界的,Python 2.7.9里MAXINDENT的定義是100,如果你寫一段縮進層級超過100的代碼會爆炸=w=

Tokenizer中和縮進處理相關的代碼見Parser/tokenizer.c [projects] Contents of /python/trunk/Parser/tokenizer.c

既然Tokenzier在縮進上直接做了hack,那麼parser拿到的token序列應該是帶有INDENT/DEDENT以識別塊的開始/結束的。於是這裡就可以用傳統的方法寫出一個塊的CFG了

(Grammar/Grammar) [projects] Contents of /python/trunk/Grammar/Grammar:

suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT

非終結符suite表示一個縮進塊,於是形如函數定義,if statement的產生式可以寫成這種形式:

funcdef: "def" NAME parameters ":" suite
if_stmt: "if" test ":" suite ("elif" test ":" suite)* ["else" ":" suite]
......

之後的處理就是老生常談了你懂得=w=

至於要不要將space和tab同時考慮取決於語言的設計,Python是space和tab都考慮的,當然你也可以像make一樣強制使用tab把space給reject掉=w=


關鍵詞: layout sensitive parsing, off-side rule

@Kontinuation 講的 lexer 插入偽 INDENT / DEDENT token 的方式是主流做法, 不過維護一個狀態變數會對實現 scannerless parser, online parser 或者 parallel parser 帶來一些困難.

另一個做法是在語法描述中添加 layout constraint --- 當然你的分析器生成程序要支持對語法添加約束, 例如 Antlr 可以用 {boolean-expr}? 指定 semantic predicate. 然後解析 python 函數定義的語法可以像這麼寫 (偽代碼):

funcdef: "def" NAME parameters ":" funcdef_body {
$5.line &> $1.line $5.col &> $1.col
}?
;

上面約束意思是: $5 (funcdef_body) 的開始行和列都必須大於 $1 ("def") 的開始行和列.

上面的規則在多個 funcdef 擺一起時會不會出現問題呢? 這同樣可以加約束:

funcdefs: funcdef | funcdef funcdefs { $2.col == $1.col }?

如果分析器生成程序內建 layout constraint, 那就可以多做一些自動優化和分析, 而且還能減少寫錯約束或者引入狀態變數導致的 bug. 例如 http://www.informatik.uni-marburg.de/~seba/publications/layout-parsing.pdf 給 SDF (syntax definitions formalism) 添加的 layout constraint 擴展.

寫起來就像這樣 (注意 SDF 和 Antlr/Bison 語法不同, 它是左右翻轉的):


ptl 裡面的做法是這樣,維護一個 stack,然後對每一個可能作為語句分隔符的行首:

  1. 如果行首的空白序列棧頂相同,判定為相同的縮進塊;
  2. 如果棧頂記錄的縮進序列是行首空白序列的真前綴,則判定為縮進,當前行首空白壓棧;

  3. 否則,嘗試退棧並和新的棧頂比對,若退到某一級棧頂和當前行空白相同了,則判定為縮出,否則(堆棧彈空了)語法錯。

於是你可以 tab 空白隨便用了,混用也沒可以,只要保證是前綴關係就行了


我有一個想法。

首先確定源代碼的縮進是由空格控制還是製表符控制,並在之後使用一致的方式進行處理。為了便於說明,下面不妨假設我們需要處理的代碼都是由製表符控制縮進的。

在詞法解析的階段,需要把製表符輸出為一個token,比如叫tabToken。然後對於每個語句,就有這樣一個特點:在換行符的後邊的tabToken數目就是代碼的層級數(特殊情況另說)。根據這個原理,處理的時候就可以在層級數變化的時候,插入花括弧token:當層級數變大的時候,插入左花括弧token;變小的時候,插入右花括弧token。

那麼,我們就可以使用處理C代碼的方法來處理Python代碼了。


先說結論:

正如 @飯米 和 @薛銀松 所說,處理這種基於縮進的語言,首先把 Tab 按照統一的規則替換成空格,然後根據空格的層級,解析生成 INDENT 和 DEDENT 兩種 Token,其實也就相當於把空格根據上下文縮進替換成 { 和 },然後縮進錯誤神馬的,用一個棧來存,INDENT 就進棧,DEDENT 就彈棧,大概這樣

然後說說如何解決的

首先查閱 Python 官方文檔(2. Lexical analysis),關於 Lexical Analysis 這塊的 Indentation 處理是這麼說的

Leading whitespace (spaces and tabs) at the beginning of a logical line is used
to compute the indentation level of the line, which in turn is used to determine
the grouping of statements.

First, tabs are replaced (from left to right) by one to eight spaces such that
the total number of characters up to and including the replacement is a multiple
of eight (this is intended to be the same rule as used by Unix). The total
number of spaces preceding the first non-blank character then determines the
line』s indentation. Indentation cannot be split over multiple physical lines
using backslashes; the whitespace up to the first backslash determines the
indentation.

然後放狗搜索 StackOverflow,發現有很多類似問題,比如下面這個

Parsing "off-side" (indentation-based) languages

然後下面這個鏈接給出了一個示例

c++ - Indentation control while developing a small python like language

最後,還是直接參考 Python 源碼比較準確,相關代碼位於 Python-2.7.9/Parser/tokenizer.c 的 1209 行到 1359 行

/* Get next token, after space stripping etc. */

static int
tok_get(register struct tok_state *tok, char **p_start, char **p_end)
{
register int c;
int blankline;

*p_start = *p_end = NULL;
nextline:
tok-&>start = NULL;
blankline = 0;

/* Get indentation level */
if (tok-&>atbol) {
register int col = 0;
register int altcol = 0;
tok-&>atbol = 0;
for (;;) {
c = tok_nextc(tok);
if (c == " ")
col++, altcol++;
else if (c == " ") {
col = (col/tok-&>tabsize + 1) * tok-&>tabsize;
altcol = (altcol/tok-&>alttabsize + 1)
* tok-&>alttabsize;
}
else if (c == "14") /* Control-L (formfeed) */
col = altcol = 0; /* For Emacs users */
else
break;
}
tok_backup(tok, c);
if (c == "#" || c == "
") {
/* Lines with only whitespace and/or comments
shouldn"t affect the indentation and are
not passed to the parser as NEWLINE tokens,
except *totally* empty lines in interactive
mode, which signal the end of a command group. */
if (col == 0 c == "
" tok-&>prompt != NULL)
blankline = 0; /* Let it through */
else
blankline = 1; /* Ignore completely */
/* We can"t jump back right here since we still
may need to skip to the end of a comment */
}
if (!blankline tok-&>level == 0) {
if (col == tok-&>indstack[tok-&>indent]) {
/* No change */
if (altcol != tok-&>altindstack[tok-&>indent]) {
if (indenterror(tok))
return ERRORTOKEN;
}
}
else if (col &> tok-&>indstack[tok-&>indent]) {
/* Indent -- always one */
if (tok-&>indent+1 &>= MAXINDENT) {
tok-&>done = E_TOODEEP;
tok-&>cur = tok-&>inp;
return ERRORTOKEN;
}
if (altcol &<= tok-&>altindstack[tok-&>indent]) {
if (indenterror(tok))
return ERRORTOKEN;
}
tok-&>pendin++;
tok-&>indstack[++tok-&>indent] = col;
tok-&>altindstack[tok-&>indent] = altcol;
}
else /* col &< tok-&>indstack[tok-&>indent] */ {
/* Dedent -- any number, must be consistent */
while (tok-&>indent &> 0
col &< tok-&>indstack[tok-&>indent]) {
tok-&>pendin--;
tok-&>indent--;
}
if (col != tok-&>indstack[tok-&>indent]) {
tok-&>done = E_DEDENT;
tok-&>cur = tok-&>inp;
return ERRORTOKEN;
}
if (altcol != tok-&>altindstack[tok-&>indent]) {
if (indenterror(tok))
return ERRORTOKEN;
}
}
}
}

tok-&>start = tok-&>cur;

/* Return pending indents/dedents */
if (tok-&>pendin != 0) {
if (tok-&>pendin &< 0) { tok-&>pendin++;
return DEDENT;
}
else {
tok-&>pendin--;
return INDENT;
}
}

again:
tok-&>start = NULL;
/* Skip spaces */
do {
c = tok_nextc(tok);
} while (c == " " || c == " " || c == "14");

/* Set start of current token */
tok-&>start = tok-&>cur - 1;

/* Skip comment, while looking for tab-setting magic */
if (c == "#") {
static char *tabforms[] = {
"tab-width:", /* Emacs */
":tabstop=", /* vim, full form */
":ts=", /* vim, abbreviated form */
"set tabsize=", /* will vi never die? */
/* more templates can be added here to support other editors */
};
char cbuf[80];
char *tp, **cp;
tp = cbuf;
do {
*tp++ = c = tok_nextc(tok);
} while (c != EOF c != "
"
(size_t)(tp - cbuf + 1) &< sizeof(cbuf)); *tp = ""; for (cp = tabforms; cp &< tabforms + sizeof(tabforms)/sizeof(tabforms[0]); cp++) { if ((tp = strstr(cbuf, *cp))) { int newsize = atoi(tp + strlen(*cp)); if (newsize &>= 1 newsize &<= 40) { tok-&>tabsize = newsize;
if (Py_VerboseFlag)
PySys_WriteStderr(
"Tab size set to %d
",
newsize);
}
}
}
while (c != EOF c != "
")
c = tok_nextc(tok);
}


我思考過這個問題: Cirru 解析縮進的方案

最後想的方案是用一個變數記錄上一次縮進的層級, 後面每解析一行做一次比對, 並刷新記錄,

我只考慮了空格, 而且語法也限定在很簡單的情況.

大多數基於縮進的語言都是同時支持 Tab 跟空格的, 我好像只看到 Nim 只支持空格的.

如果是發布給他人使用, 照顧不同的使用習慣是有必要考慮的.


個人感覺可以把tab和換行符當成token處理。
* 這樣,記錄 的數量,這樣處理每一個statement都可以方便地知道在哪一層縮進了。


這真是程序界的恐怖故事:你以為makefile快掛了,結果它在python上復活


推薦閱讀:

為什麼所有的教科書中都不贊成手寫自底向上的語法分析器?
學好c++,是不是最好研究下其編譯器?因為感覺c++的編譯器做了很多僅從語言前端看不出的工作。?
如何去學習程序員的三大浪漫,編譯原理,圖形學,操作系統?
寄存器分配問題?

TAG:Python | 編譯原理 | 編譯器 |