[Oberon] Re (2): Detecting whether a Text is a module source.

Chris Burrows chris at cfbsoftware.com
Sun Jan 29 21:47:44 CET 2017


> -----Original Message-----
> From: Oberon [mailto:oberon-bounces at lists.inf.ethz.ch] On Behalf Of
> peter at easthope.ca
> Sent: Monday, 30 January 2017 2:41 AM
> To: oberon at lists.inf.ethz.ch
> Subject: [Oberon] Re (2): Detecting whether a Text is a module
> source.
> 
> > According to the EBNF for O7, the smallest legal module ...
> 
> OK, thanks.  Will keep in mind for later. For now I'm concerned only
> with detecting the presence of a word in a text; not with conformity
> to a syntax.
> 
> What is efficient code to find whether the word "Jaguar" is present
> in a text for example?  There are many ways of varying efficiency.  A
> compiler must have a solution but I'm unlikely to recognize it.  Can
> anyone give a code example or direct me to one?
> 

As others have said Boyer-Moore algorithm is the most efficient in terms of
searching speed. However, that is a general search algorithm for arbitrary
words in arbitrary texts. The compiler only has to search for a fixed set of
*known* keywords / reserved words. Look in the scanner module of the Oberon
compilers for various ways (hashing, CASE statements, linear search,
balanced tree search) that have been used to do this.

One example is ORS.Mod.txt in the RISC5 compiler:

https://www.inf.ethz.ch/personal/wirth/ProjectOberon/Sources

Look at the part commented (*search for keyword*) in PROCEDURE Identifier.

It uses a simple linear search except that the length of the string is used
as an index into the keyword table to make the search more efficient.

Regards,
Chris Burrows
CFB Software
http://www.astrobe.com/RISC5








More information about the Oberon mailing list