用预测分析法的总控程序、分析栈和预测分析表对输入串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))))`的子节点,依次类推。

相关推荐

最新推荐

recommend-type

基于Java实现的明日知道系统.zip

基于Java实现的明日知道系统
recommend-type

NX二次开发uc1653 函数介绍

NX二次开发uc1653 函数介绍,Ufun提供了一系列丰富的 API 函数,可以帮助用户实现自动化、定制化和扩展 NX 软件的功能。无论您是从事机械设计、制造、模具设计、逆向工程、CAE 分析等领域的专业人士,还是希望提高工作效率的普通用户,NX 二次开发 Ufun 都可以帮助您实现更高效的工作流程。函数覆盖了 NX 软件的各个方面,包括但不限于建模、装配、制图、编程、仿真等。这些 API 函数可以帮助用户轻松地实现自动化、定制化和扩展 NX 软件的功能。例如,用户可以通过 Ufun 编写脚本,自动化完成重复性的设计任务,提高设计效率;或者开发定制化的功能,满足特定的业务需求。语法简单易懂,易于学习和使用。用户可以快速上手并开发出符合自己需求的 NX 功能。本资源内容 提供了丰富的中英文帮助文档,可以帮助用户快速了解和使用 Ufun 的功能。用户可以通过资源中的提示,学习如何使用 Ufun 的 API 函数,以及如何实现特定的功能。
recommend-type

别墅图纸编号D020-三层-10.00&12.00米- 效果图.dwg

别墅图纸编号D020-三层-10.00&12.00米- 效果图.dwg
recommend-type

操作系统实验指导书(2024)单面打印(1).pdf

操作系统实验指导书(2024)单面打印(1).pdf
recommend-type

基于Python实现的校园教务系统

Api Function | Api | Description | Argument | | :-------- | :----- | :---- | | user_login | 登陆函数 | account, password, user_type=1, use_cookie_login=True | | get_schedule | 课表查询 | schedule_year=None, schedule_term=None, schedule_type=None | | get_score | 成绩查询 | score_year=None, score_term=None, use_api=0 | | get_info | 用户信息查询 | | | get_place_schedule| 教学场地课表查询(可用于空教室查询) |campus_list=None,
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

MATLAB柱状图在信号处理中的应用:可视化信号特征和频谱分析

![matlab画柱状图](https://img-blog.csdnimg.cn/3f32348f1c9c4481a6f5931993732f97.png) # 1. MATLAB柱状图概述** MATLAB柱状图是一种图形化工具,用于可视化数据中不同类别或组的分布情况。它通过绘制垂直条形来表示每个类别或组中的数据值。柱状图在信号处理中广泛用于可视化信号特征和进行频谱分析。 柱状图的优点在于其简单易懂,能够直观地展示数据分布。在信号处理中,柱状图可以帮助工程师识别信号中的模式、趋势和异常情况,从而为信号分析和处理提供有价值的见解。 # 2. 柱状图在信号处理中的应用 柱状图在信号处理
recommend-type

HSV转为RGB的计算公式

HSV (Hue, Saturation, Value) 和 RGB (Red, Green, Blue) 是两种表示颜色的方式。下面是将 HSV 转换为 RGB 的计算公式: 1. 将 HSV 中的 S 和 V 值除以 100,得到范围在 0~1 之间的值。 2. 计算色相 H 在 RGB 中的值。如果 H 的范围在 0~60 或者 300~360 之间,则 R = V,G = (H/60)×V,B = 0。如果 H 的范围在 60~120 之间,则 R = ((120-H)/60)×V,G = V,B = 0。如果 H 的范围在 120~180 之间,则 R = 0,G = V,B =
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。