ARTS挑战-第四周

2019-04-14 本文已影响0人陈_振

Algorithm

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int charset[256] = {0};
        int left = 0, right = -1;
        int length = 0;
       
        while(left < s.size()){
            if(right+1 < s.size() && charset[s[right+1]] == 0){
                right++;
                charset[s[right]]++;
            } else {   
                charset[s[left]]--;
                left++;
            }
            length = max(length, right-left+1);
        }
        return length;
    }
};

Review

LLVM能做什么

Clang provides infrastructure to write tools that need syntactic and semantic information about a program. This document will give a short introduction of the different ways to write clang tools, and their pros and cons.
Clang提供了需要程序语法语义信息的编写工具的基础设施。本文将会简述编写clang工具的基本方法。

LibClang is a stable high level C interface to clang. When in doubt LibClang is probably the interface you want to use. Consider the other interfaces only when you have a good reason not to use LibClang.

LibClang是Clang的一个稳定的高级C接口。当你对是否使用LibClang有疑虑时，只有当您有充分的理由不使用LibClang时，再考虑其他接口。

Canonical examples of when to use LibClang:

Xcode
Clang Python Bindings

使用LibClang的典型案例：

Xcode
Clang Python Bindings

Use LibClang when you…:

want to interface with clang from other languages than C++
need a stable interface that takes care to be backwards compatible
want powerful high-level abstractions, like iterating through an AST with a cursor, and don’t want to learn all the nitty gritty details of Clang’s AST.

使用LibClang当你：

想要除C++以外的其他语言与Clang进行交流时
需要一个负责向后兼容的稳定的接口时
需要强大高级的抽象，就像使用游标遍历抽象语法树。并且你不想要了解Clang抽象语法树所有繁杂的细节。

Do not use LibClang when you…:

want full control over the Clang AST

不要使用LibClang当你：

想要完全控制Clang的抽象语法树。

Clang Plugins allow you to run additional actions on the AST as part of a compilation. Plugins are dynamic libraries that are loaded at runtime by the compiler, and they’re easy to integrate into your build environment.
Clang插件允许你作为编译的一部分运行其他的操作。插件是被编译器在运行时动态加载的动态库，它们很容易集成到构建环境。

Canonical examples of when to use Clang Plugins:

special lint-style warnings or errors for your project
creating additional build artifacts from a single compile step

使用Clang插件的典型案例：

为你的工程提供特殊样式的警告和错误提示信息
从单一的编译阶段创建其他的构建工件。

Use Clang Plugins when you…:

need your tool to rerun if any of the dependencies change
want your tool to make or break a build
need full control over the Clang AST

使用Clang 插件当你：

需要重新运行，如果有任何依赖发生变化
想要你的工具建立或打破一次构建
需要完全控制Clang的抽象语法树

Do not use Clang Plugins when you…:

want to run tools outside of your build environment
want full control on how Clang is set up, including mapping of in-memory virtual files
need to run over a specific subset of files in your project which is not necessarily related to any changes which would trigger rebuilds

不要使用Clang插件当你：

想要在构建环境之外去运行工具
想要完全控制Clang是怎么被设置的，包括虚拟文件在内存中的映射
需要在项目中运行特定的文件子集，这些文件不涉及任何会触发重构的变化

LibTooling is a C++ interface aimed at writing standalone tools, as well as integrating into services that run clang tools. Canonical examples of when to use LibTooling:

a simple syntax checker
refactoring tools

LibTooling是一个C++接口，旨在编写独立的工具，并集成到运行clang工具的服务中去。使用LibTooling的典型案例：

简单的语法检查器
重构工具

Use LibTooling when you…:

want to run tools over a single file, or a specific subset of files, independently of the build system
want full control over the Clang AST
want to share code with Clang Plugins

使用LibTooling当你：

想要在独立于构建系统的单个文件或指定文件集上运行工具
想要完全控制Clang抽象语法树
想用Clang插件共享代码

Do not use LibTooling when you…:

want to run as part of the build triggered by dependency changes
want a stable interface so you don’t need to change your code when the AST API changes
want high level abstractions like cursors and code completion out of the box
do not want to write your tools in C++

不要使用LibTooling当你：

想要作为构建系统的一部分，依赖变化触发去运行。
希望有一个稳定的接口，这样当AST API发生变化时，您就不需要更改代码了
想要使用高级的抽象就像游标和开箱即用的代码
不想使用C++编写你的工具

重点词汇

infrastructure ['ɪnfrə'strʌktʃɚ]
n. 基础设施
例句：Clang provides infrastructure to write tools .
canonical [kə'nɑnɪkl]
adj. 依教规的；权威的;
例句：Canonical examples of when to use LibClang.

** artifact** ['ɑrtə,fækt]
n. 人工制品；手工艺品；工件
例句：creating additional build artifacts from a single compile step.

** standalone** ['stændə,lon]
adj. 单独的
例句：writing standalone tools.

Tips

设计原则相关：

找出应用中可能需要变化之处，把它们独立出来，不要和那些不需要变化的代码混在一起。
针对接口编程，而不是针对实现编程。

GCC将C语言的程序转化为用机器语言描述的程序。将机器语言的程序按照ELF这种特定的文件格式注入文件，得到的就是可执行文件。
编程语言的运行方式：编程语言可以被编译成机器语言然后被执行，也可以不进行编译，直接运行编程语言的方法，例如解释器，Ruby和Perl的语言处理器就是用解释器来实现的。C语言也可以用解释器来执行，Ruby也可以被编译成机器语言。总之，运行语言的手段不止一种，编程语言与其运行方式可以自由搭配。但是根据语言的特点，其运行方式有适合与不适合该语言之说。一般来讲，有静态类型检查的，要求较高可靠性的情况下使用编译的方式；相反，没有静态类型检查，对灵活性要求高于严密性的情况下则使用解释的方式。
Build分为四个阶段：预处理-编译-汇编-链接
编译分为四个阶段：语法分析-语义分析-生成中间代码-代码生成-（优化）
语法分析syntax analyzing：解析器parser（或语法分析器syntax analyzer）转换成计算机易于理解的形式，即语法分析树。语法分析又分为两个阶段：
1. 词法分析lexical analyze。将代码分割为一个个的单词，也可以称为扫描。在分隔的同时还会推算出单词的种类，并为单词添加语义值。将“单词”和“单词的种类（语义值）”统称为token。所以词法分析器的作用可以简述为解析字符行，并生成token。下图为打印helloword程序的token序列：

tokens.png

语法分析。

语义分析semantic analysis：获得语法树之后，就要解析语法树，除去多余的内容，添加必要的信息，生成抽象语法树（Abstract Syntax Tree，AST）。上述处理就是语义分析。语义分析具体做了如下工作：
1. 区分变量为局部变量还是全局变量。
2. 解析变量的声明和引用。（在变量的声明和引用之间添加链接）
3. 变量和表达式的类型检查。
4. 检查在引用变量之前是否进行了初始化。
5. 检查函数是否按照定义返回了结果。
生成中间代码：将抽象语法树转化为只在编译器内部使用的中间代码（Intermediate Representation，IR）。之所以特地转为中间代码是为了支持多种编程语言或者机器语言。
解析代码转化为中间代码的这部分内容称为编译器的前端。
代码生成：最后把中间代码转化为汇编语言的阶段称为代码生成。由代码生成器Code Generator负责。
优化optimization：优化可以在编译器的各个环节进行。
字符串能够作为扫描器中的一个token被识别。而‘语句’，‘函数调用’则对应多个单词，即对应多个token，这样的语法扫描器是无法是别的。将上述多个token构成的语法单位识别出来是解析器的工作。
像‘函数调用’，‘表达式’，‘语句’等非token的语法单位成为非终端符，并将非终端符像java函数调用一样在后面加上括号写成stmt()或expr()。终端符可以被归纳为token。
解释为什么会称为终端符和非终端符：因为在画语法树的图时，终端符位于树的末端，非终端符位于分叉处。
定义definition包含语句statement，语句statement包含表达式expression，表达式expression包含项term。

ARTS挑战-第四周

Algorithm

Review

重点词汇

Tips

Share

猜你喜欢

热点阅读