Re: Parsing Roman numbers

joe@erix.ericsson.se (Joe Armstrong) writes:
>Has anybody got a grammar (preferably yacc) for parsing roman numbers?
>Are they LL(k) LR(k) or what?


Well, unless I misunderstand Roman numerals (too possible!), they are
composed of the alphabet IVXLCDM. I think I can prove they form a
regular language.


Proof: A Roman numeral consists of zero or more M's followed possibly by a
number of symbols in the alphabet IVXLCDM which denote an integer from 1
to 999.


It is possible to construct a DFA to recognize the pattern


M* (number from 1 to 999 in roman numerals)?


because it is just the union of the two DFAs that recognize


M*


and


(number from 1 to 999 in r.n.)?


and this second DFA can be constructed by making an NDFA that accepts
either \epsilon or I or II or III, etc. by using the DFAs that recognize
each numeral and choosing the correct one nondeterministically.


Therefore the language is regular.


Now, this doesn't help you parse roman numerals very much, but at least it
proves it's possible, and in fact could be done with sed if you could
stomach the r.e. that resulted. :-)


(Seriously, I wouldn't use yacc, I would try to write some kind of state
machine in C; yacc seems like overkill for this.)
--

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