差别

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

--- 2020-2021:teams:namespace:递归下降与优先爬升 [2021/04/08 14:26]
great_designer [递归下降]
+++ 2020-2021:teams:namespace:递归下降与优先爬升 [2021/04/09 14:06] (当前版本)
great_designer [算符优先]
@@ 行 1: / 行 1: @@
-===== 递归下降与优先爬升 =====
+===== 编译简介 =====
 ==== 文法规则 ====
@@ 行 10: / 行 10: @@
 表示“句子由主语和谓语构成”，“谓语由动词和宾语构成”。这种构成是按顺序的。
+对于语法中的大写字母，或者用尖括号括起来的部分，称为“语法项”或者“非终结符号”。非终结符号可以出现在文法规则的左部或者右部。
+对于语法中的小写字母，或者用单引号引起来的部分，表示具体的字符，称为“终结符号”。终结符号只能出现在文法规则的右部，无法再向下推导。最终待匹配的字符串只由终结符号构成。
+文法G[S]的含义是，文法G的“起始符号”是S，相当于语法树的根节点。起始符号规定为一个非终结符号。
 文法规则中有一些特殊符号。
-符号ε：表示空串，即长度为0的字符串，就是什么都没有。空串的概念类似于空集，但是空串是串，仍旧作为元素来看待，与空集概念有区别。
+符号ε：希腊字母epsilon，表示空串，即长度为0的字符串，就是什么都没有。空串的概念类似于空集，但是空串是串，仍旧作为元素来看待，与空集概念有区别。
 符号|：表示“或”。例如：
@@ 行 26: / 行 32: @@
 表示A可以匹配ε、a、aa、aaa、……，所有只由a构成的字符串。
+如果要表示这些特殊符号，一般会用单引号引起来，或者用转义字符'\'去转义。
 ==== 语法分析 ====
@@ 行 41: / 行 49: @@
 能够递归下降的文法，需要满足3个条件：
-没有左递归。
+.没有左递归。例如文法
-候选式首符号不相交。
+A ::= a | Ab
-如果候选式可以为ε，则候选式的首符号与该语法项的后继符号也不相交。
+无法使用递归下降，必须改写为与之等价的
+A ::= a{b}
+才能使用递归下降。
+.候选式首符号不相交。例如文法：
+A ::= ab | ac
+无法使用递归下降。必须改写为与之等价的
+A ::= aB
+B ::= b | c
+才能使用递归下降。
+.如果候选式可以为ε，则候选式的首符号与该语法项的后继符号也不相交。例如文法：
+S ::= Aa
+A ::= ε | ab
+无法使用递归下降。必须改写为与之等价的
+S ::= aB
+B ::= ε | ab
+才能使用递归下降。
 递归下降的设计方法是：
@@ 行 65: / 行 103: @@
 于是设计的程序为：
-```C
+<code C>
 int S() {
     int ans = A();//括号匹配
@@ 行 128: / 行 166: @@
     }
 }
-```
+</code>
+==== 算符优先 ====
+文法可能有二义性。例如：
+A ::= 'x' | A '+' A | A '*' A
+就具有二义性。因为对于字符串x+x*x，有两种解读方式：先运算x*x，或者先运算x+x。
+解决二义性有两种办法：
+.改写为无二义性的文法。比如：
+A ::= B '+' A
+B ::= C '*' B
+C ::= x
+没有二义性。
+.对算符引入优先级。这种办法只适用于算符优先文法。
+例如对上面的文法，强行定义算符'+'的优先级是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

用户工具

站点工具

差别

页面工具