编译原理整理
计算机
1、图灵机
状态
输入——时钟作为一种标准输入，另一种最好能够读取人类的想法。
状态转换函数F(将输入和当前状态转换为下一个状态)
输出
所以可以有物理计算机，电子计算机，量子计算机。
如何描述状态
数字就可以——一切皆可以用数字表示，如ASCII、动物植物分类、商品
一个数字不够(需要数组)
状态转换函数是什么
一个表格就可以，将接收到的输入l变成新的状态S。
输入
时间是最重要的输入
可以通过设备读取外界信息(鼠标、键盘、头盔、脑电波)
输出
从计算机中读取状态(打印机，显示器)
图灵机理论提出的时候还没有现在的计算机，图灵机也不是专为现代计算机提出的，它只是一个抽象的描述，跟具体的实现无关，只要满足图灵机的四个条件——状态、状态转换函数、输入、输出的机器都可以叫计算机。
这是一台最早的图灵机，由纸带输入，经过处理在显示面板上输出。这台机器在性能上跟现代的计算机虽然不能比，但是在逻辑上，它能解决的问题，我们现代计算机也可以解决，它不能解决的问题，我们现代计算机也不能解决。
2、冯.诺依曼模型
图灵机的思想比较抽象，它不管你具体的实现，用机械做也可以，用电子器材做也可以，用生物做也可以。而冯.诺依曼基于图灵机的思想，基于电子器材，又写了一个抽象模型。
从冯.诺依曼开始，我们今天的计算机才开始繁荣起来。
而其CPU、寄存器、算术逻辑单元(ALU)发展出了二进制的机器语言，这是第一代语言。再将机器语言转化成人比较好识别的汇编语言指令集，汇编语言是第二代语言。而我们所常用的C,C++,Java,C#等等这样的高级程序设计语言都属于第三代语言。第四代语言是为特定应用设计的语言，比如用于数据库查询的SQL语言。但不论是哪一种，他们都属于冯.诺依曼语言。
3、编译原理
所有高级语言的建立，最终都是要将其转化成机器语言，这是一个翻译的过程，我们称之为编译。当然，也不一定是高级语言向低级语言转化，也可以是某一种未知的语言向已存在的高级语言转化，比如C或者Java，再去执行。当然还有用计算机语言来实现硬件设备，如硬件语言VHDL。
这是一个实现硬件加法器的代码，然后将编程语言翻译成电路布线，最后由3D打印机打印出来。
编译原理的"翻译"能力只能作用在形式语言上。所谓形式语言就是不能有特定的意义，比如"大唐李世民"，"机器猫"，这些我们人可以理解，但是机器是不理解的，这就是一些特定的意义。
计算机语言提供给了我们新的思考方式。比如ddd领域模型，它也是在OOP语言的发展下产生出来的新的思考领域。当然还包括了各种各样的面相对象的设计模式等等。
什么是编译器
编译器将源程序编译成目标程序。编译成的目标程序才可以接受输出，产出输出，其代表为C语言
什么是解释器
解释器同时接受源程序和输入，执行并返回输出。其代表为JavaScript
混合编译器
中间代码更容易被翻译成目标程序、优化空间更大。中间语言的存在更利于编译器的实现。让虚拟机处理复杂的执行环境(跨平台)。其代表为早期的Java。
即时编译器(Just-in-time compiler)
一种提高效率的方法，中间代码不是直接执行，而是先被编译成机器码再执行。其代表为现在的Java。这样现在的Java的效率比早期提高了50%以上。
交叉编译
在一个平台上编译产生多个平台的可执行代码。
我们现在来模拟一门新的语言，让其转化为Java。新的语言的样式如下
func tower(int n,int from,int to,int use) void {
if(n == 1){
print("move from " + from + " to " + to);
return
}
tower(n - 1,from,use,to)
tower(1,from,to,use)
}
tower(3,1,3,2)我们要将这段代码给编译成Java，第一步一定是做词法分析，然后是语法分析。
4、编译过程
词法分析
int a = 1 + 4 * 5;词法分析是一个分词断句+判断词性的过程，上面这条语句，我们会拆分成int、a、=、1、+、4、*、5、;的各个不同的词。词法分析的主要目的是将字符流转成符号流。输入:源代码(字符流) 输出:符号流
int是一个Integer整型的类型。
a是一个变量。
=是一个操作符
1是一个整型数字常量
+是一个操作符
4是一个整型数字常量
*是一个操作符
5是一个整型数字常量
;是一个结束符
词法分析是对这些词进行“词性标注”,每个词是一个元组，至少包含一个字符串和一个词性描述。根据这些情况，我们来进行Java的定义
/**
* 词类型，包括关键字、值类型变量、操作符、括号、各种数据类型的常量
*/
public enum TokenType {
KEYWORD,
VARIABLE,
OPERATOR,
BRACKET,
INTEGER,
STRING,
FLOAT,
BOOLEAN
}/**
* 源代码的词
*/
@AllArgsConstructor
public class Token {
@Getter
private TokenType type; //词性描述
@Getter
private String value; //源代码的词本身的字符串
@Override
public String toString() {
return String.format("type %s, value %s",type,value);
}
/**
* 是否是一个值类型常量
* @return
*/
public boolean isScalar() {
return type == TokenType.INTEGER || type == TokenType.FLOAT
|| type == TokenType.STRING || type == TokenType.BOOLEAN;
}
}现在我们要从源代码(字符流)中拿取每一个字符，这里使用流Stream，而不是数组，是因为我们不知道源代码中有多少个字符。
/**
* 从源代码(字符流)中取每一个字符
* @param <T>
*/
public class PeekIterator<T> implements Iterator<T> {
//最大缓存数
private final static int CACHE_SIZE = 10;
//代码流的迭代器
private Iterator<T> it;
//所有迭代器it取出来的元素都会放进该队列缓存中
private Queue<T> queueCache = new LinkedList<>();
//当需要看到next之前的元素时，从该栈中获取
private Stack<T> stackPutBacks = new Stack<>();
//结束词，根据实际情况而定
private T endToken = null;
public PeekIterator(Stream<T> stream) {
it = stream.iterator();
}
public PeekIterator(Stream<T> stream,T endToken) {
it = stream.iterator();
this.endToken = endToken;
}
/**
* 查看代码流迭代器next的值，查看完放回栈中，下次
* 优先从栈中获取
* @return
*/
public T peek() {
if (stackPutBacks.size() > 0) {
return stackPutBacks.firstElement();
}
if (!it.hasNext()) {
return endToken;
}
T val = next();
this.putBack();
return val;
}
/**
* 将next取出的字符放回栈中(这里不是放回迭代器中)
*/
@SuppressWarnings("unchecked")
public void putBack() {
if (queueCache.size() > 0) {
stackPutBacks.push((T) ((LinkedList) queueCache).pollLast());
}
}
@Override
public boolean hasNext() {
return endToken != null || stackPutBacks.size() > 0 || it.hasNext();
}
/**
* 取出源代码流中的字符(从流中移除)
* 先从栈中获取，如果栈中没有数据再从流中获取
* @return
*/
@Override
public T next() {
T val = null;
if (stackPutBacks.size() > 0) {
val = stackPutBacks.pop();
}else {
if (!it.hasNext()) {
T tmp = endToken;
endToken = null;
return tmp;
}
val = it.next();
}
while (queueCache.size() > CACHE_SIZE - 1) {
queueCache.poll();
}
queueCache.add(val);
return val;
}
}由于我们从源代码流中取出来的肯定是一个一个的字符(char)，所以我们要看哪些字符可以构成一个词(token)，最后再给这些词定性。首先我们要知道这些字符属于哪个范畴，这里就需要用到正则表达式。
public class AlphabetHelper {
private static Pattern ptnLetter = Pattern.compile("^[a-zA-Z]$");
private static Pattern ptnNumber = Pattern.compile("^\\d$");
private static Pattern ptnLiteral = Pattern.compile("^\\w$");
private static Pattern ptnOperator = Pattern.compile("^[+-\\\\*/<>=!&|^%]$");
/**
* 判断是否为字母
* @param c
* @return
*/
public static boolean isLetter(char c) {
return ptnLetter.matcher(c + "").matches();
}
/**
* 判断是否为数字
* @param c
* @return
*/
public static boolean isNumber(char c) {
return ptnNumber.matcher(c + "").matches();
}
/**
* 判断是否为本文(包含字母，数字，下划线_)
* @param c
* @return
*/
public static boolean isLiteral(char c) {
return ptnLiteral.matcher(c + "").matches();
}
/**
* 判断是否为操作符
* @param c
* @return
*/
public static boolean isOperator(char c) {
return ptnOperator.matcher(c + "").matches();
}
}关于正则表达式的内容请参考正则表达式
在进行真正从源代码流中取字符之前，我们需要对新语言的关键字进行一下整理
public class KeyWords {
private static String[] keywords = {
"if",
"else",
"for",
"while",
"break",
"func",
"return"
};
private static Set<String> set = new HashSet<>(Arrays.asList(keywords));
/**
* 判断是否为一个关键字
* @param word
* @return
*/
public static boolean isKeyword(String word) {
return set.contains(word);
}
}在判断过程中，需要定义一个异常
@AllArgsConstructor
public class LexicalException extends Exception {
@Getter
private String msg;
public LexicalException(char c) {
msg = String.format("Unexpected character %c",c);
}
}现在我们可以开始从源代码流(字符流)中提取两种类型了，一种是变量，一种是关键字。
/**
* 提取变量或关键字
* @param it
* @return
*/
public static Token makeVarOrKeyword(PeekIterator<Character> it) {
String s = "";
while (it.hasNext()) {
char lookahead = it.peek();
if (AlphabetHelper.isLiteral(lookahead)) {
s += lookahead;
}else {
break;
}
it.next();
}
if (KeyWords.isKeyword(s)) {
return new Token(TokenType.KEYWORD,s);
}
if (s.equals("true") || s.equals("false")) {
return new Token(TokenType.BOOLEAN,s);
}
return new Token(TokenType.VARIABLE,s);
}该方法是Token类的静态方法。我们可以对其进行单元测试，测试代码如下
@Test
public void test_varOrKeyword() {
PeekIterator<Character> it1 = new PeekIterator<>("if abc".chars().mapToObj(x -> (char) x));
PeekIterator<Character> it2 = new PeekIterator<>("true abc".chars().mapToObj(x -> (char) x));
Token token1 = Token.makeVarOrKeyword(it1);
Token token2 = Token.makeVarOrKeyword(it2);
//判断token1的词性是否是一个关键字
assertEquals(TokenType.KEYWORD,token1.getType());
//判断token1的源代码字符串是否是if
assertEquals("if",token1.getValue());
//判断token2的词性是否是一个BOOLEAN型常量
assertEquals(TokenType.BOOLEAN,token2.getType());
//判断token2的源代码字符串是否是true
assertEquals("true",token2.getValue());
it1.next();
Token token3 = Token.makeVarOrKeyword(it1);
//判断token3的词性是否是一个变量
assertEquals(TokenType.VARIABLE,token3.getType());
//判断token3的源代码字符串是否是abc
assertEquals("abc",token3.getValue());
}要使用该测试，需要使用该依赖
<dependency>
<groupId>org.junit.jupiter</groupId>
<artifactId>junit-jupiter-api</artifactId>
<version>RELEASE</version>
</dependency>这里的@Test为
import org.junit.jupiter.api.Test;assertEquals()方法为
import static org.junit.jupiter.api.Assertions.assertEquals;结果
现在我们要开始提取字符串，提取字符串需要用到有限状态机
这是一个提取字符串的有限状态机。由于是新语言，我们设定无论是双引号"aaa"还是单引号'aaa'都可以组建一个字符串。此时无论我们进入提取方法的第一个字符是单引号还是双引号，我们都设定此时状态机的状态为0，当第一个字符为双引号的时候，此时状态机的状态变为1，直到遇到另外一个双引号，提取字符串，其他时候状态不变。当第一个字符为单引号的时候，此时状态机的状态变为2，直到遇到另外一个单引号，提取字符串，其他时候状态不变。
现在我们用两种方式来实现，一种是常规方式，一种是状态模式来实现
/**
* 提取字符串
* @param it
* @return
* @throws LexicalException
*/
public static Token makeString(PeekIterator<Character> it) throws LexicalException {
String s = "";
int state = 0;
while (it.hasNext()) {
char c = it.next();
switch (state) {
case 0:
if (c == '"') {
state = 1;
}else {
state = 2;
}
s += c;
break;
case 1:
if (c == '"') {
return new Token(TokenType.STRING,s + c);
}else {
s += c;
}
break;
case 2:
if (c == '\'') {
return new Token(TokenType.STRING,s + c);
}else {
s += c;
}
break;
}
}
throw new LexicalException("Unexpected error");
}状态模式中，我们需要设计状态接口、实现类和状态上下文
/**
* 获取字符串时状态接口
*/
public interface MakeStrState {
Token doAction(MakeStrContent content,String s);
}/**
* 获取字符串的状态上下文
*/
@Data
@RequiredArgsConstructor
public class MakeStrContent {
@NonNull
private MakeStrState state;
private char c;
}初始状态实现类
public class StartMakeStrState implements MakeStrState {
@Override
public Token doAction(MakeStrContent content,String s) {
if (content.getC() == '"') {
content.setState(new DoubleQuotesMakeStrState());
}else {
content.setState(new SingleQuotesMakeStrState());
}
return null;
}
}双引号状态实现类
public class DoubleQuotesMakeStrState implements MakeStrState {
@Override
public Token doAction(MakeStrContent content,String s) {
if (content.getC() == '"') {
return new Token(TokenType.STRING,s);
}else {
return null;
}
}
}单引号状态实现类
public class SingleQuotesMakeStrState implements MakeStrState {
@Override
public Token doAction(MakeStrContent content,String s) {
if (content.getC() == '\'') {
return new Token(TokenType.STRING,s);
}else {
return null;
}
}
}提取字符串方法
/**
* 提取字符串
* @param it
* @return
* @throws LexicalException
*/
public static Token makeStr(PeekIterator<Character> it) throws LexicalException {
String s = "";
MakeStrState startState = new StartMakeStrState();
MakeStrContent content = new MakeStrContent(startState);
while (it.hasNext()) {
char c = it.next();
content.setC(c);
if (content.getState() instanceof StartMakeStrState) {
content.getState().doAction(content,"");
s += c;
}else {
Token token = content.getState().doAction(content, s + c);
if (token != null) {
return token;
}else {
s += c;
}
}
}
throw new LexicalException("Unexpected error");
}对这两种方式进行单元测试
@Test
public void test_makeString() {
String[] tests = {
"\"123\"",
"\'123\'"
};
Stream.of(tests).map(s -> new PeekIterator<Character>(s.chars().mapToObj(x -> (char) x)))
.map(c -> {
try {
return Token.makeString(c);
} catch (LexicalException e) {
e.printStackTrace();
return null;
}
}).forEach(t -> assertEquals(TokenType.STRING,t.getType()));
}结果
@Test
public void test_makeStr() {
String[] tests = {
"\"123\"",
"\'123\'"
};
Stream.of(tests).map(s -> new PeekIterator<Character>(s.chars().mapToObj(x -> (char) x)))
.map(c -> {
try {
return Token.makeStr(c);
} catch (LexicalException e) {
e.printStackTrace();
return null;
}
}).forEach(t -> assertEquals(TokenType.STRING,t.getType()));
}结果
当然更好的可以用状态机来实现，不过我没有添加别的第三方包，所以暂时用不了开源状态机，关于状态机可以参考Spring状态机