语法分析——自底向上语法分析中的SLR

SetOfItems SLR::CanonicalLR::closure(SetOfItems& set) {
    SLR::ContextFreeGrammar grammer = this->grammer;
    SetOfItems result(set);
    /// SLR::SetOfItems::items_iterator
    /// 循环当前项集，需要注意的是是result集合自己在发生变动，同时也是该集合在循环。也就是说如果有新的项被添加到集合内之后，还会继续查看这个新项的产生式情况
    for (SLR::items_iterator itr = result.begin(); itr != result.end(); ++itr)
    {
       Item item = *itr;
       /// 在书中我们知道项的表示方式是：数对
       /// item.id: 一个数表示当前项在产生式集合中和的下标（第几个具体的产生式）
       /// item.position: 另一个数是表示点号在产生式体中的下标
       SLR::Production production = grammer.productions[item.id]; /// 没有做越界保护
       vector<Symbol *>bodies = production.bodies;
       if (item.position >= bodies.size())
       { /// 说明此时点号在产生式的最右边，也就是说此时我们已经可以把产生式体归约为产生式头部了，无需继续添加
           continue;
       }
       Symbol* symbol = production.bodies[item.position];
       bool isTerminal = symbol->isTerminal();
       if (isTerminal)
       {
           continue;
       }
       /// 此时点号右边是非终结符，需要查看该非终结符是否有对应的产生式
       int id = symbol->identifier();
       vector<Production> productions = grammer.productions;
       bool contain_grammer = false;
       for (vector<Production>::iterator itr = productions.begin(); itr != productions.end(); ++itr)
       {
           int idx = itr-productions.begin();
           if ((itr->header).identifier() == id)
           {
                Item new_item(idx,0);
                result.push_back(new_item);
           }
       }
    }
    return result; 
}

SetOfItems SLR::CanonicalLR::lr_goto(SetOfItems& set, Symbol *symbol, int *offset) {
    int index = set.cacheForSymbol(symbol->identifier);
    if (index >= 0)
    {
        if (offset != nullptr)
        {
           *offset = index;
        }    
        return item_set[index];
    }
    
    ContextFreeGrammar grammer = this->grammer;
    SetOfItems result;
    for (SLR::items_iterator itr = set.begin(); itr != set.end(); ++itr) 
    {
        Item item = *itr;
        /// 在书中我们知道项的表示方式是：数对
        /// item.id: 一个数表示当前项在产生式集合中和的下标（第几个具体的产生式）
        /// item.position: 另一个数是表示点号在产生式体中的下标
        uint idx = item.id;
        if (idx >= grammer.productions.size())
        {
            return set; /// 异常
        }
        Production production = grammer.productions[idx];
        vector<Symbol *> bodies = production.bodies;
        if (item.position >= bodies.size())
        {
            continue; /// 点号在产生式的最右边；
        }
        Symbol *current_sym = bodies[item.position];
        if (current_sym->identifier() != symbol->identifier())
        {
            continue;
        }
        
        Item new_item(idx,item.position+1); /// 点号右移
        int index = contain_item(new_item);
        if (index >= 0)
        { /// 如果生成的item已经存在于某一个项集中，则返回当前项集
            return item_set[index];
        }
        /// 新生成的item并未存在，将该项放入新的项集中
        std::string key  = format("%d_%d",item.id,item.position);
        item_map.insert(make_pair(key, item_set.size()));
        result.push_back(new_item);
    }
    if (result.count() > 0)
    {
        if (offset)
        {
            *offset = item_set.size();
            item_set.push_back(result);
            set.setCache(*offset, symbol->identifier());
        }
    }
    return result;
}

void SLR::CanonicalLR::items() {
    /// 获取增广文法的初始化产生式，并构造初始的项集
    SetOfItems set;
    Item augmented_item(0,0);
    set.push_back(augmented_item);
    (this->item_set).push_back(set); /// 初始项集族
    /// 遍历每一个项集
    for (vector<SetOfItems>::iterator vitr = (this->item_set).begin(); vitr != (this->item_set).end(); ++vitr)
    {
        /// 遍历当前文法所有的符号
        for (vector<SLR::Symbol *>::iterator itr = grammer.symbols.begin(); itr != grammer.symbols.end() ++itr)
        {
            SetOfItems result = lr_goto(*vitr, *itr);
            int contain = contain_set(result);
            if (contain == -1)
            {
                item_set.push_back(result);
            }
        }
    }
}

SLR::LR_Action* SLR::CanonicalLR::action(SetOfItems& set, SLR::Symbol *symbol) {
    if (symbol->isTerminal() == false) /// 非终结符直接返回
    {
        return nullptr;
    }
    LR_Action *action = set.actionForSymbol(symbol->identifier());
    if (action != nullptr)
    {
        return action;
    }
    
    int offset = -1;
    SetOfItems result = lr_goto(set,symbol, &offset);
    if (result != set) /// 不同的两个状态，说明goto函数有效，此时应该做移入操作
    {
        action = new ShiftAction(offset);
        set.setActionForSymbol(symbol->identifier(), action);
        return action;
    }
    ContextFreeGrammar grammer = this->grammer;
    SetOfItems result;
    for (SLR::items_iterator itr = set.begin(); itr != set.end(); ++itr) 
    {
        Item item = *itr;
        /// 在书中我们知道项的表示方式是：数对
        /// item.id: 一个数表示当前项在产生式集合中和的下标（第几个具体的产生式）
        /// item.position: 另一个数是表示点号在产生式体中的下标
        uint idx = item.id;
        if (idx >= grammer.productions.size())
        {
            continue; /// 异常
        }
        Production production = grammer.productions[idx];
        vector<Symbol *> bodies = production.bodies;
        if (item.position != bodies.size())
        {
            continue; 
        }
        /// 点号在最左边，并且当前产生式为产生式集合中的第一个，即增广文法的产生式
        if (idx == 0)
        {
            action = new AcceptAction();
            set.setActionForSymbol(symbol->identifier(), action);
            return action;
        }
        
        /// 点号在产生式的最右边的一般情况
        vector<Symbol *> syms = grammer.FOLLOW(&(production.header));
        for (vector<Symbol *>::iterator itr = syms.begin(); itr != syms.end(); ++itr)
        {
            if (symbol -> identifier() == (*itr)->identifier()) 
            {
                action = new ReduceAction(&production);
                set.setActionForSymbol(symbol->identifier(), action);
                return action;
            }
        }
    }
    action = new ErrorAction();
    set.setActionForSymbol(symbol->identifier(), action);
    return action;
}

class CanonicalLR {
private:
    ContextFreeGrammar grammer;
    vector <SetOfItems> item_set;
    map<string,int> item_map; /// key: item.id+item.position; value: item_set index
public:
    SetOfItems closure(SetOfItems& set);
    SetOfItems lr_goto(SetOfItems& set, SLR::Symbol *symbol, int *offset);
    SLR::LR_Action* SLR::CanonicalLR::action(SetOfItems& set, SLR::Symbol *symbol);
    void items();
    int contain_set(SetOfItems& set); /// 不包含返回-1，包含返回非负数
    int contain_item(Item& item); /// 不包含返回-1，包含返回非负数
    friend class SLRAnalyser;
};
class SLRAnalyser {
    vector<Symbol *> inputTokens; /// 输入串
    stack<int> stack_;
    CanonicalLR lr;
public:
    /// 出现错误时，信息记录
    struct Error{
        Symbol *sym;
        stack<int> stck;
        Error(Symbol *s, stack<int>& sk):sym(s),stck(sk){}
        Error() {
            sym = nullptr;
        }
    };
private:
    Error error;
public:   
    SLRAnalyser() {
        stack_.push(0);
    }
    SLRAnalyser::Error slrError() { /// 当出现异常时，获取错误信息
        return error;
    }
    vector<Production> start() {
        vector<Production> result;
        int i = 0;
        Symbol *input_sym = inputTokens[i];
        while (1)
        {
            int idx = stack_.top();
            SetOfItems set = lr.item_set[idx];  
            LR_Action *action = lr.action(set, input_sym);
            if (action->isShiftAction()) /// 移入
            {
                ShiftAction *shift_action = dynamic_cast<ShiftAction *>(action);
                int dst = shift_action->opNum;
                stack_.push(dst);
                i++;
                input_sym = inputTokens[i];
            }
            else if (action->isReduceAction()) /// 归约
            {
                stack_.pop();
                ReduceAction *reduce_action = dynamic_cast<ReduceAction *>(action);
                Symbol *sym = &(reduce_action->production->header);
                SetOfItems c_set = lr.item_set[stack_.top()];
                int dst;
                lr.lr_goto(c_set, sym, &dst);
                stack_.push(dst);
                result.push_back(reduce_action->production);
            }
            else if (action->isAcceptAction()) /// 接受
            {
                error.sym = nullptr;
                stack<int> sk;
                error.stck = sk;
                break;
            }
            else /// 报错
            { 
                SLRAnalyser::Error err(input_sym, stack_);
                error = err;
                break;
            }
        }
        return result;
    }
};

objc-at-expression : '@' (string-literal | encode-literal | selector-literal | protocol-literal | object-literal)
                   ;
object-literal : ('+' | '-')? numeric-constant
               | character-constant
               | boolean-constant
               | array-literal
               | dictionary-literal
               ;
boolean-constant : '__objc_yes' | '__objc_no' | 'true' | 'false'  /* boolean keywords. */
                 ;
array-literal : '[' assignment-expression-list ']'
              ;
assignment-expression-list : assignment-expression (',' assignment-expression-list)?
                           | /* empty */
                           ;
dictionary-literal : '{' key-value-list '}'
                   ;
key-value-list : key-value-pair (',' key-value-list)?
               | /* empty */
               ;
key-value-pair : assignment-expression ':' assignment-expression
               ;