[antlr-interest] Implementation decision help

Gustaf Johansson gustaf.j at gmail.com
Wed Jul 8 07:44:19 PDT 2009


On Wed, Jul 8, 2009 at 4:16 PM, Jim Idle<jimi at temporal-wave.com> wrote:
>
>
> On Jul 8, 2009, at 4:59 AM, Gustaf Johansson <gustaf.j at gmail.com> wrote:
>
>> Hello!
>>
>> I am trying to implement the ETSI TTCN-3 BNF into Antlr.
>> The major part is done and working as it should but there are some
>> quirks which i don't know how to solve.
>>
>> I have rules like this:
>> stm : stmGroup1 | stmGroup2 ... | stmGroupX;
>>
>> And all/some of these stmGroup's can start with the same type of
>> token, but they are distinguishable by some token along the line
>> further down the parse tree.
>>
>> I have tried to solve this by using backtrack=true which didn't work.
>>
>> My current solution is a specific order of the stmGroup's and a few
>> syntactic predicates. But i don't like this solution since i don't
>> know if it will work for all possible input (the grammar is really
>> complex).
>>
>> Basically what i want to accomplish is make Antlr try all of the rules
>> in "stm" and only report error if none of them matches. Currently it
>> reports errors even though a rule later in the list will match the
>> input completely, just because the rule reporting the error matches it
>> partly.
>>
>> The only solution other then syntactic predicates and backtrack i can
>> think of is to combine the stmGroup's into a rule which has truly
>> distinctive paths depending on the next token.
>> Is this the way to do it?
>
> Yes.
>
>> It will require a huge amount of work since all the stmGroup's are
>> quite large and complex themselves. Also it will make the grammar
>> almost unreadable.
>
> I think you will find that it doesn't result in an readable grammar in fact.
> Formatting is your friend here.
>
You mean it will be readable i suppose.

> I keep trying to influence people to practice by presenting an approach to
> writing such grammars. But I think people basically download Works and start
> typing. There are lots of posts about left factoring, not using backtrack
> and so on. Basically the normative spec is rarely written with the parser
> programmer in mind and you must interpolate.
>
I want the parser grammar to differ from the spec as little as
possible so its easy to add changes aso for other people.

> Generally you can get backtrack to work as you want but with terrible error
> messages. If you can't then I would suggest starting again and use the
> recommended incremental approach to building grammars. You already have a
> lexer so you can cut and paste parser pieces until you get it correct.
>
This is what ive done, i had backtrack on at first, which you
suggested me to remove and then redo the grammar.

Ive done that and have 12 rules that currently have syntactic
predicates in order to remove:
"Decision can match x using multiple alts..." warnings and
"non-LL(*) recursion" errors.

So i just want to know the correct way to get those right as well,
without using syntactic predicates if possible.


As you have stated, my next move will be to left-factor the statements
rule and format it nicely if possible.

Thanks for the help!

/Gustaf

>
> Jim
>
>>
>>
>>
>> An example of a problematic rule is:
>>
>> http://www.trex.informatik.uni-goettingen.de/trac/wiki/ttcn-3_4.0.4#FunctionStatement
>>
>> These are two parts of that problem:
>> -> ConfigurationStatements -> StartTCStatement
>> -> TimerStatements -> StartTimerStatement
>>
>> PS. backtrack is not used at all in the grammar.
>>
>> BR Gustaf
>>
>> List: http://www.antlr.org/mailman/listinfo/antlr-interest
>> Unsubscribe:
>> http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>


More information about the antlr-interest mailing list