1

I am trying to learn about parsers in Compiler Construction. So far, I understand that there is ambiguity problems in production rules that we need to pay attention to.

The one example I can't understand is as follow:

if e1 then if e2 then s1 else s2

I understand here that we have an ambiguity problem with dangling if. So for example:

 if(e1)
   {
       if (e2)
       {
           s1
       }
       else
       {
           s2
       }

   }

so the else needs to go to the inner if and not the outer if. However having:

stmt::= if expression then stmt
      |if expression then stmt else stmt
      |other

will cause ambiguity because it might link the outer if to the else of the inner if.

Now the solution is to use matched and unmatched statements:

>stmt:: = matched | unmatched
>matched:: = ?
>unmatched:: = ?

I also understand that match refers to an if else and unmatched refers to a dangling if.

I already have the answer to matched and unmatched but I don't understand why it is the way it is (Specially the unmatched part).

>Stmt ::= matchedStmt | unmatchedStmt
>matchedStmt ::= if Expr then matchedStmt else matchedStmt
>               |other
>unmatchedStmt ::= if Expr then Stmt
>                 |if Expr then matchedStmt else unmatchedStmt

How can I understand this?

I tried google, reading book and stack overflow previous questions but I still can't understand it as well as I can't find any well detailed explained source (the book just says we can solve through this new set of production rules for instance).

Sara Kat
  • 378
  • 2
  • 19
  • 1
    [This answer](https://stackoverflow.com/a/34256059/1566221) attempts to explain. If there is something you don't understand, please ask a specific question which can be answered. – rici Jan 31 '19 at 07:39
  • I read it multiple times but I cant seem to understand how this match and unmatch logic works – Sara Kat Jan 31 '19 at 08:24
  • 1
    i'd like to help you but if you can't find a question, I can't give you an answer. All I could do is try randomly rewriting the answer in the hope that I stumble upon a formulation which works for you. Without any guidance, the probability of success seems low. Here's my suggestion: sit down with a pad of paper and use the grammar to *generate* different sentences. Keep track of the generation by writing it as a parse tree, by making the expansion of each non-terminal a child of the non-terminal. Hopefully that will give you some insight. – rici Jan 31 '19 at 13:42

0 Answers0