#include <iostream> #include<stdio.h> #include<cstring> using namespace std; char str[10]; int index_a = 0; void E(); //E->TG; void X(); //G->+TG | e void T(); //T->FS void Y(); //S->*FS | e void F(); //F->(E) | i int main() { int len; cin >> str; len = strlen(str); str[len + 1] = '\0'; E(); cout << str; cout << "为合法符号串" << endl; index_a = 0; return 0; } /*******Beign*******/ /*构造递归关系及子程序*/ void E() { } void X() { } void T() { } void Y() { } void F() { } /*******End*******/ 以上为编程的提示代码，以下为该编程题目的具体要求：根据提示，在右侧编辑器补充代码，运行程序，进行结果对比。 根据下列文法完成程序设计，并给出相应提示： （1）E- TG （2）G- +TG|—TG （3）G- ε （4）T- FS （5）S- *FS|/FS （6）S- ε （7）F- (E) （8）F- i 输出的格式如下： (1) 输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (2) 输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 按照给出的要求和原代码完成编程，生成编程后的代码

### 递归下降分析器的实现 递归下降分析是一种自顶向下的语法分析方法，适用于LL(1)文法。通过构建一组相互调用的过程来模拟文法规则的应用，从而验证输入字符串是否属于该文法。 #### 文法描述 给定文法如下： - \( E \to TG \)[^1] - \( G \to +TG | -TG | \epsilon \)[^1] - \( T \to FS \)[^1] - \( S \to *FS | /FS | \epsilon \)[^1] - \( F \to (E) | i \) #### FIRST 和 FOLLOW 集合 为了编写递归下降分析器，需要先计算每个非终结符的FIRST和FOLLOW集合[^2]。 ##### FIRST 集合 - \( FIRST(E) = FIRST(T) = \{i, (\} \) - \( FIRST(G) = \{+, -, \epsilon\} \) - \( FIRST(T) = FIRST(F) = \{i, (\} \) - \( FIRST(S) = \{* , /, \epsilon\} \) - \( FIRST(F) = \{(, i\} \) ##### FOLLOW 集合 - \( FOLLOW(E) = \{\#, )\} \) - \( FOLLOW(G) = \{\#, )\} \) - \( FOLLOW(T) = \{+, -, \#, )\} \) - \( FOLLOW(S) = \{+, -, \#, )\} \) - \( FOLLOW(F) = \{*, /, +, -, \#, )\} \) #### Python 实现代码 下面是一个基于上述文法的递归下降分析器的Python实现： ```python class RecursiveDescentParser: def __init__(self, input_string): self.input_string = input_string.strip()[:-1] # Remove the '#' at the end and strip spaces. self.index = 0 def match(self, expected_token): if self.index < len(self.input_string) and self.input_string[self.index] == expected_token: self.index += 1 else: raise Exception(f"Syntax error: Expected '{expected_token}' but found '{self.input_string[self.index:self.index+1]}'.") def parse_E(self): try: self.parse_T() self.parse_G() except Exception as e: print(e) return False return True def parse_G(self): if self.index < len(self.input_string) and self.input_string[self.index] in ['+', '-']: operator = self.input_string[self.index] self.match(operator) self.parse_T() self.parse_G() elif self.index >= len(self.input_string) or self.input_string[self.index] not in ['+', '-', ')', '#']: raise Exception(f"Syntax error: Unexpected token '{self.input_string[self.index:self.index+1]}'.") def parse_T(self): self.parse_F() self.parse_S() def parse_S(self): if self.index < len(self.input_string) and self.input_string[self.index] in ['*', '/']: operator = self.input_string[self.index] self.match(operator) self.parse_F() self.parse_S() elif self.index >= len(self.input_string) or self.input_string[self.index] not in ['*', '/', '+', '-', ')', '#']: raise Exception(f"Syntax error: Unexpected token '{self.input_string[self.index:self.index+1]}'.") def parse_F(self): if self.index < len(self.input_string) and self.input_string[self.index] == '(': self.match('(') self.parse_E() self.match(')') elif self.index < len(self.input_string) and self.input_string[self.index] == 'i': self.match('i') else: raise Exception(f"Syntax error: Expected 'i' or '(', but found '{self.input_string[self.index:self.index+1]}'.") ``` #### 使用示例 假设我们有一个输入字符串 `i+i*i#`，可以这样测试解析器： ```python input_str = "i+i*i#" parser = RecursiveDescentParser(input_str) if parser.parse_E(): if parser.index == len(parser.input_string): # Ensure all characters have been consumed. print("Input string is valid.") else: print("Input string is invalid.") ``` --- ### 解析流程说明 对于输入字符串 `i+i*i#` 的解析过程如下： 1. 调用 `parse_E()` 开始匹配整个表达式。 2. 在 `parse_E()` 中调用 `parse_T()` 来处理第一个项 `i`。 3. 继续调用 `parse_G()` 处理后续操作符 `+` 及其后的子表达式。 4. 对于第二个加法部分 `i*i`，重复类似的步骤直到结束。 如果所有字符都被成功消耗且未发生错误，则表明输入字符串有效。 --- ###