自上而下的运算符优先级(2007)

2020-12-17 04:45:06

沃恩·普拉特(Vaughan Pratt)提出了“自上而下的运算符优先级”。在1973年于波士顿举行的第一届年度编程语言原理研讨会上,Pratt描述了一种结合了递归下降和Floyd运算符优先级的最佳属性的解析技术。这个用起来很简单。感觉很像递归下降,但是需要更少的代码,并且需要明显更好的性能。他声称该技术易于理解,易于实施,易于使用,极其高效且非常灵活。它是动态的,为真正的可扩展语言提供支持。

奇怪的是,这种明显的乌托邦式的编译器构建方法如今已被完全忽略。为什么是这样?普拉特(Pratt)在论文中提出,对BNF语法及其各种后代以及与之相关的自动机和定理的全神贯注,已经排除了在自动机理论领域不明显的方向上的发展。

另一个解释是,他的技术在动态功能编程语言中使用时最有效。以静态的程序语言使用它会更加困难。在本文中,Pratt使用LISP并几乎毫不费力地从令牌流中构建了解析树。但是解析技术在LISP社区中并没有得到很高的重视,该社区赞扬Spartan拒绝语法。自从LISP创建以来,已经进行了许多尝试,以使该语言具有丰富的类似于ALGOL的语法,包括Pratt的CGOL,LISP 2,MLISP,Dylan,Interlisp的Clisp和McCarthy's。的原始M表达式。所有人都没有找到接受的机会。该社区发现程序和数据之间的对应关系比表达语法要有价值得多。但是主流编程社区喜欢它的语法,因此LISP从未被主流接受。 Pratt的技术需要一种动态语言,但是动态语言社区历史上一直没有使用Pratt的技术方便地实现的语法。

随着JavaScript的出现,情况发生了变化.JavaScript是一种动态的功能语言,但从语法上讲,它显然是C系列的成员。这是一种动态语言,社区喜欢语法。

JavaScript也是面向对象的。普拉特(Pratt)于1973年发表的论文曾预言过面向对象,但缺乏针对性的表述。 JavaScript是开发Pratt技术的理想语言。我将展示我们可以用JavaScript快速廉价地生成解析器。

我们在本简短的章节中没有时间来处理整个JavaScript语言,也许我们不想因为这是一团糟。但是其中有一些很棒的东西值得考虑。我们将构建一个可以处理简化JavaScript的解析器。我们将使用简体JavaScript编写解析器。简化的JavaScript就是好东西,包括:

具有原型继承的动态对象。对象是无类的。我们可以通过普通分配将新成员添加到任何对象。一个对象可以从另一个对象继承成员。

对象文字和数组文字。这是用于创建新对象和数组的非常方便的表示法。 JavaScript文字是JSON数据交换格式的灵感来源。

我们将利用JavaScript的原型性质来制作从符号继承的令牌对象。我们的实现依赖于Object.create方法(该方法使新对象继承现有对象的成员)和令牌生成器(令牌生成器从字符串生成简单令牌对象的数组)。随着解析树的增长,我们将逐步通过这组标记。

每个令牌(例如运算符或标识符)都将从符号继承。我们将所有符号(决定我们语言中标记的类型)保留在symbol_table对象中。

original_symbol对象是所有其他符号的原型。它的方法通常会被覆盖。 (我们将在下面的“优先顺序”部分中描述裸露,领导和约束力的作用)。

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;如果(s){如果(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;};

(结束)符号表示令牌流的结束。 (名称)符号是新名称(例如变量名称)的原型。这些符号的ID中包含的括号可避免与用户定义的令牌发生冲突。

我们假定源文本已转换为简单令牌对象(令牌)的数组,每个令牌对象都包含类型成员(" name&#34 ;、" string&#34 ;、" number&# 34;或" operator"),以及值成员,该成员是字符串或数字。

Advance函数从数组中的下一个简单标记中创建一个新的标记对象,并将其分配给标记变量。它可以采用可选的id参数,该参数可以对照前一个令牌的id进行检查。新令牌对象的原型是当前作用域中的(名称)令牌或符号表中的符号。新令牌的名称是“名称”,“文字”或“运营商”。以后可以将其友善性更改为" 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)"];返回; } t =令牌[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];如果(!o){t.error("未知运算符。"); }} if if(a ===" string" || a ===" number"){a =" literal&#34 ;; o = symbol_table ["(literal)"]; } else {t.error("意外令牌。"); }令牌= Object.create(o); token.value = v; token.arity = a;返回令牌;};

大多数语言都有一些定义新符号(例如变量名)的符号。用一种非常简单的语言,当我们遇到一个新单词时,我们可以给它一个定义并将其放在符号表中。在更复杂的语言中,我们希望具有作用域,从而使程序员可以方便地控制变量的寿命和可见性。

作用域是程序中定义和访问变量的区域。合并范围可以嵌套在其他合并范围内。范围内定义的变量在范围外不可见。

original_scope是所有作用域对象的原型。它包含一个define方法,该方法用于定义范围内的新变量。 define方法将名称标记转换为变量标记。如果变量已经在作用域中定义,或者名称已经用作保留字,则会产生错误。

var original_scope = {定义:函数(n){var t = this.def [n.value]; if(typeof t ===" object"){n.error(t.reserved?" Already。":"已经定义。"); } this.def [n.value] = n; n.reserved =假; n.nud =本身; n.led = null; n.std = null; n.lbp = 0; n.scope =作用域;返回n; },

find方法用于查找名称的定义。它从当前作用域开始,并在必要时从父作用域链中寻找,最后到符号表。如果找不到定义,则返回symbol_table ["(name)"]。

find方法测试其发现的值,以确定它们不是未定义的(这将表明未声明的名称),也不是函数(这将表明与继承的方法发生冲突)。

查找:函数(n){var e = this,o; while(true){o = e.def [n]; if(o&& typeof o!==' function'){return e.def [n]; } e = e.parent;如果(!e){o = symbol_table [n];返回o&& typeof o!=='功能' ? o:symbol_table ["(name)"]; }}},

reserve方法用于指示名称已在当前作用域中用作保留字。

reserve:function(n){if(n.arity!==" name" || n.reserved){返回; } var t = this.def [n.value]; if(t){if(t.reserved){返回; } if(t.arity ===" name"){n.error("已经定义。"); }} this.def [n.value] = n; n.reserved = true; }};

我们需要保留字的政策。在某些语言中,保留结构上使用的单词(例如if),并且不能将其用作变量名。解析器的灵活性使我们可以制定更有用的策略。例如,我们可以说在任何函数中,任何名称都可以用作结构词或变量,但不能同时用作两者。仅当它们用作保留字后,我们才会在本地保留这些字。这对语言设计人员来说是件好事,因为在语言中添加新的结构词不会破坏现有程序,对程序员来说则更好,这是因为它们不受名称使用的不相关限制的困扰。

每当我们要为函数或块建立新作用域时,我们都将调用new_scope函数,该函数将为原始作用域原型提供新实例。

var new_scope = function(){var s = scope;作用域= Object.create(original_scope); scope.def = {}; scope.parent = s;返回范围;};

令牌是带有方法的对象,这些方法允许它们做出优先级决策,与其他令牌匹配并构建树(并且在更具野心的项目中,还检查类型并优化和生成代码)。基本优先级问题是这样的:给定两个运算符之间的操作数,该操作数是绑定到左运算符还是右运算符?

如果Ⓐ和Ⓑ是运算符,则操作数e绑定到Ⓐ还是Ⓑ?换句话说,我们在谈论

最终,解析过程的复杂性归结为这种歧义的解决。我们将在此处开发的技术使用令牌对象,其成员包括绑定能力(或优先级),以及称为nud(空符号)和led(左侧符号)的简单方法。裸露不关心左侧的标记。一个领导。值(例如变量和文字)和前缀运算符使用nud方法。前缀运算符和后缀运算符使用led方法。令牌可以同时具有nud方法和led方法。例如,-可能既是前缀运算符(否定)又是中缀运算符(减法),因此它同时具有nud和led方法。

普拉特技术的核心是表达功能。它具有权限绑定功能,该权限控制它在多大程度上积极地绑定到其右侧的令牌。

var expression = function(rbp){var left; var t =令牌;提前();左= t.nud(); while(rbp< token.lbp){t =令牌;提前();左= t.led(左); }返回左;}

表达式调用令牌的nud方法。 nud用于处理文字,变量和前缀运算符。然后,只要右绑定能力小于下一个标记的左绑定能力,就会在下一个标记上调用led方法。 led用于处理中缀和后缀运算符。该过程可以是递归的,因为nud和led方法可以调用表达式。

+运算符是一个infix运算符,因此它具有led方法,该方法将令牌对象编织到一棵树中,该树的两个分支(第一个和第二个)是+左边的操作数和右边的操作数。左操作数被传递到led中,然后通过调用表达式函数来获得右操作数。

symbol(" +&#34 ;, 50).led = function(left){this.first = left; this.second =表达式(50); this.arity =" binary&#34 ;;返回此;};

*的符号与ID相同,除了id和绑定力。它具有更高的结合力,因为它结合得更紧密。

symbol(" *&#34 ;, 60).led = function(left){this.first = left; this.second =表达式(60); this.arity =" binary&#34 ;;返回此;};

并非所有的中缀运算符都将是相似的,但是很多会相似,因此我们可以通过定义一个中缀函数来简化工作,该函数将帮助我们为中缀运算符制作符号。中缀函数具有id,绑定力和可选的led函数。如果未提供led功能,则infix函数将提供在大多数情况下有用的默认led。

var infix = function(id,bp,led){var s = symbol(id,bp); s.led = led ||函数(左){this.first = left; this.second =表达式(bp); this.arity =" binary&#34 ;;返回这个}; return s;}

三元运算符采用三个表达式,以?和:分隔。它不是普通的中缀运算符,因此我们需要提供其led函数。

infix("?&#34 ;, 20,函数(左){this.first = left; this.second = expression(0); advance(":"); this.third = expression(0); this.arity =" ternary&#34 ;;返回this;});

的。运算符用于选择对象的成员。右侧的令牌必须是名称,但是它将用作文字。

infix("。&#34 ;, 80,function(left){this.first = left; if(token.arity!==" name"){token.error(&#34 ;期望的属性名称。}} token.arity =" literal&#34 ;; this.second = token; this.arity =" binary&#34 ;; advance();返回这个;});

[运算符用于从对象或数组中动态选择成员。右边的表达式后面必须带有一个结束[]。

infix(" [&#34 ;, 80,function(left){this.first = left; this.second = expression(0); this.arity =" binary&#34 ;; advance(& #34;]");返回此;});

这些中缀运算符保留关联性。我们还可以通过减小权限绑定能力来创建权限关联运算符,例如短路逻辑运算符。

var infixr = function(id,bp,led){var s = symbol(id,bp); s.led = led ||函数(左){this.first = left; this.second = expression(bp-1); this.arity =" binary&#34 ;;返回这个}; return s;}

&&如果第一个操作数为falsy,则operator返回第一个操作数。否则,它返回第二个操作数。 ||如果第一个操作数为真,则运算符返回第一个操作数。否则,它返回第二个操作数。 (伪造的值是数字0,空字符串""的值是false和null。所有其他值(包括所有对象)都是真实的。)

我们用于正确的关联中缀运算符的代码可以改编为前缀运算符。前缀运算符是正确的关联。前缀没有左绑定能力,因为它没有绑定到左边。前缀运算符有时也可以是保留字。

var prefix = function(id,nud){var s = symbol(id); s.nud =裸体||功能(){scope.reserve(this); this.first = expression(70); this.arity ="一元&#34 ;;返回这个}; return s;}

(将调用()的nud匹配平衡的)标记。 (标记不会成为解析树的一部分,因为nud返回内部表达式。

我们可以使用infixr来定义赋值运算符,但是我们将创建一个专门的赋值函数,因为我们希望它完成两个额外的工作:检查左操作数以确保它是正确的左值,并设置赋值成员,以便以便我们稍后可以快速识别赋值语句。

var Assignment = function(id){return infixr(id,10,function(left){if(left.id!=="。"&&left; id!==&#34 ; [&& left.arity!==" name"){left.error(" Bad lvalue。");} this.first = left; this.second = expression(9); this.assignment = true; this.arity =" binary&#34 ;;返回this;});};

请注意,我们已经实现了一种继承模式,其中赋值返回调用infixr的结果,而infixr返回调用symbol的结果。

constantfunction将常量构建到语言中。裸名将名称标记转换为文字标记。

var constant = function(s,v){var x = symbol(s); x.nud = function(){scope.reserve(this); this.value = symbol_table [this.id] .value; this.arity =" literal&#34 ;;返回这个}; x.value = v;返回x;};

(文字)符号是所有字符串和数字文字的原型。文字标记的nud方法返回标记本身。

普拉特(Pratt)的原始表述使用了功能性语言,其中一切都是表达。大多数主流语言的语句不如表达式可嵌套。我们可以通过向标记添加另一种方法std(语句表示)来轻松处理语句。 std类似于nud,只是仅在语句的开头使用它。

语句函数解析一条语句。如果当前令牌具有std方法,则保留该令牌并调用std。否则,我们假设一个表达式表达式以分号结尾。为了可靠性,我们将拒绝不是赋值或调用的表达式语句。

var statement = function(){var n =令牌,v;如果(n.std){advance(); scope.reserve(n);返回n.std(); } v =表达式(0); if(!v.assignment&& v.id!=="("){v.error(" Bad expression statement。");} advance(&# 34 ;;");返回v;};

语句函数分析语句,直到看到(end)或}表示块结束为止。该函数返回一条语句,一组语句;如果不存在任何语句,则返回null。

var语句= function(){var a = [],s; while(true){if(token.id ==="}" || token.id ==="(end)"){break; } s = statement();如果({a.push(s);返回a.length === 0吗? null:a.length === 1吗? a [0]:a;};

stmt函数用于将语句符号添加到符号表。它需要一个语句id和一个std函数。

var stmt = function(s,f){var x = symbol(s); x.std = f;返回x;};

block语句将一对花括号括在语句列表周围,从而赋予它们新的作用域。 (JavaScript没有阻止范围。简化的JavaScript可以纠正这一点。)

var语句在当前块中定义一个或多个变量。每个名称都可以选择后面跟有=和初始化表达式。

stmt(" var&#34 ;, function(){var a = [],n,t; while(true){n =令牌; if(n.arity!==" name" ){n.error("期望一个新的变量名。");} scope.define(n); advance(); if(token.id ===" =&#34 ;){t =令牌; advance(" ="); t.first = n; t.second = expression(0); t.arity =" binary&#34 ;; a。 push(t);} if(token.id!==","){break;} advance(",");} advance(&#34 ;;& #34;);返回a.length === 0?null:a.length === 1?a [0]:a;});

while语句定义一个循环。 它包含一个以括号为单位的表达式和一个块。 stmt(" while&#34 ;, function(){advance("("); this.first = expression(0); advance(")"); this.second = block(); this.arity =" statement&#34 ;;返回this;}); if语句允许条件执行。 如果在该块之后看到else符号,那么我们将分析下一个块或if语句。 stmt(" if&#34 ;, function(){advance("("); this.first = expression(0); advance(")"); 这个.secon ......