Re: How to resolve ambiguity?

Scott Nicol <>
2 Jan 2004 03:39:32 -0500

          From comp.compilers

Related articles
How to resolve ambiguity? (2003-12-27)
Re: How to resolve ambiguity? (Scott Nicol) (2004-01-02)
Re: How to resolve ambiguity? (Derk Gwen) (2004-01-02)
Re: How to resolve ambiguity? (Scott Nicol) (2004-01-02)
| List of all articles for this month |

From: Scott Nicol <>
Newsgroups: comp.compilers
Date: 2 Jan 2004 03:39:32 -0500
Organization: APK Net
References: 03-12-143
Keywords: parse
Posted-Date: 02 Jan 2004 03:39:32 EST

On 27 Dec 2003 15:02:36 -0500, (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
| interface-type
| array-type
| delegate-type
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
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
2. Real grammar either non-existant or too ugly for words. Clean it
up to make it more presentable,

Scott Nicol

Post a followup to this message

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