差别

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

--- 2020-2021:teams:namespace:递归下降与优先爬升 [2021/04/08 15:16]
great_designer [优先爬升]
+++ 2020-2021:teams:namespace:递归下降与优先爬升 [2021/04/09 14:06] (当前版本)
great_designer [算符优先]
@@ 行 195: / 行 195: @@
 A ::= 'x' | A '+' A | A '*' A
-就是算符优先文法。算符优先文法的每个终结符号都称为算符，右部中连接两个非终结符号的终结符号称为二元算符。。
+就是算符优先文法。算符优先文法的每个终结符号都称为算符，右部中连接两个非终结符号的终结符号称为二元算符。
 算符优先文法常常具有二义性，这时为了方便，常常需要为二元算符定义优先级来消除二义性。
@@ 行 215: / 行 215: @@
 }
-struct expression parse_opg(struct expression lhs, int prec) {
+struct expression parse_opg(struct expression lhs, int precedence) {
-    while (peek.is_binary_op && peek.prec >= prec) {
+    char peek=getchar();
-        char op = getchar();
+    while (is_binary_op(peek)&&prec(peek)>=precedence) {
+        char op=peek;
         struct expression rhs = parse_primary();
-        while (peek.is_binary_op && ( peek.prec > op.prec || ( peek.is_right_assoc && peek.prec == op.prec ))) {
+        peek=getchar();
-            rhs = parse_opg(rhs, peek.prec);
+        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;
 }
@@ 行 231: / 行 236: @@
 其中：
-字符peek表示下一个字符。
+函数is_binary_op(char peek)判断是否二元算符。
-整型prec表示算符优先级。
+函数is_right_assoc(peek)判断该二元算符是否具有右结合性，即先计算右边，再计算左边。
+函数prec(char peek)计算算符优先级。优先级最低为1，规定先运算高优先级，再运算低优先级。
+函数combine(struct expression lhs, char op, struct expression rhs)将二元表达式的各部分组合。
 函数parse_primary()解析一元表达式。
-函数combine(struct expression lhs, char op, struct expression rhs)将表达式的各部分组合。
+上面的优先爬升算法仅仅解决了最普通的算符优先文法，即只有二元算符的算符优先文法。
+一般认为，前置一元算符的优先级高于二元算符。如果我们对函数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

用户工具

站点工具

差别

页面工具