LL(1) 语法和 first & follow 集合

Question

我认为下面实际上是 LL(1)，但我不是 100% 确定。我们是否能够证明这个 iss LL(1) 文法以及给出的第一个和后面的集合是否正确？我不太确定如何真正获得跟随集。

语法

expr ::= term {addop term}
term ::= factor {mulop factor}
factor ::= variable| unsigned-number| ( expr)
variable ::= identifier
addop ::= + | -
mulop ::= * | /

第一组

First(expr) = identifier, unsigned number, (
First(Term) = identifier, unsigned number, (
First(Factor) = identifier, unsigned number, (
First(Variable) = Identifier
First(addop) = +, -
First(mulop) = *, /

关注集合

Follow(Expr) = First(term)
Follow(Term) = First(Factor)

Do not understand how to do the Follow sets of the below sets
Follow(Factor) = First( ")" ) = )
Follow(Variable) Follow(addop) Follow(mulop)

Answer 1

第一组是正确的。

关注组：

FOLLOW(A) of non-terminal A is the set of terminal symbols that can follow in the derivation sequence

FOLLOW(expr): 检查它出现在产生式右侧的位置。就是有factor:=(expr)，当我们在推导中取这个产生式时，expr后面是)，expr是一个开始符号。

   FOLLOW(expr)={),$}

同样，

   FOLLOW(term) = FIRST(addop) U FOLLOW(expr) = {+,-,),$}
   FOLLOW(factor) = FIRST(mulop) U FOLLOW(trem) = {*,/,+,-,),$}
   FOLLOW(addop) = FIRST(term) = {identifier,unsigned number,(}
   FOLLOW(multop) = FIRST(factor) = {identifier,unsigned number,(}
   FOLLOW(Variable)= FOLLOW(factor) = {*,/,+,-,),$}

其中 $ 是输入的结尾。

给定的语法是 LL(1)。第一组因子是不相交的，我们不需要检查后续组，因为没有 epsilon 产生式。

LL(1) 语法和 first & follow 集合

LL(1) grammar and first & follow sets

compiler-construction

parsing

context-free-grammar