编译器构造中自底向上的LALR(1)语法分析的语法分析表生成的实现

提示：阅读本文需掌握编译原理的相关基础知识

本文中使用C++语言系统地实现了龙书中LALR(1)语法分析表的构造算法,首先计算增广文法的LR(0)项集族，每一个项集只包含内核项，计算过程中自动生成了LR(0)自动机,该自动机使用基于十字链表存储结构的有向图表示。然后通过确定自发生成和传播的向前看符号算法计算各LR(0)内核项集自发生成的向前看符号(增广文法新增产生式的向前看符号不包括在内)并确定LR(0)内核项集之间向前看符号的传播关系。最后一遍扫描前将为增广文法新增产生式添加向前看符号即输入结束符$，然后传播向前看符号直到不能传播为止，扫描结束后就生成了LALR(1)内核项集族。随后调用函数计算各LALR(1)项集的非内核项集确定LALR(1)项集族，并得到LALR(1)自动机。最后根据LALR(1)自动机填写LALR(1)语法分析表完成语法分析表的生成工作。

程序测试用例为博主自行编写的正则表达式文法(文法部分地方写得较别扭，而且并非反映正则表达式全部特性的文法，对正反向预查的支持存在一些问题，请读者见谅)，由于文法保存在文本中，需要由计算机读入分析，为了便于计算机理解需要将书写格式标准化,博主自行设计了书写格式，具体如下：

#1b 非终结符 非终结符 ---- #1e （非终结符号集合）

#2b 终结符 终结符 —- #2e   （终结符号集合）

#3b 增广文法开始符号 原文法开始符号 #3e

#4b

#b 非终结符(产生式头) $1($2) 非终结符或终结符 $1($2) 非终结符或终结符 —- #e  (产生式体)   （$1标志非终结符，$2标志终结符，第一个产生式必须为增广产生式，第二个产生式必须为原文法以原文法开始符号为头的产生式）

---

#4e

其中省略号表示相同格式子项的重复出现，按照以上格式书写的文法(该文法修改了无数遍，说多了都是泪)为：

#1b S’ S preSurvey E T M F G outSquare B V C B’ inSquare inSquareRange #1e

#2b \ SPECTRANMETA POSITIVE-SURE-PRE POSITIVE-NEGA-PRE NEGATIVE-SURE-PRE NEGATIVE-NEGA-PRE ) | CLOSURE ? GIVEN LBOUND ULBOUND CLOSURE-NONGREEDY LBOUND-NONGREEDY ULBOUND-NONGREEDY CAP NONPRECAP SPECTRAN TRANMETA UPPERALPHA LOWERALPHA DIGIT SPECMETA REVERSEREF ^ [ ] - OTHERMETA $ #2e

#3b S’ S #3e

#4b

#b S’ $1 S #e

#b S $1 E #e

#b S $1 preSurvey #e

#b preSurvey $1 E $2 POSITIVE-SURE-PRE $1 E $2 ) #e

#b preSurvey $1 E $2 POSITIVE-NEGA-PRE $1 E $2 ) #e

#b preSurvey $2 NEGATIVE-SURE-PRE $1 E $2 ) $1 E #e

#b preSurvey $2 NEGATIVE-NEGA-PRE $1 E $2 ) $1 E #e

#b E $1 E $2 | $1 T #e

#b E $1 T #e

#b T $1 T $1 M #e

#b T $1 M #e

#b M $1 M $2 CLOSURE #e

#b M $1 M $2 ? #e

#b M $1 M $2 GIVEN #e

#b M $1 M $2 LBOUND #e

#b M $1 M $2 ULBOUND #e

#b M $1 M $2 CLOSURE-NONGREEDY #e

#b M $1 M $2 LBOUND-NONGREEDY #e

#b M $1 M $2 ULBOUND-NONGREEDY #e

#b M $1 F #e

#b F $2 CAP $1 E $2 ) #e

#b F $1 G #e

#b F $2 NONPRECAP $1 E $2 ) #e

#b F $1 outSquare #e

#b outSquare $2 SPECTRAN #e

#b outSquare $2 TRANMETA #e

#b outSquare $2 \ #e

#b outSquare $2 SPECTRANMETA #e

#b outSquare $2 UPPERALPHA #e

#b outSquare $2 LOWERALPHA #e

#b outSquare $2 DIGIT #e

#b outSquare $2 SPECMETA #e

#b outSquare $2 REVERSEREF #e

#b outSquare $2 ^ #e

#b G $2 [ $1 B $1 V $1 C $2 ] #e

#b V $2 ^ #e

#b V #e

#b B $1 B $1 B’ #e

#b B $1 B’ #e

#b B’ $1 V $1 inSquareRange $2 - $1 inSquareRange #e

#b inSquareRange $2 SPECTRAN #e

#b inSquareRange $2 SPECMETA #e

#b inSquareRange $2 OTHERMETA #e

#b inSquareRange $2 UPPERALPHA #e

#b inSquareRange $2 LOWERALPHA #e

#b inSquareRange $2 DIGIT #e

#b inSquareRange $2 CLOSURE #e

#b inSquareRange $2 \ #e

#b inSquareRange $2 SPECTRANMETA #e

#b inSquareRange $2 ? #e

#b inSquareRange $2 CAP #e

#b inSquareRange $2 | #e

#b inSquareRange $2 ) #e

#b C $1 C $1 inSquare #e

#b C $1 inSquare #e

#b inSquare $1 inSquareRange #e

#b inSquare $2 NONPRECAP #e

#b inSquare $2 POSITIVE-SURE-PRE #e

#b inSquare $2 POSITIVE-NEGA-PRE #e

#b inSquare $2 NEGATIVE-SURE-PRE #e

#b inSquare $2 NEGATIVE-NEGA-PRE #e

#b inSquare $2 ULBOUND #e

#b inSquare $2 LBOUND #e

#b inSquare $2 ULBOUND-NONGREEDY #e

#b inSquare $2 LBOUND-NONGREEDY #e

#b inSquare $2 CLOSURE-NONGREEDY #e

#b inSquare $2 GIVEN #e

#b G $2 [ $1 B $2 ] #e

#b G $2 [ $1 V $1 C $2 ] #e

#4e

#1b和#1e之间的部分为文法非终结符,#2b和#2e之间的部分为文法终结符,S’为增广文法开始符,S为原文法开始符

#4b和#4e之间的部分为产生式,紧跟于#b之后的是产生式头,随后为产生式体, $2表示紧跟其后的文法符号为终结符,$1表示紧跟其后的文法符号为非终结符，所有这些构成了对上下文无关文法的完整描述。这里非终结符、终结符以及产生式的含义博主会在将来发布的有关构建正则表达式引擎的文章中详解，现在只需着眼于文法本身，不必关心它们的具体含义。

需要另外说明的是，文法设计不当会导致一些异常现象的发生，例如如果把以上文法第三道产生式的产生式头的非终结符S改为F(这样就允许了预查表达式任意的自嵌套)，程序会在计算follow集时陷入死循环，原因是修改过的文法第6，7道产生式直接导致程序在计算出非终结符E的follow集前必须先计算出E的follow集，导致循环计算，这样计算follow集时会陷入死循环。可以验证，如果去掉产生式6、7程序就可以正常运行并输出结果(但是存在语法分析动作冲突)。

下面贴出代码

代码清单(C++):

见github 地址 https://github.com/naturerun/LALRAnalysisGenerator

注意，这里有两个头文件Priority_Queue.h和assistfunction.h。Priority_Queue.h存放的是博主自己实现的优先级队列类，之所以没有使用标准库提供的容器适配器是因为适配器实现的优先级队列缺少一些操作队列成员的必要方法，如以下代码中的begin(),end()且容器适配器提供的接口的调用约定和返回值不符号程序编写要求，此外优先级队列是用堆实现的，但计算LALR闭包的算法要求优先队列必须用数组实现，其成员按优先级从小到大排序，故楼主自行实现了优先级队列。Priority_Queue.h代码如下：

#include <iostream>
#include <list>
#include <functional>
using namespace std;

template <typename T>
class Priority_Queue    //设备等待队列类(优先级队列),队列数据元素为t
{
public:
    typedef typename list<T>::iterator iterator;
    Priority_Queue() = default;
    Priority_Queue(const function<bool(const T&,const T&)> &com) :comparator(com) {}
    ~Priority_Queue() = default;
    pair<bool, typename Priority_Queue<T>::iterator> Insert(const T &x);  //插入操作,返回的pair的first指示插入是否成功,second为指向插入元素的迭代器
    bool RemoveTop(T &x);     //删除最高优先级元素并用x将其返回
    bool GetTop(T &x) const;  //获取最高优先级元素并用x将其返回 
    void MakeEmpty() { Queue.clear(); }    //清空队列
    bool isEmpty() const { return Queue.empty(); }   //判断队列是否为空
    bool isFull() const { return Queue.size() == Queue.max_size(); }   //判断队列是否已满
    typename Priority_Queue<T>::iterator erase(const typename Priority_Queue<T>::iterator &p) { return Queue.erase(p); }  //删除队列中p所指元素返回被删元素的下一元素
    typename Priority_Queue<T>::iterator insert(const typename Priority_Queue<T>::iterator &p, const T &c) { return Queue.insert(p, c); }  //将c插入至p所指位置,返回指向插入元素的迭代器
    typename list<T>::size_type  GetSize() const { return Queue.size(); }   //获取队列实际大小
    iterator begin() { return Queue.begin(); }   //获取指向队列最高优先级元素的迭代器
    iterator end() { return Queue.end(); }   //获取队列尾后迭代器

private:
    function<bool(const T&, const T&)> comparator;  //比较T类型的可调用对象，左操作数小于右操作数返回true
    typename list<T>::iterator adjust();   //新元素加入队列后调整元素位置,使队列中各元素保持优先级关系
    list<T> Queue;
};

template <typename T>
typename list<T>::iterator Priority_Queue<T>::adjust()
{
    T temp = Queue.back();
    auto p = Queue.end();
    --p;
    p = Queue.erase(p);

    if (Queue.begin() != p)
        --p;
    else
    {
        return Queue.insert(p, temp);
    }

    while (true)
    {
        if (comparator(temp, (*p)))
        {
            if (p != Queue.begin())
            {
                --p;
                if (p == Queue.begin())
                    continue;
            }
        }
        else
        {
            ++p;
            return Queue.insert(p, temp);
        }

        if (p == Queue.begin())
            break;
    }
    return Queue.insert(p, temp);
}

template <typename T>
pair<bool, typename Priority_Queue<T>::iterator> Priority_Queue<T>::Insert(const T &x)
{
    if (isFull())
        return { false, end() };
    else
    {
        Queue.push_back(x);
        return { true, adjust() };
    }
}

template <typename T>
bool Priority_Queue<T>::RemoveTop(T &x)
{
    if (isEmpty())
        return false;
    else
    {
        x = Queue.front();
        Queue.pop_front();
        return true;
    }
}

template <typename T>
bool Priority_Queue<T>::GetTop(T &x) const
{
    if (isEmpty())
        return false;
    else
    {
        x = Queue.front();
        return true;
    }
}

头文件assistfunction.h中定义了一些算法需要使用的辅助例程(只有第一个函数和算法有关，其他例程用于正则表达式引擎，后续会解读)，由于代码简洁易懂，不是很重要，这里就不详细解说了。

#include<set>
#include<map>
#include<string>
void setToMap(const set<string> &source, map<string, int> &goal, int &count)
{
    for (set<string>::iterator p = source.cbegin(); p != source.cend(); ++p)
    {
        goal.insert(make_pair(*p, count++));
    }
}

char strToChar(const string &m)
{
    if (m.size() == 1)
        return m[0];
    else if (m.size() == 2)
    {
        switch (m[1])
        {
        case'f':    return '\f';
        case'n':    return '\n';
        case'r':    return '\r';
        case't':    return'\t';
        case'v':    return'\v';
        case'^':    return'^';
        case'-':    return'-';
        case'\\':    return'\\';
        case'*':    return'*';
        case'+':    return'+';
        case'?':    return'?';
        case'$':    return'$';
        case'.':    return'.';
        case'(':    return'(';
        case')':    return')';
        case':':    return':';
        case'=':    return'=';
        case'!':    return'!';
        case'<':    return'<';
        case'|':    return'|';
        case'[':    return'[';
        case']':    return']';
        case'{':    return'{';
        case'}':    return'}';
        }
    }
}

void insertIntoSet(map<size_t, set<size_t>> &beinserted, const size_t &source, const size_t &goal)
{
    map<size_t, set<size_t>>::iterator it = beinserted.find(goal);
    if (it == beinserted.end())
    {
        beinserted.insert(make_pair(goal, set<size_t>())).first->second.insert(source);
    }
    else
    {
        it->second.insert(source);
    }
}

void insertIntoMap(map<size_t, set<size_t>> &beinserted, map<size_t, map<size_t, set<size_t>>> &from)
{
    for (map<size_t, map<size_t, set<size_t>>>::iterator p = from.begin(); p != from.end(); ++p)
    {
        for (map<size_t, set<size_t>>::iterator q = p->second.begin(); q != p->second.end(); ++q)
        {
            map<size_t, set<size_t>>::iterator m = beinserted.find(q->first);
            if (m == beinserted.end())
            {
                beinserted.insert(make_pair(q->first, set<size_t>(q->second)));
            }
            else
            {
                m->second.insert(q->second.begin(), q->second.end());
            }
        }
    }
}

void insertIntoMap(map<size_t, map<size_t, map<size_t, size_t>>> &end, size_t substart, size_t subend, size_t sub_start_stackindex, size_t sub_end_stackindex)
{
    map<size_t, map<size_t, map<size_t, size_t>>>::iterator p = end.find(subend);
    if (p == end.end())
    {
        end.insert(make_pair(subend, map<size_t, map<size_t, size_t>>())).first->second.insert(make_pair(substart, map<size_t, size_t>())).first->second.insert(make_pair(sub_start_stackindex, sub_end_stackindex));
    }
    else
    {
        map<size_t, map<size_t, size_t>>::iterator q = p->second.find(substart);
        if (q == p->second.end())
        {
            p->second.insert(make_pair(substart, map<size_t, size_t>())).first->second.insert(make_pair(sub_start_stackindex, sub_end_stackindex));
        }
        else
        {
            q->second[sub_start_stackindex] = sub_end_stackindex;
        }
    }
}

程序的使用方法请参看main函数中的注释，分析结果会输出至指定文件，文件中加入了必要的逗号分隔符，将其扩展名改为csv用excel打开即可看到经整理的分析结果，如果文法不是LALR(1)的，程序运行时在命令行窗口上会打印语法分析动作冲突的相关信息。注意如果自定义文法进行测试文法需设计合理，避免存在逻辑错误，否则程序可能会陷入死循环或抛出异常。博主给出的示例文法可以得到分析结果且无语法分析冲突，可以把示例文法拷贝至输入文件中测试。

PS：本人微信号memoryundersun，欢迎各位同仁主动联系我，大家一起学习一起进步

2018.11.14重要更新

---

先前提到过改动文法会导致在计算follow集时陷入死循环,原因是循环依赖链造成的间接循环依赖，非终结符E的follow集依赖于另一个非终结符，另一个又依赖其他非终结符的follow集——这种依赖关系最终会延伸到E自身，造成E的follow集依赖于E的follow集的间接循环依赖。原先计算follow的算法不适用于间接循环依赖的情况，会陷入死循环，因而是错误的，所以简单调整一下follow集的计算算法，该算法中能够计算出follow集的非终结符最终会分离出去，剩下的是位于循环依赖链上的非终结符，此时对依赖链上的非终结符按照依赖关系反复迭代直到这些follow集的非终结符不再增大即可，最后把依赖链上非终结符follow集的计算结果加入已计算出follow集的非终结符表。分离出已计算出follow集的非终结符以避免对计算完成的非终结符的无效迭代，将非终结符依赖的其他非终结符从依赖关系中删去，并把被删去的非终结符的follow集的计算结果添加到被依赖非终结符的计算结果中以避免依赖非终结符对被依赖终结符的无效迭代。如果某一轮循环已完成follow集计算的非终结符构成的表不再增大，那么表中非终结符和尚未完成计算的非终结符依赖的非终结符集合交集始终为空集，故求交运算可以跳过，这些为必要的优化处理

修改过的follow集计算算法如下：(应该没有错误了，如果有请提出)

shared_ptr<map<string, set<string>>> LALRAutomata::calculateFollow()
{
    enum class GeneratingCycles {CURRENT_CYCLE, PREVIOUS_CYCLE};
    map<string, tuple<set<string>, set<string>, set<string>, bool>> temp;  //非终结符,当前follow，新增follow,依赖符号,是否计算完成
    map<string, pair<GeneratingCycles, map<string, tuple<set<string>, set<string>, set<string>, bool>>::iterator>> pre_and_cur_cycle_finish_follow_compute_info;  //非终结符 产生轮次 temp中对应项迭代器
    {
        auto h = temp.insert(make_pair(AugGraSS, tuple<set<string>, set<string>, set<string>, bool>())).first;
        get<0>(h->second).insert("$");
        get<1>(h->second).insert("$");
    }

    for (map<long, tuple<string, vector<ProductionBodySymbol>, set<string>>>::iterator p = productionSet.begin(); p != productionSet.end(); ++p)
    {
        for (vector<ProductionBodySymbol>::size_type i = 0; i < get<1>(p->second).size(); ++i)
        {
            if (get<1>(p->second)[i].TerminalOrNot == false)
            {
                if (i == get<1>(p->second).size() - 1)
                {
                    map<string, tuple<set<string>, set<string>, set<string>, bool>>::iterator it = temp.insert(make_pair(get<1>(p->second)[i].symbol, tuple<set<string>, set<string>, set<string>, bool>())).first;
                    get<2>(it->second).insert(get<0>(p->second));
                }
                else
                {
                    shared_ptr<set<string>> q = calculateFirst(get<1>(p->second), i + 1, get<1>(p->second).size() - 1);
                    map<string, tuple<set<string>, set<string>, set<string>, bool>>::iterator it = temp.insert(make_pair(get<1>(p->second)[i].symbol, tuple<set<string>, set<string>, set<string>, bool>())).first;
                    if (*(q->begin()) == "")
                    {
                        set<string>::iterator w = q->begin();
                        get<0>(it->second).insert(++w, q->end());
                        get<1>(it->second).insert(w, q->end());
                        get<2>(it->second).insert(get<0>(p->second));
                    }
                    else
                    {
                        get<0>(it->second).insert(q->begin(), q->end());
                        get<1>(it->second).insert(q->begin(), q->end());
                    }
                }
            }
        }
    }

    for (map<string, tuple<set<string>, set<string>, set<string>, bool>>::iterator p = temp.begin(); p != temp.end(); ++p)
    {
        if (get<2>(p->second).empty() == true)
        {
            get<3>(p->second) = true;
            pre_and_cur_cycle_finish_follow_compute_info.insert(make_pair(p->first, make_pair(GeneratingCycles::PREVIOUS_CYCLE, p)));
        }
        else
        {
            set<string>::iterator tempit;
            if ((tempit = get<2>(p->second).find(p->first)) != get<2>(p->second).end())
            {
                get<2>(p->second).erase(tempit);
                if (get<2>(p->second).empty() == true)
                {
                    get<3>(p->second) = true;
                    pre_and_cur_cycle_finish_follow_compute_info.insert(make_pair(p->first, make_pair(GeneratingCycles::PREVIOUS_CYCLE, p)));
                }
                else
                {
                    get<3>(p->second) = false;
                }
            }
            else
            {
                get<3>(p->second) = false;
            }
        }
    }

    bool first_set_has_changed = false;
    bool result_has_changed = false;
    bool result_has_changed_previous_run = true;
    bool is_first_cycle = true;
    while (true)
    {
        map<string, pair<GeneratingCycles, map<string, tuple<set<string>, set<string>, set<string>, bool>>::iterator>>::iterator n = pre_and_cur_cycle_finish_follow_compute_info.begin();
        for (map<string, tuple<set<string>, set<string>, set<string>, bool>>::iterator p = temp.begin(); p != temp.end(); ++p)
        {
            if (get<3>(p->second) == true)
            {
                if (pre_and_cur_cycle_finish_follow_compute_info.find(p->first) == pre_and_cur_cycle_finish_follow_compute_info.end())
                    get<1>(p->second).clear();
                continue;
            }

            if (is_first_cycle == false)
            {
                get<1>(p->second).clear();
            }

            set<string>::size_type size = get<0>(p->second).size();
            if (result_has_changed_previous_run)
            {
                map<string, pair<GeneratingCycles, map<string, tuple<set<string>, set<string>, set<string>, bool>>::iterator>>::iterator itleft = pre_and_cur_cycle_finish_follow_compute_info.begin();
                set<string>::iterator itright = get<2>(p->second).begin();
                while (itleft != pre_and_cur_cycle_finish_follow_compute_info.end() && itright != get<2>(p->second).end())
                {
                    if (itleft->first == *itright)
                    {
                        computeDifferenceSet(get<1>(itleft->second.second->second), get<0>(p->second), get<1>(p->second), false);
                        itright = get<2>(p->second).erase(itright);
                        ++itleft;
                    }
                    else if (itleft->first < *itright)
                    {
                        ++itleft;
                    }
                    else
                    {
                        ++itright;
                    }
                }
                if (get<2>(p->second).empty())
                {
                    pre_and_cur_cycle_finish_follow_compute_info.insert(make_pair(p->first, make_pair(GeneratingCycles::CURRENT_CYCLE, p)));
                    get<3>(p->second) = true;
                    result_has_changed = true;
                    continue;
                }
            }

            for (set<string>::iterator m = get<2>(p->second).begin(); m != get<2>(p->second).end(); ++m)
            {
                computeDifferenceSet(get<1>(temp[*m]), get<0>(p->second), get<1>(p->second), false);
            }

            if (get<0>(p->second).size() != size)
            {
                first_set_has_changed = true;
            }

            if (n != pre_and_cur_cycle_finish_follow_compute_info.end())
            {
                if (p->first == n->first)
                {
                    if (n->second.first == GeneratingCycles::CURRENT_CYCLE)
                    {
                        ++n;
                    }
                    else
                    {
                        n = pre_and_cur_cycle_finish_follow_compute_info.erase(n);
                    }
                }
            }
        }

        if (!first_set_has_changed && !result_has_changed)
        {
            break;
        }
        else
        {
            result_has_changed_previous_run = result_has_changed;
            first_set_has_changed = false;
            result_has_changed = false;
        }

        if (is_first_cycle)
            is_first_cycle = false;

        for (map<string, pair<GeneratingCycles, map<string, tuple<set<string>, set<string>, set<string>, bool>>::iterator>>::iterator temp = pre_and_cur_cycle_finish_follow_compute_info.begin(); temp != pre_and_cur_cycle_finish_follow_compute_info.end(); ++temp)
        {
            temp->second.first = GeneratingCycles::CURRENT_CYCLE;
        }
    }

    shared_ptr<map<string, set<string>>> result = make_shared<map<string, set<string>>>();
    for (map<string, tuple<set<string>, set<string>, set<string>, bool>>::iterator p = temp.begin(); p != temp.end(); ++p)
    {
        result->insert(make_pair(p->first, set<string>())).first->second.insert(get<0>(p->second).begin(), get<0>(p->second).end());
    }
    return result;
}

78-170行为迭代求解的核心步骤

主程序代码也进行了更新

2019.1.15更新

---

对LALR(1)自动机构造算法进行了优化，避免明显不等LALR项之间的冗余比较，提升生成性能

优化了LALR闭包生成算法，避免对相同非内核项点号右边符号串first集不必要的计算

2019.4.25更新

新增了firstK和followK集的生成算法，详见github readme文件

这个项目中Trie树的实现存在问题，有内存泄漏问题和删除的逻辑错误，但不影响程序的正确性，后续应该会修正

---

2021.12.14更新

重新修改了Trie树实现,修正了内存泄漏错误,并精简了代码