SyntaxEditor grammar/AST framework part 7: Adding error handling to the Simple grammar

August 13, 2010 at 1:30 AM

In the previous post, we saw how the grammar framework supports callbacks nearly everywhere in the EBNF terms. You are able to inject custom code before and after any term is matched. One of the most important injection points is the Error callback since that allows you to tell the parser how to handle errors.

In today’s post, we’ll examine the importance of adding error handling. We’ll enhance our Simple language grammar to properly recover from nearly any invalid syntax in a document so that it can continue parsing the rest of the document.

Why add error handling?

An error occurs when one or more terminals is expected by the parser (per the grammar) but a different token is found at the current location in the document.

By default when this scenario occurs, the parser will report a parse error if a single terminal is expected. If there is more than one terminal that could be next, and if the containing non-terminal has an error alias set, it will report a parse error instead. This behavior is described in the previous post.

Following any possible error reporting, the parser will immediately exit the current non-terminal and will continue up the non-terminal stack, exiting each one as it goes until the root non-terminal is reached and exited itself.

Thus the result is that if any invalid syntax is found in a document, parsing stops at that point and no AST will be built. That’s definitely not good since we expect code being parsed from our SyntaxEditor control editing to be invalid most of the time. End users are continuously typing in it.

As shown in the previous post, the grammar framework has a lot ways to recover from errors, and they are easy to add.

Enhancing the Simple language grammar with error handling

Adding an error alias to some non-terminals

The first step in adding error handling is to identify which non-terminals should get error aliases (described in the previous post). When a non-terminal has an error alias and an error occurs within it, it will report a parse error.

In the Simple language grammar, we’ll add an error alias to the Statement and Expression non-terminals like this:

   1: var statement = new NonTerminal("Statement") { ErrorAlias = "Statement" };

   2: var expression = new NonTerminal("Expression") { ErrorAlias = "Expression" };

Now say we are parsing and an Expression is expected next but our look-ahead token is Var. The Terminal for Var doesn’t start any expressions, so this is an error. Thus an Expression expected error will be reported since we assigned an error alias to the Expression non-terminal.

Adding iterative error handling in the root production

As described in the previous post, when you have a scenario where some child non-terminal is being repeated, which often is the case in the root non-terminal, we want to force the child non-terminal being repeated to get parsed. We do this, even if the look-ahead token doesn’t match the child non-terminal’s “first set.”

Otherwise if some token was first in the document that didn’t match with the “first set” of the child non-terminal, the parsing would exit immediately, which is not good.

We can force a non-terminal to ignore its “first set” and always be matched by setting its can-match callback to the built in CanAlwaysMatch method on Grammar:

   1: // NOTE: Next line added so that FunctionDeclaration will always be examined,

   2: //   even if the next token is not 'function'... This ensures that a non-function

   3: //   token at the start of the document will not prevent the rest of the document

   4: //   from being parsed

   5: functionDeclaration.CanMatchCallback = CanAlwaysMatch;

The next step is to add an error callback to the FunctionDeclaration EBNF non-terminal:

   1: // Outputs a root 'CompilationUnit' node that contains the children of the ZeroOrMore quantifier,

   2: //   which is zero or more FunctionDeclarations...

   3: // If an error occurs in a FunctionDeclaration we will call the AdvanceToDefaultState method,

   4: //   that is defined below... it advances to the next 'Function' token and flags to continue parsing

   5: this.Root.Production = functionDeclaration.OnError(AdvanceToDefaultState).ZeroOrMore().SetLabel("decl")

   6:     > Ast("CompilationUnit", AstChildrenFrom("decl"));

The AdvanceToDefaultState method is called when an unhandled error occurs in FunctionDeclaration. It advances to the next Function token, which is what properly starts a FunctionDeclaration, thus skipping over any other tokens that would cause more parse errors. It then tells the parser to continue on.

   1: /// <summary>

   2: /// Advances the token reader to the next 'function' token from where

   3: /// parsing can resume.

   4: /// </summary>

   5: /// <param name="state">A <see cref="IParserState"/> that provides information

   6: /// about the parser's current state.</param>

   7: /// <returns>An <see cref="IParserErrorResult"/> value indicating a result.</returns>

   8: private IParserErrorResult AdvanceToDefaultState(IParserState state) {

   9:     state.TokenReader.AdvanceTo(SimpleTokenId.Function);

  10:     return ParserErrorResults.Continue;

  11: }

Let’s walk through what happens now. Say there is an invalid look-ahead token while parsing in the middle of a FunctionDeclaration. An error will occur and possibly be reported. The error will bubble up to the root non-terminal, where the error callback will execute AdvanceToDefaultState. That moves to the next Function token and then tells the parser to continue on. Thus the ZeroOrMore quantifier in the root non-terminal will not be exited and the FunctionDeclaration non-terminal will be entered again.

This design is very important because it allows us recover from invalid syntax and to continue on parsing a document.

Adding more inline error handling to productions

The last step we’ll do to add error handling to the Simple language grammar is to insert OnErrorContinue handlers in various places throughout the productions.

It’s good to insert them on Terminals that are generally insignificant we don’t want things like a missing semi-colon to prevent an entire function declaration from being parsed. Here’s an example:

   1: // Outputs a 'VariableDeclarationStatement' node whose child is the variable name

   2: variableDeclarationStatement.Production = @var + @identifier["name"] + @semiColon.OnErrorContinue()

   3:     > Ast("VariableDeclarationStatement", AstFrom("name"));

It’s up to you to determine when you think a parser should just continue on (by specifying OnErrorContinue) and when it should bubble up to the calling non-terminal. The grammar framework gives you complete flexibility in how you wish to process things.

Final grammar productions for the Simple language

Here is our finalized set of grammar productions for the Simple language. It completely parses Simple code, builds a concise AST, and properly recovers from syntax errors.

   1: // Outputs a root 'CompilationUnit' node that contains the children of the ZeroOrMore quantifier,

   2: //   which is zero or more FunctionDeclarations...

   3: // If an error occurs in a FunctionDeclaration we will call the AdvanceToDefaultState method,

   4: //   that is defined below... it advances to the next 'Function' token and flags to continue parsing

   5: this.Root.Production = functionDeclaration.OnError(AdvanceToDefaultState).ZeroOrMore().SetLabel("decl")

   6:     > Ast("CompilationUnit", AstChildrenFrom("decl"));

7:

   8: // Outputs a 'FunctionDeclaration' node with children:

   9: //   1) The function declaration name value

  10: //   2) A 'Parameters' node that contains each parameter name; or nothing gets inserted

  11: //      if there are no parameters

  12: //   3) The Block statement result

  13: functionDeclaration.Production = @function + @identifier["name"] +

  14:     @openParenthesis.OnErrorContinue() + functionParameterList["params"].Optional() +

  15:     @closeParenthesis.OnErrorContinue() + block["block"].OnErrorContinue()

  16:     > Ast("FunctionDeclaration", AstFrom("name"),

  17:         AstConditionalFrom("Parameters", "params"), AstFrom("block"));

18:

  19: // Outputs a 'FunctionParameterList' node whose children are parameter name values...

  20: //   Is an excellent sample of how to build node for a delimited list

  21: functionParameterList.Production = @identifier["param"] +

  22:     (@comma + @identifier["param"].OnErrorContinue() > AstFrom("param")).ZeroOrMore().SetLabel("moreparams")

  23:     > Ast("FunctionParameterList", AstFrom("param"), AstChildrenFrom("moreparams"));

24:

  25: // Outputs the result that came from the appropriate statement type that was matched...

  26: //   We don't want to wrap the results with a 'Statement' node so we use AstFrom

  27: statement.Production = block["stmt"] > AstFrom("stmt")

  28:     | emptyStatement > null

  29:     | variableDeclarationStatement["stmt"] > AstFrom("stmt")

  30:     | assignmentStatement["stmt"] > AstFrom("stmt")

  31:     | returnStatement["stmt"] > AstFrom("stmt");

32:

  33: // Outputs a 'Block' node whose children are the contained statements

  34: block.Production = @openCurlyBrace + statement.OnErrorContinue().ZeroOrMore().SetLabel("stmt") +

  35:     @closeCurlyBrace.OnErrorContinue()

  36:     > Ast("Block", AstChildrenFrom("stmt"));

37:

  38: // Don't output anything since we don't care about empty statements

  39: emptyStatement.Production = semiColon > null;

40:

  41: // Outputs a 'VariableDeclarationStatement' node whose child is the variable name

  42: variableDeclarationStatement.Production = @var + @identifier["name"] + @semiColon.OnErrorContinue()

  43:     > Ast("VariableDeclarationStatement", AstFrom("name"));

44:

  45: // Outputs a 'AssignmentStatement' node whose children are the variable name and the assigned expression

  46: assignmentStatement.Production = @identifier["varname"] + @assignment +

  47:     expression["exp"].OnErrorContinue() + @semiColon.OnErrorContinue()

  48:     > Ast("AssignmentStatement", AstFrom("varname"), AstFrom("exp"));

49:

  50: // Outputs a 'ReturnStatement' node whose child is the expression to return

  51: returnStatement.Production = @return + expression["exp"].OnErrorContinue() + @semiColon.OnErrorContinue()

  52:     > Ast("ReturnStatement", AstFrom("exp"));

53:

  54: // Outputs the resulting node from the EqualityExpression

  55: expression.Production = equalityExpression["exp"] > AstFrom("exp");

56:

  57: // Outputs the resulting node from the AdditiveExpression; or if an equality operator is found,

  58: //   outputs a '==' or '!=' node whose children are the left and right child expressions of the operator

  59: equalityExpression.Production = additiveExpression["leftexp"] +

  60:     ((@equality | @inequality).SetLabel("op") +

  61:     equalityExpression["rightexp"].OnErrorContinue()).Optional()

  62:     > AstValueOfConditional(AstChildFrom("op"), AstFrom("leftexp"), AstFrom("rightexp"));

63:

  64: // Outputs the resulting node from the MultiplicativeExpression; or if an additive operator is found,

  65: //   outputs a '+' or '-' node whose children are the left and right child expressions of the operator

  66: additiveExpression.Production = multiplicativeExpression["leftexp"] +

  67:     ((@addition | @subtraction).SetLabel("op") +

  68:     additiveExpression["rightexp"].OnErrorContinue()).Optional()

  69:     > AstValueOfConditional(AstChildFrom("op"), AstFrom("leftexp"), AstFrom("rightexp"));

70:

  71: // Outputs the resulting node from the PrimaryExpression; or if an multiplicative operator is found,

  72: //   outputs a '*' or '/' node whose children are the left and right child expressions of the operator

  73: multiplicativeExpression.Production = primaryExpression["leftexp"] +

  74:     ((@multiplication | @division).SetLabel("op") +

  75:     multiplicativeExpression["rightexp"].OnErrorContinue()).Optional()

  76:     > AstValueOfConditional(AstChildFrom("op"), AstFrom("leftexp"), AstFrom("rightexp"));

77:

  78: // Outputs the result that came from the appropriate expression type that was matched...

  79: //   We don't want to wrap the results with a 'Expression' node so we use AstFrom

  80: primaryExpression.Production = numberExpression["exp"] > AstFrom("exp")

  81:     | functionAccessExpression["exp"] > AstFrom("exp")

  82:     | simpleName["exp"] > AstFrom("exp")

  83:     | parenthesizedExpression["exp"] > AstFrom("exp");

84:

  85: // Outputs the numeric value

  86: numberExpression.Production = @number.ToTerm().ToProduction();

87:

  88: // Outputs the name value

  89: simpleName.Production = @identifier.ToTerm().ToProduction();

90:

  91: // Outputs a 'FunctionAccessExpression' node with children:

  92: //   1) The function name

  93: //   2) An 'Arguments' node that contains each argument name; or nothing gets inserted

  94: //      if there are no arguments

  95: functionAccessExpression.Production = @identifier["name"] + @openParenthesis +

  96:     functionArgumentList["args"].Optional() + @closeParenthesis.OnErrorContinue()

  97:     > Ast("FunctionAccessExpression", AstFrom("name"), AstConditionalFrom("Arguments", "args"));

98:

  99: // Outputs a 'FunctionArgumentList' node whose children are argument expressions...

 100: //   Is an excellent sample of how to build node for a delimited list

 101: functionArgumentList.Production = expression["exp"] +

 102:     (@comma + expression["exp"].OnErrorContinue() > AstFrom("exp")).ZeroOrMore().SetLabel("moreexps")

 103:     > Ast("FunctionArgumentList", AstFrom("exp"), AstChildrenFrom("moreexps"));

 104:

 105: // Outputs a 'ParenthesizedExpression' node whose child is the contained expression

 106: parenthesizedExpression.Production = @openParenthesis + expression["exp"] +

 107:     @closeParenthesis.OnErrorContinue()

 108:     > Ast("ParenthesizedExpression", AstFrom("exp"));

Error handling in action

Now let’s see our error handling in action. We’ll use this input code:

   1: function Add(x, y {

   2:     return x + y;

   3: }

Note that there is a ) missing in the function declaration and a ) expected error is reported. But we still get this complete AST, as if there were no syntax error:

   1: CompilationUnit[

   2:     FunctionDeclaration[

   3:         "Add"

   4:         Parameters[

   5:             "x"

   6:             "y"

   7:         ]

   8:         Block[

   9:             ReturnStatement[

  10:                 +[

  11:                     SimpleName[

  12:                         "x"

  13:                     ]

  14:                     SimpleName[

  15:                         "y"

  16:                     ]

  17:                 ]

  18:             ]

  19:         ]

  20:     ]

  21: ]

Let’s create some more complex syntax errors now:

   1: invalid

   2: function Add(x,) {

   3:     return x +

   4: }

Here we have three syntax errors:

‘function’ expected that highlights the invalid word
Identifier expected that highlights the )
‘;’ expected that highlights the }

Even with three syntax errors, we still get an AST:

   1: CompilationUnit[

   2:     Error[]

   3:     FunctionDeclaration[

   4:         "Add"

   5:         Parameters[

   6:             "x"

   7:         ]

   8:         Block[

   9:             ReturnStatement[

  10:                 SimpleName[

  11:                     "x"

  12:                 ]

  13:             ]

  14:         ]

  15:     ]

  16: ]

You’ll note that an Error node was inserted as the first child of the CompilationUnit node. An Error node is inserted when a non-terminal fails to match but is told by error callbacks to continue on as is the case with the error handling we added.

Next steps

Today we’ve seen how to enhance a grammar to properly support robust error handling. Really this is about the last thing you need to do when designing a grammar.

In the next post, we’ll take a sneak peek at the grammar debugger that we’ve written.

Tags: wpf, silverlight, syntaxeditor

Filed under: Actipro, In development, Silverlight, WPF

August 13, 2010 at 01:58

SyntaxEditor grammar/AST framework part 7: Adding error handling

You've been kicked (a good thing) - Trackback from DotNetKicks.com

DotNetKicks.com

August 27, 2010 at 01:40

FeedBurner blog post RSS feed issue fixed

FeedBurner blog post RSS feed issue fixed

The Actipro Blog - WPF and WinForms Development

The Actipro Blog

Latest Twitter News

Month List

About Us