Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I am trying to define a non terminal symbol in a LALR(1) grammar (with CUP parser). It is requested that

the <code> token must appear exactly twice, 
while the <hour> token must appear at least once.

In the end I came up with this definition:

section     ::= hour_l CODE SC hour_l CODE SC hour_l ;
hour_l      ::= /* epsilon */ 
            | hour_l HOUR SC ;

where SC is a separator (semicolon) between tokens and hour_l is the non terminal symbol for hour's list. This solution has a problem: HOUR can be absent, because epsilon can be reduced from hour_l. Is there a clever solution other than specifying all possibilities or using the semantic capabilities of CUP (ie. putting a counter of how many times HOUR is present in section)? I'd prefer not to use semantics in order to achieve this; in fact, it seems to me this is syntax related.

Thanks

share|improve this question
    
if it's at least one, you must replace $\epsilon$ by the canonical element (here HOUR). –  didierc Feb 20 '13 at 17:59
add comment

1 Answer

up vote 2 down vote accepted

My solution, suggested by a friend, is to use a Finite State Machine. I drew a Deterministic Finite Automata, and $C$ is the final state accepted by this machine:

DFA

I then transformed it into a right regular grammar:

section     ::= c ;
a           ::= CODE SC ;
b           ::= a CODE SC ;
c           ::= c HOUR SC | b HOUR SC | e CODE SC ;
d           ::= HOUR SC | d HOUR SC ;
e           ::= e HOUR SC | a HOUR SC | d CODE SC ;

Hope it helps.

share|improve this answer
    
very interesting! –  didierc Feb 21 '13 at 21:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.