精华内容
下载资源
问答
  • 大概1年半前的1个暑假,闲着在家没事做,读了1部分龙书,然后自己写了个Regular Expression(正则表达式)的分析,有点类似Lex,根据定义的Regular Expression在内存中构建相对应的DFA。C++写的,今天看来那个时候的...

    我的编译器之旅 (1):

    写在最前面:

    研究编译原理纯粹是我的个人爱好。

    大概1年半前的1个暑假,闲着在家没事做,读了1部分龙书,然后自己写了个Regular Expression(正则表达式)的分析器,有点类似Lex,根据定义的Regular Expression在内存中构建相对应的DFA。C++写的,今天看来那个时候的代码很幼稚。不过这对复习和巩固了词法分析起了很大帮助,由于自己动手写过,所以很多东西现在想来还可以很容易的推导出来。还好词法分析东西不多,最近一直在做语法分析器,也是自己的兴趣所好,感觉比较复杂。Biason和Yacc都是很不错的语法生成器。 编译器的Front-end主要就是这2部分,Back-end比较复杂。在MS的Training上也被我偶尔听到,VC++的back-end差不多已经10年没有修改过了。MS的Pheonix(凤凰)计划也正在推进中。很多学校加入了研究,如果这个成功那MS的地位将更加不可动摇了。好了不说那么多了,回忆开始。。。。。。

    今天的主题是Post-order(后缀国内应该这样称呼吧)。先回顾一下Tree(树),遍历树的顺序一般有3种: Pre-order, In-order, Post-order国内应该分别称为:前缀,中缀,后缀。以二叉树为例, 对应它们的访问顺序分别为:VLR, LVR, LRV, 如果L代表左子树,V代表节点,R代表右子树的话。所以很容易看出一个表达式的正常顺序为LVR也就是中缀。如果我们以后缀的方式遍历树,那么我们最后得到的便是Post-order 也称 Polish Notation (波兰表达式).

    算法 (1):

     输入中缀表达式

     输出后缀表达式

    操作符Stack

    如果字符是操作符(比如:+ - * /)则推入Stack。

    (1)如果字符为 '( ' 左括号,那么把它压入Stack

    (2)如果字符为 ')'右括号,开始弹出Stack知道弹出一个'('左括号为止。同时删除右括号和左括号两个字符。

    (3)如果Stack顶部的操作符要比当前的操作副优先等级低的话,推入当前的操作符到Stack。比如: *的优先级要比+的高,所以*压入Stack。

    剩下的状态不停的POP,知道Stack为空为止。

    举例:

    5+4*1

    Operator Stack    

    * +                          541

    合并之后的Postfix为:541*+。

    根据这个后缀表达式,很容易被转换成汇编代码为:

    PUSH 5

    PUSH 4

    PUSH 1

    POP reg1

    POP reg2

    MUL reg1 reg2

    PUSH reg1 //4被压入Stack

    POP reg1

    POP reg2

    ADD reg1 reg2  //9存在reg中。

    最后的结果存在reg1 中。

    应用这个算法,源程序中的一些数学表达式,很容易的可以被装换至汇编代码。

    至此,总算向编译器迈出了勇敢的第一步。

    注:算法不是我发明,很早就已经被实现了,但是编译器中涉及很多经典高效的算法,如果能够理解作者的出发点和设计思路,对自身能力将有很大的一个提高。

     

    展开全文
  • -将运算符写在两个操作数之后的表达式称为“后缀表达式”,如上面的中缀表达式可转换后缀表达式1 2 3 4 - * + 5 +。后缀表达式中没有括号,而且运算符没有优先级。后缀表达式的求值过程能够严格地从左到右按顺序...

    提交测试截图和码云练习项目链接,实现Linux下dc的功能,计算后缀表达式的值

    -将运算符写在两个操作数之后的表达式称为“后缀表达式”,如上面的中缀表达式可转换为后缀表达式1 2 3 4 - * + 5 +。后缀表达式中没有括号,而且运算符没有优先级。后缀表达式的求值过程能够严格地从左到右按顺序进行,符合运算器的求值规律。

    应注意的问题;

    -老师主要是想考察课上是否听懂了,并且检验我们的实际动手编程能力。

    在课堂是是听懂了老师所说的课程,虽然没有编写出相应的代码,但也回来及时将博客补上,并且对代码进行了了解。
    -优先级问题;
    -入栈,出栈顺序参考PPT

    老师给出的代码(不完整)

    mport java.util.StringTokenizer;
    import java.util.Stack;
    public class MyDC {
        /**
         * constant for addition symbol
         */
        private final char ADD = '+';
        /**
         * constant for subtraction symbol
         */
        private final char SUBTRACT = '-';
        /**
         * constant for multiplication symbol
         */
        private final char MULTIPLY = '*';
        /**
         * constant for division symbol
         */
        private final char DIVIDE = '/';
        /**
         * the stack
         */
        private Stack<Integer> stack;
    
        public MyDC() {
            stack = new Stack<Integer>();
        }
    
    
        public int evaluate(String expr)
    
    
        {
            int op1, op2, result = 0;
            String token;
            StringTokenizer tokenizer = new StringTokenizer(expr);
    
            while (tokenizer.hasMoreTokens()) {
                token = tokenizer.nextToken();
    
                //如果是运算符,调用isOperator
                if () {
                    //从栈中弹出操作数2
                   
    
                    //从栈中弹出操作数1
                   
    
                    //根据运算符和两个操作数调用evalSingleOp计算result;
                   
    
                    //计算result入栈;
                    
    
                } else//如果是操作数
                    stack.push(new Integer(Integer.parseInt(token)));
    
                //操作数入栈;
    
            }
    
            return result;
    
        }
    
    
        private boolean isOperator(String token)
    
    
        {
            return (token.equals("+") || token.equals("-") ||
                    token.equals("*") || token.equals("/"));
    
        }
    
    
        private int evalSingleOp(char operation, int op1, int op2)
    
    
        {
            int result = 0;
    
            switch (operation) {
                case ADD:
                    result = op1 + op2;
                    break;
                case SUBTRACT:
                    result = op1 - op2;
                    break;
                case MULTIPLY:
                    result = op1 * op2;
                    break;
                case DIVIDE:
                    result = op1 / op2;
    
            }
    
            return result;
    
        }
    
    }

    -MyDCTester

    import java.util.Scanner;
    public class MyDCTester  {public static void main (String[] args) {
               String expression, again;
    
                int result;
    
              try {
                  Scanner in = new Scanner(System.in);
    
                  do {
                      MyDC evaluator = new MyDC();
                      System.out.println("Enter a valid postfix expression: ");
                      expression = in.nextLine();
    
                      result = evaluator.evaluate(expression);
                      System.out.println();
    
                      System.out.println("That expression equals " + result);
    
                      System.out.print("Evaluate another expression [Y/N]? ");
                      again = in.nextLine();
                      System.out.println();
                  }
                  while (again.equalsIgnoreCase("y"));
              } catch (Exception IOException) {
                  System.out.println("Input exception reported");
              }
    }
    }
    

    dc

    dc 命令是一个任意精度的算术计算器。dc 命令从 File 参数或者标准输入得到其输入直到它读到一个文件结束符。一旦 dc 命令接收到输入,它将求出计算值并将计算值写入到标准输出当中。它按十进制整数计算,但是您可以指定输入和输出的基数,以及小数部分保留的位数。dc 命令结构如同一个堆栈、逆波兰表示法计算。

    考点:

    考课堂上刚讲的入栈和弹栈

    补充代码如下

     while (tokenizer.hasMoreTokens()) {
                token = tokenizer.nextToken();
                //如果是运算符,调用isOperator
                if (isOperator(token)==true) {
                    op2=stack.pop();
                    op1=stack.pop();
                    //从栈中弹出操作数2
                    //从栈中弹出操作数1
                    result=evalSingleOp(token.charAt(0),op1,op2);
                    //根据运算符和两个操作数调用evalSingleOp计算result;
                    stack.push(result);
                    //计算result入栈;
                }
                else//如果是操作数
                {
                    stack.push(Integer.parseInt(token));
                }
                //操作数入栈;
            }
    
    运行结果:

    1071583-20170531182443414-1782781136.jpg

    码云链接

    转载于:https://www.cnblogs.com/hpl20155329/p/6925448.html

    展开全文
  • 如果是操作符,则检测是否是右括号,如果是右括号,则直接将其入栈;如果是左括号,则将栈中的操作符依次弹栈,归入前缀表达式,直至遇到右括号,将右括号弹栈,处理结束;如果是其他操作符,则检测栈顶操作符的...

    参考:http://www.cnblogs.com/unixfy 

    一、中缀表达式转前缀

    首先设定一个操作符栈,从右到左顺序扫描整个中缀表达式,如果是操作数,则直接归入前缀表达式;如果是操作符,则检测器是否是右括号,如果是右括号,则直接将其入栈;如果是左括号,则将栈中的操作符依次弹栈,归入前缀表达式,直至遇到右括号,将右括号弹栈,处理结束;如果是其他操作符,则检测栈顶操作符的优先级与当前操作符的优先级关系,如果栈顶操作符优先级大于当前操作符的优先级,则弹栈,并归入前缀表达式,直至栈顶操作符优先级小于等于当前操作符优先级,这时将当前操作符压栈。

             当扫描完毕整个中缀表达式后,检测操作符栈是否为空,如果不为空,则依次将栈中操作符弹栈,归入前缀表达式。最后,将前缀表达式翻转,得到中缀表达式对应的前缀表达式。

    二、中缀表达式转后缀 

    使用操作符栈;对于操作数直接进入后缀表达式;对于“(”,入栈;对于“)”,弹栈,直至“(”;对于其他操作符,弹栈并进入后缀表达式,直至小于当前操作符优先级或者“(”;扫描中缀表达式后,弹出栈中所有操作符并进入后缀表达式。

    总结:

     

    中缀转前缀

    中缀转后缀

    操作符栈

    操作符栈

    扫描顺序

    从右到左

    从左到右

    遇到操作数

    直接归入

    直接归入

    遇到右括号

    直接入栈

    将栈中操作符依次弹栈,归入,直至遇到左括号,将左括号弹栈,处理完毕

    遇到左括号

    将栈中操作符依次弹栈,归入,直至遇到右括号,将右括号弹栈,处理完毕

    直接入栈

    遇到其他操作符

    检测栈顶操作符优先级与当前操作符优先级关系,如果栈顶大于当前,则出栈,归入,直至栈顶小于等于当前,并将当前操作符入栈

    检测栈顶与当前优先级关系,如果栈顶大于等于当前则出栈,归入,直至栈顶小于当前,并将当前操作符入栈

    操作符栈中的优先级

    从栈底到栈顶操作优先级:非递减。即:栈顶可以大于或等于下面的

    从栈底到栈顶优先级:递增。即:栈顶必须大于下面的

    是否翻转

    翻转

    无需翻转

    三、前缀表达式转中缀表达式

     

    展开全文
  • 一个编译原理中缀转后缀表达式(递归下降翻译成AST,后序遍历得到后缀)的 Java 程序,读取文件中的中缀表达式(每个表达式以分号结束,文件中可以有多个表达式)并转换为等价的后缀表达式后输出到屏幕上, 表达式中...
  • 栈是一种后入先出(LIFO)的数据结构,数据只能在栈顶添加或者删除,所以操作很快,容易实现。抽象数据类型定义 栈的JS实现 解决实际问题 抽象数据类型定义 ... 使用构造调用模式,这是一套类似类的对象

    栈是一种后入先出(LIFO)的数据结构,数据只能在栈顶添加或者删除,所以操作很快,容易实现。将从3个方面来深入理解和使用栈这种数据结构。

    • 抽象数据类型定义
    • 栈的JS实现
    • 解决实际问题

    抽象数据类型定义

    属性及方法 作用
    push() 入栈
    pop() 出栈
    peek() 显示栈顶元素
    dataStore 存储数据
    top 记录栈的长度和位置

    栈的JS实现

    使用构造器调用模式,这是一套类似类的对象构建语法,通过在函数前面加上new调用,同时this会绑定到这个新对象上。

    //Stack.js
    //Stack对象定义
    function Stack(){
        this.dataStore = [];
        this.pop = pop;
        this.push = push;
        this.peek = peek;
        this.clear = clear;
        this.length = length;
        this.top = 0;
    }
    function push(element){
        this.dataStore[this.top++] = element;
    }
    function pop(){
        return this.dataStore[--this.top]
    }
    function peek(){
        return this.dataStore[this.top-1]
    }
    function length(){
        return this.top;
    }
    function clear(){
        this.top = 0;
    }
    
    //实例化Stack对象
    var oneStack = new Stack();

    栈的实际应用

    (一)网页展示

    这里写图片描述

    (二)html代码

    <!DOCTYPE html>
    <html>
    <head>
        <title>JS structure - Stack</title>
        <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
        <script src="stack.js" type="text/javascript"></script>
        <script src="practice.js" type="text/javascript"></script>
    </head>
    <style>
    div {
        width: 60%;
        margin: 30px auto;
        padding: 10px;
        border: 1px solid #333;
    }
    </style>
    <body>
        <div>
            <h2>进制转换</h2>
            <form>
                <label for="input_number">输入一个数字:</label>
                <input type="text" id="input_number" />
                <label for="input_radix">输入进制:</label>
                <input type="text" id="input_radix" />
                <input type="button" value="转换" onClick="transfer()">
                <textarea id="transfer_result"></textarea>
            </form>
        </div>
        ……
    </body>
    </html>

    (三)Javascript方法

    1. 进制转换

    //practice.js
    function mulBase(num, base){
        var tStack = new Stack();
        do{
            tStack.push(num%base);//最高位为n%b
            num = Math.floor(num / base);//n/b代替n
        }while(num > 0);
    
        var converted = "";
        while(tStack.length()>0){
            converted += tStack.pop();//FILO
        }
        return converted;
    }

    2. 阶乘

    //practice.js
    function fact(number){
        var fStack = new Stack();
        while(number > 0)
        {
            fStack.push(number);//将数字从大到小压入栈中
            number = number -1;
        }
        var result = 1;
        while(fStack.length()>0)
        {
            result *= fStack.pop();//弹出的元素挨个出栈相乘
        }
        return result;
    }

    3. 括号匹配

    //practice.js
    function bracketmatch(expression)
    {
        var bStack = new Stack();
        for(var i=0; i<expression.length; i++)
        {
            if(expression[i] == "(")
            {
                bStack.push(expression[i]);//遇到“(”将其压入栈出
            }
            else if(expression[i] == ")")
            {
                if(bStack.peek() == "(")
                    bStack.pop();//直到遇到“)”,将“("弹出栈
            }
            else
            {
                //其他符号,不进行任何操作
            }
    
        }
        if(bStack.length()>0)
            return false;
        else
            return true;
    }

    4. 后缀表达式

    将中缀表达式转换成后缀表达式的算法思路,可以参看Miibotree的数据结构文,http://blog.csdn.net/gaoxin1076/article/details/7364098

    //practice.js
    function expressionChange(expression){
        var result = "";
        var operators = new Stack();
        for(var i=0; i<expression.length; i++)
        {
            var currentCharac = expression[i];
            switch(currentCharac)
            {
                case "("://左括号直接入栈
                    operators.push(currentCharac);
                    break;
                case ")"://右括号将所有栈内元素弹出
                    while(operators.peek()!="(")
                    {
                        result += operators.pop()+" ";
                    }
                    operators.pop();//弹出左括号
                    break;
                case "+":
                case "-"://因为+和-的优先级最低,将所有栈内元素弹出后,将当前符号压入栈。
                    while(operators.length()>0 && operators.peek() != "(")
                    {
                        result += operators.pop()+" ";
                    }
                    operators.push(currentCharac);
                    break;
                case "/":
                case "*"://只有当栈顶元素是/,*的时候,才需要弹出所有栈内元素。
                    while(operators.length()>0 && (operators.peek() == "*" || operators.peek() == "/"))
                    {
                        result += operators.pop()+" ";
                    }
                    operators.push(currentCharac);
                    break;
                default:
                    while(currentCharac<="9" && currentCharac>="0")
                    {
                        result += currentCharac;
                        currentCharac = expression[++i];
                    }
                    result += " ";
                    i--;//一定要减,不然的话i加了两次1
                    break;  
            }
        }
        while(operators.length()>0)//最后要将站内剩下元素弹出
        {
            result += operators.pop()+" ";
        }
        return result;
    }
    展开全文
  • C#写的表达式解析,支持多种操作符 如加减乘除幂模,同时还支持正负、三角函数,随机值等函数,可以支持自己扩展操作符,同时能支持...表达式使用的是逆波兰式(中缀表达式转换成的后缀表达式),非递归实现,执行效率非常高.
  • 对于中缀式转后缀式,这已经不算一个很困难的问题了,之前也学了很多能够解决此问题的数据结构和算法,比如栈和表达式树。今天算是又多学了一种解法。不同的是,该方法更强劲。 构造产生式 定义一下字母表 {0-9+-*...
  • 正则表达式

    2014-12-03 14:51:39
    正则表达式中的特殊字符 字符 含意 \ 做为转意,即通常在"\"后面的字符不按原来意义解释,如/b/匹配字符"b",当b前面加了反斜杆后/\b/,转意为匹配一个单词的边界。 -或- 对正则表达式功能字符的还原,如"*"匹配它...
  • 实现递归下降解析,将输入,中缀表达式转换后缀表达式,然后对其求值以输出结果。 用法 只需调用二进制文件,然后调用要评估的表达式即可 $ calculate 2*2 2*2 = 24.000000 支持+ , - , * , / , ^运算符,...
  • 一个简单的语法制导翻译的流程,建立一个将中缀算术表达式转换后缀表达式的语法制导翻译
  • 内容: 项目名称:简易计算器程序项目内容: 编写程序,模拟简单运算...(1) 从键盘录入中缀表达式,将中缀表达式转换后缀表达式输出; (2) 输入后缀表达式,计算后缀表达式的值。 代码实现: 节点类: ...
  • 内容: 项目名称:简易计算器程序项目内容: ...(1) 从键盘录入中缀表达式,将中缀表达式转换后缀表达式输出; (2) 输入后缀表达式,计算后缀表达式的值。 代码实现: #include<iostream> #inclu...
  • 2018-01-27 22:06:00
     中缀表达式转换后缀表达式  计算后缀表达式  实现函数调用(包括递归)  求范围误差(极差)  网页浏览器中的back按钮和历史记录  文本编辑中的撤销操作  HTML和XML中的tag匹配  2、间接应用 ...
  • 栈(stack)

    2012-03-15 15:56:09
    一个仅在一端访问的线性集合,这端叫做...n 中缀表达式到后缀表达式转换,以及对后缀表达式的求值 n 回溯算法 n 方法调用 n 文本编辑中的撤销功能 n web浏览器的链接历史信息的保留 中缀表达式到后缀表
  •  将中缀算术表达式转换后缀表达式的语法制导翻译  之后扩展,使之能将某些程序片段转换为三地址代码。 此章即用示例把第一章介绍的所有流程实现一下。 删除空白和注释 预读  有时需要...
  • 这里写自定义目录标题课前预习将中缀表达式转换后缀表达式计算逆波兰表达式三级目录功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表...
  • 数据结构--栈与队列

    2018-09-27 15:46:37
    中缀转后缀表达式2. 后缀表达式求值3. 括号匹配检测4. 数制转换为什么需要队列?怎样定义队列?1. 队列的定义2. 队列的两种实现队列的应用栈和队列笔试题用栈实现队列用队列实现栈栈的出栈顺序 为什么需要栈? 1....
  • 递归下降语法分析

    千次阅读 2013-05-17 18:35:46
    为了体现出递归下降法简洁之处,计算表达式采用lisp语言的方式来书写,这样就能避免中缀表达式转换后缀表达式,破坏了递归下降的格局。在lisp语言里,会强制指出运算符优先级:(1+2 * 5)*(3+4)在LISP会被写成(*(+
  • 然后点击“转换器”后面的那个省略号,会出来自定义转换器对话框;在右边选择你需要的编码方式,添加到左边,然后点确定;最后在下拉框中选择需要的编码方式,然后打开文件即可。 【11】软件技巧——FTP 上传的设置 ...
  • 这个源码主要是对我的Jsoup笔记进行整合,初步实现saz格式文件到csv文件转换的基本功能,程序要实现的基本功能主要是: 1、saz文件遍历:获取Java工程所在目录的上层目录中,指定扩展名(.saz)的文件, 2、遍历获得...
  • 作者:yxin1322http://blog.csdn.net/yxin1322转载请注明出处一、逆波兰式的转换: 简单表达式有三中表示方法:中缀表示法:把双目运算符放在两个运算分量中间。前缀表示法:把双目运算符放在两个运算分量前面, 也...
  • jxTMS--web端的自动计算

    2020-06-26 12:51:32
    jxTMS会解析这些算式,将其转换后缀表达式形式 web端在创建控件时,会检测本控件是否参与自动计算,如果本控件参与自动计算,则为其安装自动计算的执行 当用户在某控件输入后,如果该控件安装有自动计
  • 第二章给出了一个将前缀表达式转换后缀表达式的编译器,主要使用本书的一些基本技巧来构建;第三章阐述了词法分析、正则表达式、有限自动机和扫描生成工具,这章中的技术广泛应用于文本处理;第四章详细阐述了...
  • 6.1.9 隐式常量表达式转换 112 6.1.10 涉及类型形参的隐式转换 112 6.1.11 用户定义的隐式转换 113 6.1.12 匿名函数转换和方法组转换 113 6.2 显式转换 113 6.2.1 显式数值转换 114 6.2.2 显式枚举转换 115 6.2.3 ...
  • 6.1.9 隐式常量表达式转换 112 6.1.10 涉及类型形参的隐式转换 112 6.1.11 用户定义的隐式转换 113 6.1.12 匿名函数转换和方法组转换 113 6.2 显式转换 113 6.2.1 显式数值转换 114 6.2.2 显式枚举转换 115 6.2.3 ...
  • 6.1.6 隐式常数表达式转换 148 6.1.7 用户定义的隐式转换 148 6.2 显式转换 148 6.2.1 显式数值转换 148 6.2.2 显式枚举转换 148 6.2.3 显式引用转换 148 6.2.4 取消装箱转换 148 6.2.5 用户定义的显式转换 148 6.3 ...
  • 6.1.6 隐式常数表达式转换 223 6.1.7 用户定义的隐式转换 224 6.2 显式转换 225 6.2.1 显式数值转换 226 6.2.2 显式枚举转换 228 6.2.3 显式引用转换 229 6.2.4 取消装箱转换 230 6.2.5 用户定义的显式转换 231 6.3 ...
  • 7.4 后缀表达式 166 7.4.1 下标表达式 166 7.4.2 成员选择 168 7.4.3 函数调用 169 7.4.4 后缀增值和减值操作符 171 7.4.5 复合字面值 172 7.5 单目表达式 173 7.5.1 类型转换 174 7.5.2 sizeof操作符 174 ...
  • 它们与对应的二叉树结构相关,关于如何转化中缀表达式为前缀与后缀表达式本文不作详细介绍,请参阅《数据结构》与《编译原理》等相关教材。 这里我们通常选用后缀表达式作为中间临时输出,又称逆波兰表达式。但是,...
  • C# 语言规范

    2008-01-16 07:22:16
    转换 216 6.1 隐式转换 217 6.1.1 标识转换 218 6.1.2 隐式数值转换 219 6.1.3 隐式枚举转换 220 6.1.4 隐式引用转换 221 6.1.5 装箱转换 222 6.1.6 隐式常数表达式转换 223 6.1.7 用户...

空空如也

空空如也

1 2 3 4
收藏数 61
精华内容 24
关键字:

后缀表达式转换器