Writing parsers?

[Paatsch, Bernd]

------_=_NextPart_001_01C630F9.78EE12D1
Content-Type: text/plain

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

------_=_NextPart_001_01C630F9.78EE12D1--

 

[David Vallner]

D=C5=88a Utorok 14 Febru=C3=A1r 2006 00:59 Paatsch, Bernd nap=C3=ADsal:

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

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

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

David Vallner

 

[Doug H]

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://www.zenspider.com/ZSS/Products/CocoR/

 

[Timothy Goddard]

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

 

[Robert Klemme]

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/ruby-yacc/

robert

 

[Phil Tomson]

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

This is a bit like Grammar:
http://grammar.rubyforge.org/0.5/

Phil

 

[Timothy Goddard]

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.