本部分介绍了c++11的崭新的类型推导、循环、模板和构造方法。 弃用的特性 1.　不允许以下赋值出现，应使用const char *后者auto。 1 char *str = "hello world!"; 2.　C语言风格的类型转换被弃用，应该使用 static_cast、reinterpret_cast、const_cast 来进行类型转换 3.　register， auto_ptr关键字被弃用。 语言增强 新的关键字 使用nullptr而不是NULL。新的nullptr为nullptr_t类型，可以隐式转换为任何类型，同时避免了NULL == 0这种类型冲突。 constexpr函数：告诉编译器返回的值为常量表达式 类型推导 auto类型 auto型可以作为变量的声明类型，函数的返回类型 auto型作为函数参数在c++17中才可使用，但要注意重载的问题 auto不能用于数组的类型推导 迭代器的样例： 1 for(auto itr = vec.cbegin(); itr != vec.cend(); ++itr); decltype函数 返回值为一个类型。比如我们可以把z声明为推测的类型 1 decltype(x+y) z = x + y; for(item:array)循环 像Python一样地迭代： 1 2 3 4 5 std::vector<int> arr(5, 100); // & 启用了引用, 如果没有则对 arr 中的元素只能读取不能修改 for(auto &i : arr) { std::cout << i << std::endl; } 初始化列表 除了

以下的socket 都是python实现的服务端接受客户端键盘输入的信息，改为大写返回客户端的模板 都是同步、阻塞的 都会在数据长度大于1024时产生错误，请自己写协议 端口都是8080，请确保未被占用 tcp_server.py 6行控制监听的最大tcp链接数。 tcp是有链接的。9行建立链接，10行接受数据，11行发送数据，12行关闭链接。 1 2 3 4 5 6 7 8 9 10 11 12 import socket server = socket.socket(socket.AF_INET, socket.SOCK_STREAM) server.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1) server.bind(("0.0.0.0", 8080)) server.listen(1) while True: conn, addr = server.accept() data_from_client = conn.recv(1024).decode('utf8') conn.sendall(data_from_client.upper().encode('utf8')) conn.close() tcp_client.py 5行链接，6行发送数据，7行接收数据，9行关闭链接。 1 2 3 4 5 6 7 8 9 import socket while True: client = socket.socket(socket.AF_INET, socket.SOCK_STREAM) client.connect(("0.0.0.0", 8080)) client.sendall(input().encode('utf8')) data_from_server = client.recv(1024).decode('utf8') print('GET ' + data_from_server) client.

函数说明 18.3. select — Waiting for I/O completion — Python 3.6.0 documentation select.select(rlist, wlist, xlist[, timeout]) Unix select()系统调用的一个简单接口。前三个参数是文件描述符（int类型）的序列。 1 2 3 rlist：等待准备读取 wlist：等待准备写作 xlist：等待一个异常 参数说明 在Unix上序列可以为空，但在Windows则不可以。可选的timeout参数将超时指定为浮点数（以秒为单位）。当省略timeout参数时，该函数阻塞，直到至少一个文件描述符已准备好。该值为0时表示轮询从不停止。 返回值 准备好的对象列表的三元组（前三个参数的子集）。当超时但没有文件描述符就绪时，返回三个空列表。 序列对象 序列中可用的对象类型包括Python文件对象（例如sys.stdin或由open()或os.popen()返回的对象），由socket.socket()返回的socket对象。你也可以自己定义一个类，只要它有一个合适的fileno()方法（返回一个真正的文件描述符，而不只是一个随机整数）。 注意： Windows上的文件对象不可接受，但socket可以。在Windows上，底层的select()函数由WinSock库提供，不处理不是源自WinSock的文件描述符。 实现HTTP代理 代理由两个部分组成：客户端-代理的socket，和代理-Web服务器的socket。 因为代理像两边接受数据时调用recv方法都会发生阻塞， 所以，在这个样例中，事件循环由两个事件组成：客户端-代理链接可以继续接受数据了，和代理-Web服务器链接可以接受数据了（指都是代理端）。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 import select import socket import _thread BUFF_SIZE = 1024 # get http head data from a connection def get_post(conn): res = b'' while True: res += conn.

学期初写代理的时候发现阻塞式socket并不能满足需要，多线程也不是一个很好的解决方案。这篇文章系统地介绍了epoll是什么以及如何使用。 英文好的同学可以直接看 How To Use Linux epoll with Python 本博客的大部分内容都是基于这篇文章的。 什么是epoll （维基百科） 于Linux 2.5.44首度登场的epoll是Linux内核的可扩展I/O事件通知机制。它设计目的只在替换既有POSIX select(2)与poll(2)系统函数，让需要大量操作文件描述符的程序得以发挥更优异的性能(举例来说：旧有的系统函数所花费的时间复杂度为O(n)，epoll则耗时O(1))。epoll与FreeBSD的kqueue类似，底层都是由可配置的操作系统内核对象建构而成，并以文件描述符(file descriptor)的形式呈现于用户空间。 为什么使用epoll 首先理解同步异步的概念： 怎样理解阻塞非阻塞与同步异步的区别？- 知乎 同步与异步 同步和异步关注的是消息通信机制 (synchronous communication/ asynchronous communication) 所谓同步，就是在发出一个调用时，在没有得到结果之前，该调用就不返回。但是一旦调用返回，就得到返回值了。 换句话说，就是由调用者主动等待这个调用的结果。 而异步则是相反，调用在发出之后，这个调用就直接返回了，所以没有返回结果。换句话说，当一个异步过程调用发出后，调用者不会立刻得到结果。而是在调用发出后，被调用者通过状态、通知来通知调用者，或通过回调函数处理这个调用。 阻塞与非阻塞 阻塞和非阻塞关注的是程序在等待调用结果（消息，返回值）时的状态. 阻塞调用是指调用结果返回之前，当前线程会被挂起。调用线程只有在得到结果之后才会返回。 非阻塞调用指在不能立刻得到结果之前，该调用不会阻塞当前线程。 阻塞式socket： 阻塞式socket使用单线程进行通信。主线程创建一个新的socket线程并侦听该socket，它一次性接受所有连接，然后让这个线程与客户端进行交互。因为创建的线程都只和一个客户端通信，所以阻塞并不妨碍其他线程工作 虽然多线程的阻塞式通信编码简单，但是在多线程共享资源时非常困难，在多核下表现也很差 非阻塞的socket： 于是很多替代并发阻塞式socket的方法出现了，例如基于事件系统设计的epoll，它并不会阻塞线程，它可以使用一个线程实现，大大节约了资源. 可见epoll是一个同步的非阻塞解决方案。 一般步骤 使用python中的epoll一般有如下步骤： 创建epoll对象 告诉epoll对象监视特定socket上的特定事件 询问epoll对象哪些socket可能有自上次查询以来的指定事件 对这些socket执行一些操作 告诉epoll对象修改要监视的socket和事件的列表 重复步骤3到5直到完成 销毁epoll对象 代码实例 epoll设有水平触发和边沿触发两种模式。 在边沿触发操作模式下，socket发生读或写事件后，调用epoll.poll()只会给socket返回一次事件。调用程序必须处理与该事件相关的所有数据。当事件的数据为空时，对socket的继续操作将导致异常。 在水平触发操作模式中，对epoll.poll()的重复调用将导致注册事件的重复通知，直到与该事件相关联的所有数据都已被处理。 边沿触发往往被用于程序员不想使用系统的事件管理机制时。 下面的示例是一个水平触发的典型样例。 需要注意的是，event & select.EPOLLIN 表示事件的掩码，当掩码值为0时对应的事件发生。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 import socket, select EOL1 = b'\n\n' EOL2 = b'\n\r\n' response = b'HTTP/1.

语义分析是编译系统的第三部分,负责赋值检查,表达式检查以及代码生成. 基本思想 代码沿用了上一部分的文法表, 利用递归下降算法对每一个非终结符写一个函数. 但是文法多达70多条, 工作量太大, 就只实现了赋值语句, 表达式, 条件语句这几个代表性的文法规则. 其他实现起来也类似, 多写几个函数即可. 函数介绍 需要注意的几个细节: compare_var_type用于比较类型, 比较失败则raise一个CompileError 在生成代码过程中, 有的传入了其他的变量, 是为了回填 把if回填做成了label的方式, 可以在后阶段再处理 未初始化的变量调用也留给了后阶段处理. 函数表: 成员函数 对应非终结符 备注 init() 初始化 get_register() 分配寄存器 get_label_no() 分配记号 compare_var_type(var_type_1,var_type_2) 比较类型,raise错误 build_table(x) 建立符号表 check_factor(factor) <因式> 用于检查 check_factors(factor) <因式递归> 用于检查 check_factor_c(fc) <因子> 用于检查 check_term(term) <项> 用于检查 check_exp(x) <表达式> 用于检查 check_stm(x) <赋值函数> 用于检查 generate_factor(factor) <因式> 用于生成 generate_factors(factors,factor) <因式递归> 用于生成 generate_factor_c(fc) <因子> 用于生成 generate_term(term,factor) <项> 用于生成 generate_exp(x) <表达式> 用于生成 generate_stm(x) <赋值函数> 用于生成 generate_func_blocks(x) <函数块闭包> 用于生成 generate_func_block(x) <函数块> 用于生成 generate_else_block(x) <否则语句> 用于生成 generate_logical(x) <逻辑表达式> 用于生成 generate_if(x) <条件语句> 用于生成 generate_code(tree) <函数定义> 用于生成 dfs(tree,func) 搜索函数 run(code) 获取生成结果 文法表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 <函数定义>-><修饰词闭包><类型><变量>[(]<参数声明>[)][{]<函数块>[}] <修饰词闭包>-><修饰词><修饰词闭包> <修饰词闭包>->[@] <修饰词>->[public] <修饰词>->[private] <修饰词>->[protected] <类型>->[int]<取地址> <类型>->[char]<取地址> <类型>->[boolean]<取地址> <类型>->[void]<取地址> <取地址>-><星号><取地址> <取地址>->[@] <星号>->[*] <变量>-><标志符><数组下标> <标志符>->[id] <数组下标>->[[]<因式>[]] <数组下标>->[@] <因式>->[(]<表达式>[)] <因式>-><变量> <因式>-><数字> <数字>->[digit] <表达式>-><因子><项> <因子>-><因式><因式递归> <因式递归>->[*]<因式><因式递归> <因式递归>->[/]<因式><因式递归> <因式递归>->[@] <项>->[+]<因子><项> <项>->[-]<因子><项> <项>->[@] <参数声明>-><声明><声明闭包> <参数声明>->[@] <声明>-><修饰词闭包><类型><变量><赋初值> <赋初值>->[=]<右值> <赋初值>->[@] <右值>-><表达式> <右值>->[{]<多个数据>[}] <多个数据>-><数字><数字闭包> <数字闭包>->[,]<数字><数字闭包> <数字闭包>->[@] <声明闭包>->[,]<声明><声明闭包> <声明闭包>->[@] <函数块>-><声明语句闭包><函数块闭包> <声明语句闭包>-><声明语句><声明语句闭包> <声明语句闭包>->[@] <声明语句>-><声明>[;] <函数块闭包>-><赋值函数><函数块闭包> <函数块闭包>-><for循环><函数块闭包> <函数块闭包>-><条件语句><函数块闭包> <函数块闭包>-><函数返回><函数块闭包> <函数块闭包>->[@] <赋值函数>-><变量><赋值或函数调用> <赋值或函数调用>->[=]<右值>[;] <赋值或函数调用>->[(]<参数列表>[)][;] <参数列表>-><参数><参数闭包> <参数闭包>->[,]<参数><参数闭包> <参数闭包>->[@] <参数>-><标志符> <参数>-><数字> <参数>-><字符串> <字符串>->[string] <for循环>->[for][(]<赋值函数><逻辑表达式>[;]<后缀表达式>[)][{]<函数块>[}] <逻辑表达式>-><表达式><逻辑运算符><表达式> <逻辑运算符>->[<] <逻辑运算符>->[>] <逻辑运算符>->[==] <逻辑运算符>->[!

语法分析器是这套编译系统的第二部分,可以直接用上一篇中的词法分析器的结果继续做语法分析. 文法表 = =一直没时间更, 直到考试周格外闲… 借鉴了一个网络上的文法表, 覆盖了一些基础的C文法, 测试后发现该文法是LL(1)文法. 文法如下: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 <函数定义>-><修饰词闭包><类型><变量>[(]<参数声明>[)][{]<函数块>[}] <修饰词闭包>-><修饰词><修饰词闭包> <修饰词闭包>->[@] <修饰词>->[public] <修饰词>->[private] <修饰词>->[protected] <类型>->[int]<取地址> <类型>->[char]<取地址> <类型>->[boolean]<取地址> <类型>->[void]<取地址> <取地址>-><星号><取地址> <取地址>->[@] <星号>->[*] <变量>-><标志符><数组下标> <标志符>->[id] <数组下标>->[[]<因式>[]] <数组下标>->[@] <因式>->[(]<表达式>[)] <因式>-><变量> <因式>-><数字> <数字>->[digit] <表达式>-><因子><项> <因子>-><因式><因式递归> <因式递归>->[*]<因式><因式递归> <因式递归>->[/]<因式><因式递归> <因式递归>->[@] <项>->[+]<因子><项> <项>->[-]<因子><项> <项>->[@] <参数声明>-><声明><声明闭包> <参数声明>->[@] <声明>-><修饰词闭包><类型><变量><赋初值> <赋初值>->[=]<右值> <赋初值>->[@] <右值>-><表达式> <右值>->[{]<多个数据>[}] <多个数据>-><数字><数字闭包> <数字闭包>->[,]<数字><数字闭包> <数字闭包>->[@] <声明闭包>->[,]<声明><声明闭包> <声明闭包>->[@] <函数块>-><声明语句闭包><函数块闭包> <声明语句闭包>-><声明语句><声明语句闭包> <声明语句闭包>->[@] <声明语句>-><声明>[;] <函数块闭包>-><赋值函数><函数块闭包> <函数块闭包>-><for循环><函数块闭包> <函数块闭包>-><条件语句><函数块闭包> <函数块闭包>-><函数返回><函数块闭包> <函数块闭包>->[@] <赋值函数>-><变量><赋值或函数调用> <赋值或函数调用>->[=]<右值>[;] <赋值或函数调用>->[(]<参数列表>[)][;] <参数列表>-><参数><参数闭包> <参数闭包>->[,]<参数><参数闭包> <参数闭包>->[@] <参数>-><标志符> <参数>-><数字> <参数>-><字符串> <字符串>->[string] <for循环>->[for][(]<赋值函数><逻辑表达式>[;]<后缀表达式>[)][{]<函数块>[}] <逻辑表达式>-><表达式><逻辑运算符><表达式> <逻辑运算符>->[<] <逻辑运算符>->[>] <逻辑运算符>->[==] <逻辑运算符>->[!

思路 这次的内容是写一个双向队列和随机队列, 双向队列自不必说, 用链表即可, 注意一下表头表尾的操作以及只有一个元素时的删除操作. 随机队列实现随机的时候需要查询具体下标的元素, 是一个O(1)操作, 所以使用自增长内存池实现. 刷到满分的过程中逐步解决的一些问题: 1. 对题目要求的每一个Exception都要抛出.否则会有以下问题: case test 失败 测试中断: Warning: the grading output was truncated due to excessive length. 2. 删除的节点和数组需要置null释放, 比如Deque出队的节点, RandomizedQueue出队的元素, 否则会报 - loitering observed during 71 of 100 deletions 3. 注意RandomizedQueue的capacity大小调节的时机, 在size到达capacity一半时扩大, 在size到达capacity四分之一时减小.否则会有以下问题: 不缩小capacity: 会导致内存测试失败 调节时机不对: 会导致一半的时间测试失败, 或者测试中断: Warning: the grading output was truncated due to excessive length. size 不为正数的边界情况: 数组越界 = =这个capacity大小要求过于严格了, 导致我用自己习惯的增长方式没有AC… Deque.java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 /** * Created by chestnutheng on 16-11-14.

最近在上华保健老师的课, 在学习的过程中做了一套编译系统, 外加顺便应付学校的作业. 这个词法分析器是这套编译系统的第一部分. 其中RE到DFA, DFA到NFA的部分都是手工完成, 自己规定token格式(C语言格式), 得到一个NFA. 课程内容详见: 编译原理MOOC 算法都是课程中的算法, 不再详述.伪代码可以在华老师的课件中找到. state_machine.json 第一部分是手写的DFA, 用类似树状数组的方式存储. 几个Key的含义如下: 1 2 3 4 5 SS: 起始状态 FS: 接受状态 I: 接受字符 T: 转换表 //如"8": {"3": 10, "5": 9}表示状态8输入I[3]可以转换到状态10, 状态8输入I[3]可以转换到状态9 S: 状态表 //下标对应的状态的含义 json文件: state_machine.json Driver.py 驱动文件,分析结果为三元组**(标识符, 内容, 行数)**的序列. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 #!

Percolation.java 题目见 渗透问题 运用题目给出的API来解决问题. 第一个文件是Percolation.java, 用来编写解决单个渗透问题相关代码. API: 1 2 3 4 5 6 7 8 9 public class Percolation { public Percolation(int n) // create n-by-n grid, with all sites blocked public void open(int row, int col) // open site (row, col) if it is not open already public boolean isOpen(int row, int col) // is site (row, col) open? public boolean isFull(int row, int col) // is site (row, col) full?

时间分析 time 命令 用*nix自带的系统命令 1 2 3 4 5 $ time python3 reg.py real 0m1.617s user 0m1.504s sys 0m0.112s sys 系统调用时间 user 用户空间花费时间 real 实际时间 如果user + sys < real 说明时间被花费在IO上。 profile和cProfile python自带了两个函数时间分析工具，cProfile和profile。cProfile是纯C写的，所以用起来快了很多。 查看帮助: 1 2 3 4 5 6 7 8 9 $ python3 -m cProfile -h Usage: cProfile.py [-o output_file_path] [-s sort] scriptfile [arg] ... Options: -h, --help show this help message and exit -o OUTFILE, --outfile=OUTFILE Save stats to <outfile> -s SORT, --sort=SORT Sort order when printing to stdout, based on pstats.