Are regular expressions $LR(k)$?

Problem Detail: 

If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I know if a type 3 grammar is $LR(1)$, $LL(1)$, $SLR(1)$, etc. without constructing any parse tables?

Asked By : Andrea Tucci

Answered By : templatetypedef

All regular languages have LL(1) grammars. To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), then convert it to a right-recursive regular grammar. This grammar is then LL(1), because any pair of productions for the same nonterminal either start with different symbols, or one produces ε and has $ as a lookahead token. Consequently, all regular languages are also LR(1), since any LL(1) grammar is LR(1). Additionally, using an important result from this paper, you can show that any LR(1) language has an SLR(1) grammar, meaning that any regular language has an SLR(1) grammar.

However, the regular languages are not all LR(0). The LR(0) languages have very specific properties - in particular, they must be prefix-free. Thus the regular language {a, aa} is not LR(0), though it's clearly regular (regex a|(aa)). However, the LR(0) languages are not properly contained within the regular languages; this grammar for { 0ⁿ21ⁿ | n ≥ 1 } is LR(0), but the language is not regular:

S -> E E -> 0E1 | 2 

Hope this helps!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2713