<Definition> ::= <Name> <LeftPar> <param> <RightPar>
<Name> ::= <Letter><LetterTail> 
<LetterTail> ::= <Letter><LetterTail> | ‘’

A question that confused when doing the derivation is the following. Lets say after matching f++u++n we match the last char 'c' with LetterTail and then match c with letter. When we peek now, it is '(' but how come we match it with the empty string?

Also how can I prove that it only uses one lookahead?

  • I see two votes for this question being off-topic (asking for help writing code). I do not believe this is the case. This is a question about a conceptual design problem with a parser and lexer with enough constraints to identify a good answer. In my opinion, this is a perfect fit for this community. +1, BTW. Commented May 23 at 15:59

1 Answer 1


A production rule for an empty string (or equivalently an empty token) can always succeed by consuming nothing from the input.

So, when you peek '(', the parser first tries the production <Letter><LetterTail> and tries to see if '(' matches <Letter>. When that fails, the parser backtracks to see if there is another way to proceed. When coming back to <LetterTail>, the parser tries the empty string and it can match that by not consuming any input.

This completes a number of <LetterTail> production rules and also the <Name> production rule.

To prove that you only need one lookahead, you need to prove that in all cases it is enough to know one unconsumed character to determine what to do next.

  • Thanks for you answer. I personally think this is a LL(1) grammar. But here is another part of my grammar. Here given 54, when we first start we peek 5 but how can we decide which way to go without looking at the next element? Another follor up question is before consuming a "token" for example "5" we must first derive it right? <int> :: <digit><int> | <digit> [The definition for digit] <digit> ::= 0|1|2|3|4|5|6|7|8|9
    – User
    Commented May 23 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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