给出E->E+T|T,T->(E)|a的分析表,并用Java语言编写它的LR(0)分析器
时间: 2024-03-16 15:43:15 浏览: 22
好的,下面是 LR(0) 分析表:
| 状态 | ( | ) | a | + | $ | E | T |
| :----: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 0 | s4 | | s5 | | | 1 | 2 |
| 1 | s4 | | s5 | s3 | acc | | |
| 2 | s6 | | s7 | | | | |
| 3 | s4 | | s5 | | | | 8 |
| 4 | s4 | | s5 | | | | 9 |
| 5 | s4 | | s5 | | | | 10 |
| 6 | s4 | | s5 | | | | |
| 7 | s4 | | s5 | | | | |
| 8 | r2 | r2 | r2 | r2 | r2 | | |
| 9 | r1 | r1 | r1 | s3 | r1 | | |
| 10 | r3 | r3 | r3 | r3 | r3 | | |
其中,s 表示移入(shift),r 表示规约(reduce),acc 表示接受(accept)。
下面是 Java 代码实现:
```java
import java.util.Stack;
public class LR0Parser {
private static final int[][] ACTION = {
{4, 0, 5, 0, 0, 1, 2},
{4, 0, 5, 3, -1, 0, 0},
{6, 0, 7, 0, 0, 0, 0},
{4, 0, 5, 0, 0, 0, 8},
{4, 0, 5, 0, 0, 0, 9},
{4, 0, 5, 0, 0, 0, 10},
{4, 0, 5, 0, 0, 0, 0},
{4, 0, 5, 0, 0, 0, 0},
{-2, -2, -2, -2, -2, 0, 0},
{-1, -1, -1, 3, -1, 0, 0},
{-3, -3, -3, -3, -3, 0, 0}
};
private static final int[][] GOTO = {
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 8, 0},
{0, 0, 0, 0, 0, 0, 0, 9, 0},
{0, 0, 0, 0, 0, 0, 0, 10, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0}
};
private static final int[] PRODUCTION_LHS = {0, 0, 1, 1, 2, 2, 2};
private static final int[] PRODUCTION_RHS_LEN = {3, 1, 3, 1, 1, 1, 1};
public static void main(String[] args) {
String input = "a+(a+a)";
Stack<Integer> stateStack = new Stack<>();
Stack<Character> symbolStack = new Stack<>();
stateStack.push(0);
symbolStack.push('$');
int inputIndex = 0;
while (true) {
int state = stateStack.peek();
char symbol = inputIndex < input.length() ? input.charAt(inputIndex) : '$';
int action = ACTION[state][getSymbolIndex(symbol)];
if (action > 0) { // 移入
stateStack.push(action);
symbolStack.push(symbol);
inputIndex++;
} else if (action < 0) { // 规约
int productionIndex = -action - 1;
int rhsLen = PRODUCTION_RHS_LEN[productionIndex];
for (int i = 0; i < rhsLen; i++) {
stateStack.pop();
symbolStack.pop();
}
state = stateStack.peek();
int lhs = PRODUCTION_LHS[productionIndex];
int nextState = GOTO[state][lhs];
stateStack.push(nextState);
symbolStack.push(getNonterminalSymbol(lhs));
} else { // 接受
System.out.println("Accepted");
break;
}
}
}
private static int getSymbolIndex(char symbol) {
switch (symbol) {
case '(':
return 0;
case ')':
return 1;
case 'a':
return 2;
case '+':
return 3;
case '$':
return 4;
case 'E':
return 5;
case 'T':
return 6;
default:
return -1;
}
}
private static char getNonterminalSymbol(int nonterminal) {
switch (nonterminal) {
case 0:
return 'E';
case 1:
return 'T';
default:
return ' ';
}
}
}
```
注意,这个代码只能处理 LR(0) 文法,如果要处理其他类型的文法,需要相应地修改分析表和代码逻辑。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![IntLib](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)