|
所在平台: Udemy |
课程主页: https://www.udemy.com/course/compiler-design-significance-of-bottom-up-parsing/
课程评论：没有评论
Coursera 编译器设计课程总结 本课程深入探讨了编译器设计中的核心概念，重点在于**自底向上解析**。 **核心思想：** * 自底向上解析器从输入的叶子节点开始，逐步构建语法树，直至到达根节点。 * 其本质是反向寻找给定输入字符串的**最右推导**。 * 自底向上解析也称为**移入-归约解析 (Shift-Reduce Parsing)**。 **过程：** * 通过“归约”将输入字符串 `w` 缩减到文法的开始符号。 * 在每一步归约中，匹配产生式右侧的某个子串会被替换为该产生式左侧的非终结符。 * 如果子串选择得当，就能反向追踪出最右推导。 **主要解析方法：** 1. **算符优先解析 (Operator-Precedence Parsing)**：一种易于实现的移入-归约解析形式。 2. **LR 解析 (LR Parsing)**：一种更为通用的移入-归约解析形式，广泛应用于自动解析器生成器。 **关键概念：** * **句柄 (Handle)**：字符串 `w` 的一个子串，它匹配某个产生式的右侧，并且将其归约为产生式左侧的非终结符代表了反向最右推导中的一步。并非所有匹配产生式右侧的子串都是句柄。 * **句柄截除 (Handle-Pruning)**：通过“句柄截除”可以获得反向的最右推导。 本课程为学习者提供了理解编译器如何解析代码结构的基础知识，特别是通过自底向上方法来构建和验证代码语法。
A bottom-up parser creates the parse tree for a given input string starting from leaves towards the root. A bottom-up parser tries to find the right-most derivation of the given input string in the reverse order. Bottom-up parsing is also known as shift-reduce parsing. Bottom-up parsing is the process of "reducing" a string ‘w' to the start symbol of the grammar. At each reduction step, a particular substring matching the right-side of a production is replaced by the symbol on the left-side of the production. If the substring is chosen correctly, a right most derivation is traced out in reverse. A general style of bottom-up syntax analysis, known as shift-reduce parsing. Two types of bottom-up parsing: Operator-Precedence parsing - an easy to implement form of shift reduce parsing. LR parsing - a much more general form of Shift Reduce Parsing. LR parsing is used in a number of automatic parser generators. Informally a Handle of a string ‘w' is a substring that matches the RHS of some production and whose reduction to the non-terminal on the LHS of the production represents one step along the reverse of a rightmost derivation. But not every substring that matches the right side of a production rule is handle. A rightmost derivation in reverse can be obtained by "handle-pruning."
