程序的語法

jopen 8年前發布 | 12K 次閱讀 Python

『我不生產代碼，我只是代碼的搬運工。』當然了，這是一個玩笑。說到代碼，我們要學習各種編程語言，學習如何讓編譯器能懂我們編寫的代碼。但是，編譯器是如何做到能聽懂我們的話的呢？按照我們既定的語句一行行的去執行，最終達到我們的目的。這篇文章，我會講一個很簡單的四則運算解釋器，通過使用 Python 實現它來一步步了解一個解釋器是如何工作的，它們又是怎么得到我們想要的結果的。

語法

計算機語言同樣也是一種語言，是一種計算機能夠理解的語言，我們想要和計算機對話，就要去學習這種語言。和我們人類的語言一樣，計算機語言也是有語法的。以漢語為例，我說『我是中國人』，因為漢語的語法，你聽到這句話之后會知道『我』是主語，『是』是謂語，『中國人』是賓語，同時你又很清楚每一個成分的含義，最終理解了整句話的意思。

同樣，對于計算機語言也是一樣，有著程序的語法，一個解釋器知道哪個詞是操作數，哪個是操作符，哪個是關鍵字，它們都有著怎樣的含義和功能，通過解釋器的解釋，計算機明白了某行語句的意義，然后進行運算，得到最后的執行結果。

語法圖

語法圖就是用來表示一種編程語言語法規則設計的示意圖，它很直觀的顯示出了在一種編程語言中，允許使用的語句和不支持的語句。語法圖十分易于閱讀：只需跟隨箭頭指示的路徑。一些路徑表示選擇。另一些路徑表示循環。

一個簡單的語法圖

這里我們舉一個語法圖的例子：

這個語法圖就是一個描述了簡單的加減運算的語法圖，term 在其中的意思就是一個操作數，一開始輸入一個操作數，有三條路徑可以選擇『+』，『-』和退出，如果進入了『+』、『-』路徑，則需要再輸入一個操作數，之后的路徑包括『+』、『-』和退出，如此循環，就能解釋一個簡單的加減法解釋器。

根據上邊的語法圖，下面的表達式都是合法的：

4
1 + 1
1 + 4 - 3

下面的表達式不合法：

-
+ -
2 +
+ 3 - 3

語法圖可以幫助我們：

用圖的方式表示出一種計算機語言的設計規范
可以幫助理解解釋器，將圖表表示成代碼

代碼實現（Python）

學習一樣東西最簡單的就是閱讀代碼（Read the Fucking Code！），因此我們先來看完整代碼然后再來分析一下，完整代碼在： https://github.com/luoyhang003/Pascal-Interpreter/blob/master/calc3.py

# Token Types:
EOF: End-Of-File
INTEGER, PLUS, MINUS, EOF = 'INTEGER', 'PLUS', 'MINUS', 'EOF'
class Token(object):
    def init(self, type, value):

    # Token types: INTEGER, PLUS, MINUS, EOF
    self.type = type
    # Token value: 0,1,2,3,4,5,6,7,8,9,+,None
    self.value = value

def __str__(self):
    """ The format of the print infomation For examle: Token(INTEGER, 3) Token(PLUS, '+') Token(MINUS, '-') """
    return 'Token({type},{value})'.format(
            type = self.type,
            value = repr(self.value)
            )

def __repr__(self):
    return self.__str__()


class Interpreter(object):
    def init(self, text):

    # Process the whole input
    # e.g. 3+5
    self.text = text
    self.pos = 0
    self.current_token = None
    self.current_char = self.text[self.pos]

def error(self):
    raise Exception('Error Parsing Error!')

def advance(self):
    # Advance the pos and set current_char
    self.pos += 1

    if self.pos > len(self.text)-1:
        self.current_char = None
    else:
        self.current_char = self.text[self.pos]

def skip_whitespace(self):
    # Skip space
    while self.current_char is not None and self.current_char.isspace():
        self.advance()

def integer(self):
    # Support mutidigit integer
    result = ''

    while self.current_char is not None and self.current_char.isdigit():
        result += self.current_char
        self.advance()

    return int(result)

def get_next_token(self):
    """ Lexical Analyzer: Parsing the input into tokens. Strategy: 1. is pos past the end of the text? 2. if so, return EOF 3. get a character at pos, and decide its type depends on the single char 4. if it is a space, advance the pos 5. if it is a digit, then convert it to integer and return INTEGER token 6. if it is a '+', then return PLUS token 7. if it is a '-', then return MINUS token """

    while self.current_char is not None:

        if self.pos > len(self.text) - 1:
            return Token(EOF, None)

        current_char = self.text[self.pos]

        if current_char.isspace():
            self.skip_whitespace()
            continue

        if current_char.isdigit():
            return Token(INTEGER, self.integer())

        if current_char == '+':
            self.advance()
            return Token(PLUS, '+')

        if current_char == '-':
            self.advance()
            return Token(MINUS, '-')


        self.error()

    return Token(EOF, None)

def eat(self, token_type):
    # compare the current token with the passed token type
    # if they match then eat the current token and assign next token to the self.current_token
    # otherwise raise an Exception

    if self.current_token.type == token_type:
        self.current_token = self.get_next_token()
    else:
        self.error()

def term(self):
    # return an Integer Token's value
    token = self.current_token
    self.eat(INTEGER)
    return token.value





def expr(self):
    # expr -> INTEGER PLUS INTEGER
    # expr -> INTEGER MINUS INTEGER

    self.current_token = self.get_next_token()

    result = self.term()

    while self.current_token.type in (PLUS, MINUS):
        token = self.current_token
        if token.type == PLUS:
            self.eat(PLUS)
            result += self.term()
        if token.type == MINUS:
            self.eat(MINUS)
            result -= self.term()

    return result


def main():
    while True:
        try:
            text = raw_input('cal> ')
        except EOFError:
            break
        if not text:
            continue

    interpreter = Interpreter(text)
    result = interpreter.expr()
    print(result)


if name == 'main':
    main()</pre> 
 
在代碼中，我們首先定義了四種 Token：整數（Integer）、加法（+）、減法（-）、終止符（EOF）

代碼中主要分為幾個主要部分：
 
  term 方法，在表達式中解析出一個整數

 
    def term(self):

    # return an Integer Token's value
    token = self.current_token
    self.eat(INTEGER)
    return token.value</pre> 

 
  expr 方法，根據語法圖的流程來解析語句

 
    def expr(self):

    # expr -> INTEGER PLUS INTEGER
    # expr -> INTEGER MINUS INTEGER

    self.current_token = self.get_next_token()

    result = self.term()

    while self.current_token.type in (PLUS, MINUS):
        token = self.current_token
        if token.type == PLUS:
            self.eat(PLUS)
            result += self.term()
        if token.type == MINUS:
            self.eat(MINUS)
            result -= self.term()

    return result</pre> 

expr 方法，首先調用 term 方法獲取一個整數，然后判斷后邊的 Token 是加法還是減法，之后再獲取一個整數，然后進行運算，然后判斷之后還有沒有運算符，如果沒有就返回結果，如果還有就重復以上步驟。我們看到 expr 方法是嚴格按照語法圖進行解釋的。
執行結果
cal> 1+2
3
cal> 1+4-3
2
cal> 1+ 5 -6
0
cal> 1 +
Traceback (most recent call last):
  File "calc3.py", line 176, in <module>
    main()
  File "calc3.py", line 172, in main
    result = interpreter.expr()
  File "calc3.py", line 155, in expr
    result += self.term()
  File "calc3.py", line 136, in term
    self.eat(INTEGER)
  File "calc3.py", line 131, in eat
    self.error()
  File "calc3.py", line 54, in error
    raise Exception('Error Parsing Error!')
Exception: Error Parsing Error! 
 文法

文法是另一種被廣泛使用的、用于指定一種程序設計語言語法的表示法，它叫做『上下文無關文法』，簡稱文法。
為什么要使用文法？
 
  文法以更簡明的方式說明一種程序設計語言的語法。比起來語法圖，文法十分簡潔。

  文法可以用作很好的文檔

  文法可以非常方便的轉換成代碼（非常方便~）

 
文法原理
我們以『3 * 4 / 5 * 2』這樣的算數乘除表達式為例，它對應的文法表達式為：
expr: factor ((MUL | DIV) factor)*
factor: INTEGER
 一段文法由 一系列的規則（rule） 組成，在上述文法中，我們有兩條規則： expr: factor ((MUL | DIV) factor)* 和 factor: INTEGER 
 一條規則由由 一個非終結符（稱規則的頭或者左邊） 、 一個冒號： 、 一系列終結符非終結符（稱規則的主體或者右邊） 組成 
分析以上文法：
 
   expr 、 factor 這樣的變量叫做非終結符 

   MUL 、 DIV 、 Integer 這樣的標記稱為終結符 

   | 表示『或』，多選一。 (MUL | DIV) 表示要么 MUL（乘）要么 DIV（除） 

   ( ) 一對圓括號表示把終結符非終結符組合起來，就像 (MUL | DIV) 一樣 

   ( )* 表示匹配組合里面的內容 0 次或者多次，就像 while 循環 

 
 
  解釋一下 expr 規則：

   expr 可以是一個 factor 可選地接著一個乘法或者除法運算符，再接著另一個 factor，依次可選地接著一個乘法或者除法運算符，再接著另一個 factor…… 

 
現在我們以解釋『3 * 4 / 5 * 2』這樣的算數乘除表達式為例：
expr
factor ((MUL | DIV) factor)*
factor MUL factor ((MUL | DIV) factor)*
factor MUL factor DIV factor ((MUL | DIV) factor)*
factor MUL factor DIV factor MUL factor
INTEGER MUL INTEGER DIV INTEGER MUL INTEGER
 3       *   4       /   5       *   2 
 將文法映射稱為為代碼

 
  對于文法中定義的每一條規則 R，都可以在代碼中變成同名的方法 R()

   對于多個可選項 ( | ) 可以編程為 if-else 語句 

   可選的 ( )* 集合編程稱為 while 語句，表示可以循環 0~n 次 

 
因此，上述文法用代碼表示出來就是：
 
  factor 方法

 
def factor(self):

# return an Integer Token's value
# factor: Integer
token = self.current_token
self.eat(INTEGER)
return token.value</pre> 

 
  expr 方法

 
def expr(self):

# Arithmetic expression parser
# expr: factor( (MUL | DIV) factor)*
# factor: Integer

result = self.factor()

while self.current_token.type in (MUL, DIV):
    token = self.current_token

    if token.type == MUL:
        self.eat(MUL)
        result = result * self.factor()
    elif token.type == DIV:
        self.eat(DIV)
        result = result / self.factor()

return result</pre> 

擴充我們的文法
加入加減運算
因為，我們加入了加減運算，因此現在存在運算優先級問題，很顯然乘除運算優先級要高于加減運算
我們得到以下的優先級表格：
 
   
    
    操作符

    優先級

    結合性

   

   
   
    
     
     
       - 
     
 

    2

    左結合

   

    
     
     
       / 
     
 

    1

    左結合

   

  

 
根據優先級表格構建文法：
 
  為每個優先級定義一個非終結符。非終結符所在產生式的主體應該包含同等級的算術運算符和優先級高一級的非終結符

  為表達式創建一個額外的非終結符 factor 作為基本單位，在我們的例子中該基本單位是整數。通用的規則是如果你有 N 層優先級，那么你總共需要 N + 1 個非終結符：每層優先級需要一個非終結符，加上一個用作表達式基本單位的非終結符。

 
更新我們的文法：
expr: term ((PLUS | MINUS) term)*
term: factor ((MUL | DIV) factor)*
factor: INTEGER
加入括號表達式
在之前，我們的基本單位只有 INTEGER，這次我們加入括號表達式。
更新后的文法為：
expr: term ((PLUS | MINUS) term)*
term: factor ((MUL | DIV) factor)*
factor: INTEGER | LPAREN expr RPAREN
 
  LPAREN 表示左括號，RPAREN 表示右括號

  括號表達式內的非終結符 expr 表示 expr 規則

 
下面我們以『 3 * （1 + 5）』為例，來說明該文法是如何工作的：
  
最終的四則運算解釋器
 
   完整代碼見： https://github.com/luoyhang003/Pascal-Interpreter/blob/master/calc6.py 

 
# Token Types:
EOF: End-Of-File
INTEGER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, EOF = (
    'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', '(', ')', 'EOF'
)
class Token(object):
    def init(self, type, value):

    # Token types: INTEGER, PLUS, MINUS, MUL, DIV, EOF
    self.type = type
    # Token value: 0,1,2,3,4,5,6,7,8,9,,+,-,*,/,None
    self.value = value

def __str__(self):
    """ The format of the print infomation For examle: Token(INTEGER, 3) Token(PLUS, '+') Token(MINUS, '-') TOKEN(MUL, '*') TOEKN(LPAREN, ')') """
    return 'Token({type},{value})'.format(
            type = self.type,
            value = repr(self.value)
            )

def __repr__(self):
    return self.__str__()


class Lexer(object):
    def init(self, text):

    # Process the whole input
    # e.g. 3+ 5 * 2 - 4/2
    self.text = text
    self.pos = 0
    self.current_char = self.text[self.pos]

def error(self):
    raise Exception('Invalid character!')

def advance(self):
    # Advance the pos and set current_char
    self.pos += 1

    if self.pos > len(self.text)-1:
        self.current_char = None
    else:
        self.current_char = self.text[self.pos]

def skip_whitespace(self):
    # Skip space
    while self.current_char is not None and self.current_char.isspace():
        self.advance()

def integer(self):
    # Support mutidigit integer
    result = ''

    while self.current_char is not None and self.current_char.isdigit():
        result += self.current_char
        self.advance()

    return int(result)

def get_next_token(self):
    """ Lexical Analyzer: Parsing the input into tokens. Strategy: 1. dictate current char 2. if it is a space, advance the pos 3. if it is a digit, then convert it to integer and return INTEGER token 4. if it is a '+', then return PLUS token 5. if it is a '-', then return MINUS token 6. if it is a '*', then return MUL token 7. if it is a '/', then return DIV token 8. if it is a '(', then return LPAREN token 9. if it is a ')', then return RPAREN token """

    while self.current_char is not None:

        if self.current_char.isspace():
            self.skip_whitespace()
            continue

        if self.current_char.isdigit():
            return Token(INTEGER, self.integer())

        if self.current_char == '+':
            self.advance()
            return Token(PLUS, '+')

        if self.current_char == '-':
            self.advance()
            return Token(MINUS, '-')

        if self.current_char == '*':
            self.advance()
            return Token(MUL, '*')

        if self.current_char == '/':
            self.advance()
            return Token(DIV, '/')

        if self.current_char == '(':
            self.advance()
            return Token(LPAREN, '(')

        if self.current_char == ')':
            self.advance()
            return Token(RPAREN, ')')

        self.error()

    return Token(EOF, None)


class Interpreter(object):
    def init(self, lexer):
        self.lexer = lexer
        self.current_token = self.lexer.get_next_token()

def error(self):
    raise Exception('Invalid Syntax')

def eat(self, token_type):
    # compare the current token with the passed token type
    # if they match then eat the current token and assign next token to the self.current_token
    # otherwise raise an Exception

    if self.current_token.type == token_type:
        self.current_token = self.lexer.get_next_token()
    else:
        self.error()

def factor(self):
    # factor: Integer | LPAREN expr RPAREN
    token = self.current_token

    if token.type == INTEGER:
        self.eat(INTEGER)
        return token.value

    if token.type == LPAREN:
        self.eat(LPAREN)
        result = self.expr()
        self.eat(RPAREN)
        return result

def term(self):
    # term: factor( (MUL | DIV) factor)*
    # factor: Integer
    result = self.factor()

    while self.current_token.type in (MUL, DIV):
        token = self.current_token

        if token.type == MUL:
            self.eat(MUL)
            result = result * self.factor()
        elif token.type == DIV:
            self.eat(DIV)
            result = result / self.factor()

    return result

def expr(self):
    # expr: term( (PLUS | MINUS) term)*
    # term: factor( (MUL | DIV) factor)*
    # factor: Integer
    result = self.term()

    while self.current_token.type in (PLUS, MINUS):
        token = self.current_token

        if token.type == PLUS:
            self.eat(PLUS)
            result = result + self.term()
        elif token.type == MINUS:
            self.eat(MINUS)
            result = result - self.term()

    return result


def main():
    while True:
        try:
            text = raw_input('cal> ')
        except EOFError:
            break
        if not text:
            continue

    lexer = Lexer(text)
    interpreter = Interpreter(lexer)
    result = interpreter.expr()
    print(result)


if name == 'main':
    main()</pre> 
 
運行結果

cal> 1+1
2
cal> 1*3
3
cal> 1+3*3
10
cal> 5*(1+5)
30
cal> (5+6)/(3-1)*2
10 
 參考資料

 
    Python Cookbook(第3版) 
 

    Ruslan’s Blog 
 

 
 
   本文的版權歸作者 羅遠航 所有，采用 Attribution-NonCommercial 3.0 License 。任何人可以進行轉載、分享，但不可在未經允許的情況下用于商業用途；轉載請注明出處。感謝配合！ 

</div>
 </div>
來自： http://blog.csdn.net/luoyhang003/article/details/50532770
                    
                    
                         本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
                         轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
                         本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
                         本文地址：http://www.baiduhome.net/lib/view/open1453038075058.html
                         Python

程序的語法

語法

語法圖

一個簡單的語法圖

語法圖可以幫助我們：

代碼實現（Python）

相關經驗

相關資訊

相關文檔

目錄