Re: Limits of regular languages

e0726905 <e0726905@student.tuwien.ac.at> writes:
> ...Is every regular language LL(1)? ...


Yes, this can be shown by an algorithm for constructing an LL(1)
grammar from any DFA. The grammar should have one nonterminal symbol
for each state in the DFA and one terminal symbol for each symbol in
the DFA's alphabet. The nonterminal corresponding to the start state
is the start symbol of the grammar. For each transition edge in the
DFA, say from S1 to S2 labeled with x, include a corresponding
production:


S1 -> x S2


Additionally, for every accepting state in the DFA, say A, include a
corresponding epsilon production:


A -> epsilon


To show this is an LL(1) grammar, you need to show the various
productions that share any particular left hand side have disjoint
FIRST sets for their right hand sides, and that if there is an epsilon
production, the FOLLOW set of the right hand side is also disjoint
from the various FIRST sets. In the constructed grammar, each
production of the form


S1 -> x S2


has just {x} for its FIRST set, and since the automaton was
deterministic, these must be disjoint. Also, given the form of the
productions, you can show that FOLLOW(A) = {$} for any (reachable)
nonterminal A, where $ is an end-of-input marker that must be
different from each of the alphabetic symbols labeling the
transitions.


To show that the grammar generates the same language as the DFA
recognizes, you would show that the parse trees of the grammar are in
a straightforward one-to-one correspondence with accepting paths
through the DFA.

Return to the comp.compilers page.
Search the comp.compilers archives again.