《CPython Internals》學(xué)習(xí)第 8 天，p118-p150 總結(jié)，總計(jì) 33 頁。

一、技術(shù)總結(jié)

補(bǔ)充一些本人整理的關(guān)于 Context-Free Grammar(CFG) 的知識(shí)。

1.symbol(符號(hào))

A mathematical symbol is a figure or a combination of figures that is used to represent a mathematical object（符號(hào)是一個(gè)數(shù)字或數(shù)字的組合，用來表示一個(gè)數(shù)學(xué)對(duì)象）。

symbols也稱為character(字符), letter(字母)，范圍比較廣，可以是 deciamal digits(十進(jìn)制數(shù)，0,1,2,3,4,5,6,7,8,9), 也可以是letters(a,...,z, A,...,Z)，還可以是 >, <, =, !等。

2.alphabet(字母表)

2.1.定義

An alphabet is a finite, nonempty set of symbols. Conventionally, we use the symbol ∑(sigma) for an alphabet.

2.2.示例

{0, 1}，{a, ..., z}。

3.string(串)

3.1. 定義

A string (or sometimes 01ì) is a finite sequence of symbols chosen from some alphabet.

3.2. 示例

For example, 01101 is a string from the binary alphabet Σ = {0, 1}. The string 111 is another string chosen from this alphabet.

3.3.empty string(空串)

The empty string is the string with zero occurrences of symbols. This string, denoted ?, is a string that may be chosen from any alphabet whatsoever.

3.4. length of string

4.language(語言)

4.1. 定義

A set of strings all of which are chosen from some alphabet, where Σ is a particular alphabet, is called a language.

注：language 是 string 的集合。

4.2. 示例

{10, 11, 101, 111, 1011,...}

5. grammar(文法)

全稱為 Context-Free grammar(上下文無關(guān)文法)，簡寫為grammar(文法)。

G=(V, T, P, S)

注：G 是 grammar 的首字母。(V, T, P, S)稱為四元組(及有四個(gè)元素的元組)。集合里面的元素是無序的，元組里面的元素是有序的——示例： {1, 2, 3, 4} 和 {4, 3, 2, 1}可以是相等的，但是 (V, T, P, S) 和 (S, P, T, V)是不相等的，因?yàn)轫樞虿灰粯印?/p>

5.1. V

V is a finite set of variables, also called sometimes nonterminals(非終結(jié)符) or syntactic categories(語法范疇).

5.2. T

T is a finite set of symbols that form the strings of the language being defined. We call this alphabet the terminals(終結(jié)符), or terminal symbols(終結(jié)符號(hào)).

5.3. P

P is a finite set of productions(產(chǎn)生式) or rules that represent the recursive definition of a language.

There is a finite set of productions or rules that represent the recursive definition of a language. Each production consists of:

(a) A variable that is being (partially) defined by the production. This variable is often called the head of the- production.

(b) The production symbol →.

(c) A string of zero or more terminals and variables. This string, called the body of the production, represents one way to form strings in the language of the variable of the head. In so doing, we leave terminals unchanged and substitute for each variable of the body any string that is known to be in the language of that variable.

5.4. S

One of the variables represents the language being defined; it is called the start symbol(開始符號(hào)).

二、英語總結(jié)(生詞：0)

無。

關(guān)于英語的注解同步更新匯總到 https://github.com/codists/English-In-CS-Books 倉庫。

三、其它

The Compiler章節(jié)簡評(píng)：今日不想評(píng)。

四、參考資料

1. 編程

(1) Anthony Shaw，《CPython Internals》：https://book.douban.com/subject/35405785/

2. 英語

(1) Etymology Dictionary：https://www.etymonline.com

(2) Cambridge Dictionary：https://dictionary.cambridge.org

歡迎搜索及關(guān)注：編程人(a_codists)