tolmasky/language — Issue #13: Difficult parse trees
Author: andrewdep
Created: 2012-01-14 05:47:50+00:00
State: open

The JavaScript grammar produces parse trees that can be very difficult to work with. Take this simple JavaScript:

function() { console.log(30); }

It parses to the tree below (output via util.inspect in nodejs). The JavaScript grammar has rules like this:

AssignmentExpression =
LeftHandSideExpression _ AssignmentOperator _ AssignmentExpression /
ConditionalExpression
...
ConditionalExpression =
LogicalOrExpression (_ "?" _ AssignmentExpression _ ":" _ AssignmentExpression)?
...
LogicalOrExpression =
LogicalAndExpression (_ "||" _ LogicalAndExpression)*
...
LogicalAndExpression =
BitwiseOrExpression (_ "&&" _ BitwiseOrExpression)*

And so on... so, while 30 is a numeric literal, I end up with all these nested nodes that don't actually exist in that part of the source code (ConditionalExpression -> LogicalOrExpression -> LogicalAndExpression -> BitwiseOrExpression -> and so on) - 30 is not a ConditionalExpression, it's not a LogicalOrExpression, it's not a LogicalAndExpression... you get the idea. I have to either make my code smart enough to ignore these particular types when they are incomplete (which is a pain), or prune them out of my tree (which is also a pain)... and both of those are a performance hit.
Surely this is a common issue with peg parsers that has a standard solution? I'm not familiar enough with PEG parsers yet to know the answer, but it would be nice if I had an option to generate a parser that would not add misleading/pointless intermediate elements.

{ name: '#document',
source: 'function() { console.log(30); }',
range: { location: 0, length: 0 },
children:
[ { name: 'start',
source: 'function() { console.log(30); }',
range: { location: 0, length: 31 },
children:
[ { name: '_',
source: 'function() { console.log(30); }',
range: { location: 0, length: 0 },
children: [] },
{ name: 'SourceElements',
source: 'function() { console.log(30); }',
range: { location: 0, length: 31 },
children:
[ { name: 'SourceElement',
source: 'function() { console.log(30); }',
range: { location: 0, length: 31 },
children:
[ { name: 'Statement',
source: 'function() { console.log(30); }',
range: { location: 0, length: 31 },
children:
[ { name: 'FunctionExpression',
source: 'function() { console.log(30); }',
range: { location: 0, length: 31 },
children:
[ { name: 'FUNCTION',
source: 'function() { console.log(30); }',
range: { location: 0, length: 8 },
children: [ 'function' ] },
{ name: '_',
source: 'function() { console.log(30); }',
range: { location: 8, length: 0 },
children: [] },
{ name: '_',
source: 'function() { console.log(30); }',
range: { location: 8, length: 0 },
children: [] },
'(',
{ name: '_',
source: 'function() { console.log(30); }',
range: { location: 9, length: 0 },
children: [] },
{ name: '_',
source: 'function() { console.log(30); }',
range: { location: 9, length: 0 },
children: [] },
')',
{ name: '_',
source: 'function() { console.log(30); }',
range: { location: 10, length: 1 },
children:
[ { name: 'WhiteSpace',
source: 'function() { console.log(30); }',
range: { location: 10, length: 1 },
children: [ ' ' ] } ] },
'{',
{ name: '_',
source: 'function() { console.log(30); }',
range: { location: 12, length: 1 },
children:
[ { name: 'WhiteSpace',
source: 'function() { console.log(30); }',
range: { location: 12, length: 1 },
children: [ ' ' ] } ] },
{ name: 'FunctionBody',
source: 'function() { console.log(30); }',
range: { location: 13, length: 17 },
children:
[ { name: '_',
source: 'function() { console.log(30); }',
range: { location: 13, length: 0 },
children: [] },
{ name: 'SourceElements',
source: 'function() { console.log(30); }',
range: { location: 13, length: 16 },
children:
[ { name: 'SourceElement',
source: 'function() { console.log(30); }',
range: { location: 13, length: 16 },
children:
[ { name: 'Statement',
source: 'function() { console.log(30); }',
range: { location: 13, length: 16 },
children:
[ { name: 'ExpressionStatement',
source: 'function() { console.log(30); }',
range: { location: 13, length: 16 },
children:
[ { name: 'Expression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'AssignmentExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'ConditionalExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'LogicalOrExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'LogicalAndExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'BitwiseOrExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'BitwiseXOrExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'BitwiseAndExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'EqualityExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'RelationalExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'ShiftExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'AdditiveExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'MultiplicativeExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'UnaryExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'PostfixExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'LeftHandSideExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'CallExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 15 },
children:
[ { name: 'MemberExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 11 },
children:
[ { name: 'PrimaryExpression',
source: 'function() { console.log(30); }',
range: { location: 13, length: 7 },
children:
[ { name: 'Identifier',
source: 'function() { console.log(30); }',
range: { location: 13, length: 7 },
children:
[ { name: 'IdentifierName',
source: 'function() { console.log(30); }',
range: { location: 13, length: 7 },
children:
[ { name: 'IdentifierStart',
source: 'function() { console.log(30); }',
range: { location: 13, length: 1 },
children:
[ { name: 'UnicodeLetter',
source: 'function() { console.log(30); }',
range: { location: 13, length: 1 },
children: [ 'c' ] } ] },
{ name: 'IdentifierPart',
source: 'function() { console.log(30); }',
range: { location: 14, length: 1 },
children:
[ { name: 'IdentifierStart',
source: 'function() { console.log(30); }',
range: { location: 14, length: 1 },
children:
[ { name: 'UnicodeLetter',
source: 'function() { console.log(30); }',
range: { location: 14, length: 1 },
children: [ 'o' ] } ] } ] },
{ name: 'IdentifierPart',
source: 'function() { console.log(30); }',
range: { location: 15, length: 1 },
children:
[ { name: 'IdentifierStart',
source: 'function() { console.log(30); }',
range: { location: 15, length: 1 },
children:
[ { name: 'UnicodeLetter',
source: 'function() { console.log(30); }',
range: { location: 15, length: 1 },
children: [ 'n' ] } ] } ] },
{ name: 'IdentifierPart',
source: 'function() { console.log(30); }',
range: { location: 16, length: 1 },
children:
[ { name: 'IdentifierStart',
source: 'function() { console.log(30); }',
range: { location: 16, length: 1 },
children:
[ { name: 'UnicodeLetter',
source: 'function() { console.log(30); }',
range: { location: 16, length: 1 },
children: [ 's' ] } ] } ] },
{ name: 'IdentifierPart',
source: 'function() { console.log(30); }',
range: { location: 17, length: 1 },
children:
[ { name: 'IdentifierStart',
source: 'function() { console.log(30); }',
range: { location: 17, length: 1 },
children:
[ { name: 'UnicodeLetter',
source: 'function() { console.log(30); }',
range: { location: 17, length: 1 },
children: [ 'o' ] } ] } ] },
{ name: 'IdentifierPart',
source: 'function() { console.log(30); }',
range: { location: 18, length: 1 },
children:
[ { name: 'IdentifierStart',
source: 'function() { console.log(30); }',
range: { location: 18, length: 1 },
children:
[ { name: 'UnicodeLetter',
source: 'function() { console.log(30); }',
range: { location: 18, length: 1 },
children: [ 'l' ] } ] } ] },
{ name: 'IdentifierPart',
source: 'function() { console.log(30); }',
range: { location: 19, length: 1 },
children:
[ { name: 'IdentifierStart',
source: 'function() { console.log(30); }',
range: { location: 19, length: 1 },
children:
[ { name: 'UnicodeLetter',
source: 'function() { console.log(30); }',
range: { location: 19, length: 1 },
children: [ 'e' ] } ] } ] } ] } ] } ] },
{ name: '_',
source: 'function() { console.log(30); }',
range: { location: 20, length: 0 },
children: [] },
{ name: 'DotAccessor',
source: 'function() { console.log(30); }',
range: { location: 20, length: 4 },
children:
[ '.',
{ name: '_',
source: 'function() { console.log(30); }',
range: { location: 21, length: 0 },
children: [] },
{ name: 'IdentifierName',
source: 'function() { console.log(30); }',
range: { location: 21, length: 3 },
children:
[ { name: 'IdentifierStart',
source: 'function() { console.log(30); }',
range: { location: 21, length: 1 },
children:
[ { name: 'UnicodeLetter',
source: 'function() { console.log(30); }',
range: { location: 21, length: 1 },
children: [ 'l' ] } ] },
{ name: 'IdentifierPart',
source: 'function() { console.log(30); }',
range: { location: 22, length: 1 },
children:
[ { name: 'IdentifierStart',
source: 'function() { console.log(30); }',
range: { location: 22, length: 1 },
children:
[ { name: 'UnicodeLetter',
source: 'function() { console.log(30); }',
range: { location: 22, length: 1 },
children: [ 'o' ] } ] } ] },
{ name: 'IdentifierPart',
source: 'function() { console.log(30); }',
range: { location: 23, length: 1 },
children:
[ { name: 'IdentifierStart',
source: 'function() { console.log(30); }',
range: { location: 23, length: 1 },
children:
[ { name: 'UnicodeLetter',
source: 'function() { console.log(30); }',
range: { location: 23, length: 1 },
children: [ 'g' ] } ] } ] } ] } ] } ] },
{ name: '_',
source: 'function() { console.log(30); }',
range: { location: 24, length: 0 },
children: [] },
{ name: 'Arguments',
source: 'function() { console.log(30); }',
range: { location: 24, length: 4 },
children:
[ '(',
{ name: '_',
source: 'function() { console.log(30); }',
range: { location: 25, length: 0 },
children: [] },
{ name: 'ArgumentList',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'AssignmentExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'ConditionalExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'LogicalOrExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'LogicalAndExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'BitwiseOrExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'BitwiseXOrExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'BitwiseAndExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'EqualityExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'RelationalExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'ShiftExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'AdditiveExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'MultiplicativeExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'UnaryExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'PostfixExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'LeftHandSideExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'NewExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'MemberExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'PrimaryExpression',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'Literal',
source: 'function() { console.log(30); }',
range: { location: 25, length: 2 },
children:
[ { name: 'NumericLiteral',