# Is this a proper LL(1) Grammar?

Please take this question with a grain of salt. I'm trying to write a very simple layout engine and wanted to formally create a grammar to parse the input. I stayed up all night researching LL(k) parsers - mostly from papers from different colleges. They tend to use the same examples and I've never been a fan of abstracting through notation, so I'm almost positive I have the syntax incorrect.

The input is very trivial:

header>rows>h-row>a|b

main>rows>m-row>qs|d
qs>qs-row>qa|qu

footer>rows>f-row>a|b


And this is the grammar definition:

S -> aBC
B -> op
C -> a


First:

S: [a]
B: [>, |, /]
C: [a]


Follow:

S: $$C:$$
B: C | S


It's a perfectly valid grammar, and it's certainly LL(1). But since it only generates three sentences, it's probably not what you are looking for.

The three sentences:

a < a
a | a
a / a


For precision: As written, it's not quite correct. In order to achieve what I imagine you meant by the FIRST sets, you'd actually need to he a bit more precise. Instead of using $$op$$, you write:

\begin{align}B& \to \mathbb{<}\\ B&\to\text{|}\\ B&\to\text{/} \end{align}

Alternatively, you could define $$op$$ as the three possible operators, as above, and leave $$B\to op$$.

Also: $$FOLLOW$$ sets (like $$FIRST$$ sets) are sets of terminals. So $$S$$ and $$C$$ are not going to be found in any $$FOLLOW$$ set. $$FOLLOW(B)$$ is $$\{a\}$$.

• Thanks for your response! It's encouraging to know I didn't go completely off the rails. Could you perhaps explain follow sets a bit more? I'm sure you did a great job explaining to begin with, but I'm having a bit of trouble grokking it. – iwannawriteacompiler Feb 26 at 20:49
• $FOLLOW(N)$, where $N$ is a non-terminal, is the set of terminals which might in some valid sentence immediately follow the derivation of $N$. In other words, it is the union of the $FIRST$ sets of the part following $N$ in each right-hand side which includes $N$, plus the $FOLLOW$ sets of each non-terminal whose right-hand side might end with $N$. If the second description seems complicated, start with the first one, which is the actual meaning (as opposed to an algorithm which computes the set). – rici Feb 26 at 20:55