编译原理初解

词法分析

词法分析器事作为编译的第一阶段,词法分析器的主要任务是读入源程序的输入字符,将他们组成词素,生成并输出一个词法单元token序列

一个计算器的主要token序列 词法分析器的主要功能就是读入源程序,再作为统一的token序列输出

1
2
3
4
5
6
7
8
9
10
public static final int  EOI = 0;
public static final int SEMI = 1;
public static final int PLUS = 2;
public static final int TIMES = 3;
public static final int LP = 4;
public static final int RP = 5;
public static final int NUM_OR_ID = 6;
public static final int WHITE_SPACE = 7;
public static final int UNKNOWN_SYMBOL = 8;
public static final int SUB = 9;

文法

文法用来描述语言的规则,文法G定义为一个四元组(VN,VT,P,S),其中,VN为非终结符集合,VT终结符集合;P是产生式结合;S称为识别符或开始符号,也是一个非终结符,至少要在一条产生式的左边出现。

产生式的形式是α → β,α称为产生式左部,β称为产生式右部,α属于VN,β∈(VN∪VT)*,α∉ε

上下文无关语法

上下文无关语法中产生式的左边只有一个符号,只要文法的定义里有某个产生式,不管一个非终结符前后的串是什么,就可以应用相应的产生式进行推导

1
2
S -> dc // 上下文无关,即用S就可以推出dc
aSb -> dc // 上下文相关,即还需要确定ab才能确定推出dc

左递归

一个文法形似

1
A -> Aα | B

就称为左递归

左递归文法是不能用自顶向下分析的,需要改变语法消除左递归

语法的歧义性

如果,对输入的字符串,给定的语法能根据输入构建两颗不同的语法推导树的话,我们就称,语法具有歧义性。

消除歧义性的一种方法是重新定义语法。

PDA 下推自动机

用栈来辅以的有限状态机叫作下推自动机(PushDown Automaton,PDA)。

因为有限状态机自身无法保存数据,所以增加栈来增加存储数据的能力,增加了栈之后,在进行状态转移的时候我们还需要压栈和出栈操作

括号匹配有限自动机

输入字符
( ) EOF
state 0 push1 error
1 push1 pop

以前的二维表,表中元素对应的是跳转关系,而当前二维表对应元素对应的不再是跳转关系,而是对应于某种动作。栈顶也就是表示当前状态

利用PDA做自顶向下语法分析

  1. 如果解析堆栈是空的,那么语法解析结束。

  2. 如果栈顶端是非终结符,那么将它对应的右边推导以逆向的方式压入堆栈,例如如果有推导:
    a -> b c d,
    那么我们先将d 压入栈,然后是c,然后是b.如果右边是ε,那么我们就将栈顶元素弹出即可。

  3. 如果栈顶是终结符,那么该终结符必须与当前读入的字符匹配,若不然,则出现语法错误,如果匹配,那么将它弹出栈顶,然后转到步骤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
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
//计算器输入的语法分析器
public void parse() {
while (!pdaStack.empty()) {
Grammar action = pdaStack.peek();

switch (action) {
case STMT:
if (lexer.match(Lexer.EOI)) {
pdaStack.pop();
}
else {
pdaStack.pop();
pdaStack.push(Grammar.STMT);
pdaStack.push(Grammar.SEMI);
pdaStack.push(Grammar.EXPR);
}
break;
case EXPR:
pdaStack.pop();
pdaStack.push(Grammar.EXPR_PRIME);
pdaStack.push(Grammar.TERM);
break;
case TERM:
pdaStack.pop();
pdaStack.push(Grammar.TERM_PRIME);
pdaStack.push(Grammar.FACTOR);
break;
case TERM_PRIME:
pdaStack.pop();
if (lexer.match(Lexer.TIMES)) {
pdaStack.push(Grammar.TERM_PRIME);
pdaStack.push(Grammar.FACTOR);
pdaStack.push(Grammar.MULTIPLE);
}
break;
case FACTOR:
pdaStack.pop();
if (lexer.match(Lexer.NUM_OR_ID)) {
pdaStack.push(Grammar.NUM_OR_ID);
}
else if (lexer.match(Lexer.LP)) {
pdaStack.push(Grammar.RIGHT_PARENT);
pdaStack.push(Grammar.EXPR);
pdaStack.push(Grammar.LEFT_PARENT);
}
else {
parseError();
}
break;
case EXPR_PRIME:
pdaStack.pop();
if (lexer.match(Lexer.PLUS)) {
pdaStack.push(Grammar.EXPR_PRIME);
pdaStack.push(Grammar.TERM);
pdaStack.push(Grammar.PLUS);
}
break;
case NUM_OR_ID:
pdaStack.pop();
if (!lexer.match(Lexer.NUM_OR_ID)) {
parseError();
}
lexer.advance();
break;
case PLUS:
pdaStack.pop();
if (!lexer.match(Lexer.PLUS)) {
parseError();
}
lexer.advance();
break;
case MULTIPLE:
pdaStack.pop();
if (!lexer.match(Lexer.TIMES)) {
parseError();
}
lexer.advance();
break;
case LEFT_PARENT:
pdaStack.pop();
if (!lexer.match(Lexer.LP)) {
parseError();
}
lexer.advance();
break;
case RIGHT_PARENT:
pdaStack.pop();
if (!lexer.match(Lexer.RP)) {
parseError();
}
lexer.advance();
break;
case SEMI:
pdaStack.pop();
if (!lexer.match(Lexer.SEMI)) {
parseError();
}
lexer.advance();
break;
default:
break;
}
}
}

语法制导翻译

语法分析、语义分析、中间代码生成同时进行,称为语法制导翻译,也就是在在解析输入的字符串时,在特定位置执行指定的动作

在语法分析复合代码生成

1
2
3
4
5
6
7
8
9
10
11
private void term_prime() { 
if (lexer.match(Lexer.TIMES)) {
lexer.advance();
factor();
op("*"); //代码生成
term_prime();
}
else {
return;
}
}

在语法分析的非终结符的属性

非终结符的属性有两种,一种叫继承性属性,这种属性在语法解析树中,是由父节点传递给子节点的。语法解析树的非叶子节点对应于代码中的一次函数调用,父节点把属性传给子节点,在代码中相当于父节点对应的函数在调用子节点对应的函数时,传递给子节点函数的参数。另一种属性称之为综合性属性,综合性属性相当于子节点把属性由下往上传递给父节点,在代码中对应于子节点对应的函数执行结束后,通过返回值把信息传递给父节点。

在PDA中引入属性堆栈来以此实现属性之间的传递

1
2
3
4
5
6
7
8
9
10
private Stack<Attribute> valueStack = new Stack<Attribute>();


public static Attribute getAttribute(Object attrVal) {
Attribute obj = new Attribute();
obj.left = attrVal;
obj.right = attrVal;

return obj;
}
  1. 如果解析堆栈为空,那么解析流程结束。
  2. 如果当前栈顶解析符号是ACTION,那么执行相应的代码生成逻辑,同时将ACTION弹出解析堆栈,并且将ACTION对应的属性对象弹出属性值堆栈。
  3. 如果解析堆栈栈顶是非终结符,那么执行以下步骤:
    • 将该非终结符对应的属性对象存储到一个全局变量中parentAttribute中
    • 将该非终结符所对应的语法推导表达式右边的解析符号压入堆栈,同时为每一个符号构造一个属性对象,将属性对象的left和right都初始化成parentAttribute.right,然后压入属性值堆栈。
    • 跳转到0
  4. 如果当前栈顶的符号是终结符,判断当前读入的字符是否跟终结符匹配,如果不匹配,显示语法错误,要不然将当前符号弹出解析堆栈,将其对应的属性对象也弹出属性值堆栈。跳转到0
1
2
3
4
5
6
7
8
9
10
11
12
13
case ACTION_0:
pdaStack.pop();
String t = getname();
int curPos = valueStack.size() - 1;
System.out.println("value stack grammar: " + valueStack.get(curPos - 1).getGrammar());
valueStack.get(curPos - 1).right = new String();
valueStack.get(curPos - 1).right = t;

System.out.println("value stack grammar: " + valueStack.get(curPos - 2).getGrammar());
valueStack.get(curPos - 2).right = new String();
valueStack.get(curPos - 2).right = t;
valueStack.pop();
break;