Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|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
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:


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|cite|improve this answer
very interesting! – didierc Feb 21 '13 at 21:27

Your Answer


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.