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:




And this is the grammar definition:

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


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


S: $
C: $
B: C | S

1 Answer 1


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\}$.

  • $\begingroup$ 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. $\endgroup$ Feb 26, 2019 at 20:49
  • $\begingroup$ $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). $\endgroup$
    – rici
    Feb 26, 2019 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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