已知文法 exp→ exp + factor | factor, factor → (exp)|number；请用BNF消除左递归并且设计一个消除左递归后的文法的L-SDD来求表达式的值

消除左递归后的文法为：

exp → factor exp'
exp' → + factor exp' | ε
factor → (exp) | number

其中，exp → factor exp' 是为了消除左递归，exp' → ε 是为了处理 exp 后面没有加号的情况。

L-SDD 代码如下：

exp → factor { $$ = $1; }
exp' → + factor { op = '+'; } exp' { $$ = $3 + $2; }
exp' → ε { $$ = 0; }
factor → ( exp ) { $$ = $2; }
factor → number { $$ = atoi($1); }

其中，exp 产生式的语义动作计算 factor 的值，并将其赋值给 $$. exp' 产生式的第一个语义动作记录加号的操作符，并将 factor 的值赋值给 $2，exp' 的值赋值给 $3；第二个语义动作将 $2 和 $3 相加并将结果赋值给 $$. factor 产生式的第一个语义动作返回括号内表达式的值，第二个语义动作将数字字符串转换为整型并返回。

相关问题

一种比较简单的算术表达式的BNF定义如下 〈算术表达式〉→〈项〉|〈算术表达式〉+〈项〉|〈算术表达式〉-〈项〉 〈项〉→〈因式〉|〈项〉*〈因式〉|〈项〉/〈因式〉 〈因式〉→〈变量〉|（〈算术表达式）） 〈变量〉→i 用符号表示如下： E→T|E+T|E-T T→F|T*F|T/F F→i|(E) 2、消去上面文法的左递归 E→TE’ E’→+TE’|-TE’|ε T→FT’ T’→*FT’|/FT’|ε F→i|(E) 3. 按消去左递归的文法，使用Java写出对应的递归下降语法分析器。

以下是消除左递归后的文法：

E → TE’
E’ → +TE’ | -TE’ | ε
T → FT’
T’ → *FT’ | /FT’ | ε
F → i | (E)

下面是对应的递归下降语法分析器的Java代码：

import java.util.Scanner;

public class Parser {
    private static String input;
    private static int pos;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入算术表达式：");
        input = scanner.nextLine();
        pos = 0;

        try {
            parseE();
            if (pos == input.length()) {
                System.out.println("输入合法");
            } else {
                System.out.println("输入不合法");
            }
        } catch (Exception e) {
            System.out.println("输入不合法");
        }
    }

    private static void parseE() throws Exception {
        parseT();
        parseEPrime();
    }

    private static void parseEPrime() throws Exception {
        if (pos < input.length() && (input.charAt(pos) == '+' || input.charAt(pos) == '-')) {
            pos++;
            parseT();
            parseEPrime();
        }
    }

    private static void parseT() throws Exception {
        parseF();
        parseTPrime();
    }

    private static void parseTPrime() throws Exception {
        if (pos < input.length() && (input.charAt(pos) == '*' || input.charAt(pos) == '/')) {
            pos++;
            parseF();
            parseTPrime();
        }
    }

    private static void parseF() throws Exception {
        if (pos < input.length() && input.charAt(pos) == '(') {
            pos++;
            parseE();
            if (pos < input.length() && input.charAt(pos) == ')') {
                pos++;
            } else {
                throw new Exception();
            }
        } else if (pos < input.length() && input.charAt(pos) == 'i') {
            pos++;
        } else {
            throw new Exception();
        }
    }
}

一个简单文法编译器的设计与实现

一个简单文法编译器的设计与实现可以分为以下几个步骤：

1. 设计文法：首先需要设计一个合适的文法，用来描述需要编译的语言的语法和语义。文法可以使用BNF、EBNF或其他形式来表示。

2. 词法分析器的设计与实现：词法分析器用来将输入的源代码分解成一个一个的记号(Token)，并将这些记号进行分类。每个记号代表了源代码中的一个词汇单元，例如关键字、标识符、运算符、常量等。常见的词法分析器生成工具有lex、flex等。

3. 语法分析器的设计与实现：语法分析器用来将输入的记号序列转化为语法树，以检查语法是否正确。常见的语法分析器生成工具有yacc、bison等。

4. 语义分析器的设计与实现：语义分析器用来分析语法树，检查语义是否正确。例如，检查类型匹配、变量定义是否正确、函数调用是否正确等。

5. 代码生成器的设计与实现：代码生成器用来将语法树转化为目标代码，可以是汇编语言、机器语言或其他高级语言。生成目标代码的方式可以使用静态单赋值(SSA)、三地址码等。

6. 优化器的设计与实现：优化器用来对目标代码进行优化，以提高程序的执行效率和节省计算资源。常见的优化技术包括常量折叠、死代码消除、循环展开等。

以上是一个简单文法编译器的设计与实现的基本流程，具体实现细节会根据不同的编程语言和编译器工具而有所不同。