如何使用Python開(kāi)發(fā)自己的編譯器

1. 前言

總所周知，編譯器是一個(gè)將一種語(yǔ)言（源語(yǔ)言）翻譯成另一種語(yǔ)言（目標(biāo)語(yǔ)言）的程序，如果我們只想使用它，我們只需要將它看作一個(gè)黑盒子即可不必關(guān)心它的實(shí)現(xiàn)，如圖1所示。


圖1 編譯器

但是如果你想發(fā)明一種新的語(yǔ)言，你就需要了解它的內(nèi)部構(gòu)造了，因?yàn)橐l(fā)明一門(mén)新語(yǔ)言，其實(shí)你需要做的就是編寫(xiě)一個(gè)新的編譯器。實(shí)際上，編譯器將源程序翻譯成目標(biāo)程序的過(guò)程可以分為詞法分析、語(yǔ)法分析、語(yǔ)義分析以及目標(biāo)代碼生成等多個(gè)階段，如圖2所示。通常，我們稱(chēng)詞法分析、語(yǔ)法分析、語(yǔ)義分析以及中間代碼生成這幾個(gè)階段為前端，而代碼優(yōu)化以及目標(biāo)代碼生成為后端。根據(jù)使用場(chǎng)景的不同，其中有些階段不是必須的，例如一個(gè)編譯器可以沒(méi)有中間代碼以及代碼優(yōu)化。但是即便一個(gè)只包含詞法分析、語(yǔ)法分析語(yǔ)義分析的簡(jiǎn)單編譯器，如果需要從零開(kāi)始也是比較困難的，需要非常熟悉編譯原理。


圖2 編譯器編譯過(guò)程

由于編譯原理太過(guò)復(fù)雜，為了能讓開(kāi)發(fā)一款編譯器變得更高效，出現(xiàn)了很多編譯器框架，例如著名的LLVM。在之前的文章LLVM，一堆積木的故事中介紹過(guò)，LLVM提供了所有編譯器所需的組件，我們只需要增加或者替換一些特定組件，就能實(shí)現(xiàn)一個(gè)新的編譯器。例如，只需要提供一個(gè)新的前端，你就能實(shí)現(xiàn)一個(gè)運(yùn)行在目前LLVM所支持的硬件的上的全新語(yǔ)言。

那么要怎么快速的實(shí)現(xiàn)自己的前端呢？這就是我們今天的主角——PLY——所做的事情。

2. 鋪墊

2.1. 詞法分析器

詞法分析的作用是將組成源程序的字符流識(shí)別成一個(gè)一個(gè)的記號(hào)（Token），并去除多余的空格以及注釋等，方便語(yǔ)法分析器進(jìn)行后續(xù)的語(yǔ)法分析，其工作原理如圖3所示。


圖3 詞法分析工作原理

例如在C語(yǔ)言中，詞法分析器會(huì)將int value = 100;這個(gè)表達(dá)式轉(zhuǎn)變?yōu)橄铝械囊粋€(gè)個(gè)記號(hào)：

int (keyword), value (identifier), = (operator), 100 (constant) and ; (symbol)

2.2. 語(yǔ)法分析器

語(yǔ)法分析器——也叫解析器——的作用就是將從詞法分析器獲得的記號(hào)流與給定的一條條規(guī)則進(jìn)行比對(duì)，從而檢測(cè)源程序中是否存在錯(cuò)誤，這些規(guī)則稱(chēng)為產(chǎn)生式（Production）。如果源程序沒(méi)有錯(cuò)誤，詞法分析器會(huì)輸出一個(gè)解析樹(shù)，也成為抽象語(yǔ)法樹(shù)（AST）。語(yǔ)法分析的工作原理如圖4所示。


圖4 語(yǔ)法分析器工作原理

2.3. BNF

既然詞法分析器是通過(guò)產(chǎn)生式來(lái)判斷源代碼是否有錯(cuò)誤，那么我們就得先知道產(chǎn)生式是什么東西。我們知道，每一種程序設(shè)計(jì)語(yǔ)言都有其描述語(yǔ)法規(guī)則的結(jié)構(gòu)，而這些描述語(yǔ)法的結(jié)構(gòu)就可以用上下文無(wú)關(guān)文法——也就是BNF范式——來(lái)描述。

BNF是由John Backus以及Peter Baur提出的，它可以用于描述上下文無(wú)關(guān)語(yǔ)言，例如可以用于描述以一個(gè)語(yǔ)言中的加減乘除操作，其形態(tài)如圖5所示。組成BNF范式的每一條規(guī)則就是一個(gè)產(chǎn)生式。

圖3 BNF示例

如上圖BNF范式所示，其描述了某種語(yǔ)言中的加法和乘法操作，例如在算數(shù)表達(dá)式24 * 43中，經(jīng)過(guò)詞法分析會(huì)得到24、*、43這三個(gè)記號(hào)，其中24、43都是id。我們首先通過(guò)第三條產(chǎn)生式將24、43都替換成了E，得到了E * E，之后，我們發(fā)現(xiàn)產(chǎn)生式2正好可以匹配，說(shuō)明算數(shù)表達(dá)式24 * 43是沒(méi)有語(yǔ)法錯(cuò)誤的。反之，由于這個(gè)BNF范式中沒(méi)有定義減法的產(chǎn)生式，因此對(duì)于算數(shù)表達(dá)式88 - 43，最終找不到與它想匹配的產(chǎn)生式，因此就會(huì)出現(xiàn)語(yǔ)法錯(cuò)誤。

2.4.Lex & Yacc

Lex 與 Yacc是用于構(gòu)建編譯器前端的兩個(gè)工具，他們分別由Eric Schmidt 與Stephen Johnson于上世紀(jì)70年代創(chuàng)造。Lex用于詞法分析，而Yacc（Yet Another Compiler Compiler）用于語(yǔ)法分析，后續(xù)的許多解析器都是他們的變種。
而今天介紹的PLY，就是Lex以及Yacc的純Python實(shí)現(xiàn)

2.5. PLY簡(jiǎn)介

PLY，全稱(chēng)為Python Lex-Yacc，是Lex以及Yacc的純Python實(shí)現(xiàn)，用于構(gòu)建編譯器的前端，Lex負(fù)責(zé)詞法分析，Yacc負(fù)責(zé)語(yǔ)法分析。他們擁有與傳統(tǒng)的Lex\Yacc一樣的功能。PLY這個(gè)庫(kù)的結(jié)構(gòu)很簡(jiǎn)單，就包含兩個(gè)重要文件lex.py 以及yacc.py。使用的時(shí)候只需要在你的工程下新建一個(gè)目錄并命名為ply然后將這兩個(gè)文件拷貝進(jìn)去，然后通過(guò)import ply.lex以及import ply.yacc這兩個(gè)語(yǔ)句導(dǎo)入就可以使用了。

3. PLY舉例

我們使用PLY的時(shí)候需要遵守一定的規(guī)則，根據(jù)需要定義一些我們需要的變量以及函數(shù)。PLY運(yùn)行的時(shí)候會(huì)通過(guò)自省的方式獲取到我們定義的變量以及參數(shù)用于進(jìn)行詞法分析以及語(yǔ)法分析。

3.1. Lex

首先我們來(lái)看看如果我們要使用Lex我們需要做些什么，我們將以下面的代碼為例子作為講解。

 import ply.lex as lex
  # List of token names.   This is always required
 tokens = (
    'NUMBER',
    'PLUS',
    'MINUS',
    'TIMES',
    'DIVIDE',
    'LPAREN',
    'RPAREN',
 )
 
 # Regular expression rules for simple tokens
 t_PLUS    = r'\+'
 t_MINUS   = r'-'
 t_TIMES   = r'\*'
 t_DIVIDE  = r'/'
 t_LPAREN  = r'\('
 t_RPAREN  = r'\)'
 
 # A regular expression rule with some action code
 def t_NUMBER(t):
     r'\d+'
     t.value = int(t.value)    
     return t
 
 # Define a rule so we can track line numbers
 def t_newline(t):
     r'\n+'
     t.lexer.lineno += len(t.value)
 
 # A string containing ignored characters (spaces and tabs)
 t_ignore  = ' \t'
 
 # Error handling rule
 def t_error(t):
     print("Illegal character '%s'" % t.value[0])
     t.lexer.skip(1)
 
 # Build the lexer
 lexer = lex.lex()

在上面的例子中，首先我們需要定義一個(gè)名叫tokens的列表，這個(gè)列表中包含了所有可能被Lex所處理的記號(hào)的名字，想要使用lex.py這個(gè)列表是必須要有的，因?yàn)長(zhǎng)ex的以及就是將輸入的源代碼轉(zhuǎn)換成一個(gè)一個(gè)記號(hào)，因此你需要定義一個(gè)記號(hào)的列表告訴Lex你的源代碼都可能出現(xiàn)些什么記號(hào)，yacc.py也會(huì)用到這個(gè)列表。

之后，我們需要為每一個(gè)記號(hào)的名字定義一個(gè)正則表達(dá)式，這些正則表達(dá)式的規(guī)則必須是與Python正則表達(dá)式庫(kù)re相兼容的，因?yàn)閘ex.py使用正則表達(dá)式來(lái)識(shí)別記號(hào)，并且每個(gè)正則表達(dá)式的名字都是以t_開(kāi)頭，后面緊跟著其對(duì)應(yīng)的記號(hào)的名字。例如我們給加號(hào)+定義的這則表達(dá)式為t_PLUS = r'\+'。如果我們還希望識(shí)別到某些特定的記號(hào)的時(shí)候進(jìn)行一些自定義的操作，我們可以使用函數(shù)代替，例如上面例子中當(dāng)識(shí)別到數(shù)字的時(shí)候我們希望將其轉(zhuǎn)換為對(duì)應(yīng)的數(shù)值類(lèi)型，我們便將t_NUMBER = r'\d+變成了下面的樣子：

 def t_NUMBER(t):
     r'\d+'
     t.value = int(t.value)    
     return t

其中函數(shù)的參數(shù)t是類(lèi)LexToken的實(shí)例，LexToken有四個(gè)常用屬性，分別是(type, value, lineno, lexpos)。函數(shù)的名字與普通的記號(hào)的遵循一樣的規(guī)則，都是以t_開(kāi)頭。函數(shù)的第一行是識(shí)別該記號(hào)的正則表達(dá)式，接下來(lái)是對(duì)識(shí)別到的記號(hào)的操作，最后需要將這個(gè)LexToken實(shí)例返回，如果該函數(shù)沒(méi)有返回值，則這個(gè)被處理的記號(hào)就會(huì)被直接丟棄。

緊接著，我們定義了一個(gè)特殊的函數(shù)t_nemline()用于記錄行數(shù)以及一個(gè)t_error()用于處理錯(cuò)誤。

最后我們執(zhí)行lexer = lex.lex()去生成一個(gè)詞法分析器。

3.2. Yacc

yacc.py是PLY中Yacc的實(shí)現(xiàn)，與lex.py類(lèi)似， 我們也通過(guò)一個(gè)例子來(lái)說(shuō)明在使用yacc.py之前我們需要做的事情。使用yacc.py之前，你應(yīng)該已經(jīng)有了一個(gè)BNF范式來(lái)描述你的語(yǔ)言。
例如對(duì)于算數(shù)運(yùn)算操作，我們定義了如圖4所示BNF范式。


圖4 加減乘除BNF范式

有了這個(gè)BNF范式之后，想要使用PLY的yacc模塊來(lái)進(jìn)行語(yǔ)法分析，所需要做的就是為每個(gè)產(chǎn)生式編寫(xiě)一個(gè)處理函數(shù)。下面的例子就是根據(jù)圖4的BNF范式寫(xiě)出的對(duì)應(yīng)的產(chǎn)生式的處理函數(shù)，每個(gè)函數(shù)可以只對(duì)應(yīng)一個(gè)語(yǔ)法規(guī)則，也可以對(duì)應(yīng)同一類(lèi)型的多個(gè)語(yǔ)法規(guī)則。例如可以把下面例子中分開(kāi)的加減乘除四個(gè)產(chǎn)生式的處理函數(shù)寫(xiě)成一個(gè)：

def p_expression_binop(p):
    '''expression : expression '+' expression
                  | expression '-' expression
                  | expression '*' expression
                  | expression '/' expression
                  '''
    if p[2] == '+' :
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]
    elif p[2] == '*':
        p[0] = p[1] * p[3]
    elif p[2] == '/':
        p[0] = p[1] / p[3]

import ply.yacc as yacc
 
 # Get the token map from the lexer.  This is required.
 from calclex import tokens
 
 def p_expression_plus(p):
     'expression : expression PLUS term'
     p[0] = p[1] + p[3]
 
 def p_expression_minus(p):
     'expression : expression MINUS term'
     p[0] = p[1] - p[3]
 
 def p_expression_term(p):
     'expression : term'
     p[0] = p[1]
 
 def p_term_times(p):
     'term : term TIMES factor'
     p[0] = p[1] * p[3]
 
 def p_term_div(p):
     'term : term DIVIDE factor'
     p[0] = p[1] / p[3]
 
 def p_term_factor(p):
     'term : factor'
     p[0] = p[1]
 
 def p_factor_num(p):
     'factor : NUMBER'
     p[0] = p[1]
 
 def p_factor_expr(p):
     'factor : LPAREN expression RPAREN'
     p[0] = p[2]
 
 # Error rule for syntax errors
 def p_error(p):
     print("Syntax error in input!")
 
 # Build the parser
 parser = yacc.yacc()
 
 while True:
    try:
        s = raw_input('calc > ')
    except EOFError:
        break
    if not s: continue
    result = parser.parse(s)
    print(result)

與給Lex模塊定義記號(hào)列表類(lèi)，這些為產(chǎn)生式編寫(xiě)的函數(shù)也要準(zhǔn)守一定的規(guī)則：

  1. 函數(shù)有兩部分組成：1）docstring，對(duì)應(yīng)的是該函數(shù)所處理的產(chǎn)生式；2）函數(shù)體，代表的是這個(gè)產(chǎn)生式的語(yǔ)義；
  2. 每個(gè)函數(shù)有且只有一個(gè)參數(shù)p（當(dāng)然參數(shù)的名字是任意的，如果樂(lè)意你可以叫它做狗蛋），這個(gè)p是一個(gè)數(shù)組，每個(gè)元素代表的是對(duì)應(yīng)的語(yǔ)法中的符號(hào)的值，例如圖5所示的函數(shù)處理的是expression : expression PLUS term這條語(yǔ)法規(guī)則，那么從p[0]到p[3]所對(duì)應(yīng)的值分別如圖中所示；
    image.png
  3. 函數(shù)必須以p_開(kāi)頭，后面的名字也不重要，例如你可以吧p_expression_plus改成p_dogegg；
  4. 函數(shù)出現(xiàn)的順序是有意義的，必須按照BNF范式定義的順序來(lái)定義處理產(chǎn)生式的函數(shù)，還拿圖4的BNF范式舉例，定義處理assign : NAME EQUALS expr的產(chǎn)生式的函數(shù)必須在處理其他產(chǎn)生的函數(shù)之前。

4. 例子

下面，我們就將上面的片段整合一下，開(kāi)發(fā)一個(gè)新的語(yǔ)言的編譯器，我們就叫它Hello World編譯器。它可以編譯任何加減乘除的數(shù)學(xué)表達(dá)式，然后執(zhí)行這個(gè)表達(dá)式，執(zhí)行的結(jié)果就是數(shù)學(xué)表達(dá)式計(jì)算得到結(jié)果是多少，就輸出多少個(gè)Hello World字符串，我們這門(mén)語(yǔ)言可能是最容易打出Hello World的語(yǔ)言了。

from utils import *

sys.path.insert(0, "../..")

tokens = (
    'NAME', 'NUMBER'
)

literals = ['=', '+', '-', '*', '/', '(', ')', ',']

# Tokens

t_NAME = r'[a-zA-Z_][a-zA-Z0-9_.:]*'

def t_NUMBER(t):
    r'\#?\d+'
    if t.value.startswith('#'):
        t.value = int(t.value[1:])
    else:
        t.value = int(t.value)
    return t

# Get the comments and discard it, therefore there is not return statement
# Note: only inline comment are permit

t_ignore = " \t"

def t_newline(t):
    r'\n+'
    t.lexer.lineno += t.value.count("\n")

def t_error(t):
    print("Illegal character '%s'" % t.value[0])
    t.lexer.skip(1)

# Build the lexer
import ply.lex as lex
lexer = lex.lex()

# Parsing rules

precedence = (
    ('left', '+', '-'),
    ('left', '*', '/'),
    ('right', 'UMINUS'),
)

# dictionary of names
names = {}
alias = {}

def p_statement_assign(p):
    '''statement : NAME "=" expression
    '''
    if p[2] == '=':
        names[p[1]] = p[3]


def p_statement_expr(pppp):
    '''statement : expression'''
    for i in range(pppp[1] ):
        print('Hello world!')


def p_expression_binop(p):
    '''expression : expression '+' expression
                  | expression '-' expression
                  | expression '*' expression
                  | expression '/' expression
                  '''
    if p[2] == '+' :
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]
    elif p[2] == '*':
        p[0] = p[1] * p[3]
    elif p[2] == '/':
        p[0] = p[1] / p[3]


def p_expression_uminus(p):
    "expression : '-' expression %prec UMINUS"
    p[0] = -p[2]


def p_expression_group(p):
    '''expression : '(' expression ')'
                  | '{' expression '}' '''
    p[0] = p[2]

def p_expression_list(p):
    '''
    expression : expression
               | expression ',' expression
    '''


def p_expression_number(p):
    "expression : NUMBER"
    p[0] = p[1]


def p_expression_name(p):
    "expression : NAME"
    try:
        if p[1] in alias:
            p[0] = names[alias[p[1]]]
        else:
            p[0] = names[p[1]]
    except LookupError:
        print("Undefined name '%s'" % p[1])
        p[0] = 0


def p_error(p):
    if p:
        print("Syntax error at '%s'" % p.value)
    else:
        print("Syntax error at EOF")

import ply.yacc as yacc
parser = yacc.yacc()

while True:
    try:
        s = input('hello world calc > ')
    except EOFError:
        break
    if not s:
        continue
    yacc.parse(s)

歡1迎2關(guān)3注4個(gè)5人6微7信8公9眾0號(hào): Tensorboy
源碼 | 原理 | 語(yǔ)言

5. References

[1] http://www.dabeaz.com/ply/ply.html#ply_nn24
[2] Compilers: Principles, Techniques and Tools: Chapter#2

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容