# Writing parsers?

**URL:** <https://www.ruby-forum.com/t/writing-parsers/53719>\
**Category:** Ruby\
**Created:** [February 14, 2006, 12:59am UTC](https://www.ruby-forum.com/t/writing-parsers/53719 "2006-02-14T00:59:40Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![PaatschS\_Bernd](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/fbc32d/32.png) [@PaatschS\_Bernd](https://www.ruby-forum.com/u/PaatschS_Bernd)\
**Post date:** [February 14, 2006, 12:59am UTC](https://www.ruby-forum.com/t/writing-parsers/53719/1 "2006-02-14T00:59:40Z")

</div>

Hello,

I got this great task assigned to write a parser and looking at the  
files to  
parse is not very trivial. Does anybody know where to find a website  
that  
would explain steps and pitfalls to avoid writing a parser?  
Any suggestion/help in is appreciated.

Thanks,  
Bernd

---

<div class="post-metadata">

**Author:** ![PaatschS\_Bernd](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/fbc32d/32.png) [@PaatschS\_Bernd](https://www.ruby-forum.com/u/PaatschS_Bernd)\
**Post date:** [February 14, 2006, 1:47am UTC](https://www.ruby-forum.com/t/writing-parsers/53719/2 "2006-02-14T01:47:31Z")

</div>

DÅ?a Utorok 14 Február 2006 00:59 Paatsch, Bernd napísal:

> Hello,
> 
> I got this great task assigned to write a parser and looking at the files  
> to parse is not very trivial. Does anybody know where to find a website  
> that would explain steps and pitfalls to avoid writing a parser?  
> Any suggestion/help in is appreciated.
> 
> Thanks,  
> Bernd

[Lex & Yacc](http://epaperpress.com/lexandyacc/) seems to be a useful resource,  
provided you  
already know some theory behind formal grammars and such. The two tools  
and  
their derivatives are pretty much the open source standard for writing  
parsers. I believe there are Ruby bindings / variants of both.

ANTLR is also somewhat used, but you’re probably looking at Java there.

David V.

---

<div class="post-metadata">

**Author:** ![PaatschS\_Bernd](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/fbc32d/32.png) [@PaatschS\_Bernd](https://www.ruby-forum.com/u/PaatschS_Bernd)\
**Post date:** [February 14, 2006, 2:03am UTC](https://www.ruby-forum.com/t/writing-parsers/53719/3 "2006-02-14T02:03:35Z")

</div>

[http://www.google.com/search?hl=en&q=parser](http://www.google.com/search?hl=en&q=parser)

🙂 No seriously, check out ANTLR. Unless you are supposed to write the  
parser from scratch.  
If you want to do it in ruby, there are options like:  
[http://split-s.blogspot.com/2005/12/antlr-for-ruby.html](http://split-s.blogspot.com/2005/12/antlr-for-ruby.html)  
[http://www.zenspider.com/ZSS/Products/CocoR/](http://www.zenspider.com/ZSS/Products/CocoR/)

---

<div class="post-metadata">

**Author:** ![PaatschS\_Bernd](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/fbc32d/32.png) [@PaatschS\_Bernd](https://www.ruby-forum.com/u/PaatschS_Bernd)\
**Post date:** [February 14, 2006, 3:13pm UTC](https://www.ruby-forum.com/t/writing-parsers/53719/4 "2006-02-14T15:13:10Z")

</div>

I just whipped this up in a bit of free time. It may be a decent  
starting point for a pure ruby parser. Note that there is no lookahead  
ability.

class ParseError \< StandardError; end

class Parser

@@reductions = {}  
@@reduction\_procs = {}  
@@tokens = {}  
@@token\_values = {}

# Parse either a string or an IO object (read all at once) using the

rules defined for this parser.  
def parse(input)  
stack = []  
value\_stack = []  
text = input.is\_a?(IO) ? input.read : input.dup  
loop do  
token, value = retrieve\_token(text)  
stack \<\< token  
value\_stack \<\< value  
reduce\_stack(stack, value\_stack)  
if text.length == 0  
if stack.length == 1  
return stack[0], value\_stack[0]  
else  
raise ParseError, ‘Stack failed to reduce’  
end  
end  
end  
end  
protected

# Retrieve a single token from the input text and return an array of

it and its value.  
def retrieve\_token(text)  
@@tokens.each do |regexp, token|  
if md = text.match(regexp)  
text.gsub!(regexp, ‘’)  
return [token, @@token\_values[token] ?  
@@token\_values[token].call(md.to\_s) : nil]  
end  
end  
raise ParseError, “Invalid token in input near #{text}”  
end

# Compare the stack to reduction rules to reduce any matches found

def reduce\_stack(stack, value\_stack)  
loop do  
matched = false  
@@reductions.each do |tokens, result|  
if tokens == stack[stack.length - tokens.length, tokens.length]  
start\_pos = stack.length - tokens.length  
stack[start\_pos, tokens.length] = result  
value\_stack[start\_pos, tokens.length] =  
@@reduction\_procs[tokens] ?  
@@reduction\_procs[tokens].call(value\_stack[start\_pos, tokens.length]) :  
nil  
matched = true  
break  
end  
end  
return unless matched  
end  
end

def self.token(regexp, token, &block)  
@@tokens[Regexp.new(’\A’ + regexp.to\_s)] = token  
@@token\_values[token] = block  
end

def self.rule(\*tokens, &block)  
final = tokens.pop  
tokens += final.keys  
result = final.values.first  
@@reductions[tokens] = result  
@@reduction\_procs[tokens] = block  
end  
end

class TestParser \< Parser  
token /foo/i, :foo do |s|  
s.upcase  
end  
token /bar/i, :bar do |s|  
s.downcase  
end  
token /mega/i, :mega do |s|  
3  
end  
rule :foo, :bar =\> :foobar do |foo, bar|  
foo + bar  
end  
rule :mega, :foobar =\> :megafoobar do |mega, foobar|  
foobar \* mega  
end  
end

---

<div class="post-metadata">

**Author:** ![PaatschS\_Bernd](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/fbc32d/32.png) [@PaatschS\_Bernd](https://www.ruby-forum.com/u/PaatschS_Bernd)\
**Post date:** [February 15, 2006, 11:20am UTC](https://www.ruby-forum.com/t/writing-parsers/53719/5 "2006-02-15T11:20:00Z")

</div>

Grammar looks much more similar to Spirit, a C++ parser which looks  
really simple to use. It uses a very simple domain-specific language  
for writing grammars in C++ code. It’s part of the boost libraries. It  
would be my first choice for a medium-speed parser that could be used  
quite easily from Ruby with just a few joining bits of C. Parsers in  
the style of YACC or Bison are much faster again, but the added  
complexity of defiing grammar probably makes using it a premature  
optimisation for most tasks.

---

<div class="post-metadata">

**Author:** ![PaatschS\_Bernd](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/fbc32d/32.png) [@PaatschS\_Bernd](https://www.ruby-forum.com/u/PaatschS_Bernd)\
**Post date:** [February 14, 2006, 3:13pm UTC](https://www.ruby-forum.com/t/writing-parsers/53719/6 "2006-02-14T15:13:13Z")

</div>

Paatsch, Bernd wrote:

> Hello,
> 
> I got this great task assigned to write a parser and looking at the  
> files to parse is not very trivial. Does anybody know where to find a  
> website that would explain steps and pitfalls to avoid writing a  
> parser?  
> Any suggestion/help in is appreciated.

[http://raa.ruby-lang.org/project/racc/](http://raa.ruby-lang.org/project/racc/)  
[http://raa.ruby-lang.org/project/ruby-yacc/](http://raa.ruby-lang.org/project/ruby-yacc/)

```
robert

```

---

<div class="post-metadata">

**Author:** ![PaatschS\_Bernd](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/fbc32d/32.png) [@PaatschS\_Bernd](https://www.ruby-forum.com/u/PaatschS_Bernd)\
**Post date:** [February 15, 2006, 8:52am UTC](https://www.ruby-forum.com/t/writing-parsers/53719/7 "2006-02-15T08:52:00Z")

</div>

In article [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid),  
Timothy G. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> @@tokens = {}  
> stack \<\< token  
> end  
> end  
> start\_pos = stack.length - tokens.length  
> end  
> result = final.values.first  
> s.downcase  
> end

This is a bit like Grammar:  
[http://grammar.rubyforge.org/0.5/](http://grammar.rubyforge.org/0.5/)

Phil