积分电路公式_积分电路公式

编译原理 (4) 词法分析 　　题外话， 如果认为编译原理抽象，建议去看神书SICP ，有助于提高抽象的能力 　　（前提是有时间去磨） 　　对于一个字符，首先需要做的是表示和识别（从无到有，判断是否合法） 　　词法分析程序的主要功能（如何分析程序的一个一个的单词） 　　（The main function of lexical analysis program）读入源程序字符序列 (读取)对源程序进行预处理，如删除注释和回车换行符，宏展开等 （预处理，C 中的#define，删除注释等等）识别源程序中的单词，创建符号表并在相应的符号表中登录信息 （单词在符号表中进行登记：是什么，类型是什么）将单词与行号关联起来，以便编译器能将错误信息与源程序位置联系起来（与行进行关联，便于编译器打印错误信息的位置）输出单词序列 　　例子: const pi = 3.14159;const : 先识别是常数pi : 识别是标识符 (Id)3.14159 : 用一个值来区别不同的标识符（将3.14159 字符串转化为浮点数3.14159） 　　关键点是单词的类别和属性（就是二组：<类别，属性>） 　　单词的类别和属性 (Categories and attributes of words) 　　单词是具有独立含义的最小语法单位 　　比如自然语言(汉语，英语等)中的词 ：Noun, verb, adjective… 　　程序设计语言中的类别（类比单词中的词性：名词，动词….） ： 　　标识符 （identifier） （种类不固定）关键字 （keyword） （种类是预先定义好的）常数 （constant）运算符 (operator)分界符 (运算符其实也可以当作分界符) (delimiter)字符串 (character String) 　　单词符号的表示形式（A symbol representation of a word） 　　词法分析程序根据词类来对源代码进行划分 　　但如果只把切分出来的单词符号本身作为输出，是不够的 　　一个单词符号至少要包含两个方面的信息单词的类别(词类)单词的属性值 　　因此用二式<类别，单词的属性值>来表示单词符号 　　例子 　　E = M * C 2 　　–>><id, 指向变量E在符号表的入口> 标识符E<assign_op, _> 赋值符号 =<id, 指向变量M在符号表的入口> 标识符M<mult_op, _> 乘法运算符 *<id, 指向变量C在符号表的入口> 标识符 C<exp_op, _> 幂运算符(python 中就是这么写的)<number, 常量值2的二进制表示> 数字常数 2 　　词法分析器输出的是单词符号的二式序列，同时会创建多个符号表，如标识符表，常数表等 　　（第一是建表，第二是输出单词符号的二组序列<类别，属性值>） 　　词法分析器的组织 （具体的实现） 　　1. 作为独立的一遍: 把源程序的完整文件转换为单词符号序列文件 （单独实现，就是转化为单词符号序列） 　　2. 与语法分析合在一起作为一遍，把词法分析作为一个子程序，由语法分析器通过调用词法分析子程序来获得当前单词符号二式，供语法分析使用 　　（作为函数调用来使用词法分析器）

词法分析器作为一个子程序供语法分析器调用 　　三个概念（比较抽象） 　　单词符号(token): 即为我们前面讨论的词法分析器的输出形式，二式<类别，属性值>（学过NLP 的同学会比较熟悉这个，token就是一个二组）模式(pattern): 描述一个单词符号的可能形式，比如类别为标识符的单词符号应具有什么样子的形式？（构建模板： 和正则表达式原理一样，就是抽象出一个更加泛化的，适用范围更加广泛的”模板串“）词素(lexeme): 源程序中的一个字符序列，是单词符号的实例，比如源程序里的关键字“if”（更加具体的的一个表示） 　　抽象性 ： pattern>token>lexeme 　　（最重要的是给出一个抽象的，模板化的pattern） 　　模式的表述形式——正规表达式 （regular expression） 　　（无论是python 的re 包，还是java 的java.util.regex 或是js 的/pattern/modifiers 用过的同学会比较熟悉）关键字: “if”, “else”, “then”… 　　‘if’ | ‘else’| ‘then’|…整型: 非空的数字串 　　digit = ‘0’| ‘1’| …| ‘9’ ([0-9]) 　　digit digit*标识符: 以字母开头的字母数字串 　　letter = ‘a’| ‘b’| …| ‘z’| ‘A’| ‘B’|…| ‘Z’ [a-z] [A-Z] 　　letter(letter| digit)* （第一个是字母，第二个是字母或者数字，* 闭包：可以是空串）额外的例子，email地址 　　zhangsan@http://233.edu.cn 　　letter+‘@’letter+ ‘.’letter+ ‘.’letter+ 　　正规表达式(Regular Expression, RE) 　　正规表达式是一个表示字符串格式的模式 　　可以用来描述单词的结构 　　正规式(r)所匹配的所有字符串的集合称为正规集，实际上是一个正规语言(3型语言)，记为L(r) 　　（可以匹配到的实际字符串就是正规集） 　　在字母表Σ上的正规表达式可以递归定义如下 　　ε是一个正规式，其匹配的语言是L(ε)={ε} 　　如果a是Σ中的一个符号，那么a是一个正规式，并且L(a)={a} 　　（单个的符号） 　　（归纳基础部分） 　　如果r和s都是正规式，分别表示语言L(r)和L(s)，那么:(r)|(s)是一个正规式，表示的语言是L(r)∪L(s) （并运算）(r)(s)是一个正规式，表示语言L(r)•L(s) （与运算） (r)*是一个正规式，表示语言(L(r))* （星闭包）(r)是一个正规式，表示语言L(r)。 （括号） 　　（归纳步骤） 　　（加上递归的运算） 　　代数系统肯定设计运算符 的优先级和结合性 　　运算符的优先级和结合性 （学习一个语言必须掌握的） 　　*和+高于“连接” 和| ， “连接”高于 ||具有交换律、结合律“连接” 具有结合律、和对|的分配律 （没有交换律） 　　( )指定优先关系 　　意义清楚时，括号可以省略定义了优先级后: 　　((a) (b)*)| (c)可以写成ab*| c （后缀表达式） 　　例子 Σ={a, b} 　　a | b 　　{a, b}(a | b) (a | b ) （连接起来） 　　{aa, ab, ba, bb} 　　L(a,b)={a,b} 　　L((a|b)(a|b))={a,b}{a,b}={aa,ab,ba,bb} （就是一种组合方式）a* 　　由字母a构成的所有串集 (比如 : aaaa, aaaaaa) （含有任意个数的a）(a | b)* 　　由a和b构成的所有串集 (任意长度的ab 串： 比如 ,ababab)a|a*b 　　{a，b，以1个b结尾1个或多个a开头的ab串} 　　{a} 并 {a*}{b} 　　正规表达式的代数性质 ： 　　

正规表达式的代数性质 　　正规表达式的应用 　　程序设计语言中的单词，Σ=ASCII 　　关键字: if, then, else, while, do,… 　　Keywords = if | then |else | while | do | … 　　(可以用字符串数组或者集合set 来表示，用正则表达式定义也可以) 　　C语言的标识符集合 　　letter = A|B|…|Z|a|b|…|z|_ （字母和下划线均可以） 　　digit = 0|1|…|9 （数字） 　　id = letter (letter | digit)* （必须是字符开头：可以是字母也可以是下划线，后面接任意个字符或者数字） 　　Pascal无符号数集合 （可以类比C ，如果没有学过Pascal） 　　例1946, 11.28, 63.6E8, 1.99E－6 　　digit = 0 | 1 | … | 9 （数字） 　　digits= digit digit* = digit+ （第一个数字需要为数字） 　　optional_fraction=.digits|ε (小数部分) 　　optional_exponent = (E ( + |－|ε) digits ) |ε （指数部分） 　　（可以没有指数，一旦有了必须有E ，然后可以是+ 也可以是-，也可以没有符号（正号省略），必须有一个数字串） 　　num = digits optional_fraction optional_exponent 　　=(digit)+(. (digit)+ |ε)((E(+|-|ε)(digit)+ )|ε) 　　（构成了所有的无符号数） 　　运算符 　　op =+ | － | * | ／ |… （加减乘除） 　　关系运算符 　　relop =< | <= | = | <> | > | >= （等于，大于，小于） 　　空白符 　　delim=blank | tab | newline （空格:tab , 空格，回车） 　　ws=delim+ (ws: whitespace) （是正闭包： 必须含有一个空格） 　　分界符 　　pun = ;| : |, |… （空格某种意义上也是分界符） 　　单词的描述 　　在现有的许多文本编辑器中，正规表达式在文本查找和匹配中发挥了很大作用(emacs, vim 和shell中都有)许多高级语言，特别是一些脚本语言，如Java, C#, Perl, Python等，都具有正规表达式的文本处理功能。正规表达式RE是一种描述手段,通常用来描述程序语言的词法符号。为了识别一个串是否属于某个正则集，则一般采用自动机来做。 　　现在来介绍耳熟能详的有限自动机 　　有限自动机（就是识别的功能：search , match…） 　　有限状态系统 　　状态 ： 将事物进行区分的标识具有离散状态的系统 ：数字电路(0和1) ，交通信号灯（离散状态系统的状态是有限的）具有连续状态的系统 ：水库水位变化，温度变化，具有无穷多个状态 　　有限状态系统是离散状态的系统 　　自动售货机的操作流程？如购买一瓶价格为3的可乐需要做哪些步骤？ 　　（虽然现在是支付宝或者支付。。。） 　　假设某一台售货机只可接受5角和1的硬币 　　购买一瓶3的可乐，售货机的状态有几种？(状态可理解为购物的步骤) 　　假设已投入2，为了买到可乐，还需投入1个1硬币或2个5角硬币 　　购买一瓶3的可乐，售货机的状态有几种？ 　　需要3: 还没有投入任何硬币的机器状态需要2.5: 已投入1个5角硬币后的状态需要2.0: 已投入2个5角或1个1的硬币后的状态需要1.5: 已投入3个5角或1个1和1个5角硬币后的状态需要1: 已投入4个5角或1个1和2个5角的硬币后的状态需要0.5: 已投入5个5角或3个5角和1个1或1个5角和2个1硬币后的状态需要0: 表示已投入至少3的硬币，可以购买可乐了

有限状态图 　　（类比 ：数字电路中的状态转移图，DP动态规划中的状态转移图）有限自动机是具有离散输入与离散输出的一种数学模型用于识别输入的符号串是否属于某个语言的合法句子输入: 符号串输出: yes or no (识别是或者不是) 　　两种有限自动机的类型: 　　确定性有限自动机(DFA): 对于给定的输入符号，只做唯一的动作 （只能转移到一个确定的状态） 　　（只有一种转移可能）非确定性有限自动机(NFA): 对于同一个输入符号，存在多种动作可选 （可以转移到不同的，随机的，不确定的状态） 　　(有多种转移可能) 　　两种有限自动机均可用于识别正规表达式 　　主要组成部分（有限状态机的几个要素） 　　字母表 alphabet状态 （有限的状态） state开始状态 （起始状态） initial state接受或终结状态 （结束状态） termination转移函数 （如果进行状态转移） Transfer function 　　DFA NFA 　　start -> : 开始状态 　　两个同心圆表示： 终止状态

NFA ：Nondeterministic Finite Automata

DFA ：Deterministic Finite Automaton 　　非确定性有限自动机NFA 　　（1976 年图灵奖：DFA和NFA可以识别的是一样的，模型的等价性） 　　NFA表示为一个五组
　　（不稳定的）有限状态集Q输入字母表Σ初始状态
接受或终结状态集F⊆Q转移函数
　　给定状态和输入符号，NFA需要转换到的状态集

标签可能是一个空串（a+|b+） 　　（这里的1 和 3 状态实际上是一样的，只是为了区别后续的识别是a 还是 b ，所以用了两个状态1 和 3） 　　NFA的另外一种表示方法: 转换表 　　

转移图

转移表 　　NFA识别输入串 　　给定输入串x，它能被一个NFA识别，当且仅当在该NFA的状态转移图中存在一条从开始状态出发到某个接受状态的转移路径。 　　（只需要存在一条路径就可以了，就说明串是可接受的）

转移图 　　下列哪些输入串是可以识别的: abb, aaa, aabb, aaabb, bbb？ 　　非确定性有限自动机NFA （很容易，很好理解的一种表示方式） 　　（判断可以，是需要找到一条路径就可以了，但是如果判断不行，需要穷举所有的路径） 　　NFA所能识别的所有符号串构成的集合称为NFA接受的语言。 　　用L(A)表示自动机A接受的语言。 （字符串集合 ： 语言）

识别的语言是(a|b)*abb : 以abb 结尾的 　　识别aa*|bb*的NFA

转移图 　　ε弧表示状态转换了，但是没有使用输入符号 　　对于如下的NFA，给出识别aabaabb的所有路径 ： 　　（可能会存在大量的回溯。。。，想想DFS，深搜）

转移图 　　0→1→2→2→2→2→2→3 　　0→1→2→0→0→1→2→2→3 　　确定性有限自动机(DFA) 　　DFA是NFA的一个特例 　　没有ε边转移 　　一个状态面临一个输入符号时最多只转移到一个状态 (只有一个转移的目标)（或者没有转移目标） 　　DFA表示为一个五组
　　有限状态集Q输入字母表Σ初始状态
接受或终结状态集
转移函数
　　给定状态和输入符号，DFA需要转换到的状态 　　DFA的表示方法: 状态转换图和状态转换表 　　

确定性有限自动机(DFA) 状态转换图 　　

确定性有限自动机(DFA) 状态转换表 (开始状态只有一个，结束状态可能有多个，需要额外的标志表示) 　　（表格用数据结构表示更加简单 ： 邻接矩阵，邻接表 …） 　　DFA的模拟 (学过数电的时序逻辑电路的状态转移图和状态转移表会更好理解) 　　

状态转移图 (接受abb 结尾的串) 　　s : 当前状态 　　s0 : 初始状态 　　eof : 字符串结束 　　s = δ(s, c); 　　“yes” or “no”?abba nobabb yesaababb yesabbb no （只看最后有没有到达终止状态） 　　如果将识别的字符串放在一起，就可以表示这个自动机可以识别的一种语言 　　(如果题目给出图，反推的话需要枚举所有可能，然后找规律归纳) 　　DFA一定是NFA，是不是NFA的表述能力比DFA强呢？ 　　两种自动机识别语言的能力是一样的 　　一个语言可以被一个DFA识别，则一定存在一个NFA，可以识别同一个语言，反之亦然！ 　　实际上，这两种自动机识别的语言都是正规语言(3型语言)，也就是正规表达式所能表示的语言

三者之间的关系 　　正规表达式转化为DFA 是困难的，但是转化为NFA是简单的，由于NFA和DFA的表达能力是一样的，所以如果能找到NFA转化为DFA的方法，那么会极大提高正规表达式的实现效率 　　（可以类比数电中的原始状态到简化状态的转化） 　　学了基础知识需要配一些题目来加深理解： 　　先给出前面学过的链接 ：GAN就行了：编译原理 (2) 程序语言的概念GAN就行了：编译原理 (3) 文法分析树 　　习题 ： 　　1. 给定如下文法G[A]，用自己的语言描述它定义的语言。A→aaA | aaBB →Bcc | D#ccD →bbbD | # 　　(aa)?? (bbb)?? (#)?? (cc)?? 　　
　　2. 设有文法G[S]:S→ B = EB→ C | DC →a | b | cD → m[1] | m[2] | m[3]E → C O C | C O D | D O C | D O DO → + | -现有两个句子① b = a+b ② m[2] = b + m[1]，分别完成以下题目(1) 试画出对应的分析树(推导树)(2) 指出每个句子中的短语、直接短语和句柄 　　b=a+b 　　

b=a+b 的推导树 　　短语：相对于B 和 C : b相对于 C : a相对于 E : a+b 相对于 S : b=a+b相对于 O : 　　直接短语：a ， + ，b 　　句柄：b 　　m[2] = b + m[1] 　　

m[2] = b + m[1] 的推导树 　　短语：相对于 B， D : m[2] 相对于 C : b 相对于 O : + 相对于 D : m[1] 相对于 E : b+m[1] ，相对于 S : m[2]=b+m[1] 　　直接短语：m[2]，b， + ，m[1] 　　句柄：m[2] 　　3. 给定文法G[E] E → E + T | E – T | TT →F | T * F | T/FF →F ^ P | PP → c | id | ( E )现有文法符号串E+T*(F-id)和T*P ^ (id+c)，试完成如下题目：(1) 证明这两个符号串都是该文法的句型(2) 画出相应的分析树(3) 指出每个句型的短语、直接短语、句柄、素短语和最左素短语(1) 　　第一个文法符号串 E+T*(F-id)： 　　
　　第二个文法符号串 T*P ^ (id+c)： 　　
　　(2) 　　第一个文法字符串：

E+T*(F-id) 分析树 　　短语 :相对于 E，T : F 相对于 T ，F ，P : id相对于 E : F-id相对于 F ，P : (F-id)相对于 T ： T * (F-id)相对于 E ：E +T * (F-id) 　　直接短语： 　　F ， id 　　句柄(最左侧的直接短语) ： 　　F 　　素短语 ： 　　id 　　最左素短语： 　　id 　　第二个文法字符串：

T*P ^ (id+c) 的分析树 　　短语 :相对于 E，P ，F ，T : id 相对于 T ，F ，P : c 相对于 E : id-c相对于 P : (id+c)相对于 F ： P相对于 F ： P^(id+c)相对于 T，E ：T * [P^(id+c)] 　　直接短语： 　　id ， c ， P 　　句柄(最左侧的直接短语) ： 　　P 　　素短语(至少含一个终结符号，且不含其它素短语的短语) ： 　　id ，c 　　最左素短语： 　　id 　　4. 考虑文法G[S]: S→ aSbS | bSaS | ε(1) 为句子abab构造两个不同的最左推导，以此说明该文法是二义的。(2) 为abab构造对应的分析树。 　　(1) : 　　
S→ aSbSS→ aSbSS→ εS→ εS→ ε 　　
S→ aSbSS→ εS→ aSbSS→ εS→ ε 　　(2) : 　　第一种推导的分析树

第一种推导的分析树 　　第二种推导的分析树

第二种推导的分析树