Algorithm for computing FIRST and FOLLOW sets for context-free grammars

parsing compiler-construction grammar ll
2 8 picture 2 8 · Nov 8, 2013 · Viewed 16.9k times · Source

I need an algorithm to computing FIRST and FOLLOW sets for a grammar.

Is there a simple algorithm or simple code for computing these?

Answer

templatetypedef picture templatetypedef · Nov 8, 2013

The standard algorithm for computing FIRST and FOLLOW sets is discussed in most compiler textbooks and books on parsing algorithms. I would be surprised if you were taking a course where this was covered and had no assigned reading or materials provided on this topic.

I taught a class on compiler construction and have some lecture slides that might be useful here. You might want to check out slides 303-304 of these slides on LL parsing for an algorithm that computes FIRST sets and slide 32 of these slides on LL parsing for an algorithm that computes FOLLOW sets.

Hope this helps!

Related questions

What is the difference between LR, SLR, and LALR parsers?

What is the actual difference between LR, SLR, and LALR parsers? I know that SLR and LALR are types of LR parsers, but what is the actual difference as far as their parsing tables are concerned? And how to show …

Read More
How to determine whether a language is LL(1) LR(0) SLR(1)

Is there a simple way to determine whether a grammar is LL(1), LR(0), SLR(1)... just from looking on the grammar without doing any complex analysis? For instance: To decide whether a BNF Grammar is LL(1) you have to calculate First …

Read More
How do I generate sentences from a formal grammar?

What's a common way of generating sentences from a grammar? I want an algorithm that's sort of the opposite of a parser. That is, given a formal context-free grammar (say LL), I want to generate an arbitrary sentence that conforms …

Read More