使用递归下降法实现的简单计算器

递归下降

最近在学编译原理，讲完了递归下降法，老师就布置了一个作业，使用递归下降法实现一个简易计算器。

需求：实现简单的四则运算功能，有简单界面

实现：制作一个网页版的简单计算器用于输入输出

工具:webstorm,浏览器：谷歌（没做兼容，就别太老版本就行）

过程分析：

首先还是来复习一下递归下降法吧；

递归下降法是一种简单的将自顶向下分析算法，他的概念非常简单：讲一个非终结符A的文法规则看作将识别A的一个过程定义，A的文法规则的右边指出这个过程的代码结构：一个选择中的终结符与非终结符序列与相匹配的输入以及其他过程的调用相对应，而选择与在代码中的替代情况（case语句和if语句）相对应。

emm，这一段可以说非常的抽象了。不管他，接下来我们看看这个过程具体是怎么操作的，看完之后，再回过头看看这个定义就会清晰很多。

为了消除左递归和回溯，我们使用更加适合递归下降法的EBNF（扩展的巴科斯范式）来改写我们的文法规则。

最后我们得到的文法规则就是：

接下来我们就用代码来实现它：

//这里的token比较简单，但是我还是写了一个简单的词法分析扫描器
const digitArray = ['0','1','2','3','4','5','6','7','8','9'];
//判断是否是数字
function isDigit(x) {
    return digitArray.indexOf(x)!==-1
}
//简单的词法分析，获得token；
function getToken(str){
    var nextIndex=0;
    var prevIndex=0;
    var len = str.length;
    var state2 = 1;
    var tokens = [];
    for (nextIndex=0;nextIndex<len;){
        while( (state2 === 1 ||state2 === 2)&&(nextIndex<=len) ){
            switch (state2){
                case 1:
                    prevIndex = nextIndex;
                    if( isDigit(str.charAt(nextIndex)) ){
                        nextIndex += 1;2
                        state2 = 2;
                    }else{
                        nextIndex += 1;
                        state2 = 4;
                    }
                    break;
                case 2:
                    if( isDigit(str.charAt(nextIndex)) ){
                        nextIndex += 1;
                        state2 = 2;
                    }else{
                        nextIndex += 1;
                        state2 = 3;
                    }
                    break;
            }
        }
        if(state2 === 3){
            nextIndex = nextIndex-1;
            let tem5=str.slice(prevIndex,nextIndex);
            tokens.push(tem5);
            state2 =1;
        }else if(state2 ===4){
            let tem5=str.slice(prevIndex,nextIndex);
            tokens.push(tem5);
            state2 =1;
        }else{
            console.log("error");
        }
    }
    return tokens;
}
//语法树函数，因为这个加法，减法对的逻辑很简单，也一并写在语法树里面了
//exp函数处理exp，term函数处理term，factor函数处理factor
function snytaxTreeLeft(str) {
    var m=0;
    var token = getToken(str);
    for (;m<token.length;){
         result = exp();
    }
    return result;
    //一些简单的处理函数
    function match(expectedToken){
        if((token[m] === expectedToken)||(parseInt(token[m]) === expectedToken)){
           m +=1;
           console.log(m);
        }else{
            console.log('error');
        }
    }
    function exp() {
        let temp = term();
        while((token[m] === '+'||token[m] === "-")){
            switch (token[m]){
                case '+':
                    match("+");
                    temp +=term();
                    break;
                case '-':
                    match('-');
                    temp -=term();
                    break;
            }
        }
        return temp;
    }
    function term() {
        let temp = factor();
        while ((token[m] === '*' || token[m] === "/")) {
            switch (token[m]) {
                case '*':
                    match("*");
                    temp *= factor();
                    break;
                case '/':
                    match('/');
                    temp = temp / factor();
                    break;
            }
        }
        return temp;
    }
    function factor() {
        let temp;
        if(token[m] ==='('){
            match('(');
            temp = exp();
            match(')');
        }else if(1){
            temp = parseInt(token[m]);
            m=m+1;
        }
        return temp;
    }
}

上面的是左结合的写法，接下来是右结合的写法；

同样我们先写出他的文法规则：

按照文法规则，可以写出这一部分的代码实现：

//右结合
function snytaxTreeRight(str) {
   var token = getToken(str);
    var m=0;
    for (;m<token.length;){
        console.log(m);
        result = expRight();
    }
    return result;
    //一些简单的处理函数
    function match(expectedToken){
        if((token[m] === expectedToken)||(parseInt(token[m]) === expectedToken)){
            m +=1;
            console.log(m);
        }else{
            console.log('error');
        }
    }
    function expRight() {
        let temp = termRight();
        if((token[m] === '+'||token[m] === "-")){
            switch (token[m]){
                case '+':
                    match("+");
                    temp +=expRight();
                    break;
                case '-':
                    match('-');
                    temp = temp - expRight();
                    break;
            }
        }
        return temp;
    }
    function termRight() {
        let temp = factorRight();
        if ((token[m] === '*' || token[m] === "/")) {
            switch (token[m]) {
                case '*':
                    match("*");
                    temp *= termRight();
                    break;
                case '/':
                    match('/');
                    temp = temp / termRight();
                    break;
            }
        }
        return temp;
    }
    function factorRight() {
        let temp;
        if(token[m] ==='('){
            match('(');
            temp = expRight();
            match(')');
        }else if(1){
            temp = parseInt(token[m]);
            m=m+1;
        }
        return temp;
    }
}

最后输出结果是这样的：

这个界面非常简单，使用jquery处理的，js部分代码如下：

//界面部分
$(function(){
    var text = $('.text');
    $('.cal').click(function () {
        let calText = text.val();
        let calResultLeft = snytaxTreeLeft(calText);    //得到左结合的答案
        $('.resultLeft span').text(calResultLeft);  //把答案赋给span
        let calResultRight = snytaxTreeRight(calText);    //得到右结合的答案
        $('.resultRight span').text(calResultRight);  //把答案赋给span
        text.val("");
    });
    $('.con').click(function (e) {
        let target = e.target;
         let calText = text.val();
         calText += target.innerText;
         text.val(calText);
    });
    $('.del').click(function () {
        let calText = text.val();
        calText = calText.slice(0,calText.length-1);
        text.val(calText);
    })
});

最后是 html部分：

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Calculator</title>
    <style>
        h3{
            text-align:center;
        }
        .container{
            height: 278px;
            width:208px;
            margin:10px auto;
            border:black solid 1px;
            position: relative;
        }
        .text{
            float: left;
            width: 154px;
            height: 68px;
            resize: none;
            margin:0;
            padding: 0;
            font-size: 16px;
            border:black solid 1px;
        }
        .cal,.del{
            float: left;
           width: 26px;
            height: 70px;
        }
        .clear{
            clear:both;
        }
        .content{
            float: left;
            width:50px;
            height:50px;
            border:black solid 1px;
            font-size: 24px;
            text-align: center;
            line-height: 50px;
        }
        .resultLeft,.resultRight{
            height: 50px;
            width: 500px;
            margin: 0 auto;
            text-align: center;
        }
    </style>
    <script src="jquery-3.3.1.min.js"></script>
</head>
<body>
    <h3>一个简易计算器</h3>
    <p class="container">
        <textarea class="text"></textarea>
        <button class="cal">计算</button>
        <button class="del">取消</button>
        <p class="clear"></p>
        <p class="con">
            <p class="content" id="1">1</p>
            <p class="content" id="2">2</p>
            <p class="content" id="3">3</p>
            <p class="content" id="4">4</p>
            <p class="content" id="5">5</p>
            <p class="content" id="6">6</p>
            <p class="content" id="7">7</p>
            <p class="content" id="8">8</p>
            <p class="content" id="9">9</p>
            <p class="content" id="0">0</p>
            <p class="content" id="+">+</p>
            <p class="content" id="-">-</p>
            <p class="content" id="*">*</p>
            <p class="content" id="/">/</p>
            <p class="content" id="(">(</p>
            <p class="content" id=")">)</p>
        </p>
    </p>
    <p class="resultLeft">你的左结合计算结果是：<span></span></p>
    <p class="resultRight">你的右结合计算结果是：<span></span></p>
    <script src="main.js"></script>
</body>
</html>

中间的界面写的挺繁琐的而且又很丑，emmm，讲个就吧，重点在于算法部分

这里的代码已经是完整的了，想要更方便的下载可以访问我的

github：https://github.com/ArthurZhou123/Simple-calculator-implemented-using-recursive-descent-method

相关阅读

原来连续两次递归调用很简单

void rec(int N) { //为了区分这两个递归，分别为它们取个别名好了 if (N>0){  rec(N - 1);//rec1 rec(N - 10)

Java经典递归算法

1.斐波那契数列package com.luna.base; public class BirthRabbit { public static void main(String[] args) { int i = 1;