An LL(1) grammar is a context-free grammar for which a recursive descent parser can always tell what to do next based on just one token of lookahead.
The grammar you were given for assignment 3 is not LL(1). Here's an equivalent grammar in LL(1) form:
<message> ::= <optWS> <msg> <optWS>
<msg> ::= <integer>
| <identifier>
| <string>
| <list>
<list> ::= <lparen> <optWS> <listTail>
<listTail> ::= <rparen>
| <msg> <listTail2>
<listTail2> ::= <rparen>
| <whitespace> <listTail>
<integer> ::= <digit> <integerTail>
<integerTail> ::=
| <digit> <integerTail>
<identifier> ::= <letter> <idTail>
<idTail> ::=
| <letter> <idTail>
| <digit> <idTail>
<string> ::= <doublequote> <characters> <doublequote>
<optWS> ::=
| <whitespace> <optWS>
<whitespace> ::= <whitechar> <optWS>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| A | B | C | D | E | F | G | H | I | J | K | L | M
| N | O | P | Q | R | S | T | U | V | W | X | Y | Z
<doublequote> ::= "
<characters> ::=
::= <character> <characters>
<character> ::= <digit>
| <letter>
| <space>
<whitechar> ::= <space>
| <newline>
When the grammar is in LL(1) form, it's easy to write a recursive descent parser that decides what to do by looking at the next token (or, in this case, character) of the input.
It took the instructor about an hour to write a quick-and-dirty recursive descent parser for assignment 3. Here are the first few lines of that parser.
#!/usr/bin/env scheme-script
#!r6rs
(import (rnrs))
(define (accept-input)
(exit 0))
(define (reject-input)
(display "ERROR")
(newline)
(exit 1))
(define (parse-message)
(parse-optWS)
(parse-msg)
(parse-optWS)
(if (eof-object? (read-char))
(accept-input)
(reject-input)))
(define (parse-msg)
(let ((c (peek-char)))
(cond ((digit? c)
(parse-integer))
((letter? c)
(parse-identifier))
((doublequote? c)
(parse-string))
((lparen? c)
(parse-list))
(else
(reject-input)))))
Last updated 19 January 2014.