expr_ai.ts

//我的问题是
//expr : expr * expr 这样的文法 如何实现

//ai 是 CodeGeeX
//可以看到 ai 的回答就是龙书第二章的内容，不过不确定 term 这样的标识第一次出现是否是在龙书中。
//龙书对这部分扯了好几十页，实现上它的实现是非常简单直接的。
//我认为这是编译原理入门的最佳示例（如果是要学传统方式的话）
// -----------------------------------------------

/*
在 TypeScript 中实现类似 expr : expr * expr 这样的文法，通常需要使用递归下降解析器（Recursive Descent Parser）或
使用解析器生成器（如 BNF 解析器生成器）。下面是一个简单的递归下降解析器的实现示例，用于解析表达式 expr : expr * expr。

假设我们有一个简单的表达式语言，其中表达式由数字和乘法运算符组成。

Typescript

*/

// 更新内容
// 在 term 方法中添加了对加法运算符的支持:

// 在 while 循环中，除了检查乘法运算符 *，还检查加法运算符 +。
// 如果遇到加法运算符，则解析下一个因子并将其加到当前结果中。
// 示例用法:

// 更新了标记数组，包含乘法和加法运算符。
// 解析结果为 10，即 2 * 3 + 4。
// 这个更新后的解析器现在可以解析包含乘法和加法运算符的表达式。你可以根据需要进一步扩展它，以支持更多的运算符和表达式结构。



// 你
// 不对，你没有考虑优先级

// CodeGeeX
// Gen4
// 对不起，我理解了你的需求。我们需要实现一个更复杂的解析器，以处理运算符的优先级。例如，expr : expr * expr + expr 这样的表达式应该被解析为 (expr * expr) + expr。我们可以使用运算符优先级解析技术来实现这一点。

// 下面是一个使用运算符优先级解析的示例：

// Typescript
class Parser {
    private tokens: string[];
    private pos: number;

    constructor(tokens: string[]) {
        this.tokens = tokens;
        this.pos = 0;
    }

    private eat(token: string): void {
        if (this.tokens[this.pos] === token) {
            this.pos++;
        } else {
            throw new Error(`Unexpected token: ${this.tokens[this.pos]}, expected: ${token}`);
        }
    }

    private factor(): number {
        const token = this.tokens[this.pos];
        if (token.match(/^\d+$/)) {
            this.eat(token);
            return parseInt(token, 10);
        } else {
            throw new Error(`Unexpected token: ${token}, expected a number`);
        }
    }

    private term(): number {
        let result = this.factor();
        while (this.tokens[this.pos] === '*' || this.tokens[this.pos] === '/') {
            const op = this.tokens[this.pos];
            if (op === '*') {
                this.eat('*');
                result *= this.factor();
            } else if (op === '/') {
                this.eat('/');
                result /= this.factor();
            }
        }
        return result;
    }

    private expr(): number {
        let result = this.term();  //相当于是取二元运算符的 left
        while (this.tokens[this.pos] === '+' || this.tokens[this.pos] === '-') {
            const op = this.tokens[this.pos];
            if (op === '+') {
                this.eat('+');
                result += this.term();  //相当于是取二元运算符的 right
            } else if (op === '-') {
                this.eat('-');
                result -= this.term();  //相当于是取二元运算符的 right //和上面的一样的，只是运算符不同
            }
        }
        return result;
    }

    public parse(): number {
        return this.expr();
    }
}

// 示例用法
const tokens = ['2', '+', '3', '*', '4'];
const parser = new Parser(tokens);
const result = parser.parse();
console.log(result); // 输出: 10

/*
解释
类 Parser:

tokens 是一个字符串数组，表示输入的标记（token）。
pos 是当前解析的位置。
方法 eat:

检查当前标记是否与期望的标记匹配，如果匹配则移动到下一个标记。
方法 factor:

解析一个因子，因子是一个数字。如果当前标记是一个数字，则将其解析并返回其整数值。
方法 term:

解析一个项，项是由一个或多个因子通过乘法运算符连接而成的。它使用 factor 方法来解析因子，并在遇到乘法运算符时继续解析。
方法 parse:

调用 term 方法来解析整个表达式。
示例用法
创建一个 Parser 实例，传入标记数组。
调用 parse 方法来解析表达式并返回结果。
这个示例展示了如何使用递归下降解析器来解析一个简单的表达式，其中包含乘法运算符。你可以根据需要扩展这个解析器来支持更多的运算符和表达式结构。
*/


// 更新内容
// 添加了 expr 方法:

// expr 方法用于解析加法和减法运算符，这些运算符具有更高的优先级。
// 更新了 term 方法:

// term 方法现在只处理乘法和除法运算符，这些运算符具有较低的优先级。
// 示例用法:

// 更新了标记数组，包含乘法、加法和减法运算符。
// 解析结果为 10，即 (2 * 3) + 4。
// 这个更新后的解析器现在可以正确处理运算符的优先级。你可以根据需要进一步扩展它，以支持更多的运算符和表达式结构。