词法分析
词法分析器事作为编译的第一阶段，词法分析器的主要任务是读入源程序的输入字符，将他们组成词素，生成并输出一个词法单元token序列
一个计算器的主要token序列 词法分析器的主要功能就是读入源程序，再作为统一的token序列输出
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)*，α∉ε
上下文无关语法
上下文无关语法中产生式的左边只有一个符号，只要文法的定义里有某个产生式，不管一个非终结符前后的串是什么，就可以应用相应的产生式进行推导
S -> dc // 上下文无关，即用S就可以推出dcaSb -> dc // 上下文相关，即还需要确定ab才能确定推出dc
左递归
一个文法形似
A -> Aα | B
就称为左递归
左递归文法是不能用自顶向下分析的，需要改变语法消除左递归
语法的歧义性
如果，对输入的字符串，给定的语法能根据输入构建两颗不同的语法推导树的话，我们就称，语法具有歧义性。
消除歧义性的一种方法是重新定义语法。
PDA 下推自动机
用栈来辅以的有限状态机叫作下推自动机（PushDown Automaton，PDA）。
因为有限状态机自身无法保存数据，所以增加栈来增加存储数据的能力，增加了栈之后，在进行状态转移的时候我们还需要压栈和出栈操作
| 输入字符 | |||
|---|---|---|---|
| ( | ) | EOF | |
| state | 0 | push1 | error |
| 1 | push1 | pop |
以前的二维表，表中元素对应的是跳转关系，而当前二维表对应元素对应的不再是跳转关系，而是对应于某种动作。栈顶也就是表示当前状态
利用PDA做自顶向下语法分析
如果解析堆栈是空的，那么语法解析结束。
如果栈顶端是非终结符，那么将它对应的右边推导以逆向的方式压入堆栈，例如如果有推导：
a -> b c d, 那么我们先将d 压入栈，然后是c,然后是b.如果右边是ε，那么我们就将栈顶元素弹出即可。如果栈顶是终结符，那么该终结符必须与当前读入的字符匹配，若不然，则出现语法错误，如果匹配，那么将它弹出栈顶，然后转到步骤1
//计算器输入的语法分析器 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; } } } 语法制导翻译
语法分析、语义分析、中间代码生成同时进行，称为语法制导翻译，也就是在在解析输入的字符串时，在特定位置执行指定的动作
在语法分析复合代码生成
private void term_prime() { if (lexer.match(Lexer.TIMES)) { lexer.advance(); factor(); op("*"); //代码生成 term_prime(); } else { return; } } 在语法分析的非终结符的属性
非终结符的属性有两种，一种叫继承性属性，这种属性在语法解析树中，是由父节点传递给子节点的。语法解析树的非叶子节点对应于代码中的一次函数调用，父节点把属性传给子节点，在代码中相当于父节点对应的函数在调用子节点对应的函数时，传递给子节点函数的参数。另一种属性称之为综合性属性，综合性属性相当于子节点把属性由下往上传递给父节点，在代码中对应于子节点对应的函数执行结束后，通过返回值把信息传递给父节点。
在PDA中引入属性堆栈来以此实现属性之间的传递
private StackvalueStack = new Stack ();public static Attribute getAttribute(Object attrVal) { Attribute obj = new Attribute(); obj.left = attrVal; obj.right = attrVal; return obj; }
- 如果解析堆栈为空，那么解析流程结束。
- 如果当前栈顶解析符号是ACTION,那么执行相应的代码生成逻辑，同时将ACTION弹出解析堆栈，并且将ACTION对应的属性对象弹出属性值堆栈。
- 如果解析堆栈栈顶是非终结符，那么执行以下步骤：
- 将该非终结符对应的属性对象存储到一个全局变量中parentAttribute中
- 将该非终结符所对应的语法推导表达式右边的解析符号压入堆栈，同时为每一个符号构造一个属性对象，将属性对象的left和right都初始化成parentAttribute.right,然后压入属性值堆栈。
- 跳转到0
- 如果当前栈顶的符号是终结符，判断当前读入的字符是否跟终结符匹配，如果不匹配，显示语法错误，要不然将当前符号弹出解析堆栈，将其对应的属性对象也弹出属性值堆栈。跳转到0
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;