Sat, 13 Feb 2010 17:01:00 -0600

Related articles |
---|

Limits of regular languages e0726905@student.tuwien.ac.at (e0726905) (2010-02-11) |

Re: Limits of regular languages ott@mirix.org (Matthias-Christian Ott) (2010-02-13) |

Re: Limits of regular languages kkylheku@gmail.com (Kaz Kylheku) (2010-02-13) |

Re: Limits of regular languages cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-13) |

Re: Limits of regular languages max@gustavus.edu (Max Hailperin) (2010-02-13) |

Re: Limits of regular languages e0726905@student.tuwien.ac.at (e0726905) (2010-02-27) |

From: | Max Hailperin <max@gustavus.edu> |

Newsgroups: | comp.compilers |

Date: | Sat, 13 Feb 2010 17:01:00 -0600 |

Organization: | Compilers Central |

References: | 10-02-052 |

Keywords: | lex, DFA |

Posted-Date: | 13 Feb 2010 19:39:34 EST |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.