Parsing Expressions by Recursive Descent (1999)

Theodore Norvell (C) 1999 with updates in a while.

This text is ready parsing expressions such as a*b – a*d – e*f the use of a plot is named recursive descent. I’ve assumed you know no not as a lot as rather bit about context-free grammars and parsing.

Parsing expressions by recursive descent poses two classic complications

1. easy suggestions to catch the summary syntax tree (or other output) to follow the priority and associativity of
   operators and
2. easy suggestions to realize so efficiently when there are lots of phases of priority.

The classic formula to basically the most necessary whisper doesn’t clear up the 2d. I will latest the
classic solution, a neatly-known replacement is named the “Shunting Yard
Algorithm”, and a much less neatly-known one which I truly absorb known as “Precedence
Rock climbing”.  

Contents

• An example grammar for expressions
• Recursive-descent recognition
• The shunting yard algorithm
• The classic solution
• Precedence hiking
• Deriving priority hiking
• Bibliographic Notes

An example grammar for expressions

Consider the following example grammar, G,

    E --> E "+" E
        | E "-" E
        | "-" E
        | E "*" E
        | E "/" E
        | E "^" E
        | "(" E ")"
        | v

whereby  v  is a terminal representing identifiers and/or constants.

We want to make a parser that can

1. Make an error message if its input just isn’t in the language of this grammar.
2. Make an “summary syntax tree” (AST) reflecting the structure of the input,
   if the input is in the language of the grammar.

Each input in the language can absorb a single AST based totally on the following priority and
associativity solutions:

• Parentheses absorb priority over all operators.
• ^ (exponentiation) has priority over unary – and the binary operators /, *, -, and +.
• and / absorb priority over unary – and binary – and +.
• Unary – has priority over binary – and +.
• ^ is fantastic associative while all other binary operators are left associative.

For example basically the most necessary three solutions account for us that

    a ^ b c ^ d + e ^ f / g ^ (h + i)

parses to the tree

    +( *( ^(a,b), ^(c,d) ), /( ^(e,f), ^(g,+(h,i)) ) )

while the closing rule tells us that

    a - b - c

parses to -(-(a,b),c) in procedure of -(a,-(b,c)), whereas

    a ^ b ^ c

parses to ^(a, ^(b,c)) in procedure of ^(^(a,b), c).

The priority of binary ^ over unary – tells us that

    - a ^ - b

parses to -(^(a, -(b))). Some programming language designers snatch to put unary operators at the most effective degree of priority. I selected to present unary – a lower priority than *, /, and ^ because having some binary operators with better priority than some unary operators makes the parsing whisper correct a bit extra not easy and raises some complications that otherwise wouldn’t plot up.

Recursive-descent recognition

The basis of recursive-descent parsing is to rework each and every nonterminal of a grammar
into a subroutine that can acknowledge precisely that nonterminal in the input.

Left recursive grammars, such as G, are unhealthy for recursive-descent parsing because a left-recursive manufacturing
leads to an unlimited recursion. While the parser will be
partly fantastic, it will additionally just not discontinuance.

We can turn out to be G to an equivalent non-left-recursive grammar G1 as follows:

    E --> P {B P}
    P --> v | "(" E ")" | U P
    B --> "+" | "-" | "*" | "/" | "^"
    U --> "-"

The braces “{” and “}” signify zero or extra repetitions of what
is inner of them. Thus you can perchance consider of E as having an infinity of choices:

    E --> P | P B P | P B P B P | ... advert infinitum

The language described by this grammar is an identical as that of grammar G, that is, L(G1)=
L(G).

Now not most fascinating is left recursion eliminated, however the G1 is unambiguous and each and every selection may perchance additionally just additionally be made by the
subsequent token in the input.

Let’s detect at a recursive descent recognizer based totally on this grammar. I name
this algorithm a recognizer in procedure of a parser because all it does is to acknowledge whether or not the input is in
the language of the grammar or not. It doesn’t invent an summary syntax
tree, or every other create of output that represents the contents of the input.

I will have interaction that the following subroutines exist:

• “subsequent” returns the following token of input or particular marker “end” to
  signify that there don’t appear to be any extra input tokens. “subsequent” doesn’t alter the input
  stream.
• “utilize” reads one token. When “subsequent=end“, utilize is mute
  allowed, but has no design.
• “error” stops the parsing direction of and experiences an error.

Using these, let’s kind a subroutine “put a question to“, which I will use
in the center of this essay

put a question to( tok ) is
   if subsequent=tok 
       utilize
   else
       error

We can now write a subroutine known as “Erecognizer“. If it doesn’t name
“error“, then the input was an expression in response to the above grammars. If it
does name “error“, then the input contained a syntax error, e.g., unmatched
parentheses, a missing operator or operand, and loads others.

Erecognizer is
   E()
   put a question to( end )

E is
    P
    while subsequent is a binary operator
       utilize
       P

P is
    if subsequent is a v
         utilize
    else if subsequent="("
         utilize
         E
         put a question to( ")" )
    else if subsequent is a unary operator
         utilize
         P
    else
         error

Know how the structure of the recognition algorithm mirrors the structure of the
grammar. Here is the essence of recursive descent parsing.

The variation between a recognizer and a parser is that a parser produces some roughly
output that reflects the structure of the input. Subsequent we’ll detect at a arrangement to alter the
above recognition algorithm to be a parsing algorithm. This may perchance additionally just make an AST, in response to
the priority and associativity solutions, the use of a plot is named the “shunting
yard” algorithm.

The shunting yard algorithm

The basis of the shunting yard algorithm is to preserve operators on a stack except each and every their operands were parsed. The operands are saved on a 2d stack. The
shunting yard algorithm may perchance additionally just additionally be veteran to at as soon as overview expressions as they’re parsed
(it’s commonly veteran in digital calculators for this job), to create a reverse Polish
notation translation of an infix expression, or to create an summary syntax tree. I will
create an summary syntax tree, so my operand stacks will absorb trees.

The fundamental to the algorithm is to preserve the operators on the operator stack ordered by priority (lowest at bottom and perfect at high), no not as a lot as in the absence of parentheses. Sooner than pushing an operator onto the operator stack, all better priority operators are cleared from the stack. Clearing an operator consists of casting off the operator from the operator stack and its operand(s) from the operand stack, making a original tree, and pushing that tree onto the operand stack. At the end of an expression the
final operators are put into trees with their operands and that is that.

The next desk illustrates the plot for an input of x*y+z. Stacks are written with their tops to the left. The sentinel rate acts as an operator of lowest priority.

Compare this to parsing x + y z.

As neatly as to “subsequent“, “utilize“, “end“,
“error“, and “put a question to“, that are outlined in the previous part, I
will have interaction that the following subroutines and constants exist:

• “binary” converts a token matched by B to an operator.
• “unary” converts a token matched by U to an operator. We require that
  capabilities “unary” and “binary” absorb disjoint ranges. (For example unary(“-“) and binary(“-“) should always not equal.)
• “mkLeaf” converts a token matched by v to a tree.
• “mkNode” takes an operator and one or two trees and returns a tree.
• “push“, “pop“, “high“: the conventional stack operations.
• “empty“: an empty stack
• “sentinel” is a ticket that just isn’t in the fluctuate of both unary or binary.

In the algorithm that follows, I study operators and the sentinel with a> stamp.
This comparability is printed as follows:

• binary(x)> binary(y), if x has better priority than y, or x is left associative
  and x and y absorb equal priority.
• unary(x)> binary(y), if x has priority better or equal to y’s
• op> unary(y), never (the place op is any unary or binary operator)
• sentinel> op, never (the place op is any unary or binary operator)
• op> sentinel  (the place op is any unary or binary operator): This case doesn’t
  come up.

Now we outline the following subroutines:

Eparser is
   var operators : Stack of Operator :=empty
   var operands : Stack of Tree :=empty
   push( operators, sentinel )
   E( operators, operands )
   put a question to( end )
   return high( operands )

E( operators, operands ) is
    P( operators, operands )
    while subsequent is a binary operator
       pushOperator( binary(subsequent), operators, operands )
       utilize
       P( operators, operands )
    while high(operators) not=sentinel
       popOperator( operators, operands )

P( operators, operands ) is
    if subsequent is a v
         push( operands, mkLeaf( v ) )
         utilize
    else if subsequent="("
         utilize
         push( operators, sentinel )
         E( operators, operands )
         put a question to( ")" )
         pop( operators )
    else if subsequent is a unary operator
         pushOperator( unary(subsequent), operators, operands )
         utilize
         P( operators, operands )
    else
         error

popOperator( operators, operands ) is
   if high(operators) is binary
        const t1 :=pop( operands )
        const t0 :=pop( operands )
        push( operands, mkNode( pop(operators), t0, t1 ) )
   else
        push( operands, mkNode( pop(operators), pop(operands) ) )

pushOperator( op, operators, operands ) is
    while high(operators)> op
       popOperator( operators, operands )
    push( op, operators )

Usually the shunting yard algorithm is presented with out the use of recursion. This will probably be extra ambiance suitable and may perchance wait on in producing better error messages, but I rating the code a bit more difficult to be conscious.

The classic solution

The classic formula to recursive-descent parsing of expressions is to create a original
nonterminal for each and every degree of priority as follows. G2:

    E --> T {( "+" | "-" ) T}
    T --> F {( "*" | "/" ) F}
    F --> P ["^" F]
    P --> v | "(" E ")" | "-" T

(The brackets [ and ] enclose an non-compulsory phase of the manufacturing. As earlier than, the braces
{ and } enclose plot of the productions that may be repeated 0 or extra instances, and | separates choices. The
unquoted parentheses ( and ) encourage most fascinating to neighborhood plot in a manufacturing.)

Grammar G2 describes the same language because the previous two grammars: L(G2)=L(G1)
=L(G)

The grammar is ambiguous; for instance, -x*y has two parse trees: E(T(F(P(“-“, T(F(P(“x”)), “*”))))) and E(T(F(P(“-“,T(F(P(“x”))))),”*”,F(P(“y”)))). The ambiguity is
resolved by staying in each and every loop (in the productions for E and T) as lengthy as probably and
by taking the chance —if probably— in the manufacturing for F. With these coverage in procedure, all
choices may perchance additionally just additionally be made by searching most fascinating at the following token of input.

Show conceal that the left-associative and the fantastic-associative operators are handled
in a utterly different arrangement; left-associative operators are consumed in a loop, while fantastic-associative
operators are handled with fantastic-recursive productions. Here is to create the tree building
a bit more straightforward.

Here is an example of parsing a*b – c^d – e*f by recursive descent.

Each contour line reveals what is identified by each and every invocation of E, T, or F. As an illustration we are capable of gaze that the end degree name to E invokes T three instances; these three invocations of T respectively acknowledge a*b, c^d, and e*f. Now not proven are the calls to P, of which there’s one for each and every variable. One other arrangement to detect at it’s that the contour traces uncover the parse tree (or would if I would incorporated the contour traces for P). The valid traces uncover the AST that we’d luxuriate in to be constructed.

We can turn out to be this grammar to a parser written in pseudo code.

Eparser is
   var t : Tree
   t :=E
   put a question to( end )
   return t

E is
   var t : Tree
   t :=T
   while subsequent="+" or subsequent="-"
      const op :=binary(subsequent)
      utilize
      const t1 :=T
      t :=mkNode( op, t, t1 )
   return t

T is
   var t : Tree
   t :=F
   while subsequent="*" or subsequent="/"
      const op :=binary(subsequent)
      utilize
      const t1 :=F
      t :=mkNode( op, t, t1 )
   return t

F is
   var t : Tree
   t :=P
   if subsequent="^"
        utilize
        const t1 :=F
        return mkNode( binary("^"), t, t1)
   else
        return t

P is
   var t : Tree
   if subsequent is a v
        t :=mkLeaf( subsequent )
        utilize
        return t
   else if subsequent="("
        utilize
        t :=E
        put a question to( ")" )
        return t   
   else if subsequent="-"
        utilize
        t :=F
        return mkNode( unary("-"), t)
   else 
        error

It may perchance be excellent to stamp this algorithm on a couple of example inputs.

This classic solution has a couple of drawbacks:

• The size of the code is proportional to the amount of priority phases.
• The bustle of the algorithm is proportional to the amount of priority phases.
• The amount of priority phases and the feature of operators is built in.

When there are a monumental quantity of priority phases, as in the C and C++ languages, the
first two disadvantages turn out to be problematic. In Pascal the amount of priority phases was
deliberately saved tiny because —I believe— its designer, Niklaus Wirth, was responsive to the
shortcomings of this plot when the amount of priority phases is monumental.

The size whisper may perchance additionally just additionally be overcome by developing one subroutine that is parameterized by
priority degree in procedure of writing a separate routine for each and every degree. However the bustle
whisper remains. Show conceal that the amount of calls to parse an expression consisting of a
single identifier is proportional to the amount of phases of priority.

For languages whereby the feature of operators and their precedences and associativity should always not laborious-coded, we need a extra flexible plot.

Precedence hiking

A plot that solves the entire listed complications for the classic solution, while being
extra efficient than the shunting-yard algorithm, is what I name “priority hiking”. (Show conceal, on the replacement hand, that we’re going to climb down the priority phases.)

Consider the input sequence

    a ^ b c + d + e

The E subroutine of the classic solution will handle this by three calls to T, and
by provocative the two “+”s, building a tree

+(+(results of first name, results of 2d name), results of third name)

We say that this loop at as soon as consumes the two “+” operators.

The priority hiking algorithm has a the same loop, nonetheless it consistently at as soon as consumes
basically the most necessary binary operator, then it consumes the following binary operator that is of lower
priority, then the following operator that is of lower priority than that. When it consumes
a left-associative operator, the same loop may also utilize the following operator of equal
priority. Let me rewrite the example with operators written at utterly different heights
in response to their priority:

             +   +
         ^   
   a   b   c   d   e

One loop can utilize all 4 operators, developing the tree

+(+(*(^(results of first name, results of 2d name) results of third
name), results of 4th name), results of fifth name)

Each operator is assigned a priority quantity. To create things extra fascinating lets add
a couple of extra binary operators and use the following priority tables:

We use the following grammar G3, whereby nonterminal Exp is parameterized by a
priority degree. The basis is that Exp(p) acknowledges expressions which absorb no binary
operators (rather then in parentheses) with priority not as a lot as p

E --> Exp(0) 
Exp(p) --> P {B Exp(q)} 
P --> U Exp(q) | "(" E ")" | v
B --> "+" | "-"  | "*" |"/" | "^" | "||" | "&&" | "="
U --> "-"

The loop implied by the braces, { and }, in the manufacturing for Exp(p) offers a
whisper: when may perchance additionally just mute the loop be exited? This selection is resolved as follows:

• If the following token is a binary operator and the priority of that operator is better or
  equal to p,
           then the loop is (re)entered.
• In every other case the loop is exited.

In the productions for Exp(p) and P, the recursive use of Exp is parameterized, by a
rate q. So there is a 2d selection to catch to the underside of: how is q chosen? The rate of q is chosen
in response to the previous operator:

• In the binary operator case:
  • if the binary operator is left associative, q=the priority of the operator + 1,
  • if the binary operator is fantastic associative,  q=the priority of the
    operator.
• After unary operators, 
  • q=the priority of the operator.

 Consider what’s going to happen in parsing the expression,  a b – c d – e f
=g h – i j – okay l. To create things clearer, I will latest this expression 2
dimensionally to uncover the precedences of the operators:

        
2                      =
3           -     -           -     -
5        a b   c d   e f   g h   i j   okay l
         0  0     0     0    

The choice to Exp(0) will at as soon as utilize precisely the operators indicated by a 0 below. The
sub-expressions: a, b, c*d, e*f, and g*h-i*okay-okay*l will be parsed by calls to P and Exp(6),
Exp(4), Exp(4) and Exp(3) respectively. The total parse is illustrated by

On this image, each and every name to Exp is indicated by a dashed contour. The amount at as soon as inner the contour indicates the cost of the p parameter. Now not proven are the calls to P, of which there’s one for each and every variable, in this case.

What about fantastic-associative operators? Consider an expression

         a^b^c

Attributable to fully different plot fantastic-associative operators are handled, Exp(0) will most fascinating
at as soon as utilize basically the most necessary ^, because the 2d will be devoured up by a recursive name to Exp(6).

A recursive-descent parser based totally on this plot looks luxuriate in this:

Eparser is
   var t : Tree
   t :=Exp( 0 )
   put a question to( end )
   return t

Exp( p ) is
    var t : Tree
    t :=P
    while subsequent is a binary operator and prec(binary(subsequent))>=p
       const op :=binary(subsequent)
       utilize
       const q :=case associativity(op)
                  of Correct: prec( op )
                     Left:  1+prec( op )
       const t1 :=Exp( q )
       t :=mkNode( op, t, t1)
    return t

P is
    if subsequent is a unary operator
         const op :=unary(subsequent)
         utilize
         q :=prec( op )
         const t :=Exp( q )
         return mkNode( op, t )
    else if subsequent="("
         utilize
         const t :=Exp( 0 )
         put a question to ")"
         return t
    else if subsequent is a v
         const t :=mkLeaf( subsequent )
         utilize
         return t
    else
         error

Implementations

I’ve veteran priority hiking in a JavaCC parser for a subset of C++. That you just too can rating that here. I’ve also
veteran it in a parser based totally on monadic parsing written in Haskell.

Michael Bruce-Lockhart has utilized a desk pushed model of the priority hiking
algorithm. Download it here parser.js and parserTest.htm.

Alex de Kruijff has written an implementation of the priority hiking algorithm as a Java library known as Kilmop. That you just too can rating it here.

Christian Kaps has created an implementation of the priority hiking algorithm in PHP. That you just too can rating it at https://github.com/mohiva/pyramid.

Terrence Parr has utilized the root of priority hiking in model 4 of the ANTLR parser generator. That you just too can study it in his original book.

Matthieu Grandrie utilized priority hiking (and the shunting yard) in Python for for a calculator program.

Ed Davis utilized priority hiking in a tiny calculator written in Minute C.

Deriving priority hiking

Let’s launch with a left-recursive grammar.

S --> E0 end
E0 --> E1 | E1 "=" E1
E1 --> E2 | E1 "+" E2
E2 --> E3 | E2 "*" E3
E3 --> E4 | E3 "!"
E4 --> E5 | E5 "^" E4
E5 --> P
P --> "-" E2 | "(" E0 ")" | v

We absorb (in account for of rising priority)

• a nonassociative binary operator “=” (e.g., “a=b=c” just isn’t in the language of S),
• a left-associative operator “+”,
• a prefix operator “-“
• yet another left-associative operator “*”
• a postfix operator “!”
• an correct-associative operator “^”.

Nonassociative operators don’t appear to be dispute in lots of languages. That’s because we are capable of ban “a=b=c”, nonetheless it’s more difficult to ban “a=(b=c)”. Nonetheless, they’re easy to add to the grammar and create the whisper correct a bit extra fascinating.

This grammar just isn’t unambiguous, nonetheless it nearly is. The ambiguity is because “-” has lower priority than “*” and “^”. For example, -a*b may perchance additionally just additionally be parsed two suggestions: luxuriate in -(a*b) and enjoy (-a)*b. I would not anguish in regards to the ambiguity for now. I will correct dispute that the parse we need is the one who is luxuriate in -(a*b); in a while, we’ll take a look at that our parser truly does invent the fantastic tree for -a*b. There are replacement routes of coping with unary operators; one wait on of the most fresh plot is that a*-b is in the language.

This grammar has each and every a prefix and postfix operators. But there is a refined lack of symmetry between them. Show conceal that a^-b is in the language of S, whereas b!^a just isn’t. In essence, I’m treating postfix operators as binary operators that have not any fantastic operand. We are going to plot lend a hand to this anguish at the very end of this part. In the period in-between, we’ll go the grammar as is.

Show conceal that we are capable of use the same symbol for a prefix or binary operators. (E.g., making ‘-‘ a binary operator as neatly as prefix is completely gorgeous.) Nonetheless, I will have interaction that the sets of postfix and binary operators don’t overlap. The motive is that it’s straight forward to distinguish a unary from a binary operator based totally on the left context: unary operators follow the launch of the expression, left parentheses, binary operators, and unary operators. It’s not so easy to present an clarification for a binary operator from a postfix operator. Additionally if we allow operators to be unary, binary and postfix, there’s extra ambiguity. For example a–b is unambiguous if – is unary and binary, but ambiguous, if – may be postfix.

First transformation: Place away with left recursion and component

There’s a metamorphosis rule that A –> a | A b may perchance additionally just additionally be written as A –> a {b} the place {b} skill 0 or extra b. We can discover rule this to nonterminals E1, E2, and E3.

One other rule says we are capable of rewrite A –> s | s b as A –> s [b], the place [b] skill 0 or 1 b. We discover this to nonterminals E0 and E4.

The final consequence’s

S --> E0 end
E0 --> E1 [ "=" E1 ]
E1 --> E2 { "+" E2 }
E2 --> E3 {"*" E3 }
E3 --> E4 { "!" }
E4 --> E5 [ "^" E4 ]
E5 --> P
P --> "-" E2 | "(" E0 ")" | v

At this point, if we convert to recursive descent code, we catch the “classic” algorithm.

2nd transformation: Substitutions

Subsequent we substitute fantastic-hand sides for left-hand sides. We launch by rewriting E4‘s rule to E4 –> P [“^” E4]. Then E3 may perchance additionally just additionally be rewritten as E3 –> P [“^” E4] { “!” } and we work backwards luxuriate in this to E0. The final consequence’s

S --> E0 end
E0 --> P [ "^" E4 ] { "!" } {"*" E3 } { "+" E2 } [ "=" E1 ]
E1 --> P [ "^" E4 ] { "!" } {"*" E3 } { "+" E2 }
E2 --> P [ "^" E4 ] { "!" } {"*" E3 }
E3 --> P [ "^" E4 ] { "!" }
E4 --> P [ "^" E4 ]
P --> "-" E2 | "(" E0 ")" | v

(E5 just isn’t any longer reachable, so I trashed it.)

Or not it’s a laborious to absorb we’re making growth; absorb with me.

Third transformation: Compaction

Now we want to take wait on of the similarity of the guidelines for E0 through E4. To attain this we need a bit extra notation. First we’ll use a parameterized nonterminal E: so E(n) below will match the same strings as En above. 2nd, I will use the notation ?(B), the place B is a boolean expression, as a “take a look at”. The which technique of a take a look at is that a particular replacement of the grammar can most fascinating be taken when B is fantastic. For example X [ ?(B) Y] skill the same as X [Y] when B is fantastic, but skill the same as X when B is fake. Here is the compacted grammar.

S --> E(0) end
E(p) --> P [ ?(p≤4) "^" E(4) ] { ?(p≤3) "!" } { ?(p≤2) "*" E(3) } { ?(p≤1) "+" E(2) } [ ?(p≤0) "=" E(1) ]
P --> "-" E(2) | "(" E(0) ")" | v

Now we’re getting somewhere.

Making a deterministic recognizer

The fourth transformation is more straightforward to point to as a code transformation than as a grammar transformation, so, to prepare, we convert our grammar to a recognizer the use of the conventional recursive descent magic. I would not add any tree building instructions yet, as they clutter things up.

S is E(0) put a question to( end )

E(p) is  
    P
    if p≤4 and subsequent="^" then ( utilize ; E(4) )
    while p≤3 and subsequent="!" attain  utilize
    while p≤2 and subsequent="*" attain ( utilize ; E(3) )
    while p≤1 and subsequent="+" attain ( utilize ; E(2) )
    if p≤0 and subsequent="=" then ( utilize ; E(1) )

P is 
    if subsequent="-" then ( utilize ; E(2) )
    else if subsequent="(" then ( utilize ; E(0) ; put a question to( ")" ) )
    else if subsequent is a v then utilize 
    else error

Here is a deterministic algorithm for an ambiguous grammar: While changing from a grammar to a feature of subroutines, I’ve decided about what happens in the ambiguous cases. So, though there don’t appear to be any tree building instructions, at this point we may perchance additionally just mute end and preserve in thoughts strings such as -a*b and -a+b, and gaze whether or not they’re parsed “as it will be”. I.e., we may perchance additionally just mute quiz: if we did absorb tree building instructions, would the fantastic tree be built? Here is what happens for -a*b . S calls E(0), E(0) calls P, and P consumes the “–” and then calls E(2). After provocative “a“, the decision to E(2) sees the “*“. The well-known decision is to utilize the “*” and the “b” in the loop, in procedure of getting back from E(2) as quickly as “a” is consumed. The fantastic tree is built — or may be, if we had been building trees. Against this, in parsing -a+b, E(2) consumes the “a” and then must return; so it’s the decision to E(0) that consumes the “+“. The tree we would catch is an identical as that for (-a)+b, correct as desired.

Fourth transformation: Combining the while loops and the if instructions

The next transformation is the trickiest one. We want to combine the sequence of if instructions and while loops in scheme E into one single while loop. If I truly absorb two identical loops sequentially, say

    while A attain X
    while A attain X    ,

we are capable of rewrite them as one loop

    while A attain X

What if the loops are utterly different?. Declare we now absorb two successive while instructions

    while A attain X
    while B attain Y  ,

and, furthermore, know that not A is a loop invariant of the 2d loop (i.e. that not A and B implies that executing Y leaves A faux), then we are capable of rewrite to

    while A or B attain if A then X else Y

Equally, if we now absorb an if issue adopted by a while issue

    if A then X
    while B attain Y  ,

and, furthermore, know that

• not A is an invariant of the loop and that
• X changes A from fantastic to faux

then we are capable of rewrite the code to

    while A or B attain if A then X else Y

What if there’s not any particular relationship between the must haves and the instructions? Then we are capable of create one. We can use a counter to preserve track of how lots of the fashioned loops and ifs our one loop is mute emulating: For example

    if A attain X
    while B attain Y
    while C attain Z

can consistently be rewritten as

    var r :=2
    while 2≤r and A
       or 1≤r and B
       or 0≤r and C
    attain
        if 2≤r and A then      (X ; r :=1)
        else if 1≤r and B then (Y ; r :=1)
        else                   (Z ; r :=0)

the place r is a fresh variable. The r variable acts as a ratchet; it prevents backsliding. As soon as X is done, we feature r to 1 to be obvious X just isn’t done all all over again. As soon as Y is done, we feature rto 1 to make toddle that X just isn’t done in the lengthy chase. As soon as Z is done, we feature rto 2 to make toddle that neither X nor Y is done in the lengthy chase.

Applying this loop fusing belief to our latest E scheme we catch

E(p) is  
    P
    var r :=4
    while p≤4≤r and subsequent="^"
       or p≤3≤r and subsequent="!"
       or p≤2≤r and subsequent="*"
       or p≤1≤r and subsequent="+"
       or p≤0≤r and subsequent="="
    attain 
        if p≤4≤r and subsequent="^" then      (utilize ; E(4) ; r :=3)
        else if p≤3≤r and subsequent="!" then (utilize ;        r :=3)
        else if p≤2≤r and subsequent="*" then (utilize ; E(3) ; r :=2)
        else if p≤1≤r and subsequent="+" then (utilize ; E(2) ; r :=1)
        else /p≤0≤r and subsequent="=" */   (utilize ; E(1) ; r :=-1)

Fifth transformation: Making it desk pushed

Take a look for at the most fresh E scheme. If shall we eradicate the variations between the branches of the nested ifs, we wouldn’t need any branching in the center of the loop body. If shall we eradicate the variations between the disjuncts of the loop guard, shall we tremendously simplify the loop guard. The variations plot appropriate down to whether or not an operator is binary or postfix and three numbers:

• prec(b): the priority of the operator b (i.e., the most effective rate of p such that an invocation of E(p) can at as soon as utilize the operator),
• rightPrec(b): the bottom priority allowed for operators in b‘s fantastic operand, and
• nextPrec(b): a ticket for r that stops the loop from provocative operators whose priority is simply too low.

For example, for + these numbers are respectively 1 (from p≤1≤r and subsequent=”+”), 2 (from E(2)), and 1 (from r :=1).

We create the following three tables.

Now we rewrite the most fresh E scheme to utilize the tables and, after simplifying, we catch

E(p) is  
    P
    var r :=4
    while subsequent is a binary or a postfix operator
      and p≤prec(subsequent)≤r attain
        const b :=subsequent
        utilize
        if b is binary then E( rightPrec(b) )
        r :=nextPrec(b) 

This transformation is the one who truly makes the algorithm each and every compact and ambiance suitable. The amount of operations done and the dimension of the code (other than for the desk) are now each and every self sustaining of the amount of priority phases.

We don’t truly want three tables. We can outline rightPrec(b)=1+prec(b) when b is left-associative or nonassociative, and rightPrec(b)=prec(b) when b is fantastic-associative. We can outline nextPrec(b)=prec(b) when b is left-associative or postfix, and nextPrec(b)=prec(b)-1 when b is fantastic-associative or nonassociative. (If we now absorb a postfix operator $ and want to end, say, a$$“, we create nextPrec(‘$’)=prec(‘$’)-1.

The truly alert reader may perchance additionally just detect that we didn’t absorb the r variable or the nextPrec feature in the previous part. We need them here because we now absorb nonassociative operators and postfix operators. It also simplifies the argument that the transformation is fantastic. I will go it as an exercise to eradicate r when it be not well-known. (Otherwise you can perchance read Clarke’s paper [0].)

In the case of postfix operators, the use of r and nextPrec ensures that, for instance, a!^b is an error, correct as it’s in the fashioned grammar. If we want to permit such strings, we are capable of feature nextPrec(‘!’) to 4. In the first model of scheme E, this quantities to a backwards jump luxuriate in this:

E(p) is  
    P
    L: if p≤4 and subsequent="^" then ( utilize ; E(4) )
    if p≤3 and subsequent="!" then ( utilize ; goto L)
    while p≤2 and subsequent="*" attain ( utilize ; E(3) )
    while p≤1 and subsequent="+" attain ( utilize ; E(2) )
    if p≤0 and subsequent="=" then ( utilize ; E(1) )

In similar old, the nextPrec for any postfix operator may perchance additionally just additionally be the priority of the most effective priority operator. This permits a postfix operator to be adopted by any binary or postfix operator, correct as a prefix operator can follow any binary or prefix operator.

Including tree building operations

Sooner or later, we add the tree building operations. Strictly talking they must were added as quickly as we went to code, so that shall we gaze that the fantastic tree is built for ambiguous inputs and that subsequent transformations have not any design on the tree that is at closing built.

S is const t :=E(0) ; put a question to( end ) ; output(t)

E(p) is  
    var t :=P
    var r :=4
    while subsequent is a binary or a postfix operator
      and p≤prec(subsequent)≤r attain
        const b :=subsequent
        utilize
        if b is binary then 
            const t1 :=E( rightPrec(b) )
            t :=mknode(binary(b), t, t1)
        else t :=mknode(postfix(b), t) 
        r :=nextPrec(b) 
    return t

P is 
    if subsequent="-" then ( utilize ; const t:=E(2) ; return mknode(prefix('-', t)) )
    else if subsequent="(" then ( utilize ; const t :=E(0) ; put a question to(")") ; return t )
    else if subsequent is a v then ( const t := mkleaf(subsequent) ; utilize ;  return t )
    else error

Wasn’t that enjoyable!

Bibliographic Notes

Recursive descent looks to were first described by Peter Lucas, who, with a workforce from IBM’s Vienna laboratory, veteran it of their ALGOL 60 compiler. In his describe [2], he writes

The translator will be designed in such a plot, that each and every which technique of a metalinguistic variable corresponds to a subroutine which carries out the transformation of the string of symbols.

One other early use of recursive descent parsing was in an ALGOL 60 Compiler for the Elliott Brothers’ 803 and 503 computer systems; it was designed by a workforce of three programmers led by C. A. R. Hoare. From Hoare’s describe on that compiler:

The fundamental work is carried out by a feature of procedures, each and every of which is sweet of processing one of many syntactic devices outlined in the ALGOL 60 describe. The place one syntactic unit is printed as consisting of alternative devices, the scheme will be good of activating other procedures, and the place fundamental, itself. For example, the scheme “assemble arithmetic expression” desires to be good of compiling the bracketed constituents of an arithmetic expression, that are themselves arithmetic expressions; that is done by a recursive entry to the very scheme “assemble arithmetic expression” which is in the period in-between engaged on translating the entire expression. [3]

That you just too can use this compiler yourself; gaze http://elliott803.sourceforge.win/doctors/algol.html. That you just too can read the (disassembled) compiler at http://www.billp.org/ccs/ElliottAlgol/.

I’m not definite who invented what I’m calling the classic algorithm. (Anyone know?) It was made long-established, I consider, by Niklaus Wirth who veteran it in utterly different compilers, notably for Pascal. I realized it from one of Wirth’s books.

The Shunting-Yard Algorithm was it looks invented by Edsger Dijkstra spherical 1960 in connection with one of basically the most necessary ALGOL 60 compilers. It is described in a Mathematisch Centrum describe (starting up spherical web bellow 21) [1]. I say “aparently”, as truly the same algorithm is described by Friedrich. Bauer and Klaus Samelson in 1960 [5]. I consider I first saw a model of it described in an advert for the TI SR-52 and SR-56 calculators, two of the earliest pocket calculators to handle priority. (Sooner than 1976, pocket calculators both veteran RPN or handled 2+3*4 as (2+3)*2.)

I first saw what I’ve known as the priority hiking plot described by Keith Clarke in a posting to comp.compilers
in 1992. Keith gives a proof of its correctness, relative to the classic algorithm, by plot of program transformation in a 1985 describe “The end-down parsing of expressions” [0]. The algorithm looks to were first invented by Martin Richards to be used in the CPL and BCPL compilers. It will additionally just additionally be dispute in the part 6.6 of BCPL — the language and its compiler [4] and may perchance mute be dispute in latest distributions of BCPL’s compiler. Neither Clarke nor Richards had a undeniable name for the algorithm, so my one contribution (moreover extending it to postfix and non-associative operators) is suggesting the name “priority hiking”.

Evidently priority hiking is a undeniable case of a extra flexible plot known as Pratt parsing.  Pratt parsing was first described in a paper by Vaughn Pratt [6]. This connection was dropped at my attention by

Andy Chu who wrote about it in a weblog post [7].  I’ve explored this connection in my absorb web article From Precedence Rock climbing to Pratt Parsing [8].

References

[0] Keith Clarke, “The end-down parsing of expressions”, Review File 383, Dept of Computer Science, Queen Mary College. Archived at http://antlr.org/papers/Clarke-expr-parsing-1986.pdf.

[1] Edsger W. Dijkstra, “Algol 60 translation : An Algol 60 translator for the x1 and Making a translator for Algol 60”, Review File 35, Mathematisch Centrum, Amsterdam, 1961. Reprint archived at http://www.cs.utexas.edu/users/EWD/MCReps/MR35.PDF.

[2] Peter Lucas, “The Constructing of Formula-Translators”, ALGOL Bulletin, Field Sup 16, Sep. 1961. Archived at http://archive.computerhistory.org/sources/text/algol/algol_bulletin/AS16/AS16.HTM.

[3] C. A. R. Hoare, “File on the Elliott ALGOL translator”, The Computer Journal, Vol. 5, No. 2, pp. 127-129, 1962. Archived at http://comjnl.oxfordjournals.org/bellow material/5/2/127.brief.

[4] Martin Richards and Collin Whitby-Stevens, BCPL — the language and its compiler, 1st ed., Cambridge University Press, 1979.

[5] F. L. Bauer and K. Samelson, “Sequential plot translation”, Communications of the ACM, vol 3, #2, February, 1960.

[6] Vaughn R. Pratt, “High down operator priority”, Proceedings of the first symposium on principles of programming languages (POPL), 1973, http://dl.acm.org/citation.cfm?identification=512931

[7] Andy Chu, “Pratt Parsing and Precedence Rock climbing Are the Identical Algorithm”, Nov 2016. http://www.oilshell.org/weblog/2016/11/01.html

[8] Theodore S. Norvell, “From Precedence Rock climbing to Pratt Parsing”, 2016, www.engr.mun.ca/~theo/Misc/pratt_parsing.htm

Acknowledgement

Attributable to

Colas Schretter for pointing out an error in the priority hiking algorithm and suggesting a correction.

I’m grateful to Keith Clarke and Martin Richards for helping me stamp the origins of what I’ve known as priority hiking and to Andy Chu for pointing out the connection to Pratt parsing.

Attributable to everyone who took the trouble to e-mail me to present an clarification for me that they stumbled on this article well-known, to point me to an implementation, or to present an clarification for me that I’ve made an error.