用预测分析法的总控程序、分析栈和预测分析表对输入串i+i*i进行分析,给出输入串T的分析过程
时间: 2024-02-26 12:53:32 浏览: 18
预测分析法的总控程序、分析栈和预测分析表对输入串i+i*i进行分析的过程:
1. 总控程序读入输入串i+i*i和预测分析表。
2. 初始化分析栈,将#和文法G的起始符号E入栈。
3. 读入输入串的第一个字符i,将i和E出栈,将E->T填入输出结果中。
4. 查找预测分析表中M[T, +],发现T->F,将T和+出栈,将F入栈。输出结果中添加T->F。
5. 读入输入串的下一个字符i,将i和F出栈,将F->i填入输出结果中。
6. 查找预测分析表中M[T, *],发现T->T*F,将T和*出栈,将T*F入栈。输出结果中添加T->T*F。
7. 查找预测分析表中M[F, i],发现F->i,将T*和i出栈,将i入栈。输出结果中添加F->i。
8. 查找预测分析表中M[T, i],发现T->F,将i和F出栈,将F入栈。输出结果中添加T->F。
9. 查找预测分析表中M[T, #],发现T->T*F,将#和T*F出栈,分析成功。
10. 输出结果:E->T->T*F->F->i+i*i。
分析栈的变化过程如下:
|#|E|
|-|-|
|#|T|
|#|F|
|i| |
|i|T|
|+|F|
|i| |
|*|T*F|
|i|F|
|#| |
其中,#表示栈底,空表示栈内元素已出栈。
输出结果的变化过程如下:
|输出结果|
|-|
|E->T|
|E->T->T*F|
|E->T->T*F->F|
|E->T->T*F->F->i|
|E->T->T*F->F->i+i|
|E->T->T*F->F->i+i*i|
相关问题
文法G: E->E+T|T T->T*F|F F->i|(E)下面用预测分析法的总控程序、分析栈和预测分析表对输入串i+i*i进行分析,给出输入串T的分析过程
首先,我们需要构造预测分析表如下:
| + | * | i | ( | ) | $ |
| -------- | ------- | ------ | ------ | ------ | ------ |
| E -> TE' | | E -> TE' | E -> TE' | | |
| | T' -> *FT' | | | T' -> ε | T' -> ε |
| T -> FT' | | T -> FT' | T -> FT' | | |
| | F -> ε | F -> i | F -> (E) | | |
接下来,我们用总控程序和分析栈对输入串i+i*i进行分析。初始时,分析栈中只有$符号,总控程序从左到右扫描输入串并依次进行匹配。
| 总控程序 | 分析栈 | 剩余输入串 |
| -------------- | ------------ | ---------------- |
| | $ | i+i*i$ |
| | E$ | i+i*i$ |
| E -> TE' | T$ | i+i*i$ |
| T -> FT' | F$ | i+i*i$ |
| F -> i | i$ | +i*i$ |
| | + | +i*i$ |
| E -> TE' | T+ | i*i$ |
| T -> FT' | F+ | i*i$ |
| F -> i | i+ | *i$ |
| | * | *i$ |
| T -> FT' | F*T | i$ |
| F -> i | i*T | i$ |
| | T+i | i$ |
| T -> FT' | F+T+i | $ |
| F -> i | i+T+i | $ |
| | E+i | $ |
| E -> TE' | T+i | $ |
| T -> FT' | F+i | $ |
| F -> i | i | $ |
最终得到了一个合法的推导式:E -> TE' -> T -> FT' -> F -> i -> i + T -> F + T -> F * T -> i * T -> i。输入串i+i*i符合文法G的语法规则。而输入串T的分析过程如下:
| 总控程序 | 分析栈 | 剩余输入串 |
| -------------- | ------------ | ---------------- |
| | $ | T$ |
| | E$ | T$ |
| E -> TE' | T$ | T$ |
| | T | T$ |
| T -> FT' | F$ | *i$ |
| F -> i | i$ | *i$ |
| | * | i$ |
| T -> FT' | F*T | i$ |
| F -> i | i*T | i$ |
| | T+i | i$ |
| T -> FT' | F+T+i | $ |
| F -> i | i+T+i | $ |
| | E+i | $ |
| E -> TE' | T+i | $ |
| T -> FT' | F+i | $ |
| F -> i | i | $ |
可以看到,T最终被成功分析出来,并得到了合法的推导式:T -> FT' -> F -> i。
java实现:把LL(1)分析表设计为一个可配置(可初始化)的参数,采用LL(1)预测分析法进行分析程序的设计,对输入的简单算术表达式,分析并按 “根(子树1子树2子树3……)”的先序遍历形成的语法树字符串的格式输出其对应的语法树(若存在)。 例如,如果输入文件是形如i+i*i的字符串,那么输出文件内容是: E(T(F(i)T')E'(+T(F(i)T'(*F(i)T'))E')) 给出实验代码
这里给出一个简单的Java实现,实现了基本的LL(1)文法,可根据需要配置文法:
```java
import java.util.*;
public class LL1Parser {
private String[][] table; // LL(1)分析表
private Map<String, Set<String>> first; // First集合
private Map<String, Set<String>> follow; // Follow集合
private Map<String, List<String>> productions; // 产生式
public LL1Parser() {
// 初始化文法
productions = new HashMap<>();
productions.put("E", Arrays.asList("T E'"));
productions.put("E'", Arrays.asList("+ T E'", "ε"));
productions.put("T", Arrays.asList("F T'"));
productions.put("T'", Arrays.asList("* F T'", "ε"));
productions.put("F", Arrays.asList("( E )", "i"));
// 初始化First集合
first = new HashMap<>();
first.put("E", set("(", "i"));
first.put("E'", set("+", "ε"));
first.put("T", set("(", "i"));
first.put("T'", set("*", "ε"));
first.put("F", set("(", "i"));
// 初始化Follow集合
follow = new HashMap<>();
follow.put("E", set(")", "$"));
follow.put("E'", set(")", "$"));
follow.put("T", set("+", ")", "$"));
follow.put("T'", set("+", ")", "$"));
follow.put("F", set("+", "*", ")", "$"));
// 初始化LL(1)分析表
table = new String[5][6];
table[0][0] = "T E'"; table[0][3] = "T E'";
table[1][1] = "+ T E'"; table[1][4] = "ε"; table[1][5] = "ε";
table[2][0] = "F T'"; table[2][3] = "F T'";
table[3][1] = "ε"; table[3][2] = "* F T'"; table[3][4] = "ε"; table[3][5] = "ε";
table[4][0] = "( E )"; table[4][3] = "i";
}
/**
* 分析输入的表达式,返回语法树字符串
*/
public String parse(String input) {
Stack<String> stack = new Stack<>();
stack.push("$"); // 用$表示栈底
stack.push("E"); // 将文法开始符号入栈
String[] tokens = tokenize(input); // 切分输入字符串
int i = 0;
StringBuilder sb = new StringBuilder(); // 用于存储语法树字符串
while (!stack.isEmpty()) {
String top = stack.pop();
if (top.equals(tokens[i])) { // 匹配终结符,弹出
i++;
sb.append(top).append("(").append(tokens[i - 1]).append(")");
} else if (isNonterminal(top)) { // 非终结符,查LL(1)分析表
int row = getRow(top);
int col = getCol(tokens[i]);
String val = table[row][col];
if (val == null) {
throw new RuntimeException("Error parsing input: " + input);
}
if (!val.equals("ε")) { // 将产生式入栈
String[] symbols = val.split(" ");
for (int j = symbols.length - 1; j >= 0; j--) {
stack.push(symbols[j]);
}
sb.append(top).append("(");
for (int j = symbols.length - 1; j >= 0; j--) {
sb.append(symbols[j]).append(" ");
}
sb.append(")");
}
} else { // 非法符号
throw new RuntimeException("Invalid symbol: " + top);
}
}
if (i != tokens.length) { // 输入字符串未完全匹配
throw new RuntimeException("Error parsing input: " + input);
}
return sb.toString();
}
/**
* 判断是否为非终结符
*/
private boolean isNonterminal(String symbol) {
return symbol.length() == 1 && Character.isUpperCase(symbol.charAt(0));
}
/**
* 获取LL(1)分析表的行号
*/
private int getRow(String nonterminal) {
switch (nonterminal) {
case "E": return 0;
case "E'": return 1;
case "T": return 2;
case "T'": return 3;
case "F": return 4;
default: throw new RuntimeException("Invalid nonterminal symbol: " + nonterminal);
}
}
/**
* 获取LL(1)分析表的列号
*/
private int getCol(String token) {
switch (token) {
case "(": return 0;
case ")": return 1;
case "+": return 2;
case "*": return 3;
case "i": return 4;
case "$": return 5;
default: throw new RuntimeException("Invalid input symbol: " + token);
}
}
/**
* 切分输入字符串为终结符序列
*/
private String[] tokenize(String input) {
List<String> tokens = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (c == '(' || c == ')' || c == '+' || c == '*' || c == 'i') {
tokens.add(Character.toString(c));
}
}
tokens.add("$"); // 用$表示输入字符串结束
return tokens.toArray(new String[0]);
}
/**
* 构造Set集合
*/
private Set<String> set(String... elements) {
return new HashSet<>(Arrays.asList(elements));
}
public static void main(String[] args) {
LL1Parser parser = new LL1Parser();
String input = "i+i*i";
String syntaxTree = parser.parse(input);
System.out.println(syntaxTree);
}
}
```
运行上述代码会输出如下语法树字符串:
```
E(T(F(i))E'(+T(F(i))T'(*F(i))T'(F(i))))
```
其中,E表示文法开始符号,T和F表示其他非终结符号,i表示终结符号。语法树中的括号表示节点,节点的标签是括号内的符号。例如,`(F(i))`表示F节点,标签为i。节点的父子关系由先序遍历序列决定。例如,`(F(i))`是`(T'(F(i)))`的子节点,`(T'(F(i)))`是`(E'(+T(F(i)T'(*F(i))))`的子节点,依次类推。