设计典型的自顶向下语法分析程序—ll(1)语法分析程序

自顶向下语法分析程序是一种根据文法产生式和输入串来识别句子结构的程序。LL(1)语法分析程序则是指具有以下特点的自顶向下分析程序：采用最左推导、具有单符号向前看、只需一个向前符号的语法分析程序。

首先，我们需要构建一个LL(1)分析表，该表是一个二维数组，行代表非终结符，列表示终结符和向前看符号。根据文法产生式和First、Follow集合来填充LL(1)分析表。在填充LL(1)分析表时，需要考虑产生式右部符号串的First集合和Follow集合，以及空串的情况。填充完成后，得到一个非终结符和终结符的组合对应的产生式编号。

接下来，编写LL(1)语法分析程序的分析器部分，该部分通过输入串和LL(1)分析表来进行句子结构的识别。具体而言，分析器根据LL(1)分析表的内容来选择适当的产生式进行推导，并根据对应的产生式推导出输入串的句子结构，直到推导出句子的最左句型。在推导的过程中，需要考虑空串情况，对应选择空串产生式和进行回溯。

最后，对于输入串，LL(1)语法分析程序可以输出句子结构的推导过程或者识别出句子是否符合文法。如果输入句子符合文法，那么LL(1)语法分析程序会给出对应的推导序列和语法分析树；如果输入句子不符合文法，LL(1)语法分析程序会报告语法错误的位置和错误类型。

因此，一个典型的LL(1)语法分析程序包括构建LL(1)分析表和编写LL(1)语法分析程序的分析器部分，通过这两部分来实现句子结构的识别和语法错误的检测。

相关问题

通过完成LL(1)语法分析程序分析和调试，了解自顶向下语法分析的思路，熟悉判断LL (1)文法的方法，学会构造LL(1)文法的预测分析表以及对某一个输入串的分析过程。本实验在培养编程能力的同时培养自主学习和团队协作能力。

这是一项非常有益的实验，通过完成这个实验，你可以深入了解自顶向下语法分析的思路，包括如何判断LL(1)文法以及如何构造LL(1)文法的预测分析表。此外，你还将学习如何使用程序分析和调试技术来解决问题，这对于提高编程能力非常有帮助。

在完成实验的过程中，你可以自主学习和探索，也可以与团队成员合作完成任务。这将有助于培养你的自主学习和团队协作能力，这些都是非常重要的职业技能。

总之，这是一项非常有益的实验，可以帮助你提高编程能力，了解自顶向下语法分析的思路，并培养自主学习和团队协作能力。

语法分析程序设计LL1

### 设计实现 LL(1) 语法解析器

#### 定义文法和计算 FIRST 和 FOLLOW 集合

为了设计一个有效的 LL(1) 解析器，首先需要定义目标语言的上下文无关文法 (CFG)，并确保该文法满足 LL(1) 的条件。这意味着对于任何两个不同的产生式 A → α | β，在输入串的第一个符号集合中不存在交集。

接着，需计算每个非终结符的 FIRST 和 FOLLOW 集合：

- **FIRST(A)** 表示由非终结符A推导出来的最左端可能最先出现的终端字符组成的集合；
- **FOLLOW(A)** 则表示紧跟在某个特定非终结符之后可能出现的所有终端符号构成的集合[^2]。

std::unordered_map<std::string, std::set<char>> first;
std::unordered_map<std::string, std::set<char>> follow;

void computeFirst() {
    bool changed = true;
    while(changed){
        changed = false;
        for(auto &rule : grammarRules){
            auto [lhs,rhs]= rule; // lhs 是左侧非终结符，rhs 是右侧字符串列表
            for(const auto& symbol: rhs){
                if(isTerminal(symbol)){
                    insertIfNotPresent(first[lhs],symbol);
                    break;
                }else{
                    const auto& f=first[symbol];
                    for(char c:f){
                        insertIfNotPresent(first[lhs],c);
                    }
                    if(!containsEpsilon(f))break;
                }
            }
        }
    }
}

void computeFollow(){
    follow[startSymbol].insert('$'); // 终止符加入起始符号follow集中
    
    do{
        bool change=false;
        
        for(auto &[LHS,RHSs]:grammarRules){
            for(auto &RHS: RHSs){
                size_t i=0;
                char prev=' ';
                
                for(;i<RHS.size();++i){
                    char X=RHS[i];
                    
                    if(isNonterminal(X)){
                        if(i+1==RHS.size()){
                            for(auto y:follow[LHS]){
                                insertIfNotPresent(follow[X],y);
                                change|=true;
                            }
                        }else{
                            for(int j=i+1;j<=RHS.size();j++){
                                set<char> temp_first;
                                
                                for(int k=i+1;k<j;++k){
                                    addAll(temp_first,first[RHS[k]]);
                                    
                                    if(!containsEpsilon(first[RHS[k]]))
                                        goto end_loop;
                                }
                                end_loop:;
                                
                                if(j==RHS.size())
                                    addAll(temp_first,follow[LHS]);
                                
                                for(auto z:temp_first){
                                    if(z!='$')
                                        insertIfNotPresent(follow[X],z);
                                }
                            }
                        }
                        
                        if(prev!=' '&&isNonterminal(prev)&& containsEpsilon(first[X])){
                            for(auto w:first[X])
                                insertIfNotPresent(follow[prev],w),change=true;
                            
                            continue;
                        }
                    }
                    prev=X;
                }
            }
        }
    }while(change);
}

#### 构建 LL(1) 分析表

一旦获得了完整的 FIRST 和 FOLLOW 集合，则可以创建用于指导解析过程的动作表格——LL(1) 分析表。此表记录了针对给定栈顶状态（即当前预期读取的非终结符）以及下一个待匹配输入项时应采取的操作。

struct Action { int row,col,value;};
vector<Action> llTable;

bool buildLLTable(){
    clear(llTable);

    for(auto &[nonterminals,rightHandSides]:grammarRules){
        string NT=nonterminals;
        for(string production:rightHandSides){
            vector<string> symbols=spliteProductionIntoSymbols(production);
            
            set<char> lookaheads=getLookaheadFor(symbols); // 获取前瞻符号
            
            for(char lookahead:lookaheads){
                addActionToTable(NT,lookahead,symbols);
            }
        }
    }

    return checkConflicts();
}

#### 实现递归下降解析函数

基于上述准备好的动作表格，现在可以通过编写一组相互调用的方法来模拟自顶向下解析流程。这些方法对应于文法中的各个非终结符，并依据实际遇到的情况决定下一步骤。

class Parser {
public:
    void parse(vector<Token>& tokens){
        this->tokens=tokens;
        pos=0;
        tokenCount=(int)this->tokens.size();

        S(); // 假设'S'是文法的开始符号
        
        if(pos!=tokenCount || !stack.empty()) throw ParseError("Unexpected EOF");
    }

private:
    stack<string> stack={"$","S"}; // 初始化堆栈含结束标记与初始非终结符
    int pos{};
    int tokenCount{};

    Token currentToken(){return tokens[pos];};
    
    void match(Token expected){
        if(currentToken()==expected){
            ++pos;
        } else {
            throw ParseError{"Expected "+toString(expected)};
        }
    }

    void S(){
        switch(getAction('S',currentToken().type)){
            case ACTION_EPSILON:return ;
            default:{
                string nextRule=llTable[ACTION_S][currentToken().type];
                applyRule(nextRule);
            }
        }
    }

    void E(){
        /* Similar pattern as function `S` */
    }

    // Other non-terminal parsing functions...
};