2
$\begingroup$

I have recently started reading more about context-free parsing techniques, in particular LR parsing.

As I have read, LR state transition graph (or table(s)) used for finding handles in sentential form is created by first constructing NFA from grammar rules (with included position in the rule - dot and possibly lookahead terminal) and then by converting the NFA to DFA with powerset/subset algorithm to remove non-determinism.

LR(1) state transition graph is usually an order of magnitude larger than LR(0)/SLR(1)/LALR(1).

Is it worthy or even practically possible to use DFA minimization (either Hopcroft or Moore or Brzozowski) on LR(1) state transition graph to get a minimal LR(1) graph? I haven't found any literature mentioning this.

Also, is there an algorithm to convert NFA directly to minimal DFA? Perhaps by constructing NFA state subsets in some particular order?

Improve this question
$\endgroup$
5
  • $\begingroup$ I feel like you have too many questions in your post: (a) is it worthwhile, (b) is it possible, (c) how do you convert NFA to DFA. It's usually better stick to one question per post. (b) Yes, it's possible to minimize the DFA -- why wouldn't it be? Perhaps post question (c) as a separate question, and re-focus this on asking whether it is worthwhile to minimize the resulting DFA? $\endgroup$
    – D.W. ♦
    Sep 30, 2015 at 17:04
  • $\begingroup$ Thanks for suggestion. Actually question (b) is 'is it practically possible?'. Maybe I should formulate it differently. I am wondering if anyone has tried this on some representative grammar like one for C++ or C# and how long would it take (couple of seconds/minutes on modern machine or much more)? Question (c) is added because it would solve the minimization problem while constructing LR tables and not as a separate step. $\endgroup$
    – Stipo
    Sep 30, 2015 at 19:56
  • $\begingroup$ What research have you done? It's certainly possible - there are algorithms for DFA minimization in the usual textbooks, and in Wikipedia. You can find extensive analysis of the asymptotic running time. If you want to know what would happen if you tried minimizing such a DFA from a representative grammar, you could always try it yourself. $\endgroup$
    – D.W. ♦
    Sep 30, 2015 at 22:55
  • $\begingroup$ I have only done the research for some paper which mentions LR(1) minimization. I have found that David Pager has implemented some kind of minimized LR(1) but haven't managed to find the actual paper. Also I have found IELR(1) paper but from the quick overview I don't think it uses standard DFA minimization since the algorithm is described in 5 phases. $\endgroup$
    – Stipo
    Oct 1, 2015 at 6:53
  • $\begingroup$ If I find enough free time, I will try it for myself but it will probably take a lot of time, so I wanted to know has anyone tried this before. I suspect that it is not worthy (either because minimized LR(1) size doesn't approach to LALR(1) size or because minimization introduces additional conflicts) because the idea comes naturally and no one even mentions it. $\endgroup$
    – Stipo
    Oct 1, 2015 at 6:53

2 Answers 2

Reset to default
1
$\begingroup$

The following paper uses DFA minimisation for a minimal LR(1) parser: https://www.researchgate.net/publication/258746690_An_LR_parser_with_less_states

Improve this answer
$\endgroup$
1
$\begingroup$

As shown here, minimizing the states in an LR(1) parser is NP-hard. The basic idea is that given an arbitrary graph, you can construct a grammar such that for every node in the original graph, the LR(1) parser contains a corresponding state in its state graph, and two states can be merged if and only if there is no edge between them in the original graph. Then finding the minimum number of states for the LR parser is equivalent to finding a minimum coloring for the original graph.

For example, consider the following grammars

S = 1Xa
S = 1Yb
S = 2Xc
S = 2Yd
X = @
Y = @

and

S = 1Xa
S = 1Yb
S = 2Xc
S = 2Ya
X = @
Y = @

where 1, 2, @, a, b, c, d are arbitrary distinct tokens. In the first case, you'll end up with two states that can be merged, while in the second case, there will be a reduce-reduce conflict with the a token if you try to merge them.

Improve this answer
$\endgroup$

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.