Top Down Operator Precedence - 自顶向下算符优先分析法

这是一篇翻译,原文来自 Top Down Operator Precedence。由于毕设搞的就是相关技术,所以近期花了块两天时间把文章翻译了,实在够累,希望大侠看见,不吝赐教!

作者:Douglas Crockford

简介

1973年,波士顿 Vaughan Pratt编程语言原则座谈会(Principles of Programming Languages Symposium) 第一期年刊上发表 自顶向下算符优先(Top Down Operator Precedence)。在论文中 Pratt 描述了一种结 合递归向下(Recursive Descent)方法 以及 Floyd 算符优先(Operator Precedence)方法 优良特性的解析技术。它非常易用。同时,它看起来很像递归向下,但是却可用更少代码实现以及更高效的性能。他声称这项技术非常易懂,便于实现,方便使用,性能特出,同时也很灵活。它是动态的,支持真正语言级别的扩展。

但是很奇怪,对于编译器编译来说如此优异的方法如今却完全被忽略了。为什么会这样呢?Pratt 在论文中指出,由于更早出现的 BNF 语法以及其各种各样的变种版本,伴随着与之相关的自动机和定理的出现,限制了自动机这种不可见领域的多样发展。

另外一种解释说,他的这种技术只是在应用于动态的,函数式编程语言上才会有很高的效率。将它应用于静态程序语言上则略先困难。在论文中,Pratt 用 LISP 语言基本毫不费力地就从词法单元流中解析出来了语法树。但是这种解析技术却没有在 LISP 社区中体现出太大的价值。自从 LISP 诞生之日起,就有出现很多让它拥有算法似的语法(ALGOL-like syntax),其中包括 Pratts 的 CGOLLISP 2MLISPDylanInterlisp 的 Clisp 以及 McCarthy 的 原始 M 表达式(original M-expressions)。但是最终都没有被接纳。LISP 社区发现协调程序与数据比富裕表达的语法更有价值。但是主流编程社区依然热衷于自己的语法,所以 LISP 从来没被主流接纳过。Pratt 的技术需要一门动态语言,但是动态语言社区历来都没使用过方便 Pratt 的技术解析的那种语法。

JavaScript

随着 JavaScript 的诞生这种情况发生了改变。JavaScript 是一门动态的函数式语言,但是从语法上看它明显是 C 语言风格家族的一员。它是一门动态语言且拥有社区都喜欢的语法。

JavaScript 也拥有面向对象特性。Pratt 1973年的论文预测面向对象将会是一种趋势,但是却缺乏一套富于表达的描述方法。JavaScript 是一门非常适合使用 Pratt 技术的语言。接下来我会用 JavaScript 快速实现一个简单的解析器。

在这么短小的一个章节里,我们没有足够的时间来实现整个 JavaScript,同时我们基本上也不会想去实现,因为语言里面的有一部分是糟粕。但是语言里面依然有一些考虑周全的精华元素。我们将会编写一个只能解析 简化版 JavaScript(Simplified JavaScript) 的解析器。同时我们也会使用简化版的 JavaScript 来编写这个解析器。简化版的 JavaScript 只包含精华的部分,包括:

  • 函数是一级对象。在简化版 JavaScript 中,函数是拥有词法作用域的 lambda 表达式。
  • 原型继承的动态对象。对象是类无关的。我们可以使用普通的赋值方法像任何一个对象中添加一个成员。一个对象可以从另外一个对象中继承其成员。
  • 拥有对象直接量和数组直接量。对于创建新的对象和数组,这是一种绝佳的描述方法。JavaScript 直接量是 JSON 数据接口格式的灵感来源。

我们将充分利用 JavaScript 原型继承的先天特性让词法单元继承自符号对象(symbols)。我们的实现依赖于 Object.create 方法(这个方法是创建一个新对象,并从一个已存在的对象中继承成员)以及一个词法单元生成器(tokenizer)(这个方法是从一个字符串里面生成一个包含简单词法单元对象的数组)。我们在这个词法单元的数组中逐步前进,生成我们的解析树。

符号表

每一个词法单元,例如操作符和标识符,都继承自一个符号对象。我们把所有的符号都保存在 symbol_table 对象(这个符号表是用来判断我们语言中词法单元的类型)中。

var symbol_table = {};

这个 original_symbol 对象是所有其他符号的原型。它其中的方法同时是被用来重写(overridden)的。(我们将会在接下来的优先级一节来解释 nudled 的作用以及约束力的含义)

var original_symbol = {
    nud: function() {
        this.error('Undefined.');
    },
    led: function(left) {
        this.error('Missing operator.');
    }
};

让我们来定义一个生成符号的函数。它包含一个符号 id 和一个可选的约束力值,默认为0。函数返回一个对应 id 的符号对象。如果这个符号已经存在于 symbol_table 中,则函数就直接返回那个符号对象。否则,就创建一个继承于 original_symbol 的符号对象,存储在符号表中,并返回这个对象。一个符号对象初始的时候包含一个 id,一个符号值,一个左约束力,以及其他从 original_symbol 中继承的元素。

var symbol = function(id, bp) {
    var s = symbol_table[id];
    bp = bp || 0;
    if (s) {
        if (bp >= s.lbp) {
            s.lbp = bp;
        }
    } else {
        s = Object.create(original_symbol);
        s.id = s.value = id;
        s.lbp = bp;
        symbol_table[id] = s;
    }
    return s;
};

下列是常见的分隔符号和结束符号。

symbol(':');
symbol(';');
symbol(',');
symbol(')');
symbol(']');
symbol('}');
symbol('else');

(end) 符号表示词法单元流的结束。(name) 符号是新命名符号的原型,例如变量名。包含在 id 两边的括号主要是用来防止与用户定义的词法单元冲突。

symbol('(end)');
symbol('(name)');

词法单元

我们假设源代码已经被转换成一个包含简单词法单元对象(tokens)的数组,每一个对象有一个类型(type)成员(包含名称(name),字符串(string),数字(number)或者操作符(operator))以及一个值(value)成员(是字符串或者数字)。

token 变量总是指向当前的词法单元。

var token;

advance 方法从数组中的下一个简单词法单元创建一个新的词法单元对象,并且赋值给 token 变量。它拥有一个可选参数 id 用来检查是否和之前一个词法单元匹配。新的词法单元对象的原型是当前作用域中的 (name) 词法单元或者是符号表中的一个符号。新的词法单元的 arity(运算元) 是 名称(name),直接量(literal)或者操作符(operator)。arity 随后也可能根据我们了解更多该词法单元在程序中的角色而变化成二元运算(binary),一元运算(unary)或者语句(statement)。

var advance = function(id) {
    var a, o, t, v;
    if (id && token.id !== id) {
        token.error('Expected "' + id + '".');
    }
    if (token_nr >= tokens.length) {
        token = symbol_table['(end)'];
        return;
    }
    t = tokens[token_nr];
    token_nr += 1;
    v = t.value;
    a = t.type;
    if (a === 'name') {
        o = scope.find(v);
    } else if (a === 'operator') {
        o = symbol_table[v];
        if (!o) {
            t.error('Unknown operator.');
        }
    } else if (a === 'string' || a === 'number') {
        a = 'literal';
        o = symbol_table['(literal)'];
    } else {
        t.error('Unexpected token.');
    }
    token = Object.create(o);
    token.value = v;
    token.arity = a;
    return token;
};

阅读全文…

也谈排序算法

最近期末复习正好看到算法的分治策略,里面讲到两种排序算法:合并排序和快速排序。这里大概就谈下自己对算法的理解,代码不是最重要的,思想才是精华,所以这次不打算讲太多代码。

首先说一下分治法的基本思想,分治法是把一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同(这里需要注意分治算法与动态规划的区别)。递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这里要谈到的合并排序和快速排序便是分治算法的典型应用之一。

首先看合并排序,其基本思想是将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行排序,最终讲排好序的子集合合并成为所要求的排好序的集合。算法一般通过计算两个边界的中点作为分界点,然后再递归调用对左半边和右半边分别合并排序,递归中止条件自然是左边界小于右边界,即保证至少有两个元素参与排序。当一轮调用中,左半边和右半边分别排序完成后(或无法再划分进行排序后),就进行合并,其中对元素的真正排序便是在合并中完成的,利用一个临时数组完成对排序后数组两边元素的排序、合并。如下是一个合并排序的过程图,其中S代表mergeSort函数,即递归函数,其中参数待排序数组,左分界点,右分界点;m代表merge函数,即排序、合并函数,其参数分别为待合并数组,目的合并数组,合并左分界点,合并中点,合并右分界点。

mergesort

再来看看快速排序,其基本思想是对于输入的子数组a[p:r],按以下3个步骤进行排序:

  1. 分解(divide):以a[p]为某基准元素,将a[p:r]划分成3段,a[p:q-1], a[q]和a[q+1:r],使得a[p:q-1]中的任何元素都小于等于a[q],而a[q+1:r]中的任何元素大于等于a[q],q在划分中确定;
  2. 递归求解(conquer):通过递归调用快速排序算法,分别对a[p:q-1]和a[q+1:r]进行排序;
  3. 合并(merge):由于对a[p:q-1]和a[q+1:]r的排序在分解过程中就已经完成,所以当前a[p:q-1]和a[q+1:r]中的元素都已经排好序了,无须再执行任何计算,a[p:r]就已经完成排序了。

如下以a = [5, 3, 7, 2, 6, 4, 8, 1, 9]为例,具体分析一下快速排序的过程,【】表示划分元素,{}表示需交换元素。

quicksort

由上述分别对两种算法的说明,大致也能看出两算法的异同之处。两种算法都考虑到使用划分元素的方法进行分治的依据,但合并排序的划分元素是直接去两边界的中点,而快速排序的划分点则是在排序中找到;合并排序首先进行划分,然后再对划分的部分递归调用,而快速排序则是在排序过程中找到划分点,之后再递归调用;再次,合并排序需要借助一个临时数组完成合并操作,而快速排序则不需要特别地合并操作,也无需临时数组,其排序是在划分中完成,而合并则只需简单连接即可。

虽然自己已经对上述算法有了比较具体的了解,但是要深入理解还是需要慢慢体会,领悟其中玄机,同时也需要在不参考参考程序的过程中,完成自己程序的编写,这样不但锻炼了编程能力,更加需要对算法本身有较透彻的理解,所以下一步自己需要用一门语言用自己的方法实现算法。

不同进制之间的转换的各种方法

不同进制之间的转换纯粹是数学上的计算。不过,你不必担心会有么复杂,无非是乘或除的计算。
生活中其实很多地方的计数方法都多少有点不同进制的影子。

比如我们最常用的10进制,其实起源于人有10个指头。如果我们的祖先始终没有摆脱手脚不分的境况,我想我们现在一定是在使用20进制。

至于二进制……没有袜子称为0只袜子,有一只袜子称为1只袜子,但若有两袜子,则我们常说的是:1双袜子。

生活中还有:七进制,比如星期。十二进制,比如“一打”,六十进制,比如分钟……

一、为什么需要八进制和十六进制?

编程中,我们常用的还是10进制……必竟VB是高级语言。
比如:a = 99;
不过,由于数据在计算机中的表示,最终以二进制的形式存在,所以有时候使用二进制,可以更直观地解决问题。但是二进制数太长了。比如int 类型占用4个字节,32位。比如100,用int类型的二进制数表达将是:0000 0000 0000 0000 0110 0100
面对这么长的数进行思考或操作,没有人会喜欢。因此,C,C++ 没有提供在代码直接写二进制数的方法。
 
用16进制或8进制可以解决这个问题。因为,进制越大,数的表达长度也就越短。不过,为什么偏偏是16或8进制,而不其它的,诸如9或20进制呢?

2、8、16,分别是2的1次方,3次方,4次方。这一点使得三种进制之间可以非常直接地互相转换。8进制或16进制缩短了二进制数,但保持了二进制数的表达特点。在下面的关于进制转换的课程中,你可以发现这一点。 阅读全文…

C#解决数学问题

在VF看见的一个题目:
HOHO,占字符……

计算:1/2×3+1/3×4+1/4×5+.....1/99×100

写了个基本程序,不过无法实现分数显示结果

using System;
using System.Collections.Generic;
using System.Text;

namespace Solve_1
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = 2;
            int b = 3;
            float ans = 0;
            while (b < = 100)
            {
                float num1 = (float)a;
                float num2 = (float)b;
                ans =ans + 1 / num1 * num2;
                a++;
                b++;
             }
             Console.WriteLine(ans);
        }
    }
}

阅读全文…

C#第三章练习3.9.4

第三章的另一个练习
简单的加密

using System;
using System.Collections.Generic;
using System.Text;

namespace Chapter03Exercise394
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("What do you want to do? Encrypt(E) Or Crack(C)");
            string m = Console.ReadLine();
            if (m == "E" || m == "e")
            {
                Console.WriteLine("Please input what you want to encrypt");
                string str1 = Console.ReadLine();
                int count1 = str1.Length;
                for (int i = 0; i < count1; i++)
                {
                    char temp1 = str1[i];
                    int pass = (int)temp1;
                    pass = pass + 5;
                    char temp2 = (char)pass;
                    Console.Write(temp2);
                }
                Console.ReadLine();
            }

            else if (m == "C" || m == "c")
            {
                Console.WriteLine("Please input what you want to crack");
                string str2 = Console.ReadLine();
                int count2 = str2.Length;
                for (int i = 0; i < count2; i++)
                {
                    char temp1 = str2[i];
                    int pass = (int)temp1;
                    pass = pass - 5;
                    char temp2 = (char)pass;
                    Console.Write(temp2);
                }
                Console.ReadLine();
            }
            else
            {
                Console.WriteLine("Input Error!!!");
                Console.ReadLine();
            }
        }
    }
}
Page 1 Of 3123