Sat, 23 May 1992 06:14:38 GMT

Related articles |
---|

Parsing Roman numbers joe@erix.ericsson.se (1992-05-22) |

Re: Parsing Roman numbers byron@archone.tamu.edu (1992-05-23) |

Re: Parsing Roman numbers henry@zoo.toronto.edu (1992-05-24) |

Re: Parsing Roman numbers weberwu@inf.fu-berlin.de (1992-05-24) |

Re: Parsing Roman numbers Martin.Ward@durham.ac.uk (Martin Ward) (1992-05-26) |

Newsgroups: | comp.compilers |

From: | byron@archone.tamu.edu (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@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.)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.