Created
December 1, 2010 18:02
-
-
Save jimweirich/723913 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# An example of Mutual Recursion. | |
# A simple lexer for our parser. We only return tokens for :numbers | |
# and +, - and new lines. | |
class Lexer | |
attr_reader :token, :type | |
def initialize(stream=STDIN) | |
@stream = stream | |
@tokens = [] | |
end | |
def advance | |
@token = @tokens.shift || get_more_tokens | |
@type = (@token =~ /^\d/) ? :number : @token | |
end | |
private | |
def get_more_tokens | |
line = @stream.gets | |
if line | |
@tokens = line.scan(%r{\d+|[-+*/\(\)]}) + ["\n"] | |
else | |
@tokens = [] | |
end | |
@tokens.shift | |
end | |
end | |
# A very simple expression parser. We can handle expressions like: | |
# | |
# 3 | |
# 1+2 | |
# (1+2-3) | |
# 100 - (4 + (45 - 5)) | |
# | |
class ExpressionParser | |
class ParseError < StandardError | |
end | |
def initialize(lexer) | |
@lexer = lexer | |
end | |
# Parse a single expression. | |
def parse_expression | |
result = parse_term | |
loop do | |
case type | |
when '+' | |
advance | |
result = result + parse_term | |
when '-' | |
advance | |
result = result - parse_term | |
else | |
break | |
end | |
end | |
result | |
end | |
# Parse a term (i.e. a number or a parenthesized expression). | |
def parse_term | |
if type == :number | |
result = parse_number | |
elsif @lexer.type == "(" | |
advance | |
result = parse_expression | |
if type == ")" | |
advance | |
else | |
expected("a closing parenthesis") | |
end | |
else | |
expected("an expression") | |
end | |
result | |
end | |
# Parse a single number | |
def parse_number | |
if type == :number | |
result = token.to_i | |
advance | |
else | |
expected("a number") | |
end | |
result | |
end | |
private | |
def type | |
@lexer.type | |
end | |
def token | |
@lexer.token | |
end | |
def advance | |
@lexer.advance | |
end | |
def expected(what) | |
fail ParseError, "Expected #{what}, got: <#{@lexer.token.inspect}>" | |
end | |
end | |
lexer = Lexer.new | |
parser = ExpressionParser.new(lexer) | |
lexer.advance | |
while lexer.token | |
result = parser.parse_expression | |
puts "The answer is: #{result}" | |
while lexer.type == "\n" | |
lexer.advance | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks! I really enjoyed playing with this code.