编译原理中空字用什么表示

在编译原理中，空字（epsilon）通常用希腊字母ε来表示。空字表示一个空字符串，即一个不包含任何字符的字符串，也可以理解为一个字符串中没有字符的位置。空字在正则文法、上下文无关文法、自动机等很多概念中都有应用，常用于表示一些可选的或者可以省略的语法成分，或者用于简化某些推导过程。

举个例子，假设我们有以下的上下文无关文法：

S -> aB
B -> Cd | ε
C -> e

其中，S、B、C都是非终结符，a、d、e都是终结符，符号“|”表示选择。

这个文法表示的是一些由非终结符S开始，由终结符a、d、e组成的字符串，其中B可以是终结符d和非终结符C组成的字符串，或者是空字。如果我们使用这个文法进行推导，可以得到以下的句子：

a
ad
ae
aee

其中的第二个句子可以通过两种方式得到，一种是选择B -> Cd，另一种是选择B -> ε。因此，空字在上下文无关文法中具有重要的作用。

相关问题

编译原理语法分析LR1

### 编译原理 LR(1) 语法分析详解

#### 定义与特点
LR(1) 是一种自底向上的语法分析方法，其中 "L" 表示从左到右扫描输入串，“R” 表示最右推导的逆过程即规约，而 "(1)" 则意味着带有向前搜索符号的能力[^1]。这种特性允许 LR(1) 分析器在决定何时应用某一产生式的规约操作之前查看下一个输入符号。

#### 工作机制
为了实现上述功能，LR(1) 构建了一个项目集规范族，在每个项目后面附加一个向前看符号（lookahead symbol）。当构建状态转换图时，不仅考虑当前项目的完成情况，还要结合预期到来的第一个实际终结符来进行决策。这有效地减少了冲突的发生概率，并提高了识别能力[^2]。

#### 项目集及其闭包运算
对于每一个文法 G 和它的起始符号 S' -> .S ，初始项为 [S'->.S,$] 。这里 $ 表示文件结束标志。之后通过计算闭包 Closure(I)，可以得到所有可能扩展出来的新项目：

- 如果存在形如 A → α·Bβ 的项目，则将 B 所有规则中的第一个位置加上相应的向前查找标记加入 I 中；
- 对于任何非终结符 X ∈ Vn 及其对应的 FIRST(X) 集合内的成员 a (a 不等于 ε ) 或者 FOLLOW(A)，如果遇到的是空字则取跟随集中元素作为新的 look-ahead 符号。

def closure(items, grammar):
    new_items = set()
    
    while True:
        added = False
        
        for item in list(new_items | items):  # 使用联合后的集合迭代
            if not isinstance(item.lookahead, str):
                continue
                
            next_symbol_index = len(item.production.rhs.split()) - len(item.dot_position)
            
            if next_symbol_index >= 0 and item.production.lhs != 'S\'':
                next_nonterminal = item.production.rhs.split()[next_symbol_index]

                for production in grammar.productions_for(next_nonterminal):
                    lookahead_set = {item.lookahead} \
                        if item.dot_position == len(item.production.rhs.split()) or \
                           grammar.first_of(item.production.rhs[next_symbol_index:]) == {'ε'} \
                        else grammar.first_of(item.production.rhs[next_symbol_index:])
                    
                    for la in lookahead_set:
                        potential_item = Item(production=production, dot_position=[],
                                              lookahead=la)

                        if potential_item not in new_items.union(items):
                            new_items.add(potential_item)
                            added = True
                    
        if not added:
            break
            
    return new_items | items

编译原理 First集的实现

### 编译原理中First集合的实现方法

在编译器设计领域，`FIRST`集合用于描述给定文法符号串可能开始的终结符。如果该符号串可以推出空字符串，则`ε`也属于其`FIRST`集合。

#### 定义与性质
对于任一非终结符A，定义`FIRST(A)`为所有可以从A推导出来的最左端首个字符组成的集合（当能推导出空字时含`ε`）。此概念适用于预测分析表构建等场景[^1]。

#### 计算过程概述
为了获得某个特定非终结符X的`FIRST(X)`：

- 如果X是一个终端符号，则`FIRST(X)`仅包含自身；
- 若X是非终端且存在规则形如`X → Y...Z`，那么依次考察Y至Z各元素对应的`FIRST(Y)...FIRST(Z)`直到遇到不含`ε`的结果为止；若全含则最终还需加入`ε`到`FIRST(X)`里[^3]。

#### C++代码实例展示
下面给出一段基于上述原则编写用来计算并打印指定上下文无关文法规则集中各个非终态所对应`FIRST`集合作品质保证措施之一——测试用例验证环节不可或缺的部分程序片段:

#include <iostream>
#include <unordered_map>
#include <set>
using namespace std;

// 假设已知文法结构体Grammar及其成员函数getProductions()
struct Grammar {
    unordered_map<char,vector<string>> productions;
    
    const vector<string>& getProductions(char nonterminal){
        return productions.at(nonterminal);
    }
};

void compute_first_sets(const Grammar &grammar, unordered_map<char,set<char>>& firstSets);

int main(){
    // 初始化文法对象...
}

void compute_first_sets(const Grammar &grammar, unordered_map<char,set<char>>& firstSets) {
    bool changed = true;
    while(changed){
        changed=false;
        for(auto &[nonterm,rules]: grammar.productions){
            set<char> newFirsts;
            for(const auto& rule : rules){
                size_t i=0;
                do{
                    char symbol = rule[i];
                    if(islower(symbol)){ // 终结符处理逻辑简化表示
                        newFirsts.insert(symbol);
                        break;
                    }else{               // 对于非终结符查找已有first集合并考虑epsilon情况
                        for(auto elem:firstSets[symbol]){
                            if(elem!='\0')
                                newFirsts.insert(elem);
                        }
                        if(firstSets[symbol].find('\0')==firstSets[symbol].end())
                            break;
                    }
                }while(++i<rule.size());
                
                if(i==rule.size())       // 当前产生式全部由可选为空者构成
                    newFirsts.insert('\0');
            }

            if(newFirsts!=firstSets[nonterm]){ // 更新first集合并标记变更状态以便继续迭代直至稳定
                firstSets[nonterm]=newFirsts;
                changed=true;
            }
        }
    }
}

这段代码实现了对输入CFG（Context-Free Grammar）进行遍历，并通过固定点算法逐步填充每个非终结符关联的第一跟随项列表(`firstSets`)。这里采用了一个简单的do-while循环来模拟逐个检查产生式右侧符号的过程，同时利用了C++标准库中的容器类完成数据存储和操作[^2]。