《编译原理》学习第 5 天，p25-p32 总结，总计 8 页。

一、技术总结

1.lexical

lexical 这个单词后续会经常用到，所以首先要搞懂它的英文意思，不然看到中文的“词法，语法，文法”这三个词的时候就会懵了——lexical 对应这三个里面的哪一个？

（1）lexical: lexicon + al，加 al 后缀，表明 lexical 是一个形容词(adjective)。

（2）lexicon: 词根是 lexis(a word)。all the words used in a particular language。意思是“全部词汇”，“词典”。

（3）lexical: adj. relating to words，词汇(word)相关的。

所以 lexical 对应着“词(word)法”， lexical analyzer 称为词法分析器。

2.production

(1)定义

p26，以 C 语言中的 if-else 语句为例：

if (expression) statement else statement

如果使用 expr 表 expression，使用 stmt 表示 statement，那么上述语句就可以表示成：

stmt -> if (expr) stmt else stmt

->表示“can have the form”。形如“stmt -> if (expr) stmt else stmt”这样的 rule 称为 production。

(2)作用

书中没有给出明确的定义，按照书中的定义，长“stmt -> if (expr) stmt else stmt”这样的就叫做 production, 再简化一下还可写成： x -> y，“ x -> y”这个 production 的含义是什么呢？它的含义是 x 可以转为 y。

(3)left side & right side

以 "stmt -> if (expr) stmt else stmt" 这个 production 为例，-> 左边的部分称为 production 的 left side，-> 左边的部分称为 production 的 right side。

3.token/terminal

在 production 中，lexical element(如：if, else)和 parenthsis 称为 token，也称为 terminal、terminal symbol。

p27, "we assume that digits, signs such as <=, and boldface strings such as while are terminals"。根据这句话，terminal 包含：(1)digit：如 1，2，3。(2)signs: 如 <=。（3）boldface string: 如 while。这里用 boldface string 很不好，boldface 是从印刷的角度来说的，那非 boldface 的 string 是不是 terminal 呢？

4.nonterminal

stmt -> if (expr) stmt else stmt" 这个 production

p26, variables like expr and stmt represent sequences of tokens and are called nonterminals。在这里，作者没有给出 nonterminal 的明确定义，暂且根据这句话的意思把像 expr 和 stmt 这样的 variable 称为 nonterminal，然后继续往下阅读。

5.context-free grammar

(1)定义

首先，得对 context-free grammar 下定义，什么是 context-free grammar？p26, In this section, we introduce a notation, called a context-free grammar(grammar, for short), for specifying the synaxt of a language。用于指定语言的语法的符号称为上下文无关文法，简写为 grammar。

context-free grammar 由四部分构成：

(1)a set of terminals。

(2)a set of nonterminals。

(3)a set of production。

(4)a start symbol。

“a designation of one of the nonterminals as the start symbol”——根据书中的定义，start symbol 是从 nonterminals 中指定的。

6.|符号(or)

p27, For notational convenience, productions with the same nonterminals on the left can have their right sides grouped, with the algernative right sides separated by the symbol |, which we read as "or."——为了方便表示，可以把多个具有相同 left side 的 production，写成一个 production，production 的 right side 用符号| 隔开，|读者“or”。

示例：

以 7，3-1，9-5+2, 为例，我们把数字称为 digit(即 1 是一个 digit, 2 是一个 digit, 3 是一个 digtit......)， 把用+号或-号隔开的 expression 称为 list( "3-1"即是一个 list，"9-5+2"是一个 list,1 等数字是特殊的 list)，那么上面这三个 expression 使用 production 来表示可以写成：

(1)digit -> 0 | 1 | 2 | 4 | 5 | 6 | 7 | 8 | 9

(2)list -> digit

(3)list -> list - digit

(4)list -> list + digit

因为(2)、(3)、(4)这 3 个 production 的 left side 是一样的，都是 list, 那么可以写成一个 production：

list -> digit | list - digit | list + digit

7.production for nonterminal

p27, We say a production is for a nonterminal if the nonterminal appears on the left side of the production。

如果一个 nonterminal 出现在 production 的 left side， 那么我们就说这个 production 是这个 nonterminal 的 production(这里有点拗口，书上用的是 for 表示，意思就是这个 production 是归属于这个 nonterminal 的)。

当看到“production for nonterminal”我们就要想到 nonterminal 是在 production 的 left side。

8.parse tree

(1)tree

关于 tree 相关的定义，参考维基百科即可。书中提到的 interior node，实际就是我们常说的 internal node。

(2)定义

grammar 可以用 tree 来表示，这样的 tree 称为 parse tree。parse tree 描绘了从 start symbol 生成 string(如：9-5+2)的过程。

二、其它

alphabet, string, language 这三个概念书中没有严格的定义，但却又是核心概念，可以参考《Introduction to Automata Theory Languages and Computation》这本书。

今天的读书笔记写了很多，也是因为书上很多概念没有明确的定义,需要把相关的内容全部记下然，然后做交叉验证。

四、参考资料

1. 编程

(1)Alfred V. Aho，Monica S. Lam，Ravi Sethi，Jeffrey D. Ullman，《编译原理（英文版·第 1 版）》：https://book.douban.com/subject/5416783/

2. 英语

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

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

欢迎搜索及关注：编程人(a_codists)