Example 4.2.3. Unambiguous grammar. Productions: S _ _ | aS | aB, B _ b | bB. L(G) = _ + a+b*
Clearly these productions derive L(G).
To see that each string in L(G) has only one leftmost derivation consider apbq where p,q0. if p=q=0, then the derivation must be S _ _, if p>0 and q0, then the derivation must consist of: S _ aS _ aaS _ ap-1S _ apB _ apbB _ apbq-1B _ apbq or S _ aS _ aaS _ ap-1S _ ap if q=0
Hence the same language, _ + a+b*, is described by both ambiguous and unambiguous grammars ambiguity is a property of the grammar, not the language.
| Previous slide | Next slide | Back to first slide | View graphic version |