This post continues our series on new features coming to SyntaxEditor 2011.1, primarily centered around our LL(*) Parser Framework.
In our last post, we showed the enhancements to the Language Designer application that make it easy to design and code generate type-specific AST node classes. Whereas the default AST nodes used by the parser framework are nodes that have a string value and optional child nodes, these type-specific nodes are dedicated class types for each kind of node, with contextual properties that contain references to child nodes and other metadata.
In today’s post, we will examine the new features added to grammars, allowing for the complete building of an AST using these type-specific AST nodes. We’re really excited about the features shown here as they are unique to our parser framework, utilize the latest C# and VB language constructs, and are completely extensible. You won’t find these features in any other .NET-oriented parser generation framework.
Tree Construction Introduction
For details on how tree construction works, please see our original post on the topic from a few months back. But to give a quick overview, say we have this EBNF for a C# ‘if-statement’ non-terminal that we wish to put in our grammar:
1: if-statement:
2: "if" "(" boolean-expression ")" embedded-statement
3: "if" "(" boolean-expression ")" embedded-statement "else" embedded-statement
That EBNF comes from the C# specification. Now in our grammars, you write your EBNF productions right in C#/VB. We use operator overloads and other mechanisms to support an EBNF-like syntax. Here is a code snippet showing a production for the ‘if-statement’:
1: ifStatement.Production = @keywordIf + @openParenthesis + booleanExpression +
2: @closeParenthesis + embeddedStatement +
3: (@keywordElse + embeddedStatement).Optional();
Note that just by convention, we like to put @ signs before variables that reference terminals. Let’s enhance our production to add error handling, add labels applied to text portions we wish to capture, and add tree construction.
1: ifStatement.Production = @keywordIf + @openParenthesis +
2: booleanExpression["conditionexp"].OnErrorContinue() +
3: @closeParenthesis.OnErrorContinue() +
4: embeddedStatement["truestmt"].OnErrorContinue() +
5: (@keywordElse + embeddedStatement["falsestmt"].OnErrorContinue()).Optional()
6: > Ast("IfStatement", AstFrom("conditionexp"),
7: AstFrom("truestmt"), AstFrom("falsestmt"));
Here our tree construction nodes are using the default AST node type, which just has a string value and optional child nodes. For the next few samples we’ll use this C# code as input to our grammar:
1: if (isTrue) return 1 else return 0;
Assuming the other productions in the grammar were configured and we passed the above snippet, we’d likely see this sort of AST output:
1: IfStatement[
2: SimpleName[
3: "isTrue"
4: ],
5: ReturnStatement[
6: LiteralExpression[
7: "1"
8: ]
9: ],
10: ReturnStatement[
11: LiteralExpression[
12: "0"
13: ]
14: ]
15: ]
In an IfStatement it might be ok to just have each child node pop directly into the IfStatement node in sequence since we know the condition is always first, the true statement is second, and the false statement, if present, is always third. For more complicated nodes though, you can’t do that and you’d need more contextual information like this:
1: ifStatement.Production = @keywordIf + @openParenthesis +
2: booleanExpression["conditionexp"].OnErrorContinue() +
3: @closeParenthesis.OnErrorContinue() +
4: embeddedStatement["truestmt"].OnErrorContinue() +
5: (@keywordElse + embeddedStatement["falsestmt"].OnErrorContinue()).Optional()
6: > Ast("IfStatement",
7: Ast("ConditionExpression", AstFrom("conditionexp")),
8: Ast("TrueStatement", AstFrom("truestmt")),
9: Ast("FalseStatement", AstFrom("falsestmt")));
Which would yield this AST output when parsing the same input:
1: IfStatement[
2: ConditionExpression [
3: SimpleName[
4: "isTrue"
5: ]
6: ],
7: TrueStatement[
8: ReturnStatement[
9: LiteralExpression[
10: "1"
11: ]
12: ]
13: ],
14: FalseExpression[
15: ReturnStatement[
16: LiteralExpression[
17: "0"
18: ]
19: ]
20: ]
21: ]
You can see how easy it is to build a non-terminal production that creates an AST using our parser framework. All that is available now, even in version 2010.2.
Type-Specific Tree Construction Nodes
Now let’s get into the new type-specific tree construction nodes, being added for the 2011.1 version. Assuming we have our AST nodes created (per info in the last post), we can rewrite our production like this:
1: ifStatement.Production = @keywordIf + @openParenthesis +
2: booleanExpression["conditionexp"].OnErrorContinue() +
3: @closeParenthesis.OnErrorContinue() +
4: embeddedStatement["truestmt"].OnErrorContinue() +
5: (@keywordElse + embeddedStatement["falsestmt"].OnErrorContinue()).Optional()
6: > Ast<IfStatement>()
7: .SetProperty(s => s.ConditionExpression, AstFrom("conditionexp"))
8: .SetProperty(s => s.TrueStatement, AstFrom("truestmt"))
9: .SetProperty(s => s.FalseStatement, AstFrom("falsestmt"));
Instead of creating instances of the default AST node type, this tree constructor will create an IfStatement class instance, and will set properties on it based on labeled results. If you were programmatically creating the AST output that is yielded by parsing the sample input from above, you’d write it like so:
1: new IfStatement {
2: ConditionExpression = new SimpleName {
3: Text = "isTrue"
4: },
5: TrueStatement = new ReturnStatement {
6: Expression = new LiteralExpression() {
7: Value = 1
8: }
9: },
10: FalseStatement = new ReturnStatement {
11: Expression = new LiteralExpression() {
12: Value = 0
13: }
14: }
15: }
That is some neat stuff. Not only are we new-ing up multiple custom classes, but we are also setting new instances to properties on other AST nodes (thus forming a hierarchy), and are even able to set other simple property types like strings and ints. Since it’s written in C#/VB, we have full type checking and Intellisense while editing in Visual Studio for property names, etc.
Ast<T>()
The Ast<T>() method simple creates a new instance of type T, where T is an IAstNode. Properties can be modified (see below) on the instance that was created.
In the sample above, IfStatement was passed in as T.
AstFrom<T>(label)
The AstFrom<T>(label) method works just like the normal AstFrom method in that it grabs the IAstNode result with the specified label and returns it. Properties can be modified on the instance that was returned.
AstConditional<T>(node1, node2, …)
The AstConditional<T>(node1, node2, …) method works just like the normal AstConditional method where if more than one node is matched within the parameters to the method, the nodes are wrapped by a new IAstNode instance created by this tree constructor. Properties can be modified on the instance that was created. Otherwise, the single node that is matched is directly passed up.
This is very useful for scenarios where you have binary operator expressions and only want to wrap the left expression if an operator and right expression are present.
Modifying AST Node Properties
Either of the three tree constructor generic methods described above return an ITypedTreeConstructionNode<T> instance, which has several methods on it for describing how to update properties on the related type-specific AST node.
Note that all of these methods use one or more lambda expressions that indicate the property to update. This enables type checking and validation by the C#/VB compiler.
SetProperty
The SetProperty method is the most-used mechanism to update properties. It calls a setter for the specified property to set it to a new value. Depending on the property’s return type, different logic is used for how to obtain its value. Strings, integers, booleans, enums, flags enums, and AST node properties are supported.
Multiple instances of these values can be passed to the method for a single property too, which is especially useful for things like type modifiers. Generally there are zero or more type modifiers allowed on a type. So we end up with a list of them. But say our type-specific AST node for type declarations has a Modifiers property where the Modifiers enum value is a flags enum. In this case SetProperty will automatically OR all the flags found together and set the resulting value to the property.
Similar logic is available for strings (which get concatenated), ints (which get added together), and bools (which get OR’ed together). Generally though, only a single AST node result is passed to SetProperty for examination.
1: constantDeclarator.Production = simpleNameWithoutTypeArguments["name"] +
2: @operatorAssignment.OnErrorContinue() +
3: constantExpression["exp"].OnErrorContinue()
4: > Ast<VariableDeclarator>()
5: .SetProperty(d => d.Name, AstFrom("name"))
6: .SetProperty(d => d.Initializer, AstFrom("exp"))
7: .SetProperty(d => d.Kind, VariableDeclaratorKind.Constant);
Another overload of SetProperty allows a literal value to be assigned as the value like the above production where a constant declarator should always have its Kind property set to a specific enumeration value.
AppendToProperty
The AppendToProperty method works the same as SetProperty. The only difference is that instead of wiping out any previous property value, the previous value is included in the OR/concatenation/addition logic described above for SetProperty when multiple AST node values are passed.
1: typeDeclaration.Production =
2: attributeSection.OnErrorContinue().ZeroOrMore().SetLabel("attrs") +
3: modifier.OnErrorContinue().ZeroOrMore().SetLabel("modifiers") +
4: typeDeclarationCore["decl"]
5: > AstFrom<IDecoratedMember>("decl")
6: .AddToCollectionProperty(d => d.AttributeSections, AstChildrenFrom("attrs"))
7: .AppendToProperty(d => d.Modifiers, AstChildrenFrom("modifiers"));
The above production shows usage of AppendToProperty and how it will not wipe out any existing modifiers values that came in from the declaration AST node returned in label decl. Instead it will take the existing property value and OR in any matched modifiers. The result is set as the new Modifiers property value.
AddToCollectionProperty
The AddToCollectionProperty method appends one or more AST node result values to a collection property. In the production above, any attribute section AST nodes that are matched are added to the the AttributeSections list property.
SetCollectionItemProperties
The SetCollectionItemProperties method works just like SetProperty except that instead of setting the property value on the target AST node, it sets the properties of all items in a collection property on the target AST node.
1: constantDeclaration.Production = @keywordConst + type["type"] +
2: constantDeclarator["decl"].OnErrorContinue() +
3: (@comma + constantDeclarator["decl"] > AstFrom("decl")).OnErrorContinue()
4: .ZeroOrMore().SetLabel("moredecls") +
5: @semiColon.OnErrorContinue()
6: > Ast<FieldDeclaration>()
7: .AddToCollectionProperty(d => d.Declarators,
8: AstFrom("decl"), AstChildrenFrom("moredecls"))
9: .SetCollectionItemProperties(d => d.Declarators, v => v.Type, AstFrom("type"));
Take the above production as an example. First a FieldDeclaration AST node is created and any declarators that were matched are added to its Declarators property. Then since in C# the type is defined before the declarators, we need a way to push the type down to each VariableDeclarator instance in the Declarators collection. This is where SetCollectionItemProperties comes in to save the day.
Other New Tree Construction Nodes
We added several other features for tree construction too.
AstCount()
The new AstCount method returns counts the nodes that are passed to it and creates a default AST node whose value is the result.
1: rankSpecifier.Production = @openSquareBrace + @comma.ZeroOrMore().SetLabel("dims") +
2: @closeSquareBrace.OnErrorContinue()
3: > AstCount(Ast("FirstDim"), AstChildrenFrom("dims"));
In the above production, we need to have our rank specifier indicate the number of dimensions. Since if we even get to the rank specifier non-terminal, we know we have at least one dimension, we add in a dummy AST node that will always be passed to AstCount, thus making our count one-based instead of zero-based. If our input text for this production was [,,], our resulting AST node would have a value of 3.
AstChildrenFrom(label, depth)
The AstChildrenFrom method returns the child nodes of the specified labeled match. But what happens if due to some complex nesting the values you are looking for are actually two or more levels deep?
A new overload for AstChildrenFrom adds support for depth. The default implementation uses depth 0, meaning direct children. Depth 1 means grandchildren, and so on.
Debugging
The LL(*) Parser Debugger, found in the Language Designer has been updated to show EBNF for all the new constructs.
You’ll notice the new set method (maps to SetProperty) and add method (maps to AddToCollectionProperty) showing up the EBNF above while debugging.
Summary
As you can see, these updates are very innovative in the way you can think about constructing a parser grammar. Best of all, they are simple to use. All of this and more will be in the 2011.1 version of SyntaxEditor for WPF/Silverlight.
In the next post of this series, we’ll take a look at the can-match callback and error reporting enhancements coming in 2011.1 to the LL(*) Parser Framework.