差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:namespace:递归下降与优先爬升 [2021/04/08 14:58]
great_designer
+++ 2020-2021:teams:namespace:递归下降与优先爬升 [2021/04/09 14:06] (当前版本)
great_designer [算符优先]
@@ 行 189: / 行 189: @@
 .对算符引入优先级。这种办法只适用于算符优先文法。
-例如对上面的文法，强行定义算符'+'的优先级是1，算符'*'的优先级是2，于是就人为地规定了算符的运算顺序，先运算'*'，再运算'+'。
+例如对上面的文法，强行定义算符'+'的优先级是1，算符'*'的优先级是2，于是就人为地规定了算符的运算顺序：先运算'*'，再运算'+'。
+算符优先文法（Operator Precedence Gramma, OPG）是一种特殊的文法。它要求：在文法规则的右部，每两个终结符号都不相邻。例如上面给出的
+A ::= 'x' | A '+' A | A '*' A
+就是算符优先文法。算符优先文法的每个终结符号都称为算符，右部中连接两个非终结符号的终结符号称为二元算符。
+算符优先文法常常具有二义性，这时为了方便，常常需要为二元算符定义优先级来消除二义性。
 ==== 优先爬升 ====
-几乎所有无二义性的与上下文无关的文法，都能够改写为可以递归下降的文法。然而，适合优先爬升的文法只有“算符优先文法”。
+几乎所有无二义性的与上下文无关的文法，都能够改写为可以递归下降的文法。然而，适用于优先爬升的文法，只有引入了算符优先级的算符优先文法。
+优先爬升（Precedence Climbing）的方法，特别适合处理表达式问题。
+优先爬升算法的一个示例如下：
+<code C>
+struct expression parse() {
+    struct expression lhs = parse_primary();
+    return parse_opg(lhs, 0);
+}
+struct expression parse_opg(struct expression lhs, int precedence) {
+    char peek=getchar();
+    while (is_binary_op(peek)&&prec(peek)>=precedence) {
+        char op=peek;
+        struct expression rhs = parse_primary();
+        peek=getchar();
+        while (is_binary_op(peek) && ( prec(peek) > prec(op) || ( is_right_assoc(peek) && prec(peek) == prec(op) ))) {
+            ungetc(peek,stdin);
+            rhs = parse_opg(rhs, prec(peek));
+            peek=getchar();
+        }
+        lhs = combine(lhs, op, rhs);
+    }
+    ungetc(peek,stdin);
+    return lhs;
+}
+</code>
+其中：
+函数is_binary_op(char peek)判断是否二元算符。
+函数is_right_assoc(peek)判断该二元算符是否具有右结合性，即先计算右边，再计算左边。
+函数prec(char peek)计算算符优先级。优先级最低为1，规定先运算高优先级，再运算低优先级。
+函数combine(struct expression lhs, char op, struct expression rhs)将二元表达式的各部分组合。
+函数parse_primary()解析一元表达式。
+上面的优先爬升算法仅仅解决了最普通的算符优先文法，即只有二元算符的算符优先文法。
+一般认为，前置一元算符的优先级高于二元算符。如果我们对函数parse_primary()稍加改造，就可以处理具有前置一元算符与括号的算符优先文法。一个示例：
+<code C>
+struct expr parse_primary()
+{
+    char next=getchar();
+    if(next=='(')
+    {
+        struct expression temp=parse();//括号里允许低优先级的二元算符
+        next=getchar();//右括号
+        return temp;
+    }
+    else if(next=='-')//假设'-'是一个前置一元运算符
+    {
+        struct expression temp=parse_primary();//一般前置一元算符的优先级高于二元算符
+        return -temp;//这里对表达式的结果取负的过程，需要自己写
+    }
+    else//普通标识符
+    {
+        return expression(next);//这里利用temp构造一个表达式的过程，需要自己写
+    }
+}
+</code>
+一般认为，后置一元算符的优先级也高于二元算符。如果对函数parse_opg(struct expression lhs, int precedence)中，每个while前的peek=getchar()语句后面再插入一个while语句，还可以处理后置一元算符。例如：
+<code C>
+    peek=getchar();
+    while(peek=='.')//假设'.'是一个后置一元算符，并且优先级也高于二元算符
+    {
+        struct expression lhs=dot(lhs);//这里处理点运算符，需要自己写
+        peek=getchar();
+    }
+    while (is_binary_op(peek)&&prec(peek)>=precedence)
+</code>
+根据该代码段插入的位置不同，可以将lhs对应写成rhs。
+如果对函数parse_primary()的普通标识符分支再加一个预读，还可以处理函数调用。例如，假设函数调用的语法是标识符后面接一个括号：
+<code C>
+    else//普通标识符
+    {
+        char temp=getchar();
+        if (temp=='(')
+        {
+            return function(next);//这里处理整个函数调用，需要自己写
+        }
+        else
+        {
+            ungetc(temp,stdin);
+            return expression(next);//这里利用temp构造一个表达式的过程，需要自己写
+        }
+    }
+</code>

CVBB ACM Team

用户工具

站点工具

差别

页面工具