消除其中的左递归和公共子表达式

消除左递归和公共子表达式是常见的优化手段，可以有效地降低语法分析和代码生成的复杂度。对于左递归，可以采用以下步骤进行消除：

1. 将所有的左递归规则转换为右递归规则；
2. 对右递归规则进行提取公因子，得到一个非左递归的等价文法。

对于公共子表达式，可以采用以下步骤进行消除：

1. 对于每个表达式，建立它的语法树；
2. 在语法树中，查找所有可能存在的公共子树；
3. 将公共子树提取出来，分别存储在临时变量中；
4. 将原表达式中的公共子树替换为对应的临时变量。

这样，我们就可以消除左递归和公共子表达式，从而使得程序的执行速度更快、更高效。

相关问题

消除左递归和左因子代码

### 关于消除左递归和提取左公因子

在编译原理中，消除左递归和提取左公因子是为了确保语法分析的有效性和效率。以下是具体的算法实现。

#### 消除左递归

当文法规则形如 \( A \rightarrow A\alpha | \beta \)，其中 \(A\) 是非终结符，\(α, β\) 表达的是由其他符号组成的字符串，则该规则存在直接或间接的左递归。为了消除这种形式的左递归，可以采用如下转换：

\[ A → \beta A' \]
\[ A'→ αA'|ε \]

这里引入了一个新的非终结符 \(A'\)[^2]。

public class CFG {
    public static void eliminateLeftRecursion(Map<String, List<String>> grammar) {
        Set<String> keys = new LinkedHashSet<>(grammar.keySet());
        
        for (String key : keys) { // 对每一个非终结符处理其左递归
            List<String> productions = grammar.get(key);
            
            boolean hasDirectLeftRecursion = false;
            String nonRecursiveProductions = "";
            StringBuilder recursivePart = new StringBuilder();
            
            for (String production : productions) {
                if (production.startsWith(key)) {
                    hasDirectLeftRecursion = true;
                    recursivePart.append(production.substring(key.length())).append("|");
                } else {
                    nonRecursiveProductions += production + " ";
                }
            }

            if (hasDirectLeftRecursion) {
                String primeKey = key + "'";
                
                // 更新当前非终结符对应的产生式
                grammar.put(key, Arrays.asList((nonRecursiveProductions.trim() + " " + primeKey).split(" ")));
                
                // 添加新产生的非终结符及其对应的新产生式
                grammar.put(primeKey, Arrays.asList(recursivePart.toString().trim().replaceAll("\\|$", "") + " ε").split(" "));
            }
        }
    }
}

这段代码实现了对给定上下文无关文法（CFG）中的所有直接左递归进行消除的操作[^1]。

#### 提取左公因子

对于含有公共前缀的情况，即多个产生式的左侧相同部分被重复定义时，可以通过创建一个新的非终结符来代替这部分共同的内容，从而简化文法并提高解析效率。例如原始规则为:

\[ S → aAbc | aAdc \]

经过提取左公因子后的版本变为：

\[ S → aA X \]
\[ X → bc | dc \][^3].

public class CFG {

    private static Map<String, List<String>> extractCommonPrefixes(Map<String, List<String>> grammar) {
        Map<String, List<String>> resultGrammar = new HashMap<>();
        
        for (Map.Entry<String, List<String>> entry : grammar.entrySet()) {
            String lhs = entry.getKey();
            List<String> rhsList = entry.getValue();

            while (!rhsList.isEmpty()) {
                int commonLength = getLongestCommonPrefix(rhsList);

                if (commonLength > 0) {
                    String prefix = rhsList.get(0).substring(0, commonLength);
                    String suffixNonTerminal = lhs + "'";

                    List<String> remainingRhs = new ArrayList<>();

                    for (String rhs : rhsList) {
                        remainingRhs.add(rhs.replaceFirst(prefix, ""));
                    }

                    resultGrammar.put(lhs, Collections.singletonList(prefix + suffixNonTerminal));
                    resultGrammar.put(suffixNonTerminal, remainingRhs);
                    
                    break; // After extracting once we need to recheck the updated list.
                } else {
                    resultGrammar.put(lhs, rhsList); // No common prefixes found so add as is.
                    break;
                }
            }
        }

        return resultGrammar;
    }

    private static int getLongestCommonPrefix(List<String> strings) {
        if (strings == null || strings.size() <= 1) return 0;

        int minLength = Integer.MAX_VALUE;
        for (String str : strings) {
            if (str != null && !str.isEmpty())
                minLength = Math.min(minLength, str.length());
        }

        if (minLength == Integer.MAX_VALUE) return 0;

        char[] firstStrChars = strings.get(0).toCharArray();
        outerLoop:
        for (int i = 0; i < minLength; ++i) {
            char c = firstStrChars[i];
            for (int j = 1; j < strings.size(); ++j) {
                if (strings.get(j).charAt(i) != c) continue outerLoop;
            }
            return i + 1;
        }
        return minLength;
    }
}

此方法通过遍历每个非终结符的所有右侧表达式寻找最长公共前缀，并将其替换为一个全新的非终结符表示这些相同的开头字符序列。

对文法[E]：E→TG G→+TG|-TG|ε T→FS S→*FS|/FS|ε F→(E)|i 编写c++程序实现对输入串的递归下降法分析语法。消除二义性，消除左递归，提取公共左因子，判断是否 LL(1)文法。如果遇到表达式中的错误，应输出错误提示信息（该信息越详细越好）。 可以给出详细的推导过程，列出每一步使用的产生式规则。

根据所给的文法[E]，我们可以进行以下的推导：

1. 消除左递归

将文法[G]中的左递归消除，得到新的文法：

G → +TG
G → -TG
G → ε
T → FS
S → *FS
S → /FS
S → ε
F → (E)
F → i
E → TG

2. 提取公共左因子

对于文法[G]中的+TG和-TG，它们都有一个相同的左因子T，我们需要将它们提取出来。同样地，对于文法[S]中的*FS和/FS，它们也有一个相同的左因子F，需要将其提取出来。得到新的文法：

G → +TG
G → -TG
G → ε
T → FS
S → F S'
S' → *FS'
S' → /FS'
S' → ε
F → (E)
F → i
E → TG

3. 判断是否 LL(1) 文法

我们可以通过构造预测分析表来判断是否是LL(1)文法：

| | ( | ) | i | + | - | * | / | $ |
|---|---|---|---|---|---|---|---|---|
| E | E → TG | | E → TG | | | | | |
| G | | | | G → +TG | G → -TG | | | G → ε |
| T | T → FS | | T → FS | | | | | |
| S | | | | | | S → *FS | S → /FS | S → ε |
| F | F → (E) | | F → i | | | | | |

可以发现，上述预测分析表中没有任何冲突，因此该文法是LL(1)文法。

4. 编写c++程序实现对输入串的递归下降法分析语法

下面是一个基于上述文法实现的递归下降法分析语法的C++代码：

#include <iostream>
#include <string>

using namespace std;

string input;
int ptr = 0;

void error(string message) {
    cout << "Error: " << message << endl;
    exit(0);
}

void match(char expected) {
    if (input[ptr] == expected) {
        ptr++;
    } else {
        error("unexpected token");
    }
}

void E();
void G();
void T();
void S();
void F();

void E() {
    T();
    G();
}

void G() {
    if (input[ptr] == '+') {
        match('+');
        T();
        G();
    } else if (input[ptr] == '-') {
        match('-');
        T();
        G();
    }
}

void T() {
    F();
    S();
}

void S() {
    if (input[ptr] == '*') {
        match('*');
        F();
        S();
    } else if (input[ptr] == '/') {
        match('/');
        F();
        S();
    }
}

void F() {
    if (input[ptr] == '(') {
        match('(');
        E();
        match(')');
    } else if (isalpha(input[ptr])) {
        match(input[ptr]);
    } else {
        error("unexpected token");
    }
}

int main() {
    cout << "Enter an arithmetic expression: ";
    cin >> input;
    E();
    if (ptr == input.length()) {
        cout << "Syntax analysis succeeded." << endl;
    } else {
        error("unexpected token");
    }
    return 0;
}

输入一个算术表达式，程序会对其进行语法分析，如果分析成功则输出 "Syntax analysis succeeded."，否则输出错误提示信息。