LL(1) grammar: calculating first and follow

[@gouthamgandi3496]

Great video thanks a lott ! (Passed the exam :) )

[@SamyaDaleh]

+goutham gandi Congratulations!

[@gouthamgandi3496]

***** Thank you :)

[@noussaimenhane]

what we studied is that what follows A are the FIRST(B) because we have the rule S---> aAB and we get FOLLOW(A)={b} (we don't add Ɛ) but because we have Ɛ in FIRST(B) we have to add the FOLLOW(B) to the set of FOLLOW(A) and it becomes {$,a,b} and what follows A also follows S since we have this A--->S so FOLLOW(S)={$,a,b}. please correct me if i'm wrong! i have an important homework! thank you in advance.

[@Samya_Daleh]

Oh, I see, I made a mistake. You're right. Thanks for the correction.

[@ThEcRaZyKiLlEr93]

Sorry, but First(S) = First(A) = {a,b,epsilon} ? Why not the epsilon?

[@Samya_Daleh]

The epsilon is the empty string. It's possible to have epsilon or let's say "no terminal" below the B, because of B -> epsilon. But it's not possible for S. Look, if you have S -> Ba, what happens when B is empty, then the B kinda "disappears" and a is the first letter below the S.

[@lagaleradelconejo5005]

2 years ago I saw this video to study for a college exam, now I want to make a calculator so I came back here xd

[@Samya_Daleh]

Welcome back!

[@NOSHEDMANTIS]

Please help, I'm stuck on this problem: "Use the Factorisation method to obtain an LL(1) grammar from the following grammar: S -> aaSb S -> abSb S -> abcSb S -> b" I worked out the director sets as {a},{b},{c},{b} (in order top to bottom), is this right? I cannot find a suitable factorisation... this is driving me nuts!

[@Samya_Daleh]

Thomas Dennis I had to look some things up first. The director set (as www.cs.bgu.ac.il/~comp131/wiki.files/ps4.pdf tells me) is whether the first set or if the nonterminal can be empty, the first set merged with the follow set. You don't have any productions here. The first set contains the first terminal that is below a nonterminal or in this case below the rhs of a grammar. For S -> aaSb you say it's a. Correct, because you see the leftmost symbol on the rhs is an a. But for S-> abSb and S -> abcSb it's an a aswell. That's where you have the ll(1) conflict, because if you began with an S and you know that your next input symbol is an a, you don't know if you should take rule 1, 2 or 3 as next, because they all could give you an a as next symbol. To resolve the conflict, you merge the same beginnings of rhs into one rule. The first 3 rules can give me an a, so I want to factor out a from S -> aaSb, S -> abSb, S -> abcSb I keep a and exchange the rest by a new nonterminal: S -> aX (former a of the first three S-rules) X -> aSb (former rhs of the first S-rule without that a) X -> bSb (from second S-rule) X -> bcSb (from third S-rule) Now if you have an S and your next input symbol is an a, you know exactly which rule to take, as there's only one possibility. However. If your nonterminal is X and your next input symbol is b, you have another conflict between two rules that you have to choose from. To resolve this conflict as well, you have to factor out b and add another symbol for the rest of the rhs. Can you figure the next step out on your own?

[@Samya_Daleh]

Thomas Dennis Yes, exactly. And yes, First(S)={a,b}, that's why they're both in the director set of the rule before the last rule. Thank you for the question. Maybe I make a video about that kind of problem.

[@bokajllensch661]

That inglisch is ja geil :D

[@thrakiamaria]

Meinst du Dinglisch? 🤣

[@alialiyev6510]

Follow(B) should be {a, b, $}. So add "b" as well.

[@Samya_Daleh]

+ali aliyev This mistake is already mentioned in the video description and in an annotation, but thanks.

[@adriansimionescu1877]

why is also follow to {b}?

[@Samya_Daleh]

Because B is at the end of a right rule side of S, hence B inherits the Follow set of S.

[@rohitbale15]

Follow(B) = {$,a,b} As Follow(S)={$,b}

[@manuchaud100]

It's very clear, thank you!

[@mariapiacolavito1189]

Sorry, i don't understand if this grammar is LL(1) or not..

[@Samya_Daleh]

Mariapia Colavito That's because I don't answer the question in this video, but in two others. One of them is this: kzbin.info/www/bejne/j4C5XpiIZ8qdq7s Thank you for mentioning. I'll add links to both videos to the description.

[@mariapiacolavito1189]

thanks

[@user-vi3no2ny1i]

Thank you very much!!!!!!

[@Samya_Daleh]

You're welcome. :)

[@sbacon92]

Why isn't epsilon included in the first (Ba)?

[@Samya_Daleh]

Epsilon is the empty word. If the B in Ba is epsilon, then the a is the first terminal. If you have the sequence Ba, it can never become an empty sequence, hence epsilon is not included in the first set.

[@sbacon92]

***** Thank you for the quick reply. This has helped me more than my professor.

[@paulboldijar3288]

Thanks for this answer!

[@naropaperez44]

God bless this video, thank you

[@salitotakhel3824]

why do we have to start with First(B)

[@Samya_Daleh]

We can start with any First set we want. B doesn't expand to other nonterminals, so I don't have to change it afterwards. It's just convenient.

[@teresalin5187]

Why is First(aAB) = {a}?

[@Samya_Daleh]

The question is which string (in this case of length 1, hence one terminal) comes "first" if we have aAB. Of course we're assuming that we're reading from left to right, so what's leftmost comes "first". In a CFG if we generated a terminal we can't get rid of it anymore. aAB already contains the a leftmost, which is a terminal, so the only terminal we can get leftmost when having aAB is a.

[@kemichethiziri2893]

thanks!

[@olafschol2020]

probably the worst english i ve heard in my life :D

[@Samya_Daleh]

You should've heard me in school, even my German friends were laughing about my pronunciation back then. I think I have improved a lot. :D