I am a new comer to compiler principle and learn it by myself using
dragon book.
And now I met some problem.

how to construct the context-free grammar for Rome digit?

BTW,where I can find the answer book to dragon book ---<<Compiler
,principle technology and tools>>

and How can I learn it well?
Thanks in advance.

[ Post a follow-up to this message ]

"DaVinci" <apple.davinci@gmail.com> writes:
> I am a new comer to compiler principle and learn it by myself using
> dragon book.
> And now I met some problem.
>
> how to construct the context-free grammar for Rome digit?

Well, Roman numbers can be recognized by a regular expression, so you
don't really need a context-free grammar.  But since a context-free
grammar can trivially be deduced from a regular expression, let's
first start writing the regular expression.

Can you do it?

Roman_Number ::=  ???  .


> BTW,where I can find the answer book to dragon book ---<<Compiler
> ,principle technology and tools>>
>
> and How can I learn it well?
> Thanks in advance.


--
__Pascal Bourguignon__                     http://www.informatimago.com/

CAUTION: The mass of this product contains the energy equivalent of
85 million tons of TNT per net ounce of weight.

[ Post a follow-up to this message ]

Pascal Bourguignon wrote:
> "DaVinci" <apple.davinci@gmail.com> writes: 
>
> Well, Roman numbers can be recognized by a regular expression, so you
> don't really need a context-free grammar.  But since a context-free
> grammar can trivially be deduced from a regular expression, let's
> first start writing the regular expression.
>
> Can you do it?
>
> Roman_Number ::=  ???  .
I'm afraid that I can't do that although I am not willing to say that.

>
> 
>
>
> --
> __Pascal Bourguignon__                     http://www.informatimago.com/
>
> CAUTION: The mass of this product contains the energy equivalent of
> 85 million tons of TNT per net ounce of weight.

[ Post a follow-up to this message ]

"DaVinci" <apple.davinci@gmail.com> writes:

> Pascal Bourguignon wrote: 
> I'm afraid that I can't do that although I am not willing to say that.


Really?  Can't you count?

There's a finite number of Roman numbers!

Therefore the regular expression which recognize them is:

I|II|III|IV|V|VI|VII|VIII|IX|X|XI|XII|...|MMMCMXCVII|MMMCMXCVIII|MMMCMXCIX

And there's nothing more to it, to write a context free grammar for them:

RomanNumber ::= I|II|III|IV|V|VI|VII|...|MMMCMXCVII|MMMCMXCVIII|MMMCMXCIX .

(Actually, there are Roman digits for numbers greater than 4000, V, X,
L, C, D and M with a bar above to denote 5000, 10000, 50000, 100000,
500000 and 1000000, so the biggest number you can write in Roman
Numerals is 4999999, but this is still finite, and it seems it was
introduced in the Middle Age, so it's not really Roman anymore).


Now, if you want to write it somewhat more compactly,  you can do
manually what the compilers do for you anyways.  See chapter 3, Finite
Automata and Lexical Analysis.  You would draw the big NFA
corresponding to that big regular expression above, then you would
transform it into a DFA, then you could simplify it (eg with the
Hopcroft algorithm), to eventually get a minimal DFA or regular
expression.

An alternative, is to still read this Chapter 3, and to learn some
more about regular expressions (regex(3)) and how you use them
(grep(1), sed(1), etc).  Then read again about the Roman Numerals, for
example at: http://en.wikipedia.org/wiki/Roman_numeral
Then you should be able to write the regular expression directly.

You can start with something simple: try to write the regular
expression to match numbers between 1 and 9, then between 1 and 99.

--
__Pascal Bourguignon__                     http://www.informatimago.com/

CONSUMER NOTICE: Because of the "uncertainty principle," it is
impossible for the consumer to simultaneously know both the precise
location and velocity of this product.

[ Post a follow-up to this message ]