Re: How to resolve ambiguity?

On 27 Dec 2003 15:02:36 -0500, idht@yahoo.com (Igor) wrote:
> I am trying to write a custom compiler for C sharp,
>but I am kind of stuck with the grammar MSDN provides,
>for example, in the rule:
>
><struct-type> ::= <type-name>
> | <simple-type>
>
><type-name> would reduce to <struct-type>,
>and in
>
><class-type> ::= <type-name>
> | object
> | string
>
> <type-name> would reduce to <class-type>.
>THis is evidently a reduce-reduce conflict.


You cut out a little too much.


type: value-type
| reference-type
value-type: struct-type
| enum-type
reference-type:
class-type
| interface-type
| array-type
| delegate-type
interface-type:
type-name
array-type: non-array-type rank-specifiers
non-array-type: type
delegate-type: type-name


Starting from type. what happens if you get a type-name?


Is it a value-type? Maybe, because a value-type can be a struct-type,
and a struct-type can be a type-name.


Is it a reference-type? It could be a...


1. class-type, which can be a type-name
2. interface-type, which is a type-name
3. array type, which can start with a type-name (this will give you a
shift/reduce)
4. delegate-type, which is a type-name.


So you have 5 paths to follow, 4 of which can reduce, and one of which
can shift. This is known as "a mess". A solution would be to flatten
the type rule, like this:


type: type-name
| simple-type
| object
| string
| array-type
;


You will still get a shift/reduce, because of the "type" embedded in
array-type. To get rid of this, distribute the array-type rule within
type, like this:


type: type-name opt-array
| simple-type opt-array
| object opt-array
| string opt-array
;


opt-array: /*nothing*/ | rank-specifiers
;


>Could somebody explain why they provide a grammar like that


I don't know, but I can speculate. Most published grammars I have
seen have conflicts in them. I can think of two reasons:


1. Too lazy to pass grammar through parser generator to check for
conflicts.
2. Real grammar either non-existant or too ugly for words. Clean it
up to make it more presentable,


--
Scott Nicol
snicol@apk.net

Return to the comp.compilers page.
Search the comp.compilers archives again.