[antlr-interest] Newbie prob - nondeterminism :-(

[Robert Colquhoun]

Hello Anthony,

At 11:22 AM 24/03/2003 +0000, Anthony W. Youngman wrote:

>Thanks. I've now fixed this and got rid of the non-determinism. But I'm 
>still getting a hang. I've altered the grammar somewhat, and it's obvious 
>that it's hanging as it tries to back up. I don't know why.
>
>When I run it, my println statements show that it's got as far as 
>processing the EXIT statement, at which point the printlns should 
>presumably show that it's processed the IF. But it never gets there. And 
>if I comment out the IF, it's then obvious that it's processed the PRINT, 
>but it never gets as far as recognising the REPEAT and showing that it's 
>got there. So my problem clearly seems to be that I haven't got to grips 
>with making it recognise a complex thing like the IF/THEN or LOOP/REPEAT :-(

See below.

>Probably I should look at the java, but as a newbie there too I'll 
>probably just end up more confused than ever :-) ...

Have you any C++ experience? java is like a simplified version of that, the 
generated files are quite readable compared to lots of machine generated 
source i have seen ;-).

>Sample input (as before) ...
>
>       PROGRAM SHELL
>
>       LOOP
>          PRINT "X"
>          INPUT COMMAND
>          PRINT "Command is " : COMMAND
>          IF COMMAND EQ "Q" THEN EXIT
>       REPEAT
>    END
>
>Grammar ...
>....
>tokens {
>    LOOP="LOOP"; REPEAT="REPEAT";
>         PROGRAM="PROGRAM";
>         END="END";
>    PRINT="PRINT"; INPUT="INPUT";
>    EXIT="EXIT";
>         LOGIC_EQ="EQ";
>         IF="IF"; THEN="THEN"; ENDIF="ENDIF";
>         NULL="NULL";
>         LABEL;
>         WHILE; UNTIL;
>         MULT; OR;
>}


Not sure why you need to do this? if lexer and parser are in the same file 
the Tokens defined in the parser are automatically propagated back to the 
lexer.  Only artificial token types which have no representation in the 
lexer or parser need be specified ie tokens like "EXPR" to group all the 
different types of expressions under one label.

>entry : ( (WS|nl)* programst (WS|nl)* ) EOF ;
>
>programst : ( pr:PROGRAM^ id:IDENT ( control | statement )+ END 
>{System.out.println(pr + " " + id+" program ");} );
>
>nl : ( EOL {System.out.println("New line");});
>
>loopst : ( lp:LOOP^ EOL statement_list rp:REPEAT EOL 
>{System.out.println(lp+" "+rp+" loop ");} );
>
>ifst : (iff:IF^ logicexpr thenn:THEN statement {System.out.println(iff + " 
>" + thenn+" if/then ");} ) ;
>
>statement : ( inputst | printst | exitst | NULL )+ EOL ;
>
>control : ( loopst | ifst )+ EOL ;
>
>statement_list : ( ( statement )+ EOL ) ;

Look carefully at the above rules you come in on "entry" which goes into 
"programst" which loops around matching "controls" or "statements".

Looking at "control" it requires a EOL to match to terminate the 
rule.....*but* "ifst" and "loopst" both also require an EOL to terminate 
the rules......ie 2 EOL's are required to match.

PS I did the above in my head, there could quite possibly be other problems 
in the grammar as well...

  - Robert



 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/