I tried some examples and found that LL(1) grammar always exist.
I tried searching for formal proof but didn't find any.
Can someone give a formal proof for the above statement?
$\begingroup$
$\endgroup$
4
-
4$\begingroup$ Have you tried proving it yourself? You need to construct a grammar from a deterministic finite automaton. $\endgroup$– adrianNOct 6 '17 at 15:51
-
$\begingroup$ Use the characterisation with FIRST and FOLLOW sets. $\endgroup$– Raphael ♦Oct 6 '17 at 23:11
-
$\begingroup$ Express the corresponding DFA as a grammar. Each state becomes a non-terminal. The transitions from a state become a production. Terminal states disjoin the empty state. $\endgroup$– ThumbnailOct 7 '17 at 10:24
-
$\begingroup$ Use a left-regular or a right-regular grammar. $\endgroup$– Yuval FilmusOct 7 '17 at 10:32
Add a comment
|