grammarcontext-free-grammarll-grammar# Definition of First and Follow sets of the right-hand sides of production

I am learning about LL(1) grammars. I have a task of checking if grammar is LL(1) and if not, I then need to find the rules, which prevent it from being LL(1). I came across this link https://www.csd.uwo.ca/~mmorenom/CS447/Lectures/Syntax.html/node14.html which has a theorem which can be used as a criteria for deciding if grammar is LL(1) or not. It says that for any rule `A -> alpha | beta `

some equalities, considering FIRST and FOLLOW sets need to be true. Therefore, I need to find FIRST and FOLLOW sets of these right-hand sides of production.

Let's say, I have following rules ` A -> a b B S | eps`

. How do I calculate FIRST and FOLLOW of `a b B S`

? As far as I understand by definition these sets are defined only for 1 non-terminal symbol.

Solution

The idea behind the FIRST function is that it returns the set of terminals which could possibly start the expansion of its argument. It's usual to also add the special object ε (which is a way of writing an empty sequence of symbols) if ε is a possible expansion.

So if *a* is a terminal, FIRST(*a*) is just { a }. And if *A* is a non-terminal, FIRST(*A*) is the set of non-terminals which could possibly appear at the beginning of a derivation of *A*. Finally, FIRST(ε) must be { ε }, according to the convention described above.

Now suppose α is a (possibly empty) sequence of grammar symbols:

- If α is empty (that is, it's ε), FIRST(α) is { ε }
- If the first symbol in α is the terminal
*a*, FIRST(α) is { a }. - If the first symbol in α is the non-terminal
*A*, there are two possibilities. Let TAIL(α) be the rest of α after the first symbol. Now:- if ε ∈ FIRST(
*A*), then FIRST(α) is FIRST(A) ∪ FIRST(TAIL(α)). - otherwise, FIRST(α) is FIRST(
*A*).

- if ε ∈ FIRST(

Now, how do we compute FIRST(*A*), for every non-terminal *A*? Using the above definition of FIRST(α), we recursively define FIRST(*A*) to be the union of the sets FIRST(α) for every α which is the right-hand side of a production *A* → α.

The FOLLOW function defines the set of terminal symbols which might appear after the expansion of a non-terminal. It is only defined on non-terminals; if you look carefully at the LL(1) conditions on the page you cite, you'll see that FIRST is applied to a right-hand side, while FOLLOW is only applied to left-hand sides.

- Using grammar from a .grammar file with ruby
- Infinite recursion in pyparsing grammar for method signatures
- LALR Grammar for transforming text to csv
- ANTLR4 - Token recognition error and mismatched input
- What does the Equal Sign (not a token) in an ANTLR grammar mean?
- int a[] = {1,2,}; Why is a trailing comma in an initializer-list allowed?
- Antlr4 recover from error and continue parsing until EOF
- Strange syntax specification for python decorators
- How to build the antlr grammar provided?
- How to resolve the mistmatched input 'token' expecting 'LEXER_RULE'
- Lexing Issue in ANTLR4 Grammar for Fortran 2018: Token Misclassification
- Visual Studio Code TextMate match pattern with maximum possible length first
- How to match a single Unicode character in single quotes
- VSCode Extension - Grammar Injection Into Multiple Languages
- Operator precedence of `EXISTS`
- How to do I parse a input string in SLR(1) parser with grammar having epsilon?
- Perl6 grammar and action error : "Cannot find method 'ann' on object of type NQPMu"
- Bison parser shift/reduce conflict
- How can I construct a grammar that generates this language?
- ModuleNotFoundError: No java install detected. Please install java to use language-tool-python
- How to check if this grammar is ambiguous or not?
- A question about Python's pop and what does the grammar have to say?
- Debugging Python ANTLR4 Grammar
- Grammar for combinations of Numpy arrays
- Is the alternative operator in ABNF match first or longest?
- ANTLR4 matches to lexer rule instead of parser rule
- ANTLR4 Grammar for field validation
- a*b* and (ab)* same or not?
- Bison ID reduction conflict
- adding support for arrays in my antlr grammar