使用Python編寫(xiě)一個(gè)最基礎(chǔ)的代碼解釋器的要點(diǎn)解析

更新時(shí)間：2016年07月12日 18:31:29 作者：chosen0ne

Python、Ruby等語(yǔ)言代碼就是在解釋器程序中一行行被解釋為機(jī)器碼同步執(zhí)行的,而如果使用Python編寫(xiě)解釋器的話則可以把目標(biāo)代碼解釋為Python代碼再進(jìn)行解釋執(zhí)行,這里我們就來(lái)看一下使用Python編寫(xiě)一個(gè)最基礎(chǔ)的代碼解釋器的要點(diǎn)解析:

一直以來(lái)都對(duì)編譯器和解析器有著很大的興趣，也很清楚一個(gè)編譯器的概念和整體的框架，但是對(duì)于細(xì)節(jié)部分卻不是很了解。我們編寫(xiě)的程序源代碼實(shí)際上就是一串字符序列，編譯器或者解釋器可以直接理解并執(zhí)行這個(gè)字符序列，這看起來(lái)實(shí)在是太奇妙了。本文會(huì)用Python實(shí)現(xiàn)一個(gè)簡(jiǎn)單的解析器，用于解釋一種小的列表操作語(yǔ)言（類似于python的list）。其實(shí)編譯器、解釋器并不神秘，只要對(duì)基本的理論理解之后，實(shí)現(xiàn)起來(lái)也比較簡(jiǎn)單（當(dāng)然，一個(gè)產(chǎn)品級(jí)的編譯器或解釋器還是很復(fù)雜的）。
這種列表語(yǔ)言支持的操作：

veca = [1, 2, 3]  # 列表聲明 
vecb = [4, 5, 6] 
print 'veca:', veca   # 打印字符串、列表，print expr+ 
print 'veca * 2:', veca * 2   # 列表與整數(shù)乘法 
print 'veca + 2:', veca + 2   # 列表與整數(shù)加法 
print 'veca + vecb:', veca + vecb  # 列表加法 
print 'veca + [11, 12]:', veca + [11, 12]   
print 'veca * vecb:', veca * vecb  # 列表乘法 
print 'veca:', veca 
print 'vecb:', vecb

對(duì)應(yīng)輸出：

veca: [1, 2, 3] 
veca * 2: [2, 4, 6] 
veca + 2: [1, 2, 3, 2] 
veca + vecb: [1, 2, 3, 2, 4, 5, 6] 
veca + [11, 12]: [1, 2, 3, 2, 11, 12] 
veca * vecb: [4, 5, 6, 8, 10, 12, 12, 15, 18, 8, 10, 12] 
veca: [1, 2, 3, 2] 
vecb: [4, 5, 6]

編譯器和解釋器在處理輸入字符流時(shí)，基本上和人理解句子的方式是一致的。比如：

I love you.

如果初學(xué)英語(yǔ)，首先需要知道各個(gè)單詞的意思，然后分析各個(gè)單詞的詞性，符合主-謂-賓的結(jié)構(gòu)，這樣才能理解這句話的意思。這句話就是一個(gè)字符序列，按照詞法劃分就得到了一個(gè)詞法單元流，實(shí)際上這就是詞法分析，完成從字符流到詞法單元流的轉(zhuǎn)化。分析詞性，確定主謂賓結(jié)構(gòu)，是按照英語(yǔ)的語(yǔ)法識(shí)別出這個(gè)結(jié)構(gòu)，這就是語(yǔ)法分析，根據(jù)輸入的詞法單元流識(shí)別出語(yǔ)法解析樹(shù)。最后，再結(jié)合單詞的意思和語(yǔ)法結(jié)構(gòu)最后得出這句話的意思，這就是語(yǔ)義分析。編譯器和解釋器處理過(guò)程類似，但是要略微復(fù)雜一些，這里只關(guān)注解釋器：

2016712182247047.jpg (496×197)

我們只是實(shí)現(xiàn)一個(gè)很簡(jiǎn)單的小語(yǔ)言，所以不涉及到語(yǔ)法樹(shù)的生成，以及后續(xù)復(fù)雜的語(yǔ)義分析。下面我就來(lái)看看詞法分析和語(yǔ)法分析。
詞法分析和語(yǔ)法分析分別由詞法解析器和語(yǔ)法解析器完成。這兩種解析器具有類似的結(jié)構(gòu)和功能，它們都是以一個(gè)輸入序列為輸入，然后識(shí)別出特定的結(jié)構(gòu)。詞法解析器從源代碼字符流中解析出一個(gè)一個(gè)的token（詞法單元），而語(yǔ)法解析器識(shí)別出子結(jié)構(gòu)和詞法單元，然后進(jìn)行一些處理?？梢酝ㄟ^(guò)LL(1)遞歸下降解析器實(shí)現(xiàn)這兩種解析器，這類解析器完成的步驟是：預(yù)測(cè)子句的類型，調(diào)用解析函數(shù)匹配該子結(jié)構(gòu)、匹配詞法單元，然后按照需要插入代碼，執(zhí)行自定義操作。
這里對(duì)LL(1)做簡(jiǎn)要介紹，語(yǔ)句的結(jié)構(gòu)通常用樹(shù)型結(jié)構(gòu)表示，稱為解析樹(shù)，LL(1)做語(yǔ)法解析就依賴于解析樹(shù)。比如：x = x +2;

2016712182509962.png (187×248)
在這棵樹(shù)中，像x、=和2這樣的葉節(jié)點(diǎn)，稱為終結(jié)節(jié)點(diǎn)，其他的叫做非終結(jié)節(jié)點(diǎn)。LL(1)解析時(shí)，不需要?jiǎng)?chuàng)建具體的樹(shù)型數(shù)據(jù)結(jié)構(gòu)，可以為每個(gè)非終結(jié)節(jié)點(diǎn)編寫(xiě)解析函數(shù)，在遇到相應(yīng)節(jié)點(diǎn)時(shí)進(jìn)行調(diào)用，這樣就可以通過(guò)解析函數(shù)的調(diào)用序列中（相當(dāng)于樹(shù)的遍歷）獲得解析樹(shù)的信息。在LL(1)解析時(shí)，是按照從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的順序執(zhí)行的，所以這是一個(gè)“下降”的過(guò)程，而解析函數(shù)又可以調(diào)用自身，所以是“遞歸”的，因此LL(1)又叫做遞歸下降解析器。
LL(1)中兩個(gè)L都是left-to-right的意思，第一個(gè)L表示解析器按從左到右的順序解析輸入內(nèi)容，第二個(gè)L表示在下降過(guò)程中，也是按照從左到右的順序遍歷子節(jié)點(diǎn)，而1表示根據(jù)1個(gè)向前看單元做預(yù)測(cè)。
下面看一下列表小語(yǔ)言的實(shí)現(xiàn)，首先是語(yǔ)言的文法，文法用于描述一個(gè)語(yǔ)言，算是解析器的設(shè)計(jì)說(shuō)明書(shū)。

statlist: stat+ 
stat: ID '=' expr 
  | 'print' expr (, expr)* 
expr: multipart ('+' multipart)* 
  | STR 
multipart: primary ('*' primary)* 
primary: INT 
  | ID 
  | '[' expr (',', expr)* ']' 
INT: (1..9)(0..9)* 
ID: (a..z | A..Z)* 
STR: (\".*\") | (\'.*\')

這是用DSL描述的文法，其中大部分概念和正則表達(dá)式類似。"a|b"表示a或者b，所有以單引號(hào)括起的字符串是關(guān)鍵字，比如：print，=等。大寫(xiě)的單詞是詞法單元?？梢钥吹竭@個(gè)小語(yǔ)言的文法還是很簡(jiǎn)單的。有很多解析器生成器可以自動(dòng)根據(jù)文法生成對(duì)應(yīng)的解析器，比如：ANTRL，flex，yacc等，這里采用手寫(xiě)解析器主要是為了理解解析器的原理。下面看一下這個(gè)小語(yǔ)言的解釋器是如何實(shí)現(xiàn)的。
首先是詞法解析器，完成字符流到token流的轉(zhuǎn)換。采用LL(1)實(shí)現(xiàn)，所以使用1個(gè)向前看字符預(yù)測(cè)匹配的token。對(duì)于像INT、ID這樣由多個(gè)字符組成的詞法規(guī)則，解析器有一個(gè)與之對(duì)應(yīng)的方法。由于語(yǔ)法解析器并不關(guān)心空白字符，所以詞法解析器在遇到空白字符時(shí)直接忽略掉。每個(gè)token都有兩個(gè)屬性類型和值，比如整型、標(biāo)識(shí)符類型等，對(duì)于整型類型它的值就是該整數(shù)。語(yǔ)法解析器需要根據(jù)token的類型進(jìn)行預(yù)測(cè)，所以詞法解析必須返回類型信息。語(yǔ)法解析器以iterator的方式獲取token，所以詞法解析器實(shí)現(xiàn)了next_token方法，以元組方式(type, value)返回下一個(gè)token，在沒(méi)有token的情況時(shí)返回EOF。

''''' 
A simple lexer of a small vector language. 
 
statlist: stat+ 
stat: ID '=' expr 
  | 'print' expr (, expr)* 
expr: multipart ('+' multipart)* 
  | STR 
multipart: primary ('*' primary)* 
primary: INT 
  | ID 
  | '[' expr (',', expr)* ']' 
INT: (1..9)(0..9)* 
ID: (a..z | A..Z)* 
STR: (\".*\") | (\'.*\') 
 
Created on 2012-9-26 
 
@author: bjzllou 
''' 
 
EOF = -1 
 
# token type 
COMMA = 'COMMA' 
EQUAL = 'EQUAL' 
LBRACK = 'LBRACK' 
RBRACK = 'RBRACK' 
TIMES = 'TIMES' 
ADD = 'ADD' 
PRINT = 'print' 
ID = 'ID' 
INT = 'INT' 
STR = 'STR' 
 
class Veclexer: 
  ''''' 
  LL(1) lexer. 
  It uses only one lookahead char to determine which is next token. 
  For each non-terminal token, it has a rule to handle it. 
  LL(1) is a quit weak parser, it isn't appropriate for the grammar which is 
  left-recursive or ambiguity. For example, the rule 'T: T r' is left recursive. 
  However, it's rather simple and has high performance, and fits simple grammar. 
  ''' 
   
  def __init__(self, input): 
    self.input = input 
     
    # current index of the input stream. 
    self.idx = 1 
     
    # lookahead char. 
    self.cur_c = input[0] 
     
  def next_token(self): 
    while self.cur_c != EOF: 
      c = self.cur_c 
       
      if c.isspace(): 
        self.consume() 
      elif c == '[': 
        self.consume() 
        return (LBRACK, c) 
      elif c == ']': 
        self.consume() 
        return (RBRACK, c) 
      elif c == ',': 
        self.consume() 
        return (COMMA, c) 
      elif c == '=': 
        self.consume() 
        return (EQUAL, c) 
      elif c == '*': 
        self.consume() 
        return (TIMES, c) 
      elif c == '+': 
        self.consume() 
        return (ADD, c) 
      elif c == '\'' or c == '"': 
        return self._string() 
      elif c.isdigit(): 
        return self._int() 
      elif c.isalpha(): 
        t = self._print() 
        return t if t else self._id() 
      else: 
        raise Exception('not support token') 
     
    return (EOF, 'EOF') 
       
  def has_next(self): 
    return self.cur_c != EOF    
   
  def _id(self): 
    n = self.cur_c 
    self.consume() 
    while self.cur_c.isalpha(): 
      n += self.cur_c 
      self.consume() 
       
    return (ID, n) 
   
  def _int(self): 
    n = self.cur_c 
    self.consume() 
    while self.cur_c.isdigit(): 
      n += self.cur_c 
      self.consume() 
       
    return (INT, int(n)) 
   
  def _print(self): 
    n = self.input[self.idx - 1 : self.idx + 4] 
    if n == 'print': 
      self.idx += 4 
      self.cur_c = self.input[self.idx] 
       
      return (PRINT, n) 
     
    return None 
   
  def _string(self): 
    quotes_type = self.cur_c 
    self.consume() 
    s = '' 
    while self.cur_c != '\n' and self.cur_c != quotes_type: 
      s += self.cur_c 
      self.consume() 
    if self.cur_c != quotes_type: 
      raise Exception('string quotes is not matched. excepted %s' % quotes_type) 
     
    self.consume() 
     
    return (STR, s) 
       
  def consume(self): 
    if self.idx >= len(self.input): 
      self.cur_c = EOF 
      return 
    self.cur_c = self.input[self.idx] 
    self.idx += 1   
     
     
if __name__ == '__main__': 
  exp = ''''' 
    veca = [1, 2, 3] 
    print 'veca:', veca 
    print 'veca * 2:', veca * 2 
    print 'veca + 2:', veca + 2 
  ''' 
  lex = Veclexer(exp) 
  t = lex.next_token() 
   
  while t[0] != EOF: 
    print t 
    t = lex.next_token()

運(yùn)行這個(gè)程序，可以得到源代碼：

veca = [1, 2, 3] 
print 'veca:', veca 
print 'veca * 2:', veca * 2 
print 'veca + 2:', veca + 2

對(duì)應(yīng)的token序列：

('ID', 'veca') 
('EQUAL', '=') 
('LBRACK', '[') 
('INT', 1) 
('COMMA', ',') 
('INT', 2) 
('COMMA', ',') 
('INT', 3) 
('RBRACK', ']') 
('print', 'print') 
('STR', 'veca:') 
('COMMA', ',') 
('ID', 'veca') 
('print', 'print') 
('STR', 'veca * 2:') 
('COMMA', ',') 
('ID', 'veca') 
('TIMES', '*') 
('INT', 2) 
('print', 'print') 
('STR', 'veca + 2:') 
('COMMA', ',') 
('ID', 'veca') 
('ADD', '+') 
('INT', 2)

接下來(lái)看一下語(yǔ)法解析器的實(shí)現(xiàn)。語(yǔ)法解析器的的輸入是token流，根據(jù)一個(gè)向前看詞法單元預(yù)測(cè)匹配的規(guī)則。對(duì)于每個(gè)遇到的非終結(jié)符調(diào)用對(duì)應(yīng)的解析函數(shù)，而終結(jié)符（token）則match掉，如果不匹配則表示有語(yǔ)法錯(cuò)誤。由于都是使用的LL(1)，所以和詞法解析器類似，這里不再贅述。

''''' 
A simple parser of a small vector language. 
 
statlist: stat+ 
stat: ID '=' expr 
  | 'print' expr (, expr)* 
expr: multipart ('+' multipart)* 
  | STR 
multipart: primary ('*' primary)* 
primary: INT 
  | ID 
  | '[' expr (',', expr)* ']' 
INT: (1..9)(0..9)* 
ID: (a..z | A..Z)* 
STR: (\".*\") | (\'.*\') 
 
example: 
veca = [1, 2, 3] 
vecb = veca + 4  # vecb: [1, 2, 3, 4] 
vecc = veca * 3  # vecc: 
 
Created on 2012-9-26 
 
@author: bjzllou 
''' 
import veclexer 
 
class Vecparser: 
  ''''' 
  LL(1) parser. 
  ''' 
   
  def __init__(self, lexer): 
    self.lexer = lexer 
     
    # lookahead token. Based on the lookahead token to choose the parse option. 
    self.cur_token = lexer.next_token() 
     
    # similar to symbol table, here it's only used to store variables' value 
    self.symtab = {} 
     
  def statlist(self): 
    while self.lexer.has_next(): 
      self.stat() 
   
  def stat(self): 
    token_type, token_val = self.cur_token 
     
    # Asignment 
    if token_type == veclexer.ID: 
      self.consume() 
       
      # For the terminal token, it only needs to match and consume. 
      # If it's not matched, it means that is a syntax error. 
      self.match(veclexer.EQUAL) 
       
      # Store the value to symbol table. 
      self.symtab[token_val] = self.expr() 
       
    # print statement 
    elif token_type == veclexer.PRINT: 
      self.consume() 
      v = str(self.expr()) 
      while self.cur_token[0] == veclexer.COMMA: 
        self.match(veclexer.COMMA) 
        v += ' ' + str(self.expr()) 
      print v 
    else: 
      raise Exception('not support token %s', token_type) 
     
  def expr(self): 
    token_type, token_val = self.cur_token 
    if token_type == veclexer.STR: 
      self.consume() 
      return token_val 
    else: 
      v = self.multipart() 
      while self.cur_token[0] == veclexer.ADD: 
        self.consume() 
        v1 = self.multipart() 
        if type(v1) == int: 
          v.append(v1) 
        elif type(v1) == list: 
          v = v + v1 
       
      return v      
   
  def multipart(self): 
    v = self.primary() 
    while self.cur_token[0] == veclexer.TIMES: 
      self.consume() 
      v1 = self.primary() 
      if type(v1) == int: 
        v = [x*v1 for x in v] 
      elif type(v1) == list: 
        v = [x*y for x in v for y in v1] 
         
    return v 
         
  def primary(self): 
    token_type = self.cur_token[0] 
    token_val = self.cur_token[1] 
     
    # int 
    if token_type == veclexer.INT: 
      self.consume() 
      return token_val 
     
    # variables reference 
    elif token_type == veclexer.ID: 
      self.consume() 
      if token_val in self.symtab: 
        return self.symtab[token_val] 
      else: 
        raise Exception('undefined variable %s' % token_val) 
     
    # parse list 
    elif token_type == veclexer.LBRACK: 
      self.match(veclexer.LBRACK) 
      v = [self.expr()] 
      while self.cur_token[0] == veclexer.COMMA: 
        self.match(veclexer.COMMA) 
        v.append(self.expr()) 
      self.match(veclexer.RBRACK) 
       
      return v 
     
   
  def consume(self): 
    self.cur_token = self.lexer.next_token() 
   
  def match(self, token_type): 
    if self.cur_token[0] == token_type: 
      self.consume() 
      return True 
    raise Exception('expecting %s; found %s' % (token_type, self.cur_token[0])) 
     
if __name__ == '__main__': 
  prog = ''''' 
    veca = [1, 2, 3] 
    vecb = [4, 5, 6] 
    print 'veca:', veca 
    print 'veca * 2:', veca * 2 
    print 'veca + 2:', veca + 2 
    print 'veca + vecb:', veca + vecb 
    print 'veca + [11, 12]:', veca + [11, 12] 
    print 'veca * vecb:', veca * vecb 
    print 'veca:', veca 
    print 'vecb:', vecb 
  ''' 
  lex = veclexer.Veclexer(prog) 
  parser = Vecparser(lex) 
  parser.statlist()

運(yùn)行代碼便會(huì)得到之前介紹中的輸出內(nèi)容。這個(gè)解釋器極其簡(jiǎn)陋，只實(shí)現(xiàn)了基本的表達(dá)式操作，所以不需要構(gòu)建語(yǔ)法樹(shù)。如果要為列表語(yǔ)言添加控制結(jié)構(gòu)，就必須實(shí)現(xiàn)語(yǔ)法樹(shù)，在語(yǔ)法樹(shù)的基礎(chǔ)上去解釋執(zhí)行。

您可能感興趣的文章: