譯自：https://ruslanspivak.com/lsbasi-part4/
（已獲得作者授權，個別陳述句翻譯的不到位，我會將原句跟在后邊作為參考）
你是在被動地學習這些文章中的材料還是在積極地實踐它？希望你一直在積極練習，
孔子曾經說過：
“聞之我也野，”
“視之我也饒，”
“行之我也明，”
在上一篇文章中，我們學習了如何決議（識別）和解釋具有任意數量的加或減運算的算術運算式，例如"7 - 3 + 2 - 1"，還了解了語法圖以及如何用它來表示(specify)編程語言的語法，
今天，你將學習如何決議和解釋具有任意數量的乘法和除法運算的算術運算式，例如"7 * 4 / 2 * 3"，本文中的除法將是整數除法，因此，如果運算式為"9 / 4"，則答案將是整數：2，
今天，我還將談論廣泛用于表示某一編程語言語法的標記方法，稱為背景關系無關文法或BNF（簡稱文法）（Backus-Naur形式），在本文中，我將不使用純BNF表示法，而使用修改后的EBNF表示法，
我們為什么要使用文法，這是幾個原因：
1、文法以簡潔的方式指定編程語言的語法，與語法圖不同，文法非常緊湊，在以后的文章中會越來越多地使用文法，
2、文法可以作為出色的檔案，
3、即使你是從頭開始手動撰寫決議器，文法也是一個不錯的起點，通常，你可以按照一組簡單的規則將文法轉換為代碼，
4、有一套稱為決議器生成器的工具，可以接受文法作為輸入，并根據該文法自動生成決議器，我將在本系列的后面部分討論這些工具，
這是一個描述算術運算式的文法，例如"7 * 4 / 2 * 3"（這只是該文法可以生成的眾多運算式之一）：
文法由一系列規則(rules)組成，也稱為productions，我們的文法有兩個規則：
一個規則由稱為head或left-hand side的非終結符(non-terminal)開始，然后跟上一個冒號(colon)，最后由稱為body或right-hand side的終結符(terminal)和/或非終結符(non-terminal)組成：(A rule consists of a non-terminal, called the head or left-hand side of the production, a colon, and a sequence of terminals and/or non-terminals, called the body or right-hand side of the production)
（這里我翻譯的很繞，直接看圖會更清楚一點）
在上面顯示的文法中，諸如MUL，DIV和INTEGER之類的標記稱為終結符(terminals)，而諸如expr和factor之類的變數稱為非終結符(non-terminals)，非終結符通常由一系列終結符和/或非終結符組成：(In the grammar I showed above, tokens like MUL, DIV, and INTEGER are called terminals and variables like expr and factor are called non-terminals. Non-terminals usually consist of a sequence of terminals and/or non-terminals)
第一條規則左側的非終結符稱為開始符(start symbol)，在我們的文法中，開始符是expr：
你可以將規則expr解釋為： “expr可以只是一個因數(factor)，也可以可選地跟上乘法或除法運算子，然后再乘以另一個因數，之后又可選地跟上乘法或除法運算子，然后再乘以另一個因數，當然之后也可以繼續回圈下去”(An expr can be a factor optionally followed by a multiplication or division operator followed by another factor, which in turn is optionally followed by a multiplication or division operator followed by another factor and so on and so forth)
是什么因數(factor)？在本文中，它只是一個整數，
讓我們快速瀏覽一下文法中使用的符號及其含義：
1、"|"，表示或者，因此(MUL | DIV)表示MUL或DIV，
2、"(…)"，表示(MUL | DIV)中的終結符和/或非終結符的一個組(grouping)，
3、"(…)*"，表示該組可以出現零次或多次，
如果你過去使用過正則運算式，那么這些符號你應該非常熟悉，
文法通過解釋如何形成句子來定義語言(A grammar defines a language by explaining what sentences it can form)，那么我們如何使用文法來推匯出算術運算式呢？有這幾個步驟：首先從起始符expr開始，然后用該非終止符的規則主體重復替換非終止符，直到生成僅包含終止符的句子為止，這樣我們就通過文法來形成了語言，(first you begin with the start symbol expr and then repeatedly replace a non-terminal by the body of a rule for that non-terminal until you have generated a sentence consisting solely of terminals. Those sentences form a language defined by the grammar)
如果文法不能匯出某個算術運算式，則表示它不支持該運算式，那么決議器在嘗試識別該運算式時將生成錯誤，
這里有幾個例子，你可以看看來加深理解：
1、這是推導一個整數"3"的步驟：
2、這是推導"3 * 7"的步驟：
3、這是推導"3 * 7 / 2"的步驟：
確實這部分包含很多理論！
當我第一次閱讀文法和相關術語時會感覺像這樣：
我可以向你保證，我絕對不是這樣的：
我花了一些時間來熟悉符號(notation)，理解它如何作業方式以及它與決議器和詞法分析器之間的關系，我必須告訴你，由于它在編譯器相關文章中得到了廣泛的使用，從長遠來看，你一定會碰到它，所以我推薦你早點認識它:)
現在，讓我們將該文法映射到代碼，
這是我們將文法轉換為源代碼的一些指導方法(guideline)，遵循它們可以將文法從字面上轉換為有效的決議器：
1、語法中定義的每個規則R可以成為具有相同名稱的函式(method)，并且對該規則的參考將成為方法呼叫：R()，函式的主體中的陳述句流也依照與同樣的指導方法，(Each rule, R, defined in the grammar, becomes a method with the same name, and references to that rule become a method call: R(). The body of the method follows the flow of the body of the rule using the very same guidelines.)
2、(a1 | a2 | aN)轉換為if-elif-else陳述句，(Alternatives (a1 | a2 | aN) become an if-elif-else statement.)
3、(…)轉換while陳述句，可以回圈零次或多次，(An optional grouping (…) becomes a while statement that can loop over zero or more times.)
4、對Token的參考T轉換為對eat函式的呼叫：eat(T)，也就是如果T的型別與當前的Token型別一致的話，eat函式將消耗掉T，然后從詞法分析器獲取一個新的Token并將其賦值給current_token這個變數，(Each token reference T becomes a call to the method eat: eat(T). The way the eat method works is that it consumes the token T if it matches the current lookahead token, then it gets a new token from the lexer and assigns that token to the current_token internal variable.)
準則總結如下所示：
讓我們按照上述指導方法將文法轉換為代碼，
我們的語法有兩個規則：一個expr規則和一個因數規則，讓我們從因數規則（生產）開始，根據準則，需要創建一個稱為factor的函式（準則1），該函式需呼叫一次eat函式來消耗型別為INTEGER的Token（準則4）：
def factor(self):
self.eat(INTEGER)
很容易就可以寫出來，
繼續！
規則expr轉換為expr函式（準則1），規則的主體從對factor的參考開始，我們轉換為factor()函式呼叫，可選的組(…)*轉換為while回圈，而(MUL | DIV)轉換為if-elif-else陳述句，將這些組合在一起，我們得到以下expr函式：
def expr(self):
self.factor()
while self.current_token.type in (MUL, DIV):
token = self.current_token
if token.type == MUL:
self.eat(MUL)
self.factor()
elif token.type == DIV:
self.eat(DIV)
self.factor()
花一些時間看看我如何將語法映射到源代碼，確保你了解，
為了方便起見，我將上面的代碼放入了parser.py檔案中，該檔案包含一個詞法分析器和一個不帶解釋器的分析器，你可以直接從GitHub下載檔案并使用，它是互動式的，你可以在其中輸入運算式并查看根據文法構建的決議器是否可以識別運算式，
這是我在計算機上的運行效果：
$ python parser.py
calc> 3
calc> 3 * 7
calc> 3 * 7 / 2
calc> 3 *
Traceback (most recent call last):
File "parser.py", line 155, in <module>
main()
File "parser.py", line 151, in main
parser.parse()
File "parser.py", line 136, in parse
self.expr()
File "parser.py", line 130, in expr
self.factor()
File "parser.py", line 114, in factor
self.eat(INTEGER)
File "parser.py", line 107, in eat
self.error()
File "parser.py", line 97, in error
raise Exception('Invalid syntax')
Exception: Invalid syntax
試試看！
我們再來看看相同expr規則的語法圖：
是時候開始撰寫新的算術運算式解釋器的源代碼了，以下是一個計算器的代碼，該計算器可以處理包含任意數量整數乘法和除法運算的算術運算式，還可以看到我們將詞法分析器重構為一個單獨的Lexer類，并更新了Interpreter類以將Lexer實體作為引數：
# Token types
#
# EOF (end-of-file) token is used to indicate that
# there is no more input left for lexical analysis
INTEGER, MUL, DIV, EOF = 'INTEGER', 'MUL', 'DIV', 'EOF'
class Token(object):
def __init__(self, type, value):
# token type: INTEGER, MUL, DIV, or EOF
self.type = type
# token value: non-negative integer value, '*', '/', or None
self.value = https://www.cnblogs.com/Xlgd/p/value
def __str__(self):
"""String representation of the class instance.
Examples:
Token(INTEGER, 3)
Token(MUL,'*')
"""
return 'Token({type}, {value})'.format(
type=self.type,
value=https://www.cnblogs.com/Xlgd/p/repr(self.value)
)
def __repr__(self):
return self.__str__()
class Lexer(object):
def __init__(self, text):
# client string input, e.g. "3 * 5", "12 / 3 * 4", etc
self.text = text
# self.pos is an index into self.text
self.pos = 0
self.current_char = self.text[self.pos]
def error(self):
raise Exception('Invalid character')
def advance(self):
"""Advance the `pos` pointer and set the `current_char` variable."""
self.pos += 1
if self.pos > len(self.text) - 1:
self.current_char = None # Indicates end of input
else:
self.current_char = self.text[self.pos]
def skip_whitespace(self):
while self.current_char is not None and self.current_char.isspace():
self.advance()
def integer(self):
"""Return a (multidigit) integer consumed from the input."""
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 (also known as scanner or tokenizer)
This method is responsible for breaking a sentence
apart into tokens. One token at a time.
"""
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(MUL, '*')
if self.current_char == '/':
self.advance()
return Token(DIV, '/')
self.error()
return Token(EOF, None)
class Interpreter(object):
def __init__(self, lexer):
self.lexer = lexer
# set current token to the first token taken from the input
self.current_token = self.lexer.get_next_token()
def error(self):
raise Exception('Invalid syntax')
def eat(self, token_type):
# compare the current token type with the passed token
# type and if they match then "eat" the current token
# and assign the 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):
"""Return an INTEGER token value.
factor : INTEGER
"""
token = self.current_token
self.eat(INTEGER)
return token.value
def expr(self):
"""Arithmetic expression parser / interpreter.
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
def main():
while True:
try:
# To run under Python3 replace 'raw_input' call
# with 'input'
text = raw_input('calc> ')
except EOFError:
break
if not text:
continue
lexer = Lexer(text)
interpreter = Interpreter(lexer)
result = interpreter.expr()
print(result)
if __name__ == '__main__':
main()
將以上代碼保存到calc4.py檔案中，或直接從GitHub下載，嘗試一下，看看它是否正確，
這是我在筆記本電腦上運行效果：
$ python calc4.py
calc> 7 * 4 / 2
14
calc> 7 * 4 / 2 * 3
42
calc> 10 * 4 * 2 * 3 / 8
30
這是今天的練習：
1、撰寫描述包含任意數量的+，-，* 或/運算子的算術運算式的文法，使用此文法，應該能夠推匯出諸如"2 + 7 * 4"，"7 - 8 / 4"，"14 + 2 * 3 - 6 / 2"之類的運算式，依此類推，
2、使用上一問撰寫的文法，實作一個解釋器，該解釋器可以計算包含任意數量的+，-，* 或/運算子的算術運算式， 解釋器應該能夠處理"2 + 7 * 4"，"7 - 8 / 4"，"14 + 2 * 3 - 6 / 2"等運算式，
最后再來復習回憶一下，記住今天文章的文法，回答以下問題，并根據需要參考以下圖片：
1、什么是無背景關系文法？
2、本文中文法有多少條規則(rule)/產生式(production)？
3、什么是終結符(terminal)？ （識別圖中的所有終結符）
4、什么是非終結符？ （標識圖片中的所有非終結符）
5、什么是規則的頭部(head)？ （識別圖片中的所有頭部/左側(left-hand sides)）
6、什么是規則的主體(body)？ （標識圖中的所有主體/右側(right-hand sides)）
7、什么是文法的開始符(start symbol)？
嘿，你一直閱讀到最后！ 這篇文章包含了相當多的理論知識，所以我為你的完成感到自豪，
下次我會再寫一篇新文章，敬請期待，不要忘記練習，它們對你有好處，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/2088.html
標籤：其他