# Questions of idiom

**URL:** <https://www.ruby-forum.com/t/questions-of-idiom/226068>\
**Category:** Ruby\
**Created:** [June 7, 2010, 9:30pm UTC](https://www.ruby-forum.com/t/questions-of-idiom/226068 "2010-06-07T21:30:47Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Collins](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/b9bd4f/32.png) [@Collins](https://www.ruby-forum.com/u/Collins)\
**Post date:** [June 7, 2010, 9:30pm UTC](https://www.ruby-forum.com/t/questions-of-idiom/226068/1 "2010-06-07T21:30:47Z")

</div>

Hello List

I am relatively new to ruby. I have set myself the problem of writing  
a lexical analyzer in ruby to learn some of it’s capabilites. I have  
pasted the code for that class and for the calling test harness  
below. I beg the lists indulgence in several ways

1. has this problem already been solved in a “gem”? I’d love to see  
how a more sophisticated rubyist solves it
2. There is object manipulation with which I’m still not comfortable.  
In particular, in the buffer manipulation code in the method analyze  
makes me unhappy and I’d be happy to receive instructions in a better  
way to do it
3. Every lanuage has its idioms. I’m not at all sure that I’m using  
the best or most “ruby-like” way of doing certain things. Again I  
welcome suggestions.

Thanks in advance

```
Collins

```

##### code snippet 1

class Rule  
attr\_reader :tokID, :re  
def initialize(\_tokID, \_re)  
@tokID = \_tokID  
@re = \_re  
end

def to\_s  
self.class.name + ": " + @tokID.to\_s + "::= " + @re.to\_s  
end  
end

class Match  
attr\_reader :rule, :lexeme  
def initialize(\_r, \_s)  
@rule = \_r  
@lexeme = \_s  
end

def to\_s  
self.class.name + ": " + @rule.to\_s + "\nmatches: " + @lexeme.to\_s  
end  
end

class Lexer  
attr\_reader :errString

# keep a collection of regular expressions and values to return as

token

# types

# then match text to the longest substring yet seen

def initialize  
@rules = Array.new  
@buff = String.new  
@aFile = nil  
@errString = nil  
end

def addToken (tokID, re)  
if re.class.name == “String”  
@rules \<\< Rule.new(tokID, Regexp.new(re))  
elsif re.class.name == “Regexp”  
@rules \<\< Rule.new(tokID, re)  
else  
print "unsupported type in addToken: ", re.class.name, “\n”  
end  
end

def findMatch  
maxLexeme, maxMatch = String.new, nil  
matchCount, rule2 = 0, nil  
@rules.each { |rule|  
# loop invariant:  
# maxLexeme contains the longest matching prefix of @buff found  
so far,  
# matchCount contains the number of rules that have matched  
maxLexeme,  
# maxMatch contains the proposed return value  
# rule2 contains a subsequent rule that matches maxLexeme  
#  
# if rule matches from beginning of @buff AND  
# does not match all of @buff AND  
# match is longer than previous longest match  
# then update maxMatch and maxLexeme and matchCount and rule2  
#  
# but… we have to avoid matching and keep looking if we make  
it to the  
# end of @buff with a match active (it could still collect more  
# characters) OR if more than one match is still active. If the  
end of  
# the @buff is also the end of the file then it’s ok to match to  
the end  
#  
# TODO: think about prepending an anchor to the regexp to  
eliminate the  
# false matches (those not to the beginning of the @buff)  
#

```
  md = rule.re.match(@buff)
  if !md.nil? && md.pre_match.length == 0
    if md[0].length == @buff.length && !@aFile.eof?
# @buff is potentially ambiguous and there is more file to parse
return nil

```

elsif md[0].length \> maxLexeme.length  
# either matching less than whole buffer or at eof AND  
# match is longer than any prior match  
matchCount, rule2 = 1, nil  
maxLexeme, maxMatch = md[0], Match.new(rule,md[0])  
elsif md[0].length == maxLexeme.length  
# a subsequent match of equal length has been found  
matchCount += 1  
rule2 = rule  
else  
# short match… skip  
end  
else  
# either rule did not match @buff OR

# rule did not match the start of @buff

```
  end
}
if !maxMatch.nil? && matchCount == 1
  #return an unambiguous match
  return maxMatch
elsif !maxMatch.nil? && matchCount > 1
  print "ambiguous: ", maxLexeme, " : ", maxMatch.rule.to_s, " :

```

",  
rule2.to\_s, “\n”  
return nil  
else  
# no match was found  
return nil  
end  
end

def analyze  
aMatch = findMatch  
if !aMatch.nil?  
#remove matched text from buff  
oldBuff = String.new(@buff)  
newBuff = @buff[aMatch.lexeme.length,@buff.length-1]  
if oldBuff != aMatch.lexeme + newBuff  
puts oldBuff  
puts “compare failure!”  
puts aMatch.lexeme + newBuff  
end  
@buff = newBuff  
end  
return aMatch  
end

def parseFile(\_name)  
@fileName = \_name  
@aFile = File.new(@fileName, “r”)  
@aFile.each {|line|  
# add lines from file to @buff… after each addition yield as  
many  
# tokens as possible  
@buff += line  
# comsume all the tokens from @buff that can be found… when no  
more  
# can be found analyze will return nil… so we’ll get another  
line  
aMatch = analyze  
while !aMatch.nil?  
# deliver one \<token, lexeme pair\> at a time to caller…

# by convention a nil tokID is one about which the caller does not

# care to hear…

```
    yield aMatch.rule.tokID, aMatch.lexeme if !

```

aMatch.rule.tokID.nil?  
aMatch = analyze  
end  
}  
# @buff contains the earliest unmatched text… if @buff is not  
empty when  
# we finish with the file, this is an error  
if !@buff.empty?  
@errString = “error: unmatched text:\n” + @buff[0,[80,  
@buff.length].min]  
return false  
else  
@errStrng = “no errors detected\n”  
return true  
end  
end  
end

##### code snippet 2

WhiteSpaceToken = 0  
CommentToken = 1  
QuotedStringToken = 2  
WordToken = 3  
require “lexer”  
l = Lexer.new  
l.addToken(nil, Regexp.new("\s+", Regexp::MULTILINE))  
l.addToken(nil, Regexp.new("#._[\n\r]+"))  
 #l.addToken(QuotedStringToken, Regexp.new(’["][^"]_["]’,  
Regexp::MULTILINE))  
l.addToken(QuotedStringToken,’"\*"’)  
l.addToken(WordToken,Regexp.new("\w+"))  
foo = l.parseFile(“testFile1”) { |token, lexeme|  
print token.to\_s + “:” + lexeme.to\_s + “\n”  
}  
if foo  
print “pass!\n”  
else  
print "fail: " + l.errString + “\n”  
end

---

<div class="post-metadata">

**Author:** ![Collins](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/b9bd4f/32.png) [@Collins](https://www.ruby-forum.com/u/Collins)\
**Post date:** [June 7, 2010, 10:10pm UTC](https://www.ruby-forum.com/t/questions-of-idiom/226068/2 "2010-06-07T22:10:39Z")

</div>

On 07.06.2010 21:28, Collins wrote:

> Hello List
> 
> I am relatively new to ruby. I have set myself the problem of writing  
> a lexical analyzer in ruby to learn some of it’s capabilites. I have  
> pasted the code for that class and for the calling test harness  
> below. I beg the lists indulgence in several ways
> 
> 1. has this problem already been solved in a “gem”? I’d love to see  
> how a more sophisticated rubyist solves it

There are certainly parser and lexer generators for Ruby. I cannot  
remember one off the top of my head but you’ll likely find one in RAA:

[http://raa.ruby-lang.org/search.rhtml?search=lexer](http://raa.ruby-lang.org/search.rhtml?search=lexer)  
[http://raa.ruby-lang.org/search.rhtml?search=parser](http://raa.ruby-lang.org/search.rhtml?search=parser)

> ```
> Collins
> self.class.name + ": " + @tokID.to_s + "::= " + @re.to_s
> 
> ```
> 
> end  
> end

There are several things in the code above: we use tok\_id instead of  
tokID for members and instance variables. Only classes use CamelCase.  
Also it seems highly uncommon to start identifiers with an underscore.  
An alternative way to create the String would be

def to\_s  
“#{self.class.name}: #{@tok\_id}::= #{@re}”  
end

String interpolation implicitly applies #to\_s.

Finally you can define that class in one line:

Rule = Struct.new :tok\_id, :re

> end
> 
> class Lexer  
> attr\_reader :errString
> 
> # keep a collection of regular expressions and values to return as
> 
> token
> 
> # types
> 
> # then match text to the longest substring yet seen
> 
> def initialize  
> @rules = Array.new

If you are lazy you can as well do

@rules = []

> ```
> @buff = String.new
> 
> ```

We usually simply do

@buff = “”

This also creates a new empty String and is easier to spot.

> ```
> print "unsupported type in addToken: ", re.class.name, "\n"
> end
> 
> ```
> 
> end

def add\_token(tok\_id, re)  
@rules \<\< Rule.new(tok\_id,  
case re  
when String  
Regexp.new(re)  
when Regexp  
re  
else  
raise ArgumentError, “Neither String nor regexp”  
end)  
end

“case” works by using the #=== operator which happens do be defined for  
classes as kind\_of? check. It’s also safer to work with class instances  
than with class names.

In error cases we throw exceptions and let the someone up the call chain  
decide how to deal with the error. In your case you just get output on  
the console which might not be appropriate in all cases.

> ```
> # rule2 contains a subsequent rule that matches maxLexeme
> 
> ```
> 
> end of  
> if md[0].length == @buff.length&& !@aFile.eof?  
> rule2 = rule  
> return maxMatch  
> elsif !maxMatch.nil?&& matchCount\> 1  
> print "ambiguous: ", maxLexeme, " : ", maxMatch.rule.to\_s, " :  
> ",  
> rule2.to\_s, “\n”  
> return nil  
> else  
> # no match was found  
> return nil  
> end  
> end

Somehow this method seems a bit lengthy. I did not look too deep into  
the details but I’d probably pick a different strategy. First, I’d  
anchor expressions (like you suggested in your comment). Then I’d just  
do

matches = {}

@rules.each do |rule|  
m = rule.re.match and matches[rule] = m  
end

matches

Now you know that

case matches.size  
when 0

# nothing matches any more, take last match and strip

# buffer

when 1

# single match, remember as last match

else

# many matches, continue

end

If you place that in a loop that adds a character to the buffer at a  
time and then invokes find\_match you can do the evaluation like  
indicated above.

> ```
> end
> @buff = newBuff
> end
> return aMatch
> 
> ```
> 
> end
> 
> def parseFile(\_name)  
> @fileName = \_name  
> @aFile = File.new(@fileName, “r”)  
> @aFile.each {|line|

Better use the block form of File.open() or use File.foreach. That way  
you can be sure that the file handle is always properly closed. See

[http://blog.rubybestpractices.com/posts/rklemme/001-Using\_blocks\_for\_Robustness.html](http://blog.rubybestpractices.com/posts/rklemme/001-Using_blocks_for_Robustness.html)

I’d also choose a different reading strategy - one character at a time  
or fixed buffer width. But I would not read lines

> ```
> # add lines from file to @buff... after each addition yield as
> 
> ```
> 
> many  
> # tokens as possible  
> @buff += line

@buff \<\< line

is more efficient.

> aMatch.rule.tokID.nil?  
> else  
> QuotedStringToken = 2  
> WordToken = 3

I would rather use Symbols as token keys (names). They are similarly  
efficient but make the constant definitions superfluous.

> }  
> if foo  
> print “pass!\n”  
> else  
> print "fail: " + l.errString + “\n”  
> end

There are of course completely different strategies to tackle this.  
Lexers usually are built as a DFA or NFA (like every Regexp  
implementation uses internally). You would then feed a character at a  
time to the FA and derive token types from states.

Also, another option would be to lump all tokens into a single regular  
expression with group matches for every token type and analysing  
matchign groups, e.g.

re = %r{  
(\s+) # white space  
| (“(?:\.|[^”\])\*") # quoted string  
}x

File.read(file\_name).scan re do |m|  
case  
when $1  
printf “whitespace %p\n”, $1  
when $2  
printf “quote %p\n”, $2  
else  
raise “Cannot be, scanner error”  
end  
end

Kind regards

robert

---

<div class="post-metadata">

**Author:** ![Collins](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/b9bd4f/32.png) [@Collins](https://www.ruby-forum.com/u/Collins)\
**Post date:** [June 7, 2010, 10:20pm UTC](https://www.ruby-forum.com/t/questions-of-idiom/226068/3 "2010-06-07T22:20:36Z")

</div>

A work-in-progress Ruby Style Guide is available here:

> <https://github.com/leahneukirchen/styleguide/blob/master/RUBY-STYLE>

A few suggestions from your code samples (some are Ruby-specific, some  
are general “clean code” suggestions):

1. Use snake\_case for variable and method names, not camelCase. Use  
SHOUTING\_SNAKE\_CASE for constants, CamelCase for classes and modules.

2. Don’t needlessly shorten variable names (like @tokID). The goal is  
not brevity but clarity.

3. Do not start variable names with underscores.

4. Use string interpolation ( “#{self.class.name}: #{@token\_id}” )  
rather than concatenation via +.

5. Use puts instead of print with an “\n”, see also #3.

6. Use literals where available. [] instead of Array.new, “” instead of  
String.new, {} instead of Hash.new.

7. Take advantage of Ruby’s sane conditional evaluation semantics.  
Instead of `if !foo.nil?`, simply `if foo`.

8. Do not put extensive conditional logic in #each blocks. Rather,  
extract such logic into a method with an intention revealing name.

9. Take advantage of Enumerable methods that are more specific to your  
needs than #each. For instance, the findMatch method might use #detect  
instead of #each.

10. Variables do not need to be initialized. You assign nil to a number  
of variables and then later reassign them. This is unnecessary.

11. Use do/end for multiline blocks and {} for single-line blocks.

12. Write query methods to wrap complex truthiness expressions in  
intention revealing methods. For instance:

md = rule.re.match(@buff)  
if !md.nil? && md.pre\_match.length == 0

could be changed to:

# Define query method

class Rule  
def matches?(buffer)  
md = rule.re.match(@buff)  
md && md.pre\_match.empty?  
end  
end

# Use query method

if rule.matches?(@buff)

Note that .empty? is often a more expressive replacement for .length ==  
0

1. Use a\_string.dup instead of String.new(a\_string)

2. Alternatively, use non-destructive methods to avoid mutable state  
concerns.

3. Do not put a space between a method and its parenthesized arguments.

Good:

foo(bar)

Bad:

foo (bar)

Also good (unless clarity suffers):

foo bar

1. Do not use parallel assignment ( foo, bar = 1, 2 ) except where  
doing so results in a clear improvement in the clarity (rather than  
brevity) of your code.

Finally, there is prior art that may interest you. Ruby parser/lexers  
include:

racc  
treetop  
ripper  
grammar

All are available as gems and are probably available on Github as well.

---

<div class="post-metadata">

**Author:** ![Collins](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/b9bd4f/32.png) [@Collins](https://www.ruby-forum.com/u/Collins)\
**Post date:** [June 8, 2010, 10:17am UTC](https://www.ruby-forum.com/t/questions-of-idiom/226068/4 "2010-06-08T10:17:04Z")

</div>

> Finally, there is prior art that may interest you. Ruby parser/lexers  
> include:
> 
> racc  
> treetop  
> ripper  
> grammar

If you’re interested in Treetop, here is a video of it being presented  
at a  
conference (has a nice live code section). I tried playing with it a  
while  
back, and with a lot of effort was able to get past the basics. But I  
think  
the wall I ultimately ran into has to do with understanding what to do  
with  
it once parsed. Maybe I’ll try to get into a compiler class next  
semester.  
Also the docs could be a lot better.

---

<div class="post-metadata">

**Author:** ![Collins](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/b9bd4f/32.png) [@Collins](https://www.ruby-forum.com/u/Collins)\
**Post date:** [June 8, 2010, 10:29am UTC](https://www.ruby-forum.com/t/questions-of-idiom/226068/5 "2010-06-08T10:29:23Z")

</div>

Robert K. wrote:

> def add\_token(tok\_id, re)  
> @rules \<\< Rule.new(tok\_id,  
> case re  
> when String  
> Regexp.new(re)  
> when Regexp  
> re  
> else  
> raise ArgumentError, “Neither String nor regexp”  
> end)  
> end

or even just this:

def add\_token(tok\_id, re)  
@rules \<\< Rule.new(tok\_id, Regexp.new(re))  
end

That’s not exactly the same since Regexp.new(a\_regexp) does actually  
create a new regexp object, but AFAICT it’s a functionally identical  
regexp.

> > r1 = /foo/i  
> > =\> /foo/i
> 
> > r2 = Regexp.new(r1)  
> > =\> /foo/i
> 
> > r1 == r2  
> > =\> true
> 
> > r1.equal?(r2)  
> > =\> false