| Performance question [message #1716043] |
Mon, 30 November 2015 19:20  |
 Luis De Bello
Messages: 95
Registered: January 2015 |
Member |
|
|
Hi guys,
Based on one previous question about performance, I reduced my grammar to reduce the numbers of rules in order to analyse the performance.
I was able to simplified a lot and now I am trying to resolve the issue, maybe some of you can help me with some ideas on how to change my grammar to fully support the syntax that I need
Grammar:
grammar org.mule.tooling.dfl.DFL hidden(WS, EOL)
import "http://www.eclipse.org/emf/2002/Ecore" as ecore
generate dFL "http://www.mule.org/tooling/dfl/DFL"
Document:
content=Content;
Content:
elements+=Expression;
SingleKeyValuePairObj:
element=ObjectElement;
MultipleKeyValuePairObj:
{MultipleKeyValuePairObj} "{" (elements+=ObjectElement ((-> "," elements+=ObjectElement) | ",")*)? "}";
ObjectElement:
=> ConditionalKeyValuePair | => KeyValuePair | EnclosedExpression;
KeyValuePair:
key=Key ":" (-> value=Expression?);
ConditionalKeyValuePair:
"(" key=Key ":" value=Expression ")" "when" condition=Expression;
Key:
value=KeyExpression;
KeyExpression:
LiteralValue | EnclosedExpression;
Expression:
OrExpression;
OrExpression returns Expression:
AndExpression (-> ({Or.left=current} "or") right=AndExpression)*;
AndExpression returns Expression:
Atomic (-> ({And.left=current} "and") right=Atomic)*;
Atomic returns Expression:
=> SingleKeyValuePairObj | LiteralValue | MultipleKeyValuePairObj | EnclosedExpression;
EnclosedExpression returns Expression:
"(" Expression ")";
LiteralValue:
{QuotedStringLiteral} value=QuotedStringLiteral | {BooleanLiteral} value=BooleanLiteral | {NullLiteral} value=NullLiteral;
NullLiteral:
"null";
BooleanLiteral returns ecore::EBoolean:
"true" | "false";
QuotedStringLiteral:
STRING;
terminal STRING:
'"' ('\\' . /* 'b'|'t'|'n'|'f'|'r'|'u'|'"'|"'"|'\\' */ | !('\\' | '"'))* '"'? |
"'" ('\\' . /* 'b'|'t'|'n'|'f'|'r'|'u'|'"'|"'"|'\\' */ | !('\\' | "'"))* "'"?;
terminal WS:
(' ' | '\t')+;
terminal EOL:
LINE_BREAK;
terminal fragment LINE_BREAK:
('\r' | '\n');
This grammar support these expressions
{
"SimpleField": "SimpleValue",
"SimpleField": "SimpleField": "SimpleValue",
"ComplexField": (((((((((true) and (false) and (true)) and (false))) and (false)))))),
("DynamicField"): "SimpleValue",
("ConditionalExpression"),
("SimpleField": "SimpleValue") when true
}
However it takes 3-4 seconds to parse this, but if I remove the line ["ComplexField": (((((((((true) and (false) and (true)) and (false))) and (false))))))] it runs in less that 300 ms.
I used some profiling tool and I noted that if I remove the "EnclosedExpression" from "KeyExpression" it runs ok but it means that I cannot support all the cases
Does someone have some idea about how to continue supporting all my cases in a decent time?
Thanks in advance
Regards,
Luis
|
|
|
| Re: Performance question [message #1716046 is a reply to message #1716043] |
Mon, 30 November 2015 20:20  |
Ed Willink
Messages: 7655
Registered: July 2009 |
Senior Member |
|
|
Hi
You have multiple uses for "(" ... ")" consequently backtracking has
alternatives at Atomic and so it is quite possible that your expression
terms go exponential.
major solution: avoid "(" .. ")" ambiguity, or refactor to eliminate it.
minor solution: avoid nested complexity and precedence predicates
Expression:
Atomic ({Exp.left=current} BinaryOperator) right=Atomic)*;
BinaryOperator: "and" | "or";
and resolve precedence semantically.
Regards
Ed Willink
On 30/11/2015 19:21, Luis De Bello wrote:
> Hi guys,
>
> Based on one previous question about performance, I reduced my grammar
> to reduce the numbers of rules in order to analyse the performance. I
> was able to simplified a lot and now I am trying to resolve the issue,
> maybe some of you can help me with some ideas on how to change my
> grammar to fully support the syntax that I need
>
> Grammar:
>
>
> grammar org.mule.tooling.dfl.DFL hidden(WS, EOL)
>
> import "http://www.eclipse.org/emf/2002/Ecore" as ecore
> generate dFL "http://www.mule.org/tooling/dfl/DFL"
>
> Document:
> content=Content;
>
> Content:
> elements+=Expression;
>
> SingleKeyValuePairObj:
> element=ObjectElement;
>
> MultipleKeyValuePairObj:
> {MultipleKeyValuePairObj} "{" (elements+=ObjectElement ((-> ","
> elements+=ObjectElement) | ",")*)? "}";
>
> ObjectElement:
> => ConditionalKeyValuePair | => KeyValuePair | EnclosedExpression;
>
> KeyValuePair:
> key=Key ":" (-> value=Expression?);
>
> ConditionalKeyValuePair:
> "(" key=Key ":" value=Expression ")" "when" condition=Expression;
>
> Key:
> value=KeyExpression;
>
> KeyExpression:
> LiteralValue | EnclosedExpression;
>
>
> Expression:
> OrExpression;
>
> OrExpression returns Expression:
> AndExpression (-> ({Or.left=current} "or") right=AndExpression)*;
>
> AndExpression returns Expression:
> Atomic (-> ({And.left=current} "and") right=Atomic)*;
>
> Atomic returns Expression:
> => SingleKeyValuePairObj | LiteralValue | MultipleKeyValuePairObj |
> EnclosedExpression;
>
> EnclosedExpression returns Expression:
> "(" Expression ")";
>
> LiteralValue:
> {QuotedStringLiteral} value=QuotedStringLiteral | {BooleanLiteral}
> value=BooleanLiteral | {NullLiteral} value=NullLiteral;
>
> NullLiteral:
> "null";
>
> BooleanLiteral returns ecore::EBoolean:
> "true" | "false";
>
> QuotedStringLiteral:
> STRING;
>
> terminal STRING:
> '"' ('\\' . /* 'b'|'t'|'n'|'f'|'r'|'u'|'"'|"'"|'\\' */ | !('\\' |
> '"'))* '"'? |
> "'" ('\\' . /* 'b'|'t'|'n'|'f'|'r'|'u'|'"'|"'"|'\\' */ | !('\\' |
> "'"))* "'"?;
>
> terminal WS:
> (' ' | '\t')+;
>
> terminal EOL:
> LINE_BREAK;
>
> terminal fragment LINE_BREAK:
> ('\r' | '\n');
>
>
> This grammar support these expressions
>
> {
> "SimpleField": "SimpleValue",
> "SimpleField": "SimpleField": "SimpleValue",
> "ComplexField": (((((((((true) and (false) and (true)) and
> (false))) and (false)))))),
> ("DynamicField"): "SimpleValue",
> ("ConditionalExpression"),
> ("SimpleField": "SimpleValue") when true
> }
>
>
> However it takes 3-4 seconds to parse this, but if I remove the line
> ["ComplexField": (((((((((true) and (false) and (true)) and (false)))
> and (false))))))] it runs in less that 300 ms.
>
> I used some profiling tool and I noted that if I remove the
> "EnclosedExpression" from "KeyExpression" it runs ok but it means that I
> cannot support all the cases
>
> Does someone have some idea about how to continue supporting all my
> cases in a decent time?
>
> Thanks in advance
>
> Regards,
> Luis
>
|
|
|
|
|
|
Powered by
FUDForum. Page generated in 0.01884 seconds
] 
Search
Help
Register
Login
Home
