编译原理总结

2018年07月04日 225点热度 1人点赞 1条评论

简介

编译程序是计算机系统软件的最重要的组成部分之一,它能够把某一种语言(源语言程序)转换成另一种语言程序,且前者和后者在逻辑上是等价的,像我们常见的诸如C、Java、C++、Pascal等语言都得经过编译程序翻译成计算机所能识别的机器指令后才可以执行。

早期人们认为设计和实现编译程序是十分困难的事情,但经过科学家们40多年的努力,编译理论和技术已经得到迅速发展,现在已经形成了一套比较成熟且系统化的理论和方法,也开发出了许多方便有效的工具。

编译程序从输入源程序到输出目标程序之间通常要经历五个步骤:词法分析,语法分析、语义分析与中间代码生成、优化、目标代码生成。词法分析即对源程序的字符串进行扫描和分解以识别出其中的单词符;语法分析是在词法分析的基础上,根据语言的语法规则,把单词符号串分别成各类语法单位,如“短语”、“子句”和“程序段”等,语法规则通常用上下文无关文法来描述;语义分析和中间代码生成是根据语法分析所识别出的各类语法范畴,分析其含义并进行初步翻译并进行静态的语义检查;优化旨在对上一步生成的中间代码进行加工和变换以在后期生成高效的目标代码;目标代码生成即把优化过后的中间代码变换成在特定机器上的低级语言,这部分通常十分复杂,往往设计到硬件的操作。

上机作业着重实现了编译过程中的前两部分的功能,实现了如下功能:正则表达式转NFA、NFA转DFA、DFA转最小化DFA、Flex进行词法分析、消除文法中的左递归、根据产生式计算First集和Follow集、Yacc和Flex实现简易计算器、用递归下降法计算表达式的值、用符号优先法计算表达式的值、Bison和Flex实现逆波兰表达式计算器、Bison和Flex实现中缀表达式计算器。该实验算法除去使用Flex和Yacc之外,其余全部使用Kotlin语言进行开发,已在Github上开源,项目地址

正则表达式转NFA

正则式

对于字母表$\Sigma$的特殊字符集即为正规式,它的递归定义如下:

  1. $\varepsilon$和$\phi$都是$\Sigma$上的正规式,它们表示的正规集分别是${\varepsilon}$和$\phi$
  2. 任何$a\in\Sigma$,$a$是$\Sigma$上的一个正规式,它表示的正规集为$\{a\}$
  3. 假设$U$和$V$都是上的正规式,那么$(U|V)$、$(U\cdot V)$和$(U)^*$也是正规式

例如,令$\Sigma=\{a,b\}$,正规式$a(a|b)^*$表示$\Sigma$上所有以$a$为首的字母

非确定有穷自动机(NFA)

一个非确定有限自动机$M$是一个五元式$M=(S,\Sigma,\delta,S_0,F)$,其中$S$是一个有限集合,代表了元素的状态;$\Sigma$是一个有穷字母表;$\delta$是一个从$S \times \Sigma^*$到$S$的子集的映射,即$\delta:S \times \Sigma^* \rightarrow 2^S$;$S_0\subseteq S$是一个非空的初态集;$F\subseteq S$是一个终态集合。

Thompson构造法

对于任意一个正则表达式$regex$,首先将构成$regex$的元素进行分解,对于每个元素,按照以下方式分解:

对于$\varepsilon$

对于$a$

对于表达式$s|t$

对于表达式$st$

对于表达式$s^*$

代码

class NFA(private var regex: String) {
    companion object {
        const val MAX_NODE = 100
    }

    var finalState = BooleanArray(MAX_NODE)
    private var cntOfNode = 1
    private var endNode = TreeMap<Int, Int>()
    private var allNodes = ArrayList<Edge>()
    private var nfaGraph = arrayOfNulls<Vector<Pair>>(MAX_NODE)//NFA图
    var characterSet = TreeSet<Char>()

    private fun addEdge(u: Int, v: Int, ch: Char) {
        allNodes.add(Edge(u, v, ch))
        if (nfaGraph[u] == null)
            nfaGraph[u] = Vector()
        nfaGraph[u]!!.add(Pair(v, ch))
        if (ch != 'ε')
            characterSet.add(ch)
    }

    private fun kernelWay(fa: Int, ld: Int, rd: Int, isClosure: Boolean): Boolean {
        if (ld < 0 || rd >= regex.length) {
            println("Regex Error")
            return false
        }
        var preNode = fa
        var inBracket = 0
        for (i in ld..rd) {
            when {
                regex[i] == '(' -> inBracket++
                regex[i] == ')' -> inBracket--
                regex[i] == '|' && inBracket == 0 -> {
                    if (!kernelWay(fa, ld, i - 1, isClosure))
                        return false
                    if (!kernelWay(fa, i + 1, rd, isClosure))
                        return false
                    return true
                }
            }
        }
        var i = ld
        while (i <= rd) {
            if (regex[i] == '(') {
                var cntLeftBracket = 0
                var posRightBracket = -1
                val posLeftBracket = i
                for (j in i + 1..rd) {
                    if (regex[j] == '(')
                        cntLeftBracket++
                    else if(regex[j] == ')') {
                        if (cntLeftBracket == 0) {
                            posRightBracket = j
                            break
                        }
                        cntLeftBracket--
                    }
                }
                if (posRightBracket == -1) {
                    println("Regex Error")
                    return false
                }
                var nodeFather: Int
                if (posRightBracket + 1 <= rd && regex[posRightBracket + 1] == '*') {
                    i = posRightBracket + 1
                    addEdge(preNode, ++cntOfNode, 'ε')
                    preNode = cntOfNode
                    nodeFather = cntOfNode
                    addEdge(preNode, ++cntOfNode, 'ε')
                    preNode = cntOfNode
                    if (!kernelWay(nodeFather, posLeftBracket + 1, posRightBracket - 1, true))
                        return false
                } else {
                    nodeFather = preNode
                    if (!kernelWay(nodeFather, posLeftBracket + 1, posRightBracket - 1, false))
                        return false
                    i = posRightBracket
                }
            } else {
                if (regex[i] == ')')
                    continue
                if (i + 1 <= rd && regex[i + 1] == '*') {
                    addEdge(preNode, ++cntOfNode, 'ε')
                    preNode = cntOfNode
                    addEdge(preNode, preNode, regex[i])
                    if (i + 1 == rd && isClosure)
                        addEdge(preNode, fa, 'ε')
                    else {
                        if (endNode.containsKey(fa))
                            addEdge(preNode, endNode[fa]!!, 'ε')
                        else {
                            addEdge(preNode, ++cntOfNode, 'ε')
                            if (i == rd)
                                endNode[fa] = cntOfNode
                        }
                    }
                    preNode = cntOfNode
                    ++i
                } else {
                    if (i == rd && isClosure) {
                        addEdge(preNode, fa, regex[i])
                    } else {
                        if (endNode.containsKey(fa))
                            addEdge(preNode, endNode[fa]!!, regex[i])
                        else {
                            addEdge(preNode, ++cntOfNode, regex[i])
                            if (i == rd)
                                endNode[fa] = cntOfNode
                        }
                    }
                    preNode = cntOfNode
                }
            }
            i++
        }
        return true
    }

    private fun checkFinalState() {
        for (i in 1..cntOfNode) {
            var cc = 0
            if (nfaGraph[i] == null) {
                finalState[i] = true
                continue
            }
            for (j in nfaGraph[i]!!.indices)
                if (nfaGraph[i]!!.elementAt(j).v != i)
                    ++cc
            if (cc == 0)
                finalState[i] = true
        }
    }

    fun getNFAGraphics(): Array<Vector<Pair>?>? {
        if (kernelWay(1, 0, regex.length - 1, false)) {
            checkFinalState()
            return nfaGraph
        }
        return null
    }

    fun outputNFA() {
        if (kernelWay(1, 0, regex.length - 1, false)) {
            checkFinalState()
            allNodes.sortWith(Comparator { o1, o2 ->
                if (o1.u == o2.u)
                    o1.v - o2.v
                else
                    o1.u - o2.u
            })
            for (e in allNodes)
                println(e)
        }
    }
}

NFA转DFA

确定有穷自动机

一个有穷自动机$M$也是一个五元式$M=(S,\Sigma,\delta,s_0,F)$,其中$S$是一个有限集,它的每一个元素为一个状态;$\Sigma$是一个有穷字母表;$\delta$是一个从$S\times \Sigma$至$S$的单值部分映射,$\delta(s,a)=s'$意味着:当现行状态为$s$,输入字符为$a$时,将转换到下一个状态$s'$,我们称$s'$为$s$的一个后继状态;$s_o\in S$是唯一的初态;$F\subseteq S$是一个终态集(可空)。
显然,DFA是NFA的特例,即对于每一个NFA $M$都存在一个DFA $M''$,使得$L(M)=L(M'')$,证明如下:

  1. 首先引进新的初态结点$X$和终结结点$Y$,其中$X,Y\notin S$,从到的任意状态结点引进一条$\varepsilon$弧,从$F$中任意状态结点连一条弧$\varepsilon$到$Y$
  2. 对NFA $M$进行变化,重复如下分裂过程直到状态图中的每条弧都被标记为$\varepsilon$或为$\Sigma$中的单个字符,将最终得到的NFA记作$M'$,其中$L(M)=L(M'')$

子集构造法

  1. 假设$I$是$M'$的状态集的子集,定义$I$的$\varepsilon$闭包$\varepsilon\_CLOSURE(I)$为:
    1. 若$q\in I$,则$q\in \varepsilon\_CLOSURE(I)$
    2. 若$q\in I$,那么从$q$出发经过任意条$\varepsilon$弧所能到状态$q'\in \varepsilon\_CLOSURE(I)$
  2. 假设$I$是$M'$的状态集的子集,$a\in\Sigma$,那么定义:$I_a=\varepsilon\_CLOSURE(J)$,$J$是那些可从中的某一状态结点出发经过一条$a$弧而到达的状态结点的全体
  3. 假设$\Sigma=\{a_1,\cdots,a_k\}$,构造一张表,表的每行含有$k+1$项,令表的首行首列为$\varepsilon\_CLOSURE(X)$。通常来说,若某行的第一列的状态子集已经确定,我们假设记作$I$,那么置该行的$i+1$列为$I_{a_i}(i=1,\cdots,k)$,然后检查该行所有的状态子集,若未在表的第一列中出现过,则加入到后面空行的第一列,重复上述过程直到没有新的集合被加到表的第一列中, 由于$M'$状态的子集个数是有限的,所以该过程一定能在有限步内结束。

假设正规式为$(a|b)^*(aa|bb)(a|b)^*$,则其对应的NFA如下:

其根据子子集构法所构造出来的状态矩阵如下:

$I$ $I_a$ $I_b$
$\{X,5,1\}$ $\{5,3,1\}$ $\{5,4,1\}$
$\{5,3,1\}$ $\{5,3,1,2,6,Y\}$ $\{5,4,1\}$
$\{5,4,1\}$ $\{5,3,1\}$ $\{5,4,1,2,6,Y\}$
$\{5,3,1,2,6,Y\}$ $\{5,3,1,2,6,Y\}$ $\{5,4,1,6,Y\}$
$\{5,4,1,6,Y\}$ $\{5,3,1,6,Y\}$ $\{5,4,1,2,6,Y\}$
$\{5,4,1,2,6,Y\}$ $\{5,3,1,6,Y\}$ $\{5,4,1,2,6,Y\}$
$\{5,3,1,6,Y\}$ $\{5,3,1,2,6,Y\}$ $\{5,4,1,6,Y\}$

代码

class DFA(private var nfaGraph: Array<Vector<Pair>?>?, var characterSet: Set<Char>, private var finalState: BooleanArray) {
    var dfaNode = 0
    var newFinalState = BooleanArray(NFA.MAX_NODE)
    private var edgeSet = HashSet<Edge>()
    private var st: MyHashSet = MyHashSet()
    private var queue = LinkedList<MyHashSet>()
    private var sst = HashSet<MyHashSet>()
    var allNodes = ArrayList<Edge>()

    private fun dfs(u: Int, ch: Char) {
        nfaGraph?.get(u)?.let {
            for (i in it.indices) {
                val pair = it.elementAt(i)
                val edge = Edge(u, pair.v, pair.ch)
                if (!edgeSet.contains(edge) && pair.ch == ch) {
                    edgeSet.add(edge)
                    st.add(pair.v)
                    dfs(pair.v, 'ε')
                }
            }
        }
    }

    private fun checkIsFinalState(st: Set<Int>, state: Int) {
        for (item in st) {
            if (finalState[item])
                newFinalState[state] = true
        }
    }

    private fun initFirstSet() {
        edgeSet.clear()
        st = MyHashSet()
        st.add(1)
        st.state = ++dfaNode
        dfs(1, 'ε')
        checkIsFinalState(st, dfaNode)
        sst.add(st)
        queue.add(st)
    }

    private fun addEdge(u: Int, v: Int, ch: Char) {
        allNodes.add(Edge(u, v, ch))
    }

    fun toStateMatrix() {
        initFirstSet()
        while (!queue.isEmpty()) {
           val mySet = queue.poll()
            for (ch in characterSet) {
                st = MyHashSet()
                for (i in mySet) {
                    edgeSet.clear()
                    dfs(i, ch)
                }
                if (st.size > 0) {
                    if (!sst.contains(st)) {
                        sst.add(st)
                        queue.add(st)
                        st.state = ++dfaNode
                        checkIsFinalState(st, dfaNode)
                    } else {
                        for (item in sst) {
                            if (item == st) {
                                st = item
                                break
                            }
                        }
                    }
                    addEdge(mySet.state, st.state, ch)
                }
            }
        }
    }

    fun outputDFA() {
        toStateMatrix()
        allNodes.sortWith(Comparator { o1, o2 ->
            if (o1.u == o2.u)
                o1.v - o2.v
            else
                o1.u - o2.u
        })
        for (edge in allNodes) {
            println(edge)
        }
    }
}

最小化DFA

一个确定有限自动机$M$的化简是指寻找一个状态数比$M$少的DFA $M'$,使得L(M)=L(M')。假设$s$和$t$是的两个不同状态,我们称$s$和$t$是等价的,若从$s$出发读出某个字$w$而停于某个终态,那么同样,从$t$出发也能读出同样的字而停于终态。

将一个DFA $M$的状态最小化的过程旨在将的状态集划分成一些不可相交的子集,使得任何不同的两个子集中的状态都是可以区别的,而同一子集中的任何两个状态都是等价的,最后在每个子集中选出代表,消去它们的等价状态即可。

对$M$的状态$S$集划分的主要步骤:首先把$S$的终态和非终态分开,分成两个子集,形成基本划分$\Pi$。显然,属于这两个不同子集的状态是可区分的,假设当前$\Pi$已含有$m$个子集,记作$\Pi=\{I^{(1)},I^{(2)},\cdots,I^{(m)}\}$,并且属于不同子集的状态是可区别的,此时进一步检查中的每个是否可以进一步划分。若对于某个$I^{(i)}$,令$I^{(1)}=\{q_1, q_2,\cdots,q_k\}$,若存在一个输入字符$a$使得$I_a^{(i)}$不全包含在现行$\Pi$的某一子集$I^{(j)}$中,就将$I^{(i)}$一分为2,假定状态$s_1$和$s_2$经弧$a$分别到达状态$t_1$和$t_2$,而$t_1$和$t_2$属于现行的两个不同子集,那么就将$I^{(i)}$分成两半,一半含有$s_1$,另一半含有$s_2$。由于$t_1$和$t_2$的状态是可区别的,即存在一个字$w$,$t_1$将读出$w$而停于终态,而$t_2$或读不出$w$或虽然可读出$w$但不到达终态,因此字$w$能将状态$s_1$和$s_2$区分开来。

一般地,若$I_a^{(i)}$落入现行$\Pi$中$N$个不同子集,则应将$I^{(i)}$划分成$N$个不相交的组,使得每个组$J$的$J_a$都落入$\Pi$的同一子集中。重复上述过程,直到分划中所含的子集数不再增长为止。
经过上述的划分以后,对于这个的每一个子集,我们选取子集中的一个状态代表其他状态,例如,假定$I=\{q_1,\cdots,q_k\}$是这样的一个子集,我们即可挑选$q_1$代表这个子集,在原来的自动机中,凡导入到$q_2,\cdots,q_k$的弧都改成导入到$q_1$,然后$q_2,\cdots,q_k$将从原来的状态集$S$中删除,若$I$中含有原来的初态,则$q_1$是新的初态;若$I$是终态,则$q_1$是新终态。可以容易的证明,经如此化简后的DFA $M'$和原来的是等价的,即$L(M)=L(M')$。

对于正则式:$(a|b)^*(aa|bb)(a|b)^*$,若采用子集法对其NFA转换成DFA后,根据得到上一节中的状态转换矩阵,如果将其中的状态子集重新命名后,即可得到如下的状态转转换矩阵:

$s$ $a$ $b$
$0$ $1$ $2$
$1$ $3$ $2$
$2$ $1$ $5$
$3$ $3$ $4$
$4$ $6$ $5$
$5$ $6$ $5$
$6$ $3$ $4$

根据该状态矩阵所得到的未化简的DFA如下:

最小化后的DFA结果如下:

代码

class MinimumDFA(private var newFinalState: BooleanArray, private var allNodes: ArrayList<Edge>, private var dfaNode: Int, private var characterSet: Set<Char>) {
    private var setList = ArrayList<Set<Int>>()

    private fun init() {
        val finalStateSet = HashSet<Int>()
        val noFinalStateSet = HashSet<Int>()
        for (i in 1..dfaNode) {
            if (newFinalState[i])
                finalStateSet.add(i)
            else
                noFinalStateSet.add(i)
        }
        setList.add(finalStateSet)
        setList.add(noFinalStateSet)
    }
    private fun toMinimumDFA() {
        init()
        var flag = true
        while (flag) {
            flag = false
            case@
            for (k in setList.indices) {
                val st = setList[k]
                if (st.size <= 1)
                    continue
                for (ch in characterSet) {
                    val mp = HashMap<Int, Int>()
                    for (i in allNodes.indices) {
                        val edge = allNodes[i]
                        if (edge.key == ch && st.contains(edge.u))
                            mp[edge.u] = edge.v
                    }
                    for (i in st) {
                        if (!mp.containsKey(i))
                            mp[i] = -1
                    }
                    val firstSet = HashSet<Int>()
                    val secondSet = HashSet<Int>()
                    for (j in setList.indices) {
                        firstSet.clear()
                        secondSet.clear()
                        val tempSet = setList[k]
                        for ((key, value) in mp) {
                            if (tempSet.contains(value))
                                firstSet.add(key)
                            else
                                secondSet.add(key)
                        }
                        if (firstSet.size != 0 && secondSet.size != 0) {
                            flag = true
                            for (i in tempSet) {
                                if (!firstSet.contains(i) && !secondSet.contains(i))
                                    firstSet.add(i)
                            }
                            setList.removeAt(k)
                            setList.add(firstSet)
                            setList.add(secondSet)
                            break@case
                        }
                    }
                }
            }
        }
        for (k in setList.indices) {
            val st = setList[k]
            if (st.size > 1) {
                val first = st.first()
                val tempList = ArrayList<Edge>()
                var i = 0
                while (i < allNodes.size) {
                    val edge = allNodes[i]
                    if(st.contains(edge.u) && edge.u != first) {
                        allNodes.removeAt(i)
                        i--
                    } else if (st.contains(edge.v) && edge.v != first) {
                        allNodes.removeAt(i)
                        i--
                        tempList.add(Edge(edge.u, first, edge.key))
                    }
                    i++
                }
                allNodes.addAll(tempList)
            }
        }
    }
    fun outputMinimumDFA() {
        toMinimumDFA()
        allNodes.sortWith(Comparator { o1, o2 ->
            if (o1.u == o2.u)
                o1.v - o2.v
            else
                o1.u - o2.u
        })
        for (item in allNodes)
            println(item)
    }
}
fun main(args: Array<String>) {
    val regexList = ArrayList<String>()
    regexList.add("0*(100*)*0*")
    regexList.add("1(1010*|1(010)*1)*0")
    regexList.add("1(0|1)*101")
    regexList.add("0*1*(010)0*1*")
    for (regex in regexList) {
        val nfa = NFA(regex)
        val dfa = DFA(nfa.getNFAGraphics(), nfa.characterSet, nfa.finalState)
        dfa.toStateMatrix()
        val minimumDFA = MinimumDFA(dfa.newFinalState, dfa.allNodes, dfa.dfaNode, dfa.characterSet)
        println(regex)
        println("对应的最小化DFA如下:")
        minimumDFA.outputMinimumDFA()
        println()
    }
}

Lex实现词法分析器

Lex是Lexical Compiler的缩写,是Unix环境下十分著名的工具,它的主要功能是根据Lex语言生成一个对应的词法分析器的C源码。通常来说,Lex源程序包括两部分:正规式定义和识别规则。若$\Sigma$是一个字母表,则$\Sigma$上的正规定义式通常是如下形式:$d_i\rightarrow r_i$,例如用来描述标识符集合:

  • $letter\rightarrow A|B|..|Z|..|a|b|..|z|$
  • $digit\rightarrow 0|1|..|9|$
  • $identifier\rightarrow letter(letter|digit)^*$

识别规则是一串如下形式的Lex语句:$P_m\quad\quad\quad\{A_m\}$

其中$P_i$是一个正规式,称为词形,$P_i$中除了出现$\Sigma$中的字符外,还可以出现正规式左部所定义的任何简名$d_i$。即$d_i$是$\Sigma\cup\{d_1,\cdots,d_n\}$上的一个正规式。由于每个$d_i$最终都可以化成纯粹$\Sigma$上的正规式,因此,每个$P_i$也同样如此。如果每个$A_i$是一小段程序代码,它指出了,在识别出词型为$P_i$的单词之后,词法分析器应该采取的动作,这些识别规则完全决定了词法分析器L的功能。

由Lex形成的词法分析器L的工作流程:逐一扫描输入串中的字符,寻找一个最长的字串匹配到某个$P_i$,将该字串截取下来放到TOKEN缓冲区中,然后L调用动作子程序$A_i$,当$A_i$执行完以后,L就把所得的单词符号(种别编码和属性值)交给语法分析器,接着识别下一个单词符号。

可能存在这样的情况,即输入串无法与任何$P_i$匹配,这种情况应该进行特殊的错误处理,也可能存在一个输入串匹配多个$P_i$的情况,这种二义性的情况,以Lex中出现在最前面的那个$P_i$为准。

左递归的消除

自上而下分析

自上而下分析法就是从文法的开始符号出发,向下推导出句子的过程,一般来说,自上而下的分析法可能是带“回溯”的。对于任何输入串,从文法的开始符号(根结点)出发,自上而下地为输入串建立一棵语法树,或者说为输入串寻找一个最左推导。

实现自上而下的带回溯试探法的一种简单途径是让每个非终结符对应一个递归子程序,一旦发现某个候选式和输入串匹配,就用这个候选式去扩展语法树。

然而,这种自上而下分析法存在许多困难和缺点,如果一个文法含有左递归,即存在这样的产生式$P\overset{+}{\Longrightarrow}P\alpha$,会在分析过程中陷入无线的循环,因此,自上而下分析法必须消除文法的左递归性。

消除左递归

直接消除产生式中的左递归还是比较容易的,假设有如下产生式:

$$ P\rightarrow P\alpha|\beta$$

其中$\beta$不以$P$开头,我们可以把的规则改写成如下的形式:

$$P\rightarrow \beta P' \\ P'\rightarrow \alpha P'|\varepsilon$$

这种形式的文法和原来的形式是等价的,即从$P$推出的符号串是相同的。一般而言,假设关于的全部产生式是:

$$P\rightarrow P\alpha_1|P\alpha_2|\cdots|P\alpha_m|\beta_1|\beta_2|\cdots|\beta_n$$

那么消除消除左递归后的形式为:

$$P\rightarrow \beta_1P'|\beta_2P|\cdots|\beta_nP' \\ P'\rightarrow \alpha_1P'|\alpha_2P|\cdots|\alpha_mP'|\varepsilon$$

通常来说,用上述方法可以把表面的的直接左递归给删除,但这并不意味着已经消除了所有的左递归,例如下列文法:

$$S\rightarrow Qc|c \\ Q\rightarrow Rb|b \\ R\rightarrow Sa|a$$

虽然不存在直接的左递归,但是S、Q、R都是左递归的,例如有:

$$S\Rightarrow Rc \Rightarrow Rbc \Rightarrow Sabc$$

因此,消除一个隐式的左递归并不是一件容易的事,若一个文法不含回路(形如$P\overset{+}{\Longrightarrow}P$的推导),也不含以为右部的产生式,那么,执行下述算法可以保证消除左递归。

消除左递归算法

把文法G的所有非终结负按任一种顺序排列成$P_1,P_2,\cdots,P_n$,按此顺序执行如下步骤:

  • For i: = 1 To n Do
    • For j: = 1 To i-1 Do
      • 把形如$P_i\rightarrow P_j\gamma$的规则改写成
      • $P_i\rightarrow\delta_1\gamma|\delta_2\gamma|\cdots|\delta_k\gamma$
      • 其中$P_j\rightarrow \delta_1|\delta_2|\cdots|\delta_k$是关于$P_j$的所有规则
    • 消除关于$P_i$的直接左递归

例如对于上述文法,令非终结符排序为R、Q、S,把R带入到Q的候选式中,可以把Q的规则变为:$Q\rightarrow Sab|ab|b$

现在的Q同样不含直接左递归,把它带入到S的有关候选式后,S变成:$S\rightarrow Sab|abc|bc|c$

然后对S消除左递归,得到的文法为:

$$S\rightarrow abcS'|bcS'|cS' \\ S'\rightarrow abcS'|\varepsilon \\ Q\rightarrow Sab|ab|b \\ R\rightarrow Sa|a$$

显然,其中关于Q和R的文法规则已经是多余的,将它们删去即可。

代码

class Production(private var productions: ArrayList<Grammar>) {
    private val symbols = ArrayList<Char>()
    private val nonTerminatingSymbol = TreeSet<String>()
    private val terminatingSymbol = TreeSet<String>()

    init {
        symbolProductions()
    }

    fun removeLeftRecursion() {
        for (i in symbols.indices) {
            for (j in 0 until i) {
                iterativeReplacement(symbols[i], symbols[j])
            }
            removeLeftRecursion(symbols[i])
        }
        noOrIsTerminatingSymbol()
        output()
    }

    private fun symbolProductions() {
        if (productions.size != 0) {
            for (i in productions.indices) {
                if (!symbols.contains(productions[i].left[0])) {
                    symbols.add(productions[i].left[0])
                }
            }
        }
    }

    private fun noOrIsTerminatingSymbol() {
        for (i in productions.indices) {
            if (!nonTerminatingSymbol.contains(productions[i].left)) {
                nonTerminatingSymbol.add(productions[i].left)
            }
            if (productions[i].left == "${productions[i].left[0]}'") {
                nonTerminatingSymbol.add(productions[i].left)
            }
        }
        for (i in productions.indices) {
            var temp = productions[i].right
            temp = temp.replace("ε", "#")
            for (item in nonTerminatingSymbol) {
                temp = temp.replace(item.toRegex(), "")
            }
            temp = temp.replace("\\|".toRegex(), "")
            temp = temp.replace("'".toRegex(), "")
            val chars = temp.toCharArray()
            for (k in chars.indices) {
                if (chars[k] == '#') {
                    if (!terminatingSymbol.contains("ε")) {
                        terminatingSymbol.add("ε")
                    }
                } else {
                    if (!terminatingSymbol.contains(chars[k].toString())) {
                        terminatingSymbol.add(chars[k].toString())
                    }
                }
            }
        }
    }

    private fun iterativeReplacement(left: Char, right: Char) {
        for (item1 in productions) {
            var inRight = ""
            if (item1.left == left.toString()) {
                var isReplacement = false
                val rights1 = item1.right.split("\\|".toRegex()).dropLastWhile({ it.isEmpty() }).toTypedArray()
                for (i in rights1.indices) {
                    if (rights1[i].startsWith(right.toString())) {
                        isReplacement = true
                    }
                }
                if (isReplacement) {
                    for (item2 in productions) {
                        if (item2.left == right.toString()) {
                            val rights2 = item2.right.split("\\|".toRegex()).dropLastWhile({ it.isEmpty() }).toTypedArray()
                            for (i in rights1.indices) {
                                var isCheck = false
                                if (rights1[i].startsWith(right.toString())) {
                                    isCheck = true
                                    for (j in rights2.indices) {
                                        val temp = rights1[i]
                                        inRight += temp.replaceFirst(right.toString().toRegex(), rights2[j]) + "|"
                                    }
                                }
                                if (!isCheck) {
                                    inRight += rights1[i] + "|"
                                }
                            }
                        }
                    }
                    if (inRight.isNotEmpty()) {
                        productions.removeAt(productions.lastIndex)
                        productions.add(Grammar(left.toString(), inRight.substring(0, inRight.length - 1)))
                    }
                }
            }
        }
    }

    private fun removeLeftRecursion(left: Char) {
        for (index in productions.indices) {
            val grammar = productions[index]
            if (grammar.left == left.toString()) {
                val rights = grammar.right.split("\\|".toRegex()).dropLastWhile({ it.isEmpty() }).toTypedArray()
                var isLeftRecursion = false
                for (i in rights.indices) {
                    if (rights[i].startsWith(left.toString())) {
                        isLeftRecursion = true
                    }
                }
                if (isLeftRecursion) {
                    productions.removeAt(index)
                    var oneRight = ""
                    var twoRight = ""
                    for (i in rights.indices) {
                        if (!rights[i].startsWith(left.toString())) {
                            oneRight += rights[i] + (left.toString() + "'") + "|"
                        } else {
                            twoRight += rights[i].replaceFirst(left.toString().toRegex(), "") + (left.toString() + "'") + "|"
                        }
                    }
                    productions.add(Grammar(left.toString(), oneRight.substring(0, oneRight.length - 1)))
                    productions.add(Grammar(left.toString() + "'", "${twoRight}ε"))
                }
            }
        }
    }
    private fun output() {
        println("非终结符: $nonTerminatingSymbol")
        println("终结符: $terminatingSymbol")
        println("消除左递归后的文法:")
        for (item in productions) {
            println(item)
        }
    }
}

First集和Follow集

First集

我们定义$FIRST(X)$:可以从$X$推导出的所有串首终结符的集合。

若$X\overset{*}{\Longrightarrow}\varepsilon$,那么$\varepsilon \in FIRST(X)$

算法:

  • 不断应用下列规则,直到没有新的终结符或者$\varepsilon$可以被加入到任何$FIRST$集合中为止
  • 如果$X$是一个终结符,那么$FIRST=\{X\}$
  • 如果$X$是一个非终结符,且$X\rightarrow Y_1\cdots Y_k(k\geq 1)$,那么如果对于某个$i$,$a$在$FIRST(Y_i)$中且$\varepsilon$在左右的$FIRST(Y_1),\cdots,FIRSY(Y_{i-1})$中(即$Y_1\cdots Y_{i-1}\overset{*}{\Longrightarrow}\varepsilon$),就把$a$加入到$FIRST(X)$中,如果对于所有的$j=1,2,\cdots,k$,$\varepsilon$在$FIRST(Y_j)$中,那么将$\varepsilon$加入到$FIRST(X)$
  • 如果$X\rightarrow \varepsilon \in P$,那么将$\varepsilon$加入到$FIRST(X)
    $中

Follow集

我们定义$FOLLOW(X)$:可能在某个句型中紧跟在后面的终结符$a$的集合$FOLLOW(X)=\{a|S\overset{*}{\Longrightarrow}\alpha Aa\beta,a\in V_T,\alpha,\beta \in (V_T\cup V_N)^{*}\}$

如果$X$是某个句型的最右符号,则将结束符#添加到$FOLLOW(X)$中

算法:

  • 不断应用下列规则,直到没有新的终结符可以被加入到任何$FOLLOW$集合中为止
  • 将#放入$FOLLOW(S)$中,其中$S$是开始符号,#是输入右端的结束标记
  • 如果存在一个产生式$A\rightarrow \alpha B \beta$,那么$FIRST(\beta)$中除$\varepsilon$之外的所有符号都在$FOLLOW(B)$
  • 如果存在一个产生式$A\rightarrow \alpha B$或存在产生式$A\rightarrow \alpha B \beta$且$FIRST(\beta)$包含$\varepsilon$,那么$FOLLOW(A)$中的所有符号都在$FOLLOW(B)$中

代码

class First(private var mp: Map<String, Array<String>>) {
    var first = TreeMap<String, Set<Char>>()

    private fun findFirst(currentNode: String, rightNodes: Array<String>) : Set<Char>{
        if (first.containsKey(currentNode))
            return first[currentNode]!!
        val st = TreeSet<Char>()
        for (i in rightNodes.indices) {
            var j = 0
            while (j < rightNodes[i].length) {
                var nextNode = "${rightNodes[i][j]}"
                if (!mp.containsKey(nextNode)) {
                    st.add(nextNode[0])
                    break
                } else {
                    if (j + 1 < rightNodes[i].length && rightNodes[i][j + 1] == '\'') {
                        nextNode += rightNodes[i][j + 1]
                        ++j
                    }
                    if (mp.containsKey(nextNode)) {
                        val tempSet = findFirst(nextNode, mp[nextNode]!!)
                        st.addAll(tempSet)
                        if (!tempSet.contains('ε'))
                            break
                    }
                }
                ++j
            }
        }
        first[currentNode] = st
        return st
    }

    fun firstKernealCode() : String {
        var content = ""
        for (leftNode in mp.keys) {
            val rightNode = mp[leftNode]
            findFirst(leftNode, rightNode!!)
        }
        println("First集如下:")
        for ((key, value) in first) {
            content += "$key : $value"
            println("$key : $value")
        }
        return content
    }
}
class Follow(private var mp: Map<String, Array<String>>, private var first: Map<String, Set<Char>>) {
    private val follow = TreeMap<String, TreeSet<Char>>()

    private fun getFirstSet(st: MutableSet<Char>, node: String, temp: Int) {
        var k = temp
        if (k >= node.length) return
        if (node[k] == '\'') --k
        var nextNode = "" + node[k]
        if (k + 1 < node.length && node[k + 1] == '\'') {
            nextNode += '\''
            ++k
        }
        if (!mp.containsKey(nextNode)) {//终结点
            st.add(nextNode[0])
        } else {
            st.addAll(first[nextNode]!!)
            if (first[nextNode]!!.contains('ε'))
                getFirstSet(st, node, k + 1)
        }
    }

    private fun findFollow(currentNode: String) {
        var st: TreeSet<Char>?
        for (leftNode in mp.keys) {
            val rightNodes = mp[leftNode]
            for (i in rightNodes!!.indices) {
                var index = rightNodes[i].indexOf(currentNode, 0)
                while (index != -1) {
                    val nextIndex = index + 1
                    if (currentNode.length == 1 && index + 1 < rightNodes[i].length && rightNodes[i][index + 1] == '\'') {
                        index = rightNodes[i].indexOf(currentNode, nextIndex)
                        continue
                    }
                    index += currentNode.length
                    if (index == rightNodes[i].length) {
                        if (follow[leftNode] == null)
                            findFollow(leftNode)
                        if (follow[currentNode] == null) {
                            st = TreeSet()
                            st.addAll(follow[leftNode]!!)
                            follow[currentNode] = st
                        } else
                            follow[currentNode]!!.addAll(follow[leftNode]!!)
                    } else {
                        var nextNode = "" + rightNodes[i][index]
                        if (index + 1 < rightNodes[i].length && rightNodes[i][index + 1] == '\'') {
                            nextNode += '\''.toString()
                            ++index
                        }
                        if (mp.containsKey(nextNode)) {
                            if (first[nextNode]!!.contains('ε')) {
                                if (follow[leftNode] == null)
                                    findFollow(leftNode)
                                if (follow[currentNode] == null) {
                                    st = TreeSet()
                                    st.addAll(follow[leftNode]!!)
                                    follow[currentNode] = st
                                } else
                                    follow[currentNode]!!.addAll(follow[leftNode]!!)
                            }

                            run {
                                val tempSet = TreeSet<Char>()
                                getFirstSet(tempSet, rightNodes[i], index)
                                tempSet.remove('ε')
                                if (follow[currentNode] == null) {
                                    st = TreeSet()
                                    st!!.addAll(tempSet)
                                    follow[currentNode] = st!!
                                } else
                                    follow[currentNode]!!.addAll(tempSet)
                            }
                        } else {
                            if (follow[currentNode] == null) {
                                st = TreeSet()
                                st!!.add(nextNode[0])
                                follow[currentNode] = st!!
                            } else
                                follow[currentNode]!!.add(nextNode[0])
                        }
                    }
                    index = rightNodes[i].indexOf(currentNode, nextIndex)
                }
            }
        }
    }

    fun followKernealCode(): String {
        var content = ""
        var flag = true
        for (leftNode in mp.keys) {
            if (flag) {
                val st = TreeSet<Char>()
                st.add('#')
                follow[leftNode] = st
                flag = false
            }
            findFollow(leftNode)
        }

        println("Follow集如下:")
        for ((key, value) in follow) {
            content += "$key : $value\n"
            println("$key : $value")
        }
        return content
    }

}

递归下降分析法

递归下降法

当一个文法满足LL(1)条件时,我们可以给它构造一个不带回溯的自上而下的分析程序,这个分析过程是由一组递归过程组成的,每个过程对应文法的一个非终结符,这样的分析程序我们称为递归下降分析程序。

算术表达式分析

首先我们需要写出表达式对应的文法:

$$E\rightarrow E+T|E-T|T \\ T\rightarrow T*F|T/F|F \\ F\rightarrow (E)|i$$

由于该表达式存在左递归,因此我们需要先将其消除得到如下文法:

$$E\rightarrow TE' \\ E'\rightarrow +TE'|-TE'|\varepsilon \\ T\rightarrow FT' \\ T'\rightarrow *FT'|/FT'|\varepsilon \\ F\rightarrow (E)|i$$

然后计算其FIRST集和FOLLOW集:

$$FIRST(E')=\{+,-,\varepsilon\} \\ FIRST(T')=\{*,/,\varepsilon\} \\ FIRST(E)=\{(,i\} \\ FIRST(T)=\{(,i\} \\ FIRST(F)=\{(,i\} $$

$$FOLLOW(E)=\{), \# \} \\ FOLLOW(E')=\{), \#\} \\ FOLLOW(T)=\{+,-,),\#\} \\ FOLLOW(T')=\{+,-,),\#\} \\ FOLLOW(F)=\{*,/,+,-,),\#\}$$

根据以上的FOLLOW集合,我们可以构造如下的SELECT集:

$$SELECT(E\rightarrow TE')=\{(.i\} \\ SELECT(E'\rightarrow +TE')=\{+\} \\ SELECT(E'\rightarrow -TE')=\{-\} \\ SELECT(E'\rightarrow \varepsilon)=\{\varepsilon,),\#\} \\  SELECT(T\rightarrow TF')=\{(,i\} \\ SELECT(T'\rightarrow *FT')=\{*\} \\ SELECT(T'\rightarrow /FT')=\{/\} \\ SELECT(T'\rightarrow \varepsilon)=\{\varepsilon,+, -,),\#\} \\ SELECT(F\rightarrow (E))=\{(\} \\ SELECT(F\rightarrow i)=\{i\}$$

$$SELECT(E'\rightarrow +TE')\cap SELECT(E'\rightarrow - TE')\cap SELECT(E'\rightarrow \varepsilon)=\phi \\ SELECT(T'\rightarrow /FT')\cap SELECT(T'\rightarrow * FT')\cap SELECT(T'\rightarrow \varepsilon)=\phi \\ SELECT(F\rightarrow(E))\cap SELECT(F\rightarrow i)=\phi $$

因此,该文法所有相同左部产生式的SELECT集的交集为空,所以文法是LL(1)文法,因此算数表达式可以用下降分析法进行语法分析。

算符优先分析法

算符优先法特别有利于表达式分析,易于手工实现, 其过程是自下而上的规约过程,但这种规约未必是严格的最左规约,也就是说算法优先分析法并不是一种规范规约法。所谓的算符优先分析就是定义算符之间的某种优先关系,借助于这种优先关系寻找“可规约串”和进行规约。通常用下面方法表示任何两个可能相继出现的终结符的优先关系:

  • $a\lessdot b$,$a$的优先级低于$b$
  • $a\gtrdot b$,$a$的优先级高于$b$
  • $a\doteq b$,$a$的优先级等于$b$

一个文法,如果它的任一产生式的右部不含两个相继(并列)的非终结符号,即不含如下形式的产生式右部$\cdots QR\cdots$,则我们称该文法为算符文法。假设G是一个不含$\varepsilon$-产生式的算符文法,则对于任何一对终结符$a,b$:

  • $a\doteq b$,当且仅当文法G中含有形如$P\rightarrow \cdots ab\cdots$或$P\rightarrow \cdots aQb \cdots$的产生式
  • $a\lessdot b$,当且仅当G中含有形如$P\rightarrow \cdots aR \cdots$的产生式,而$R \overset{+}{\Longrightarrow}b\cdots$或$R\overset{+}{\Longrightarrow}Qb \cdots$
  • $a\gtrdot b$,当且仅当G中含有形如$P\rightarrow \cdots Rb \cdots$的产生式,而$R\overset{+}{\Longrightarrow}\cdots a$或$R\overset{+}{\Longrightarrow}\cdots aQ$

如果一个算符文法G中的任何终结符对$(a,b)$至多只满足上述三关系之一,则称G是一个算符优先文法。通常我们根据产生式构造其优先关系表,然后对每个非终结符计算其FIRSTVT集和LASTVT集。

$$FIRSTVT(P)=\{a|P\overset{+}{\Longrightarrow}a \cdots \vee P\overset{+}{\Longrightarrow}Qa\cdots,a\in V_T,Q\in V_N\} \\  LASTVT(P)=\{a|P\overset{+}{\Longrightarrow}\cdots a \vee P\overset{+}{\Longrightarrow}\cdots Qa,a\in V_T,Q\in V_N\}$$

有了FIRSTVT集和LASTVT集后,就可以通过检查每个产生式的候选式确定满足关系的所有终结符对。

Yacc分析器

Yacc是一个经典的生成语法分析器的工具,它根据用户提供的语言的语法描述的规格说明,自动构造出一个该语言的语法分析器,它能和词法分析器Lex一起使用,把两者生成的C文件共同编译。该实验,我用Yacc写了一个功能比较完善的计算器,不仅支持标准的加减乘除四则运算,还能进行三角函数sin、cos、tan、arcsin、arccos、arctan等函数运算,开根sqrt运算,幂^运算, 还包括对数log、ln和自然数的运算。

Bison

Bison和Yacc相类似,基本与Yacc兼容且在其基础之上进行了改进,经常和Flex一起使用,它是一种通用的分析器程序,可以用它生成从简单的计算器到复杂的程序设计语言等多种语言分析器。它向上兼容Yacc,理论上Yacc语法都可以不加更改地使用Bison生成C文件。

逆波兰表达式

逆波兰表达式又叫后缀表达式,在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,这种表示法也叫做中缀表达式,而在逆波兰表达式中,每一个运算符都置于其运算对象之后,例如:

$$a+b\longrightarrow a,b,+ \\ a+(b-c)\longrightarrow a,b,c,-,+ \\ a+(b-c)*d\longrightarrow a,b,c,-,d,*,+ \\ a=1+3\longrightarrow a,1,3,+,=$$

Plus

Think Different

文章评论

  • 头像
    fleck water softeners for sale

    Ahaa, its fastidious dialogue about this post here at this webpage,
    I have read all that, so now me also commenting at this place.

    2020年04月05日