compiler-constructioncontext-free-grammarshift-reduce-conflict

How Can I make it able to solve with LALR(1)


*X-> Ya| cYb | Zb | cZa
Y-> q | Eplison | XaZ
Z-> f | q*

I've done with LR(1) parsing table and also proved that this is not LALR(1) but is there any way to make it able so that I can make LALR(1) for this?


Solution

  • You must remove the ambiguity of the grammar, because LALR parser work just for unambigous grammars.

    The problems is:

    Example

    let the string "qa" be the input string for the grammar: we have two cases, the first:

    |---------------------|------------------|
    |      terminal       |     character    |
    |---------------------|------------------|
    |                     |         q        |
    |---------------------|------------------|
    |---------------------|------------------|
    |           q         |         a        |
    |---------------------|------------------|
    |---------------------|------------------|
    |           y         |         a        |
    |---------------------|------------------|
    |---------------------|------------------|
    |           ya        |                  |
    |---------------------|------------------|
    |---------------------|------------------|
    |           x         |                  |
    |---------------------|------------------|
    

    and the second :

    |---------------------|------------------|
    |      terminal       |     character    |
    |---------------------|------------------|
    |                     |         q        |
    |---------------------|------------------|
    |---------------------|------------------|
    |           q         |         a        |
    |---------------------|------------------|
    |---------------------|------------------|
    |           z         |         a        |
    |---------------------|------------------|
    |---------------------|------------------|
    |           za        |                  | <--- there your parser stuck
    |---------------------|------------------|
    

    Solution

    We must have one q in our grammar. So our y and z become:

    enter image description here

    so now always for the string "qa":

    |---------------------|------------------|
    |      terminal       |     character    |
    |---------------------|------------------|
    |                     |         q        |
    |---------------------|------------------|
    |---------------------|------------------|
    |           q         |         a        |
    |---------------------|------------------|
    |---------------------|------------------|
    |           D         |         a        |
    |---------------------|------------------|
    |---------------------|------------------|
    |           Da        |                  |<--- there your parser stuck
    |---------------------|------------------|
    

    so our parser stuck again? unfortunately yes, because now d is present in both y and z, so we can try to unify them like this:

    enter image description here

    and change x like this:

    enter image description here

    it's immediately understandable that also this production is ambigious, so the conclusion is that evry LALR parser can be transformed into an LR parser but not vice versa