0
$\begingroup$

How can I construct an LR($k$) grammar (which $k$ is not really of interest for now) for a given language, say:

$$L=\left\{w \in \{a, b\}^\star \ | \ \exists u \in \{a, b\}, v \in \{a, b\}^\star: w = vu \wedge |w|_u \operatorname{mod} 2 = 0\right\}$$

($|w|_u$ denotes the number of $u$'s in $w$).

Please note that I don't want a right or left linear grammar although I KNOW that the language is regular. I am interested in the process of creating an LR($k$) grammar for an arbitrary, in general more complex language. (Feel free to ignore this example.)

Improve this question
$\endgroup$
4
  • $\begingroup$ What do you mean by "For the usually Chomsky types, this is easy". What is a Chomsky type ? East as opposed to what? Your question is very confused. $\endgroup$
    – babou
    Mar 11, 2015 at 11:32
  • 1
    $\begingroup$ Deciding whether a given grammar is LR(k) for some k is not computable; see here. For fixed k there are algorithms; see here. $\endgroup$
    – Raphael ♦
    Mar 11, 2015 at 11:39
  • $\begingroup$ Ok, maybe it's not my best question... But what I want to know is very simple - and actually it's just what the title says. Given a language (which is in $\mathcal{L}(LR(k))$ - as I have no such language at hand, I took the regular one) - how can I create an LR(k) grammar for it? How do I start - do I have to give some arbitrary cf grammar and try to prove that it's an LR(k) grammar or is there a better way? $\endgroup$
    – lukas.coenig
    Mar 11, 2015 at 13:41
  • $\begingroup$ I changed the question, hopefully it's clearer now... $\endgroup$
    – lukas.coenig
    Mar 11, 2015 at 13:48

1 Answer 1

Reset to default
1
$\begingroup$

You question is very strangely stated. The answer is however very trivial. Your language $L$ is a regular language, hence recognizable by a DFA. It does not even need a pushdown stack. Hence it has to be LR(k). Indeed, the lookahead is necessary only to make the recognition deterministic, but in this case, it is deterministic to start with if you use the DFA (this is a bit tautological, since building the LR parser involve in general building a DFA, if my memory does not fail me)

You can get the LR grammar (if one dares calling it that, trivial as it is) just by taking the right-linear grammar corresponding to the transitions of the DFA.

BTW, it is not easy to decide whether a given grammar is LR(k) for some unknown k, it is undecidable. But it is decidable when k is given, you just try to build the tables.

To answer your question about a procedure to build a LR(k) grammar for a given CF language, the answer is "sorry: not in this universe".

The reason is that it is undecidable whether a given CF language is deterministic or not. Since any deterministic CF language has a LR(k) grammar, if a procedure existed to produce a LR(k) grammar for a language, when possible, that would be a procedure to decide whether the language is deterministic. Since no such procedure can exist, we have no systematic way of obtaining an LR(k) grammar for the language.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Yes, I know that, and I realize now that this confused you. Of course, what I really want to know is how to proceed if I have a language that is NOT regular. I'll try to clarify my question. $\endgroup$
    – lukas.coenig
    Mar 11, 2015 at 13:42
  • 1
    $\begingroup$ Now the answer can be made clearer, too: try building the tables for increasing $k$ until you succeed. $\endgroup$
    – reinierpost
    Mar 11, 2015 at 14:50
  • $\begingroup$ @reinierpost: Ok, than that's my answer, thank you! But there really isn't a better way in terms of a determined construction process? If I understand you correctly, you say that I have to "guess" a grammar and search for a $k$ - not knowing if it exists, and if I succeed, great, but otherwise I have to guess again? $\endgroup$
    – lukas.coenig
    Mar 11, 2015 at 15:20
  • $\begingroup$ @lukas.coenig Right, you try one k after the other. But it may be that none will work (but you will never know). BTW ... modified my answer according to request. The answer is: NO. Such a procedure cannot exist. We live in a tough world. $\endgroup$
    – babou
    Mar 11, 2015 at 15:27
  • 1
    $\begingroup$ @lukas.coenig Well, one can come up with syntactic constraints that will make sur one can build an LR(k) grammar. Being left-linear is an example. But I am afraid nothing that will leave you with enough expressive power to be interesting. But you can hardly abstract LR(k)-ness fron parsing ... it is the purpose of it. But it does not worry me too much, as there are other techniques that will parse any context-free language. The DPDA model is convenient, but there is no reasons to be restricted to it for practical applications. It is engineering: costs and benefits. $\endgroup$
    – babou
    Mar 11, 2015 at 18:07

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.