网站建站 宝,网站开发后端开发,网站转换小程序,网站安全检测产品优势《编译原理》学习第 5 天#xff0c;p25-p32总结#xff0c;总计 8 页。
一、技术总结
1.lexical
lexical这个单词后续会经常用到#xff0c;所以首先要搞懂它的英文意思#xff0c;不然看到中文的“词法#xff0c;语法#xff0c;文法”这三个词的时候就会懵了——l…《编译原理》学习第 5 天p25-p32总结总计 8 页。
一、技术总结
1.lexical
lexical这个单词后续会经常用到所以首先要搞懂它的英文意思不然看到中文的“词法语法文法”这三个词的时候就会懵了——lexical对应这三个里面的哪一个
1lexical: lexicon al加al后缀表明lexical是一个形容词(adjective)。
2lexicon: 词根是lexis(a word)。all the words used in a particular language。意思是“全部词汇”“词典”。
3lexical: 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如123。(2)signs: 如 。3boldface 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 grammarp26, 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写成一个productionproduction的right side用符号| 隔开|读者“or”。
示例
以73-19-52, 为例我们把数字称为digit(即1是一个digit, 2是一个digit, 3是一个digtit…) 把用号或-号隔开的expression称为list( 3-1即是一个list9-52是一个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-52)的过程。
二、其它
alphabet, string, language这三个概念书中没有严格的定义但却又是核心概念可以参考《Introduction to Automata Theory Languages and Computation》这本书。
今天的读书笔记写了很多也是因为书上很多概念没有明确的定义,需要把相关的内容全部记下然然后做交叉验证。
四、参考资料
1. 编程
(1)Alfred V. AhoMonica S. LamRavi SethiJeffrey D. Ullman《编译原理英文版·第1版》https://book.douban.com/subject/5416783/
2. 英语
(1)Etymology Dictionaryhttps://www.etymonline.com
(2) Cambridge Dictionaryhttps://dictionary.cambridge.org
欢迎搜索及关注编程人(a_codists)
