本文目錄：

  • 解釋器和編譯器
  • 實現一個簡單的加減計算器
  • 詞法分析
    • 概述
    • 代碼高亮
    • 詞法分析器的實現
  • 小結

讀完之後，我們應該可以知道：

  1. 編譯器和解釋器的主要區別
  2. 解釋器主要是由哪兩部分組成
  3. 怎樣實現一個詞法分析器
  4. 怎樣實現一個簡單的加減計算器

編程語言一直是民間討論的熱點話題之一，國慶的時候自己按照教程做了一個簡陋版的「解釋器」， 這裡記錄一下自己學習的心路歷程。

參考的學習資料主要是這個系列教程：Let』s Build A Simple Interpreter

在看到這個教程之前，我也有想過自己實現一個解釋器/編譯器，但是那時不知道從哪裡開始， 毫無頭緒。而實際上，我面臨的第一個問題就是：什麼是解釋器，解釋器和編譯器的區別是什麼？

解釋器和編譯器

解釋器定義：

In computer science, an interpreter is a computer program that directly executes, i.e. performs, instructions written in a programming or scripting language, without requiring them previously to have been compiled into a machine language program.

編譯器定義：

A compiler is computer software that transforms computer code written in one programming language (the source language) into another programming language (the target language).

The name compiler is primarily used for programs that translate source code from a high-level programming language to a lower level language (e.g., assembly language, object code, or machine code) to create an executable program.

簡單總結：兩者本身都是一個計算機程序，解釋器側重直接 執行 指令、代碼， 而常說的編譯器則側重將源代碼 轉換 成 機器碼。

實現一個簡單的加減計算器

問題一：編寫一個解釋器，解析執行 m+n（其中 m,n 都是 10 以內的自然數）

時間暫停，讀者可以腦補一下自己會怎麼實現。

我這裡有一個解法：

text = input(> )

def interprete(code):
try:
m = int(text[0])
plus = text[1]
n = int(text[2])
except Exception:
raise Exception(Syntax error.)
return m + n

print(interprete(text))

方法非常的簡單，分兩步：

1. 先解析程序代碼：先讀取第一個字元，記為為數字 m，讀取第二個字元， 記為加號，讀取第三個字元，記為數字 n

2. 執行解析結果：計算 m+n。

附加題：

  • 如果用戶輸入的 m+n 中間有一個或者多個空格怎麼辦？
  • 如果 m,n 可能會大於 10 怎麼辦？
  • 如果要求支持 m - n 呢？

一個解法：

from collections import namedtuple

Token = namedtuple(Token, (type_, value))

# Token types
INTERGER, OPERATOR, WHITESPACE, EOF = INTERGER, OPERATOR, WHITESPACE, EOF

class Lexer:
"""Calculator lexer: m +/- n, m and n are natural number.

lexer: also known as scanner or tokenzier.
"""
def __init__(self, text):
self.pos = 0
self.text = text

def eat_interger(self):
while self.pos < len(self.text) and self.text[self.pos].isdigit():
self.pos += 1

def eat_space(self):
while self.pos < len(self.text) and self.text[self.pos].isspace():
self.pos += 1

def get_tokens(self):
while self.pos < len(self.text):
c = self.text[self.pos]
if c.isdigit():
start_pos = self.pos
self.eat_interger()
end_pos = self.pos
yield Token(INTERGER, self.text[start_pos: end_pos])
self.pos += 1
continue
elif c.isspace(): # ignore
self.pos += 1
continue
elif c in (+, -):
yield Token(OPERATOR, c)
self.pos += 1
continue
yield Token(EOF, None)

def parse(tokens):
"""Simple parser: m +/- n
"""
m = next(tokens)
op = next(tokens)
n = next(tokens)
if op.value == +:
return int(m) + int(n)
else:
return int(m) - int(n)

tokens = Lexer(12 + 103).get_tokens()
print(parse(tokens))

# Output: 115

好像也不難，對不對？這個簡單的解釋器程序可以分為兩個步驟：

  1. 將字元串逐字解析成一串標記符 (Token)
  2. 按照加減法的語法規則解析這一串標記符並執行

其中，我們稱第一步為 詞法分析 (lexical analysis)， 進行詞法分析的工具叫做 詞法分析器 (lexer)。 第二步稱為 語法分析 (syntactic analysis, or parsing)， 進行語法分析的工具叫做 語法分析器 (parser)。 下面我們對第一步進行更深層次的研究學習，第二步在之後的筆記中進行詳細分析。

詞法分析

概念也很重要啦，再貼一下：

詞法分析（英語：lexical analysis）是計算機科學中將字元序列轉換為標記（token）序列的過程。

在上面的例子中，我們將字元串 12 + 103 分解成了 4 個 Token 供語法分析器使用：

這些標記符是有類型的，另外還有一個值。

時間暫停，下圖是一個 Emacs 編輯器，猜猜它的哪個技術用到了詞法分析？

答案：語法高亮：先識別字元類型，然後給它上個色，是不是很簡單。 想讓自己的編輯器顏色豐富起來？趕緊往下面看，2333

但是話說，實現一個這麼簡單的詞法分析器就有這麼多 if...else，是不是有的過分了？ 如果要實現一個真正的解釋器，這條件判斷得寫多長？有沒有什麼更優雅的方式呢？

詞法分析器的實現

從上面的加減法解釋器示例，我們也可以看出，詞法分析的方法其實很簡單：逐個字元的對字元串進行解析， 根據一個標記符的首字元來判斷標記符的類型，接著根據類型來解析這個標記符的起點和結尾。 循環往複即可解析出整個標記序列。

但是使用 isdigit + eat_interger, isspace eat_whitespce 這些方法來識別標記符的類型、開始結束位置，總感覺有點傻傻的。 如果有個更多 Token 類型，字元串、變數、函數名、關鍵字等，那這個詞法分析器的代碼是不是就難看了。

時間暫停，所以大家想想有沒有什麼更好的方法呢？

答案是：正則表達式，這是個實踐中真正在用的方法。

一個示例：

import re
from collections import namedtuple

Token = namedtuple(Token, (type_, value))

# Token types
INTERGER, OPERATOR, WHITESPACE, EOF = INTERGER, OPERATOR, WHITESPACE, EOF
PLUS, MINUS, MUL, DIV = PLUS, MINUS, MUL, DIV
LPAREN, RPAREN = LPAREN, RPAREN

class Lexer:
"""
支持解析加減乘除、括弧、數字、空格、換行
"""
regexes = [
(INTERGER, rd+),
(MINUS, r-),
(PLUS, r+),
(MUL, r*),
(DIV, r/),
(WHITESPACE, r[^S
]+),
(LPAREN, r(),
(RPAREN, r)),
]

def __init__(self, text):
self.text = text

self.pos = 0

#: current char
self.cc = self.text[self.pos]

def error(self, msg=lexer: Syntax Error.):
raise Exception(msg)

def get_tokens(self):
"""Tokenizer
"""
_tokens_func = []
for type_, regex in self.regexes:
_tokens_func.append((type_, re.compile(regex).match))

while 1:
for type_, rexmatch in _tokens_func:
m = rexmatch(self.text, self.pos)
if m:
self.pos = m.end()
value = m.group()
if type_ == INTERGER:
value = int(value)
elif type_ == WHITESPACE:
break
yield Token(type_, value)

break
else:
if self.pos == len(self.text):
break
else:
self.error()
yield Token(EOF, None)

for token in Lexer((1 + 2) * 5).get_tokens():
print(token)

### Ouput:

# Token(type_=LPAREN, value=()
# Token(type_=INTERGER, value=1)
# Token(type_=PLUS, value=+)
# Token(type_=INTERGER, value=2)
# Token(type_=RPAREN, value=))
# Token(type_=MUL, value=*)
# Token(type_=INTERGER, value=5)
# Token(type_=EOF, value=None)

pygments 是一個 Python 語法高亮庫，裡面有各種語言的詞法分析器，有興趣的童鞋可以去研究研究。

小結

本文簡單描述瞭解釋器和編譯器的區別，以一個簡單的加減法解釋器示例出發， 介紹了一些基本概念（如 Token, Lexer），並對詞法分析這一部分做了比較詳細的敘述。下次有機會再詳細總結一下語法分析部分的學習筆記。


推薦閱讀：
相關文章