Re: Parsing Roman numbers (Byron Rakitzis)
Sat, 23 May 1992 06:14:38 GMT

          From comp.compilers

Related articles
Parsing Roman numbers (1992-05-22)
Re: Parsing Roman numbers (1992-05-23)
Re: Parsing Roman numbers (1992-05-24)
Re: Parsing Roman numbers (1992-05-24)
Re: Parsing Roman numbers (Martin Ward) (1992-05-26)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Byron Rakitzis)
Keywords: parse
Organization: College of Architecture, Texas A&M University
References: 92-05-126
Date: Sat, 23 May 1992 06:14:38 GMT (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



(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.)

Post a followup to this message

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