Enhanced C#
Language of your choice: library documentation
Public fields | Public static fields | Properties | Public Member Functions | Static Public Member Functions | List of all members
Loyc.Syntax.Precedence Struct Reference

A four-byte tuple that represents the precedence and miscibility of an operator. More...


Source file:
Inheritance diagram for Loyc.Syntax.Precedence:

Remarks

A four-byte tuple that represents the precedence and miscibility of an operator.

Precedences encode knowledge like the fact that x & y == z will be parsed as x & (y == z) in C#. An operator's precedence is encoded in the two numbers, Left and Right. For typical operators which are left-associative, Left and Right are the same. However, some operators have different precedence on the left than on the right, a prime example being the => operator: x = a => y = a is parsed x = (a => (y = a)); it has very high precedence on the left, but very low precedence on the right.

To understand how this works, remember that a parser scans from left to right. Each time it encounters a new operator, it needs to figure out whether to include that operator in the current (inner) expression or whether to "complete" the inner expression and bind the operator to an outer expression instead. The concept of a "precedence floor" can be used to make this decision.

For example, suppose we start parsing the expression -a.b + c * d + e. The parser sees "-" first, which must be a prefix operator since there is no expression on the left. The Right precedence of unary '-' is 90 in EC#, so that will be the "precedence floor" to parse the right-hand side. Operators above 90 will be permitted in the right-hand side; operators at 90 or below will not.

The next token is 'a', which is an expression by itself and doesn't have any precedence, so it becomes the initial right-hand expression of '-'. Next we have '.', which has a Left precedence of 100, which is above the precedence floor of 90 so it can be bound to 'a'. The precedence floor (PF) is raised to 100, and the next token 'b' is bound to '.'.

However, the next token '+' (which must be the binary operator rather than the prefix operator, because there is an expression on the left) cannot be accepted with its precedence of 60. Therefore the expression "a.b" is deemed complete, and the PF is lowered back to 90. Again 60 is less than 90, so the expression "-a.b" is also deemed complete and the PF drops to int.MinValue. This expression becomes the left-hand side of the '+' operator. The PF rises to 60, and "c * d" becomes a subexpression because the precedence of '*' is 70 > 60. However, next we have '+' with precedence 60, which is not above the PF of 60. Therefore, the subexpression "c * d" is deemed complete and the PF lowers to int.MinValue again. Now the '+' can be accepted with a left-hand side of (-(a.b)) + (c * d), and the right-hand side is, of course, 'e', so the completed expression is ((-(a.b)) + (c * d)) + e. Hope that helps!

Notice that a + b + c is parsed (a + b) + c, not a + (b + c). This is the natural result when the operator's precedence is the same on the left and on the right. However, a = b = c is parsed a = (b = c), because its precedence is 1 on the left and 0 on the right. When the parser sees the first '=' it sets the PF to 0 because it is about to parse the right side. When it encounters the second '=', the precedence of the Left side of that operator is 1 which is higher than the current PF (0) so it is included in the right-hand side of the first '='. This behavior is called "right associativity"; IsRightAssociative returns true when Left > Right.

Prefix and suffix operators only have one "side"; you can imagine that the unused side (e.g. the left side of prefix -) has infinite precedence, so that EC# could parse $-x as $(-x) even though the precedence of '-' is supposedly lower than '$'.

Some languages have a conditional operator (a?b:c) with three parts. In the middle part, the PF must drop to Precedence.MinValue so that it is possible to parse a?b=x:c even though '=' supposedly has lower precedence than the conditional operator. Note that a=b ? c=d : e=f is interpreted a=(b ? c=d : e)=f, so you can see that the precedence of the conditional operator is higher at the "edges".

The above explanation illustrates the meaning of Left and Right from the perspective of a parser, but an actual parser may or may not use the PF concept and Precedence objects.

In summary: Left and Right represent the precedence of the left and right side of a binary operator. A parser can keep track of a number called the "precedence floor" or PF, which has its minimum value when parsing starts. When a binary operator Op is encountered, the parser should "accept" the operator when O.Left > PF and, if it accepts the operator, set PF = O.Right temporarily as it parses the right side of the operator.

This struct contains two other numbers, Lo and Hi, which are a precedence range that determines whether and how the operator can be mixed with other operators, as explained below.

A printer (which writes a syntax tree as text) has a different way of analyzing precedence. It starts with a known parse tree and then has to figure out how to output something that the parser will reconstruct into the original tree. This is more difficult if perfect round-tripping is required: parentheses are encoded in the Loyc tree as a #trivia_inParens attribute, so if perfect round-tripping is desired, the printer cannot simply put everything in parens "just to be safe".

The LES and EC# printers have two ways of printing any expression tree: (1) with operators (e.g. a+b), and (2) with prefix notation (e.g. `'+(a, b)). The tree <c>'+('*`(a, b), c) will be printed as "a*b+c" (unless prefix notation is specifically requested) because the precedence rules allow it, but `'*('+(a, b), c)</c> will be printed as <c>'+`(a, b)*c because both "a+b*c" and "(a+b)*c" are different from the original tree.

While a parser proceeds from left to right, a printer proceeds from parents to children. So the printer for `'*('+(a, b), c) starts at <c>'*` with no precedence restrictions, and roughly speaking will set the precedence floor to LesPrecedence.Multiply in order to print its two children. Since the precedence of `'+` (Add) is below Multiply, the + operator is not allowed in that context.

Printing has numerous "gotchas"; the ones related to precedence are

  1. Although LesPrecedence.Add has the "same" precedence on the Left and Right, `'-('-(a, b), c)</c> can be printed <c>a - b - c</c> but <c>'-(a,'-(b, c))</c> would have to be printed <c>a -'-`(b, c) instead. Clearly, the left and right sides must be treated somehow differently.
  2. Similarly, the different arguments in a?b:c and a=>b must be treated differently. And careful handling is needed for the dot operator in particular due to its high precedence; e.g. `'.(a(b))</c> cannot be printed <c>.a(b)</c> because that would mean <c>'.`(a)(b).
  3. The LES parser, at least, allows a prefix operator to appear on the right-hand side of any infix or prefix operator, regardless of the precedence of the two operators; "$ ++x" is permitted even though ++ has lower precedence than $. Another example is that a.-b.c can be parsed with the interpretation a.(-b).c, even though '- has lower precedence than '$. Ideally the printer would replicate this rule, but whether it does ot not, it also must take care that `'.(a, -b.c)</c> is not printed as <c>a.-b.c</c> even though the similar expression <c>'*(a,'-`(b.c)) can be printed as a*-b.c.
  4. Prefix notation is needed when an operator's arguments have attributes; `'+([Foo] a, b)</c> cannot be printed <c>[Foo] a + b</c> because that would mean <c>[Foo]'+`(a, b).

Printing and parsing are different

This type contains different methods for printers and parsers. A basic difference between them is that printers must make decisions (of whether an operator is allowed or not in a given context) based on both sides of the operator and both sides of the context (Left and Right), while parsers only have to worry about one side. For example, consider the following expression:

a = b + c ?? d

When the parser encounters the "+" operator, it only has to consider whether the precedence of the left-hand side of the "+" operator is above the right-hand side of the "=" operator. The fact that there is a "??" later on is irrelevant. In contrast, when printing the expression "b + c", both sides of the subexpression and both sides of the context must be considered. The right-hand side is relevant because if the right-hand operator was "*" instead of "??", the following printout would be wrong:

a = b + c * d // actual syntax tree: a = `'+`(b, c) * d

The same reasoning applies to the left-hand side (imagine if "=" was "*" instead.)

So, naturally there are different methods for parsing and printing. For printing you can use CanAppearIn(Precedence), LeftContext and RightContext, while for parsing you only need CanParse (to raise the precedence floor, simply replace the current Precedence value with that of the new operator). If one chooses to use this type to represent the precedence floor in a parser, the "current" precedence is represented by Right; the value of Left doesn't matter.

Both printers and parsers can use CanMixWith.

Miscibility (mixability)

Lo and Hi don't affect how operators are parsed into a tree, but are used to request a warning or error if operators are mixed improperly. If one operator's range overlaps another AND (the ranges are not equal OR Lo > Hi), then the two operators are immiscible. For example, == and != have the same precedence in EC#, 38..39, so they can be mixed with each other, but they cannot be mixed with & which has the overlapping range 32..45 (this will be explained below.) Normally Lo and Hi are set to Min(Left,Right) and Max(Left,Right) respectively, but this is not required–in particular, any pair where Lo > Hi is used to indicate that the operator cannot be mixed with other operators of the same precedence, even though it can (perhaps) be mixed with others of different precedence. This is called non-associativity. For example, in PHP are not allowed to write an expression such as x > y >= z; to represent this, operators > and >= should make Lo > Hi.

Certain operators should not be mixed because their precedence was originally chosen incorrectly, e.g. x & 3 == 1 should be parsed (x & 3) == 1 but is actually parsed x & (3 == 1). To allow the precedence to be repaired eventually, expressions like x & y == z are deprecated in EC#: the parser will warn you if you have mixed operators improperly. PrecedenceRange describes both precedence and miscibility with a simple range of integers. As mentioned before, two operators are immiscible if their ranges overlap but are not identical.

In LES, the precedence range feature (a.k.a. immiscibility) is also used to indicate that a specific precedence has not been chosen for an operator. If a precedence is chosen in the future, it will be somewhere within the range.

Overall Range

By convention, precedence scales range from about 0 to about 100. The precedence numbers are stored in this structure as sbytes, so Left, Right, Lo, and Hi must be between -128 and 127.

Public fields

readonly sbyte Lo
 Lo and Hi specify the miscibility of an operator; see the remarks of Precedence for details. More...
 
readonly sbyte Hi
 
readonly sbyte Left
 Left and Right denote the precedence level on the left and right sides of an operator; see the remarks of Precedence for details. More...
 
readonly sbyte Right
 

Public static fields

static Precedence MinValue = new Precedence(sbyte.MinValue)
 
static Precedence MaxValue = new Precedence(sbyte.MaxValue)
 

Properties

bool IsRightAssociative [get]
 Returns true if this object represents a right-associative operator such as equals (x = (y = z)), in contrast to left- associative operators such as division ((x / y) / z). More...
 

Public Member Functions

 Precedence (int actual)
 Initializes a left-associative operator with the specified precedence. More...
 
 Precedence (int left, int right)
 Initializes an operator with different precedence on the left and right sides. For a right associative operator, conventionally right = left-1. More...
 
 Precedence (int left, int right, int lo, int hi)
 Initializes an operator with the given precedence on the left and right sides, and the given immiscibility range (see documentation of this type). More...
 
 Precedence (sbyte left, sbyte right, sbyte lo, sbyte hi)
 
Precedence LeftContext (Precedence outerContext)
 For use in printers. Auto-raises the precedence floor to prepare to print an expression on the left side of an operator. More...
 
Precedence RightContext (Precedence outerContext)
 For use in printers. Auto-raises the precedence floor to prepare to print an expression on the right side of an operator. More...
 
bool CanAppearIn (Precedence context)
 For use in printers. Returns true if an infix operator with this precedence can appear in the specified context. More...
 
bool CanAppearIn (Precedence context, bool prefix)
 For use in printers. Returns true if an operator with this precedence can appear in the specified context (ignoring miscibility). More...
 
bool CanMixWith (Precedence context)
 Returns true if an operator with this precedence is miscible without parenthesis with the specified other operator. More...
 
bool CanParse (Precedence rightOp)
 For use in parsers. Returns true if 'rightOp', an operator on the right, has higher precedence than the current operator 'this'. More...
 
bool RangeEquals (Precedence b)
 
override bool Equals (object obj)
 
bool Equals (Precedence other)
 
override int GetHashCode ()
 

Static Public Member Functions

static bool operator== (Precedence a, Precedence b)
 
static bool operator!= (Precedence a, Precedence b)
 

Constructor & Destructor Documentation

Loyc.Syntax.Precedence.Precedence ( int  actual)
inline

Initializes a left-associative operator with the specified precedence.

Loyc.Syntax.Precedence.Precedence ( int  left,
int  right 
)
inline

Initializes an operator with different precedence on the left and right sides. For a right associative operator, conventionally right = left-1.

Loyc.Syntax.Precedence.Precedence ( int  left,
int  right,
int  lo,
int  hi 
)
inline

Initializes an operator with the given precedence on the left and right sides, and the given immiscibility range (see documentation of this type).

Member Function Documentation

bool Loyc.Syntax.Precedence.CanAppearIn ( Precedence  context)
inline

For use in printers. Returns true if an infix operator with this precedence can appear in the specified context.

Miscibility must be checked separately (CanMixWith).

References Loyc.Syntax.Precedence.Left.

bool Loyc.Syntax.Precedence.CanAppearIn ( Precedence  context,
bool  prefix 
)
inline

For use in printers. Returns true if an operator with this precedence can appear in the specified context (ignoring miscibility).

Parameters
prefixIt is assumed that the left side of a prefix operator has "infinite" precedence so when this flag is true, only the right side is checked.

This prefix rule is used by the EC# printer but is not allowed by all languages (if in doubt, set prefix=false).

References Loyc.Syntax.Precedence.Left.

bool Loyc.Syntax.Precedence.CanMixWith ( Precedence  context)
inline

Returns true if an operator with this precedence is miscible without parenthesis with the specified other operator.

CanAppearIn(Precedence) is for parsability, this method is to detect a deprecated or undefined mixing of operators.

References Loyc.Syntax.Precedence.Lo.

Referenced by Loyc.Syntax.Les.Les3Parser.Start().

bool Loyc.Syntax.Precedence.CanParse ( Precedence  rightOp)
inline

For use in parsers. Returns true if 'rightOp', an operator on the right, has higher precedence than the current operator 'this'.

Returns
rightOp.Left > this.Right

References Loyc.Syntax.Precedence.Left, and Loyc.Syntax.Precedence.Lo.

Referenced by Loyc.Syntax.Les.Les3Parser.Start().

Precedence Loyc.Syntax.Precedence.LeftContext ( Precedence  outerContext)
inline

For use in printers. Auto-raises the precedence floor to prepare to print an expression on the left side of an operator.

Parameters
outerContext
Returns

References Loyc.Syntax.Precedence.Left.

Precedence Loyc.Syntax.Precedence.RightContext ( Precedence  outerContext)
inline

For use in printers. Auto-raises the precedence floor to prepare to print an expression on the right side of an operator.

Parameters
outerContextContext in which this operator is being printed
Returns

Member Data Documentation

readonly sbyte Loyc.Syntax.Precedence.Left

Left and Right denote the precedence level on the left and right sides of an operator; see the remarks of Precedence for details.

Referenced by Loyc.Syntax.Precedence.CanAppearIn(), Loyc.Syntax.Precedence.CanParse(), and Loyc.Syntax.Precedence.LeftContext().

readonly sbyte Loyc.Syntax.Precedence.Lo

Lo and Hi specify the miscibility of an operator; see the remarks of Precedence for details.

Referenced by Loyc.Syntax.Precedence.CanMixWith(), Loyc.Syntax.Precedence.CanParse(), and Loyc.Ecs.EcsNodePrinter.PrintECSharp().

Property Documentation

bool Loyc.Syntax.Precedence.IsRightAssociative
get

Returns true if this object represents a right-associative operator such as equals (x = (y = z)), in contrast to left- associative operators such as division ((x / y) / z).