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?

$\endgroup$

migrated from stackoverflow.com Jul 12 '12 at 19:41

This question came from our site for professional and enthusiast programmers.

15
$\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!

$\endgroup$
  • 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 '12 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.

$\endgroup$
  • $\begingroup$ Perl regular expressions works on NFA $\endgroup$ – loldop Jul 11 '12 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 '12 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 '12 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 '12 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 '12 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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