16
$\begingroup$

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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
16
$\begingroup$

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 { 0n21n | n ≥ 1 } is LR(0), but the language is not regular:

S -> E
E -> 0E1 | 2

Hope this helps!

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ The fact that right-regular grammars accept exactly the set of regular languages is usually done in class (or even the exercises), so the answer is that much more immediate. $\endgroup$
    – Raphael ♦
    Jul 18, 2012 at 0:52
2
$\begingroup$

(Plain old) regular expression syntax (you said "representation") is LR(0). You don't need any lookahead to parse a string representing a regex. You can easily decide this by running a parser generator on a grammar for regexes :-} You can also easily code a simple recursive descent (LL(0)) parser for regexps; anything which is LL(0) is LR(0).

I don't know if the syntax of more complicated so-called "regexps" such as Perl's are like this; but Perl's regexps are strictly more powerful than regexps so they are not plain old regexps.

To determine if a grammar has some property, you have to run some kind of predicate. To determine if it is (S)LR(k), you have to run a predicate that can check for that property. In effect, any such predicate must in effect build the parse tables, because of the way they are defined.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Perl regular expressions works on NFA $\endgroup$
    – loldop
    Jul 11, 2012 at 14:54
  • $\begingroup$ The question wasn't about how Perl regexps worked. It was about whether (Perl?) regexps were parsable by certain technologies. I can believe Perl regexps use a NFA to do their matching, along with some other context-sensitive data capture, but I don't see the relevance to the question. $\endgroup$
    – Ira Baxter
    Jul 11, 2012 at 14:57
  • 3
    $\begingroup$ -1 The regular expressions are not LR(0). LR(0) languages must be prefix-free, but the regular expression a|(aa) describes a language that is not prefix-free. Additionally, LR(0) languages cannot handle grammars with epsilon productions, so the regular language { epsilon, a } is not LR(0). However, the regular languages are LL(1) because you can write them as regular grammars, and thus they are all LR(1). Since any LR(1) language has an SLR(1) grammar, this means all regular languages are SLR(1). $\endgroup$
    – templatetypedef
    Jul 11, 2012 at 17:39
  • 1
    $\begingroup$ Concerning LL(0), it's the other way around: LL(0) languages are a proper subset of regular languages. Note that LL(0) means that you don't use lookahead for deciding between different derivations - which basically means there are no decisions and the language consists of a single word. LR(0), in contrast, is a useful class - again you don't use lookahead to decide (here for reductions), but there still is some diversity due to the fact that shifting can distinguish between different productions. $\endgroup$
    – Gunther
    Jul 11, 2012 at 19:57
  • 1
    $\begingroup$ @IraBaxter- The syntax of regular expressions is not LR(0) either because the regular expressions aren't prefix free. They aren't LL(0) either, because LL(0) languages can only contain a single string (or no strings). $\endgroup$
    – templatetypedef
    Jul 11, 2012 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.